鱼C论坛

 找回密码
 立即注册
查看: 3938|回复: 4

猴子问题

[复制链接]
发表于 2011-10-2 03:45:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
大家好!4 A5 l8 @. l  S
这几天我在忙着编一个问题,我用了一种方法编出来!
) j, ~, Y- h( H9 u1 G* C* ~, Y但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
4 L" C8 ]* s& b, l注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
" J1 B" n0 K! H- ]/ ?; p/ K' n, k  B6 L: e

  D4 t) E1 G; }7 ?7 o
                            题目9 J- f4 @) U* o7 y. D* Z
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。/ v4 b( N- ^# T+ H6 n
第一种方法:利用循环链表9 b! H  B+ U: B5 W& K
#include<stdio.h>
( j  |  ~9 r2 T. p) T7 {0 }5 S#include<malloc.h>+ }( k$ {% \( ^
#define M 8            //共有8只猴子' t* j" m# h8 ?
#define N 3            //数到3只时退出第三只
% v; i6 @) x) Z$ K# mtypedef struct monkey9 A+ N+ k. O3 c! P1 p
{int number;/ s" P6 _, @6 @' N: Z* a, X
int flag;
1 Q" C4 {- {' }6 @8 w! ~7 y  {4 kstruct monkey* next;& v& j9 x* c7 B
}MONKEY;
6 K1 y0 S) G4 M) n/ |% Q: nmain()
) _9 k* Y5 t$ X+ h{ MONKEY *head=NULL,*p,*s;
' E( K+ U7 w, t. M( G  int i,sum=0,count=0;
4 p! M/ E$ h0 C1 S; ^! d2 q  clrscr();              //清屏/ N6 J+ D- Q, y' d8 Q
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存9 |6 X4 i. y- ?) e
  p->number=1;p->flag=1;
* y: i/ X' [( o6 ?! L: |  p->next=head;
' `4 x4 ^4 J* ^0 m" w5 t  head=p;/ h- ]7 x! N* l# _$ x# e
  for(i=2;i<=M;i++), f0 Y# F* c- t: V5 a+ A0 Y9 X" U
    { s=(MONKEY *)malloc(sizeof(MONKEY));; D. a$ ]' N4 V+ n8 C, D+ b9 b! x
     s->number=i;s->flag=1;7 R! K! {0 s' Q! u/ Y  ~
     s->next=head;
3 R( g6 o# m) m# s3 j     p->next=s;p=p->next;% d, c7 m) D4 q
    }
% D8 t; Z+ z) @1 z& D2 N    p=head;: V  O  K' _6 |% K# I+ I# x/ G/ Q
   for(;;)
