鱼C论坛

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

猴子问题

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

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

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

x
大家好!6 E& T1 m8 `4 z) g# ]- E# Q: h% u
这几天我在忙着编一个问题,我用了一种方法编出来!8 @! c1 {; o3 e, c
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!7 A& U' Q7 v% h, p: l% h5 q
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 $ e6 [5 B$ x: o. x
2 _  ?# j3 C+ b5 k! u: t
2 n5 t, N  x" t2 f: j% d9 {
                            题目$ X, D  j- m+ f: g# F$ I$ J3 `2 ~) Q
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。5 v' a$ D8 c0 y' T$ A
第一种方法:利用循环链表
- o0 ^, ?( ]* ~( |9 L2 n#include<stdio.h>( f0 b( [% c) [# }) n: d
#include<malloc.h>
& b. b2 t6 J) z# P" k. N#define M 8            //共有8只猴子# ~0 Z- n2 D5 n' c! A/ Q. T4 u
#define N 3            //数到3只时退出第三只
5 ]- Z7 @( T, U; mtypedef struct monkey
* i6 d# t# q$ D$ @2 r! @! u{int number;
" F  K1 e: i7 C, O5 `int flag;
. K7 w2 Y& _% ^- Z, c6 v' }struct monkey* next;
7 ^0 p0 x+ U7 {% X, ?% u}MONKEY;( y1 }! S2 T$ ?8 D- [$ G
main()
7 x! g2 }/ T) o/ }- s{ MONKEY *head=NULL,*p,*s;- @" X# _5 |9 Z% F/ u+ X: h1 b
  int i,sum=0,count=0;! W, D( D! j/ P/ s% I. I& J
  clrscr();              //清屏
- o5 Q# Y" v$ h  R; N  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存# E/ |0 m0 R7 e" G+ d$ b
  p->number=1;p->flag=1;
0 i# h6 @3 `  Q& O( y" [  p->next=head;
; E" w' e; J2 ]2 _# S  head=p;$ l) M/ g  s- y9 X, i: m& i5 F
  for(i=2;i<=M;i++), l9 t6 q4 Z5 v1 R* k
    { s=(MONKEY *)malloc(sizeof(MONKEY));
6 x$ |! e; `) a     s->number=i;s->flag=1;
9 R' u' d3 W1 D' l     s->next=head;
2 Y; G( \4 s# E7 v     p->next=s;p=p->next;: V" V9 W4 Z4 ~/ A
    }' g8 n# @8 i" r
    p=head;
1 Z* G' d2 Y0 O% y0 x   for(;;)
! Y# x8 `$ e" M8 w' q! o. h    {if(p->flag==1)" e  s3 A" K% n
       count++;
8 G8 u8 S9 T# J, W: S) \, f% L     if(count==N)
  [. Z$ I' b7 s* ?+ l' O8 x        {p->flag=0;. Z, V* m1 o2 X
         count=0;
; {; b7 z: _6 W  }5 h$ a: X& e7 ^" T         sum++;}
$ e- ?) r, ]7 J9 |     if(sum==M-1)
$ u2 X* ~& R) U4 B( w        break;" n& m0 `( a- x, h
     p=p->next;
) f1 Q5 I! x; r0 G, {; l- O    }. B' `5 F0 @4 y+ w& P
    p=
2 N; Z' V( x6 m- F    head;' q! E8 m  I- H0 t  {: H
    for(i=1;i<=M;i++)+ M1 _! `% [4 j. _" L* D% h
    { if(p->flag==1)
: }) X% E, d+ E  v% }  `        printf("\t%d",p->number);" u" i9 ~6 ^( v" j( v
      p=p->next;
, t  o& p! o( \! V: @$ e6 l1 W    }
$ H- P+ a# Q2 o- g; \/ B
" b0 E9 i1 y$ ~3 `0 S7 s# x# a
9 ~$ A% P9 ?' f. g# h( |
' h' e+ U8 }9 ^7 h6 S: T}
1 r8 A9 F7 w8 S2 p- y
第二种方法:数组% k& w# {3 ^5 Q' ?* h" ~. X
#include<stdio.h>$ @, U- O/ h- X
#define M 8
- ^, F- D; \+ M2 f* V2 T! cstruct monkey# Z& ~+ m# U1 i6 E4 d
{int number;
& ?' y* [' _  s% ?) Cint nextp;& X5 X4 K9 h& y; ^
}link[M+1];
( D1 A. O4 {- Z/ A6 Q( P% N, i% t+ [( P0 W4 N% Q
void main()
' p  |; \5 B! ?7 ], v{int i,count,h;
$ v4 D" d- U3 @9 g% ]% lfor(i=1;i<=M;i++)- Y. ^* D: V" E
{  if(i==M): J& _# ^  I& d  S9 d3 v2 l0 X5 Y
   link[i].nextp=1;
; F, x5 o8 }+ f6 |! g   else
' _# E/ Q2 h7 h. z1 T0 L  |   link[i].nextp=i+1;
3 g2 ?0 q" w% ?$ {, _8 c3 s1 p, s  link[i].number=i;
! \' G9 ^2 D! {- S}! u' J% s. c5 T! t- J3 j6 U  u
printf("\n");: h( l7 l. K: V" X& s0 l' |
count=0;) q7 h: T4 k6 D" w1 }# s+ D& |
h=M;
" o+ a2 J3 A/ H9 w/ cprintf("依次退出的猴子: \n");
9 w- |& @3 N9 i2 X7 S) w" C* Cwhile(count<M-1)
, q9 i' v* g3 m+ o$ f" x/ ~3 i6 d{i=0;; M5 y8 }5 j0 g" B2 z$ S
while(i!=3)/ r& s; b! ^1 y
{ h=link[h].nextp;
3 H0 [* |) @: `% ^' Q$ h; y  o+ Q   if(link[h].number)
' A" B, G! l. A! d9 c     i++;}! h2 j( Y3 M% X9 m- v2 M1 P
- c- W% c  q  p5 K; R
printf("%4d",link[h].number);
4 y, f  ^5 E9 ]1 olink[h].number=0;
5 r  X( P6 P. J0 q+ r. C' x1 K( `* \count++;
+ q& u$ g1 Z6 F}; d. d+ m5 _. x9 G0 |

4 `! w( a/ H# r( v( P) u8 nprintf("\n大王是:");
) n/ i, ]9 Y! j8 F/ P4 n6 w" R  for(i=1;i<=M;i++)0 O' c3 A0 B/ h* I8 f1 f6 u
  if(link[i].number)! w) G, l( ~9 ]  n" Y# P6 }2 w2 `
    printf("%3d\n",link[i].number);- E" ^) ]) i" u+ B% m6 |: d

9 f! }% s( r! E0 S3 m2 a' @3 m4 s
}
3 C. g' l+ p* ?! C
第三种是普通方法for循环
5 H3 G9 h9 @, a3 d
#include<stdio.h>
. v. }4 f# W+ n+ U- O! o' q, xvoid main()
1 Q  M4 K0 K4 p/ ]& a& J- s  Y, B{ int i,k,m,n,num[50],q,*p;
8 m( w0 H' a* g" ~' F    clrscr();9 q  P1 {* H5 _' E2 T$ `# o
   printf("input number of person: n=");, ^' l- `5 r) j7 `+ H
    scanf("%d",&n);: a2 n0 H# C1 s# \5 J2 ~6 x
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只# R  ?/ A# W! t7 Y4 h$ c8 i" D
    scanf("%d",&q);
( t- }4 |, t3 z1 X   p=num;
4 K2 l5 {7 b7 D7 @* c; Q, z3 _  for(i=0;i<n;i++)
7 A5 `" _8 D0 N: C7 X5 w    *(p+i)=i+1;
9 _/ h+ ~; K; [$ d, R7 Q   i=0;( f+ O( P( N7 N/ ~2 @' J
   k=0;
! S+ [0 b9 \! A* c7 R" K; l   m=0;& S7 H, x: Y7 y( G
  while(m<n-1)
# ^; e1 L9 M  {( w! O* a5 a" \   {if(*(p+i)!=0) k++;
4 |6 ?  G1 T$ Q( F1 T" R     if(k==q)
: d* \$ ^! ?, q& r( f- ~      { *(p+i)=0;
. t3 D# D6 K, `) h5 R* y( O# D        k=0;
/ P3 ?* r+ Y: v$ m        m++;
0 a7 [- V5 \! T  @' ]      }; |" T- G( L' n0 y" K
    i++;
8 k* ]. c- B, F' W7 a    if(i==n)i=0;5 v7 P4 m) h5 W7 m5 a
   }
1 P# M( c1 o5 b+ N# Y6 l& q  while(*p==0)p++;
. {: \9 s7 x& b    printf("The last one is NO:%d\n",*p);& f, h) S  M0 X1 M
     getch();
; p+ y8 L7 F: n& U
" ~% _/ u1 Z/ T4 j}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
5 S) |1 J, U4 i' k1 @namespace 又费马达又费电
3 Z0 E% p* {4 `' p' P{  q- S% c' R+ O/ k
    class Program
' Q) [: J7 S: L- P1 _" O( r    {
) |! b. x) f; k& `9 `        static void Main(string[] args)
; Q: r- Z. L) F: a' K        {1 @) y4 l: T$ ~" V3 T
            int m, n;
3 J" u6 C9 _. ^3 P* S            Console.WriteLine("请输入数组长度");
6 ]- H( Q5 c. K* N7 t+ b            m = int.Parse(Console.ReadLine());//m为数组的大小
' h* m. o; |1 p( ~            Console.WriteLine("请输入要截取数字的大小");1 L$ \7 x' H* M
            n = int.Parse(Console.ReadLine());; u1 t" }/ ^/ K
            int [] numw=new int& g2 o: S7 V( y+ Y

5 P, k6 ~3 y& t! Z$ Q&shy;&shy;&shy;;. ?9 Y- [+ l# T$ J
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数1 ?- b% u" ?1 {" L! o, l0 C
            {' o& s7 [) _, C: g
                numw[j - 1] = j;
4 w  K0 [5 h4 k, i            }
6 d# `* Y- \, m; C            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!1 J/ E) V$ z" R6 c. p
            while (d != m - 1)
2 k7 v# \! c5 ^5 }: n4 S: C9 i            {! Q; W7 B2 U* B' K' q, L
                if (i == m && d != m - 1)
$ D! L, w5 B* @6 e0 @, |7 J                {
+ w. q+ m* \9 v* Q$ z- G                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
! p: m: |4 z% e# u                    continue;
/ m( M: M6 u: P                }* c& q" y2 N; |+ C
                else
( F$ [- v) U( d7 S* h5 }/ \                {
: P  ^1 p! Q' `  w                    if (numw[i] != 0)# ]  n# j* k* h& B) G# m. |! v5 Z
                    {
8 f7 L% b1 Q/ l% Y% v6 h                        i++;9 |3 ?. p( F$ _
                        k++;* N8 U4 G: i  O0 i2 ?
                        if (k == n)5 r  P$ k6 |6 J8 k" C& J
                        {. ]" U& \7 S+ v
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
+ c" P3 ]4 B. k8 F: }2 ^: m, E                            k = 0;
) v- ~0 r, Q' V% X0 c) P8 ]/ N. ]- O              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1& G4 U# a$ w! x3 @
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);5 m, X2 c) p$ _/ r. G! K
                        }, @1 l% r$ t  W& e; m: Q. O
                        else//输出暂时还没有改变数组元素的值
" \9 N4 y8 Q# O) T                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 w: E' A) _: g5 @  J( v
                    }  _( U+ |4 i8 W4 @
                    else& o6 k3 Q! [) h7 q2 Z$ l  F- h
                        i++;//数组元素为0,直接跳过,不计数。。。6 X6 m* p( c( h; K+ l
                }. @- ~# _) u1 g# o) u% \

+ k" }0 _$ h! p3 s/ w  _: O
* H' v" t9 s. @: @4 A* r3 X            }//结束while循环
( j" l- x2 U, S2 E3 a- ?( _            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
; U1 c) [4 ?- K! t- f) u           " i4 M* z4 t7 [  \+ e; k% x
                if (numw[i] != 0)9 y- x: E) ]" ^, L- B$ b9 r
                    Console.WriteLine(numw[i]);
) ~4 K0 I2 _8 H           0 l6 z! ~( m' u# [3 J
            Console.ReadLine();
& v6 o8 g3 ]8 p7 d% u5 V6 X' Q        }$ O: U  t, E  q3 F5 d1 Y
    }/ O- c; r! f7 k8 O" m4 S% R4 V% |
}
8 V* x6 S. p/ I& e* V
小甲鱼最新课程 -> 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-9-19 12:47

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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