鱼C论坛

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

猴子问题

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

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

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

x
大家好!( o6 R* @7 B7 E
这几天我在忙着编一个问题,我用了一种方法编出来!: z4 V/ |' `# d- w
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!0 G0 G. C5 k; B# c) {# w
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ' E4 w! P  O$ v4 {8 ]8 B

: M1 {! K" B; S7 [- V
7 p9 J0 ]) l3 z) \; Q2 A$ D: L8 `
                            题目
7 v& t/ r1 J. u/ E$ V4 R山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
) s; Q- b5 x% i' \3 s第一种方法:利用循环链表$ I2 x/ C. S. R- z+ r' A  P
#include<stdio.h>: u9 X! G( d& x- {
#include<malloc.h>, C% G2 P) E/ c+ r: X  S* x' C
#define M 8            //共有8只猴子
" F* Z* b; v% X4 Z5 U#define N 3            //数到3只时退出第三只
6 t; T1 Z2 M/ Dtypedef struct monkey
7 S& N6 a% D1 H{int number;
& U+ I' {: O$ B2 h6 Kint flag;
) x) X+ f* n1 W  G9 u4 F0 P# [! rstruct monkey* next;. R- r1 s, p( }
}MONKEY;
2 p' b7 _* {+ B' {$ Omain()
2 h: I& m2 |& N8 c1 a, p! n{ MONKEY *head=NULL,*p,*s;
  ?" q! j/ H) C5 t  int i,sum=0,count=0;$ _. `+ d6 ^, Z
  clrscr();              //清屏
/ J, n; o6 p& t% U  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存, ~; |4 Q1 F: Q$ g) ]: M5 |
  p->number=1;p->flag=1;
6 S9 b3 L& P5 |" p, _  p->next=head;1 H4 X/ e' g) l- t4 Z
  head=p;