# r0 G( L$ ?3 I. J5 Z. K7 l& ]( V    {if(p->flag==1)
4 Q5 s, O( K3 F" H/ a% ^       count++;
0 w0 M' P2 `/ c     if(count==N): V5 l  h6 y( k' q3 k+ u+ l) N
        {p->flag=0;3 N. s6 _" V  Y! Z" v9 a
         count=0;( \- k4 h" _- |. _+ b  J2 s; V
         sum++;}
) k0 A" B" a* z3 M     if(sum==M-1)* g  ~9 P* G: d5 Q
        break;0 M) x% P9 c5 W, V  O6 Z. n9 i+ x
     p=p->next;3 E0 a, Y: @$ Y! k
    }! n1 Z- B# P# G
    p=1 N4 G: }( ~8 q) n! R' T) Z" H' [
    head;
7 D2 y' @  P: K+ P    for(i=1;i<=M;i++)
5 V5 w+ P% i' x8 o" }: h" x3 `& L    { if(p->flag==1): v% x9 I6 \5 U  h
        printf("\t%d",p->number);
5 ]- [, y' P8 b% B1 v1 X6 {' [      p=p->next;2 u$ [* Y; e& ]7 W
    }
% Z! [: T& }) V3 n0 ]7 P* {% j( |; l/ G$ |: s5 a) o7 d

* \- d) Y; w( Q0 O" h6 ~
( y% K; m- w# M, }# P0 T}

, E( P/ {4 V6 U/ m/ Z第二种方法:数组
8 E$ a, g+ X% k/ O! B#include<stdio.h>, p" f6 u; c2 \# F% c; x
#define M 8
, s: Z; U6 z9 T6 I4 |+ Zstruct monkey
8 t  C; z5 ^# }{int number;
3 m/ t6 Q% I! B6 {6 ^, ^: x6 iint nextp;
  _+ O2 e/ d% g+ i' w3 M1 `8 k  u}link[M+1];
; w6 G4 V4 S1 M4 \& Q6 X- Z- \: u. V
; g; Q- n+ R( p. L* Rvoid main()
, W# Z$ L6 N# t) ]{int i,count,h;( {* U+ r) n2 Q: @8 v6 X; L
for(i=1;i<=M;i++)
+ l2 Y- h; D+ A* f7 m6 l{  if(i==M), R  E* o/ Q5 D$ N% p3 n
   link[i].nextp=1;, ?9 k) b* o2 c% S) w7 p% B
   else9 A; S; h9 s/ r8 X1 ]5 l/ V% i
   link[i].nextp=i+1;
# z8 s+ i$ T# ~" u$ Y  link[i].number=i;) L% D" n% _: A  w7 W
}
% `$ ~' l, h. H7 vprintf("\n");
( i0 g/ X2 X$ _7 B# g7 s# rcount=0;: o- O7 r( W- B/ i( K1 k( i+ Y' {
h=M;
5 t4 d& M4 M% J$ \8 g6 h$ wprintf("依次退出的猴子: \n");0 D3 m) a8 I+ `# h7 B
while(count<M-1)* X9 }# d5 u; S
{i=0;' R* w+ L5 E" S
while(i!=3)
" F  V5 i! J) \; l* W4 h{ h=link[h].nextp;
4 M0 t" l4 \0 _; t   if(link[h].number), \$ f5 l. S, Q
     i++;}* P3 G5 v1 s4 J# s: G3 v9 q

* S" b4 e6 P! ?! Eprintf("%4d",link[h].number);: b5 i' u5 S5 R% z& W! q& V
link[h].number=0;) a8 L* o! G" G& b8 T& b/ _
count++;
7 X! i5 `  N- o" G( o8 U}
0 U+ X% c) `  F; i
. K2 g" c( m$ Rprintf("\n大王是:");- G( t$ {/ t* v) c2 t* N' p
  for(i=1;i<=M;i++)
! n2 ~+ q8 o$ j& h7 R  if(link[i].number)' e! _6 n- [/ ]) M
    printf("%3d\n",link[i].number);" L1 x* p0 q2 w

2 B' p0 Z& r0 c7 Y7 w9 j9 l: j( I! k% L, j. K
}

# q4 q. y+ d  `第三种是普通方法for循环

5 h1 T! F( o4 c0 b3 s#include<stdio.h>( X( J* |" r+ U5 o- j) ^5 y" w5 V% F
void main()5 v# i, t/ T$ V7 W3 |, T2 [
{ int i,k,m,n,num[50],q,*p;
! ]# B# Z) \/ a2 X    clrscr();
/ |$ b( b1 [' r5 e   printf("input number of person: n=");
+ f9 W* d  n* ^9 |  ^7 ^$ X    scanf("%d",&n);' S" q, D5 \; J# o- Q
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只$ L. i; v5 |7 t
    scanf("%d",&q);
  O2 K% B. C6 a4 ^& p( \5 w. T) ]   p=num;" e' p: b. }; H! \
  for(i=0;i<n;i++)1 e/ H0 i' r2 l9 E3 ^
    *(p+i)=i+1;; k2 e" c8 t; ]9 N! \! I2 ?# D
   i=0;3 E- f, q# n' J. u- [8 u1 ?: {
   k=0;
' W/ q1 ~. S( Y1 _; n: o   m=0;
6 x/ S9 n6 g. r; L  ^  while(m<n-1): }! o& n+ ?6 ^; W7 z  a
   {if(*(p+i)!=0) k++;2 g. m6 g# y2 W; x0 e
     if(k==q)
3 {$ C5 L5 N" P* T+ d' S/ ~$ H      { *(p+i)=0;
7 B+ k1 q! z9 r/ W+ a2 q+ O9 g        k=0;
; y. Q4 x! G8 J" `1 T5 R; m        m++;. \! f9 Q6 {, A9 Y/ X
      }$ L+ ?/ Q6 T6 O8 Y
    i++;7 Q6 f$ X  L* J4 ?& _, P  ]
    if(i==n)i=0;
7 g3 K0 c: Z; o; M   }' s, @) z, {  ~2 K% q- x
  while(*p==0)p++;8 F* k/ l2 B, L1 @7 T3 J) s
    printf("The last one is NO:%d\n",*p);7 J% n8 H5 G3 D! o0 ~8 S& ^! E
     getch();
3 H/ q3 p) D  ]  g* L8 m: `
& B  ]5 ^( W% @$ h. q( e}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;; @; I" v- @2 Z
namespace 又费马达又费电
/ J4 i4 R7 d1 y$ `# m4 ]3 I{
8 c6 r" ~% D; ]    class Program: P8 M+ F+ L5 _+ |
    {
( b8 I9 |, X% y( m, k        static void Main(string[] args)# P6 n8 p9 N; |$ Z
        {* e/ H& V& T! Q3 M( x
            int m, n;* D5 w1 g) d& x) D
            Console.WriteLine("请输入数组长度");
2 u8 s( U1 l9 ~+ t) g1 m            m = int.Parse(Console.ReadLine());//m为数组的大小" p/ |" ~) I: x7 j7 ^2 ~9 G
            Console.WriteLine("请输入要截取数字的大小");
# z+ K, E9 N$ `9 ~4 S3 l            n = int.Parse(Console.ReadLine());& ?8 o$ U% H' p
            int [] numw=new int
, n8 Z9 \% ^+ r- Y- t
2 k8 ]) {1 c2 P4 I* I&shy;&shy;&shy;;
3 S# [) N( r( M            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数8 \$ y9 a& r9 D0 s" c: N
            {/ z9 ]1 r0 ?. [1 ?' V; I3 j
                numw[j - 1] = j;
# |9 R! x# V. i7 w6 k& P            }8 U: q+ C8 Q) M( `% Q
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
0 v4 |8 u! \% B% _- H            while (d != m - 1)5 Z( R+ q5 R; p+ P3 E& T/ ~
            {
7 j  E/ U+ H# q$ ]- e) \                if (i == m && d != m - 1)
, q- F" ^0 @/ V* A& d                {4 {: f" `: K8 ~% K( J2 d1 n& T
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
* @6 `9 j; H2 e5 S: ?; @                    continue;
6 s2 Y4 I1 l  v9 w                }
1 v; K& W; H) @4 K. H8 L% |                else9 k( z' W' M6 I" D6 ?; H" n( p
                {; P. ^2 i9 w( V$ O
                    if (numw[i] != 0)
7 k9 ]  x5 K+ M$ u                    {4 k( d) z7 v- d+ B  S7 G' t
                        i++;+ a+ |! U6 {) M5 \
                        k++;+ V- d/ M, J) f7 I
                        if (k == n)
' i% y& ?& d4 b                        {
3 D  A# U3 x+ c* w* n                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
! ~6 j' n0 r) a7 z# O& ^, Q2 C                            k = 0;) d- X6 Z( E+ v) Y3 f* Q
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小18 p4 i% t* {, {* ^; u$ ]
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
0 [5 }5 z( [; U6 ^                        }& Q; K( r5 G4 ^& l& |
                        else//输出暂时还没有改变数组元素的值
  C% T/ L3 I. f( f- v, l                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
; u8 Z  ~* r: a" G4 ~* M5 K; x                    }
% r! j6 l, D( e* I3 B) P1 n% b                    else+ A. i+ _! s+ J9 R& ?5 P6 ]
                        i++;//数组元素为0,直接跳过,不计数。。。
  H2 u; K3 V! m5 C0 K                }
, B+ _( B/ d% z( l: ^ # K' Z2 n5 E! H! r1 e

3 H! f9 f; n/ G) N8 C            }//结束while循环0 R3 Q1 k& b- \; p: y
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦* w' `+ v4 i4 j; R' f' g
           , F$ ^- ~9 b$ `# H! |
                if (numw[i] != 0)
0 {2 C/ m7 z" q2 q# N: {, Q                    Console.WriteLine(numw[i]);) i! s7 C" z4 i
           
9 S  r( S4 K' V3 Z: N. n, F            Console.ReadLine();" _7 b5 D* ]" M9 d2 E8 c! y
        }- `% E7 o$ b7 p3 b
    }- A: Y  [, l7 G6 }# l- k
}
* O/ D+ F; O# A
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
小甲鱼最新课程 -> https://ilovefishc.com

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2026-8-6 20:48

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表