2 E* `% x$ D9 L4 |  for(i=2;i<=M;i++)* q2 D; D7 S* w/ Z+ M% B
    { s=(MONKEY *)malloc(sizeof(MONKEY));! E! m5 W; J2 r; ~- |2 h
     s->number=i;s->flag=1;" O' `( F7 l1 e5 i$ u9 i, [' y
     s->next=head;( r! u5 f) M) V/ m
     p->next=s;p=p->next;& s( p) G+ k. _5 p) F$ L% v# {
    }( {( V  G5 w$ X" M: m& o! H
    p=head;- P' L% J/ b: B  Y
   for(;;)- r3 c3 g$ d+ I4 T
    {if(p->flag==1): u5 C( {/ p! C2 L
       count++;: z; h; D2 T' @" a7 M& \  l
     if(count==N)
, g) A! o1 ^% f! f5 @( M        {p->flag=0;
' G( o" u4 B; v5 o) _3 f         count=0;  c8 b& W5 b5 ?
         sum++;}
! ?& `3 R; Z7 L% D0 u     if(sum==M-1)! M- |0 w( W' H6 I9 C
        break;% k5 U+ a. @8 m, @7 E
     p=p->next;! O7 e9 I* p) }  Q
    }
& B' q5 W( V& b2 _5 \/ H% R6 s3 X    p=5 u' n+ c  l+ ]; i" V3 D
    head;) R, b! B0 u" Q. a3 P" b/ D
    for(i=1;i<=M;i++)
9 B, U/ C/ `: b4 }2 P- I$ y8 Z    { if(p->flag==1). z* X/ E. C& b4 C# N& ]# J* u
        printf("\t%d",p->number);
- ^- s) g( E# T. k      p=p->next;  b8 ^0 G" e% a% s
    }5 Z* E. y! C# ], Y( b

0 W3 i  y3 C* u; x
4 u1 G# [; Q9 L; b/ O8 Z" F: z0 P
}

4 Z1 q2 C/ b! ?: E第二种方法:数组
4 o  c% ?5 c. ~5 C/ w) `#include<stdio.h>
9 z; ]  q) S$ [# B#define M 8
4 d# N5 B- h; y2 |$ O7 ^, Hstruct monkey
) E8 E2 @' O. o$ q7 T4 \{int number;
- b# @+ W' F7 a6 kint nextp;
; X( U. q0 B: F* C! H$ d}link[M+1];
1 P! T6 M! e, h  ]9 V
1 B, I! p  W7 d- S0 t8 |5 hvoid main()9 c  k0 q4 Q9 `* x
{int i,count,h;
4 T5 h# k/ d0 Q* rfor(i=1;i<=M;i++)
  P% o1 Z) W- w5 C$ n{  if(i==M)$ A  k  C7 b3 S' Z! o+ x
   link[i].nextp=1;# M; j+ f/ _3 C3 S
   else
) I0 k6 j# X4 R1 M6 G   link[i].nextp=i+1;
0 N! _! p9 A$ _1 F+ g  link[i].number=i;0 E! [* C+ W7 E6 ?1 a0 V% X; P
}
3 [0 P- I( Q! Q3 @/ V6 _printf("\n");! C" Q. q/ f# K- J6 E* L
count=0;/ ^1 Z- ]+ t% p0 g" D
h=M;+ f4 T3 G# r6 A0 Y. ]
printf("依次退出的猴子: \n");6 [' P; X3 ?* R6 L+ y4 d: s& |, E& u# ]
while(count<M-1)+ @  w/ ?! f+ q0 @
{i=0;# e  U2 z& ?7 c% B- y4 |
while(i!=3)
, V# F7 G3 p& O0 Q, n& G{ h=link[h].nextp;
2 G3 c1 R+ ]3 b4 @( Q: R   if(link[h].number)
4 o+ o! G4 l, o* G: E) O6 o     i++;}) Q: e, V; K+ `
/ I( b% t1 o) p
printf("%4d",link[h].number);8 I' K0 w3 Z. n" [" i4 b* m1 W
link[h].number=0;) Z- S/ g9 w) Z
count++;; s% y' v+ o) J2 C
}5 V6 \& l7 l( ~8 P+ @$ {% x  _1 E
0 ?0 R2 o; Y, \
printf("\n大王是:");+ W. I& v' g4 Y* b3 _5 @' m1 ], C3 u
  for(i=1;i<=M;i++)
/ k, f" [- c# R4 q5 `: K3 F) o  if(link[i].number)
1 h3 l" p. p; t( ~2 p    printf("%3d\n",link[i].number);
7 t! {% L2 A& T9 f- m- m1 v1 a' g. c. r* J$ ^: t

# f: c" [4 d$ Y" Y% f% X' Z3 m- ^' J}
) Z9 a3 y6 C* Y
第三种是普通方法for循环

2 D) u: J; R2 q& F( p#include<stdio.h>
( ]9 C2 d' e* B# K0 I2 x8 M" i: Ovoid main()  C# _3 @, G7 r, D$ z& u
{ int i,k,m,n,num[50],q,*p;
0 `, Y( F$ E/ B9 {# `. G    clrscr();, s; ?0 B4 m: m, N
   printf("input number of person: n=");
! W$ f9 g, B, k    scanf("%d",&n);- u" M; O$ J/ |9 n/ O, s0 @1 L- y
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只" a8 |6 M8 V8 L# ~& t% R3 X6 B
    scanf("%d",&q);1 g, I; t: v! C. W" L
   p=num;
  O9 X, o$ V4 x, k: s  for(i=0;i<n;i++)
7 N- Z% Q9 v4 F: f: @4 R    *(p+i)=i+1;
& u3 u* V7 t) o% Y2 P2 v. {   i=0;
+ D, s' Y% J" q( @4 g, Z; ?) n2 Z   k=0;4 h/ N$ ^' q* R/ Y1 {- x
   m=0;
/ j, l3 o; ]+ i! \4 f  while(m<n-1)
* s* x; v5 Y5 z7 K   {if(*(p+i)!=0) k++;
* `: I7 l- P2 N$ X% p: u     if(k==q)* D. _2 Y8 ~& w& \4 Y
      { *(p+i)=0;& v* `# {9 g$ t/ B2 o1 O3 U9 y
        k=0;
/ j# |3 m9 M4 H4 x; C        m++;
5 C" f* P2 ^7 Q4 @7 u3 ^. ?      }
& a8 v4 t3 F) ]; |    i++;4 N4 L# ^  N7 T
    if(i==n)i=0;1 ~/ R3 j! A8 ]3 @, j
   }
) q" X9 g& N( v! u, [7 R  while(*p==0)p++;, f- s& O: j; U$ r
    printf("The last one is NO:%d\n",*p);! I9 c% m1 N4 Y2 E) `  R2 d# i
     getch();5 X5 ]$ i" K5 s6 i# n6 y

" P% Q% M$ n) }( K! Z( y}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
& q  E: l7 G3 G" K9 u" I8 nnamespace 又费马达又费电
$ X: A' g- c, m% x{% x6 P, h8 }6 n0 I4 L2 \
    class Program9 Q- z0 s9 d8 X6 G! y/ k* X
    {" h( l) b! R% O; Q4 f& l( u3 e
        static void Main(string[] args)0 J2 a/ X  V( ~5 }7 a3 R
        {
& t& s4 F% D7 S' G5 _0 e            int m, n;, x: U+ g9 z6 s# U
            Console.WriteLine("请输入数组长度");' {1 O1 k1 ]$ \3 |, E* v& }7 Y
            m = int.Parse(Console.ReadLine());//m为数组的大小
& E! T2 B% v: Z            Console.WriteLine("请输入要截取数字的大小");" a5 }& e' N4 s9 Z: \
            n = int.Parse(Console.ReadLine());0 |6 j  P9 ^/ v7 e  x2 d" o5 r; p
            int [] numw=new int# J" |$ j: ]& c" S2 p" m

5 ?% I% p( d7 {9 n" [. P&shy;&shy;&shy;;
) j5 E1 W' C5 i, m& D5 O1 `3 Q; h4 M            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数( W- z* f  C3 D2 I  ^$ M9 u
            {
, a( G! p& g. n9 u/ c( L7 n! ~                numw[j - 1] = j;
2 e! a* p& M8 F) Y& P* z* |            }+ @% h) f5 N% X% \/ h- b, c
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!) p8 d0 K2 k2 A" t2 y
            while (d != m - 1)
6 c* k# E& U& M7 C: u' @            {
6 v. c8 n" i- H9 t                if (i == m && d != m - 1)
0 ~$ K) q7 M2 J8 N3 [                {
' N  c8 p, X/ N$ I! h                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
, J. Z: Q: {2 Y4 j; p                    continue;
7 s7 L$ ]# c! ^2 u  c/ I- V3 R                }( \* P+ z* ~: i$ m& V& M0 R+ k" I
                else
5 V; }. |; c5 Z+ V% Y  Y. f5 {4 h                {- g5 w; ~+ r4 e) Z4 b
                    if (numw[i] != 0)
: H6 P8 N# T9 ]$ \7 \3 w, u                    {% U- m: h9 Q* q4 [! @8 c
                        i++;/ T9 f7 ^# w% k
                        k++;
3 l4 F# |3 _- F+ B                        if (k == n), {* Y+ ^" @" A7 d( K
                        {
3 A- c$ G! @4 ?2 s                            numw[i - 1] = 0;//把在n位置数组元素的值改变了4 h! @' w9 x% P- i0 ]% s& {3 {
                            k = 0;8 ?1 s- H- h0 N9 F& o- n6 N
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小10 O3 P6 D2 |( `4 M8 P8 ]& r6 F
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
% C% ^8 a. \' |8 ]; j                        }) {1 \9 R) a$ o
                        else//输出暂时还没有改变数组元素的值8 X" p: f9 z2 d+ ?  a
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 b( K" D6 y) i                    }
" a# }0 T  v2 A  P8 r6 c& ]                    else( I$ l3 i. h: }) ~
                        i++;//数组元素为0,直接跳过,不计数。。。. A& F8 r: h, ^
                }
2 x) L. p5 Z. R/ j+ k
7 O7 q* Q/ a8 t+ P2 `) _8 w0 j- N- n
            }//结束while循环
" a+ \' J( b, g! f& p            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
. c' G0 [' f- N7 j/ z           
% j& i( c% g, F& g! U  Z- }                if (numw[i] != 0)
# a# h: U  }* X; G                    Console.WriteLine(numw[i]);
% Y% o2 w4 \9 ~. A. m9 p           
, V$ u( B4 S, s1 }4 ?            Console.ReadLine();0 A% @7 f! q0 X  F& w4 N
        }6 t2 q% G6 s- y  H' _
    }
# t& }7 T6 |3 q7 Q}
% a  y% N, J- 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-2-8 13:25

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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