鱼C论坛

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

猴子问题

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

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

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

x
大家好!% q4 _( ]% ~% h  K
这几天我在忙着编一个问题,我用了一种方法编出来!
+ u' w0 z6 j8 i8 N1 t1 @0 y; m但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!7 d3 ^2 I" M' Q5 }- n- t* L( R* c
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
! b) J! P# _8 H( Y) `% E. j
- C3 |! c% O3 H. c* k4 p* R1 O1 r8 b7 O% H: S* T. U
                            题目) R. C& k% x; Y+ C, d/ q; X
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
0 r2 E, p3 }4 m. d' G3 I第一种方法:利用循环链表" I5 @/ ~0 V" G9 O5 ~
#include<stdio.h>
3 G1 U0 J( ~" p8 X+ _#include<malloc.h>
, ~/ J  |& Z: n; d. u' F% r- {3 i#define M 8            //共有8只猴子
0 C6 N, Y- o5 M3 r# n#define N 3            //数到3只时退出第三只6 U, X7 w* Z" |3 g, g2 a
typedef struct monkey/ P9 w1 N4 _( q4 X9 t& e' d
{int number;
( y/ U! K! L) P  bint flag;, Q& Q% G0 k; Y5 H% H5 n
struct monkey* next;) l; Z5 R( s+ r% _0 ~( T
}MONKEY;
  c& [, z, l+ w2 }3 p# T( \5 W/ fmain()0 E) }5 M$ s) T- _8 r+ I  p
{ MONKEY *head=NULL,*p,*s;$ Z' l5 d) Z% C+ ?
  int i,sum=0,count=0;% R, b; D1 P2 }
  clrscr();              //清屏/ j- y( x) ^  w
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存! a+ n9 B0 w2 y! L' W
  p->number=1;p->flag=1;/ |, J8 J1 x& n$ O6 O
  p->next=head;
+ @( }2 U, x: P6 |& k9 W5 x  head=p;8 B, H0 Z2 i; p/ s
  for(i=2;i<=M;i++)
! X$ m+ x0 i: ^& y    { s=(MONKEY *)malloc(sizeof(MONKEY));
  v3 n( G6 @, w) p     s->number=i;s->flag=1;$ f& L3 C: q* M% Z, j7 f/ `
     s->next=head;0 f4 F- ^; Y5 h  i' ]
     p->next=s;p=p->next;+ O- M, ^0 [; ?6 M' u
    }
2 `8 ]: g1 d2 Z' s, K  \8 M    p=head;7 a' s/ C4 P3 H, D: H* B6 M
   for(;;). P5 _; ^$ x7 p" W/ Y4 d
    {if(p->flag==1): V* X  e1 A) d  G' ^- s
       count++;$ W. A$ l$ U+ G
     if(count==N)6 Q& b7 ?& }9 e) k
        {p->flag=0;
) U, _& K# W5 c0 I         count=0;
! E6 Z( E- T4 J7 ^( ]         sum++;}6 h! ]: f  }' ?% q
     if(sum==M-1)
4 ^5 f. P) B0 A) t5 i* R        break;
& O+ R. V; k" \6 X$ s     p=p->next;
# x: V5 o; G) A" b3 s    }
/ F- K5 {5 h& i) I0 |: D    p=
7 x( {/ |8 m% c    head;' P* i$ m2 e5 u6 {  x4 [7 ?
    for(i=1;i<=M;i++)
8 k3 g8 r! d2 u7 L' i1 u1 q    { if(p->flag==1)
& q% C5 `# ~+ y5 e4 q        printf("\t%d",p->number);0 u8 F+ K' B9 X
      p=p->next;3 l6 ^/ ~# E3 I$ F0 h! _+ F
    }
) K! N, u4 o& d6 S- b+ B6 v
1 J8 U1 ]0 F1 q
5 f) L$ Z% e% ~
9 D1 D+ B/ F. x# ?- e& k$ s' t}
- h' s  g( m# N) F9 s* m6 f
第二种方法:数组
- B0 |3 M) R1 Y) M0 @1 @0 t#include<stdio.h>$ H0 v* W% S% L0 t8 ^- L1 ?/ z) b* n
#define M 8. H0 Y  ^: {4 g( E5 C
struct monkey9 l' S' v3 x; S
{int number;
3 q1 F% _# G5 \/ b4 ~$ aint nextp;
. l! K1 J" C. ^}link[M+1];% j4 p, P% n' p8 Q

$ ]; t6 i- x1 G" u+ t  e8 Hvoid main(), G# A3 b  C5 y; f, j
{int i,count,h;% s" l  y0 h+ E% f" d
for(i=1;i<=M;i++)
; @2 Z$ G* g2 Y* ~{  if(i==M)
! v6 z- \" X9 ^; E   link[i].nextp=1;
! k' x8 k& ~. @( m9 N/ R   else6 e$ ^) i/ z2 B2 t+ J- _) O) x9 E2 u* ?0 ?
   link[i].nextp=i+1;. `: m) ]1 g" `" V
  link[i].number=i;0 l% j6 G8 R  F/ Z! U& Z& d8 f
}! u) a, l, [: g4 S
printf("\n");
, ?1 C* W7 q: x& e: ?! N5 ocount=0;
/ u! {2 T4 D  p8 ], rh=M;
, Y9 b, Q+ p; K1 ^: H6 E8 ], W, Aprintf("依次退出的猴子: \n");
0 d( W) B5 C$ Q  W; N! a+ Zwhile(count<M-1)
1 p. w& x! b/ Q- @{i=0;  I" H/ P& X7 J
while(i!=3)  w. r! f" d. k+ t$ c0 ]3 T
{ h=link[h].nextp;, o3 Z6 M0 [' A5 g
   if(link[h].number). H. g$ P& S- a
     i++;}
1 O6 q! `% Z% J, L& _* K0 @! A+ v! H. }) D# _
printf("%4d",link[h].number);; l2 U* C+ S- k% W& T5 a9 G
link[h].number=0;" Y: T3 ~  _- o
count++;
7 B& \! a. W: e, F- |# b}
, W( B- z1 d7 x/ f8 m/ y4 e0 U3 @2 i+ E' g, p
printf("\n大王是:");
7 n/ l, {) e4 `( M8 D6 g  for(i=1;i<=M;i++)
5 q* X7 i/ r0 J' Y; |/ \( s, J  if(link[i].number)
+ \& |+ I* ~- w5 D9 S- I% r, j    printf("%3d\n",link[i].number);, u! L% @4 L. P
' ^+ O" {5 n$ B( A0 I

! |+ V, K' Z: e( ^}
. V( \) C. q) E6 c4 r
第三种是普通方法for循环

8 J" z0 e% N9 u1 Z7 _, w- j+ K#include<stdio.h>
* Y2 o2 h( _% c$ T' e% I5 c: i( G3 nvoid main()
% y( }% i4 O& j; m. {' ]1 e+ E{ int i,k,m,n,num[50],q,*p;' H3 N4 @* U' \0 s% D& `
    clrscr();
" S) Q- D5 R/ L9 Q- s+ {  F; m   printf("input number of person: n=");2 c5 _2 k5 }. H
    scanf("%d",&n);
  w! S/ U5 r/ w1 A8 tprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
1 R+ H' H; G7 q  h  t" ]3 X6 G    scanf("%d",&q);$ b6 o/ g, Q6 `6 V
   p=num;
: K* P+ M  n: s0 N' R9 V2 x  for(i=0;i<n;i++)
1 A  i1 |3 C  g3 @5 Q2 Z( `    *(p+i)=i+1;
( _( H, M* x( a! [& r8 }   i=0;
+ s( O3 X6 ?0 o. I- C   k=0;/ d1 h$ v$ `! `6 M, ~0 _
   m=0;2 Z3 k# P7 y" T' X: g; j- }5 j7 [1 `
  while(m<n-1)3 e) A0 {2 |, H7 T
   {if(*(p+i)!=0) k++;
" V% g3 m7 d! q' I( F! E# f' Y+ a' ?+ P     if(k==q)
+ K" K, \& S5 L. R* E7 g& r! u      { *(p+i)=0;2 e* ~; Y9 f% \; e+ a2 f, e# c
        k=0;3 H; m6 v$ d+ E! J
        m++;1 H' ]4 {5 J2 f- ]$ |1 H- J3 A
      }
. v6 D* Y% _0 ?+ \' B4 Y9 o2 }    i++;' J* S& \8 `$ o* e! Q+ ~5 p0 u- x- n
    if(i==n)i=0;
( `+ a3 U- p4 H" ]   }; U0 c* C8 U' ^
  while(*p==0)p++;
9 e" k' i8 ?- m6 O    printf("The last one is NO:%d\n",*p);
# Z0 B5 I& {, a, z9 d8 n! ^" l     getch();3 p* f4 r2 c( y4 F2 b" m2 Q
- |1 K; e6 ~! v$ X8 _
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
8 m1 C7 L$ ^7 b) m! ^% l4 Y7 a- F7 _namespace 又费马达又费电
" U3 _! O* f* ^6 O7 F+ y& {/ G: Y9 S{1 K' @& L: }7 s
    class Program/ a3 E. y& D: _% R
    {8 c" Z9 o7 r  k& j9 S
        static void Main(string[] args)
. x# O( \2 B) U5 \        {
. D- Y- I8 r5 M            int m, n;
4 x1 n% a+ _1 x7 a5 d            Console.WriteLine("请输入数组长度");  [1 E3 D0 j" l% {! X
            m = int.Parse(Console.ReadLine());//m为数组的大小
: P- K) P, w) {% r' N/ k            Console.WriteLine("请输入要截取数字的大小");
2 M! G) V9 ^8 w- L0 J% _4 a            n = int.Parse(Console.ReadLine());
6 A) f* B- [" l1 T& u+ ]2 P4 ]            int [] numw=new int
, z" p' m$ c5 J( x$ |& X# k& R& b9 B
&shy;&shy;&shy;;  J8 a  y: p( n! `4 m( F
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
- i6 q. ?+ P8 Q7 P* u7 U7 E1 N            {
* x$ M2 c+ C, G. i, n                numw[j - 1] = j;
) y# O) a# F& B/ p  S, s( _  I            }
, s1 A1 G, x1 K. n. D            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
$ ^3 Z1 q( ?; D# ~; q            while (d != m - 1)" w& e* M6 y" J
            {2 g& G/ ~: m8 E" [3 T
                if (i == m && d != m - 1)
: @3 [0 k; K/ l9 c                {& }. O4 F" D& d( }) `8 r! }& p  J
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!( u+ K( [1 o8 j
                    continue;
9 c: B' C( K- h& w* y$ t& X  H/ P                }
" n8 U; r* p% v3 u  _' |                else
, @; z1 o  C3 |3 _. Y7 @( _  h8 [                {
' c/ l! A0 n( k" E* O3 X  y                    if (numw[i] != 0)2 G; S' Q- t% \0 H
                    {; G/ a& H. M8 j! e+ t$ \5 j, }
                        i++;( \* B( i- ^+ d4 i
                        k++;) E& n8 z- N  [6 d  i& C
                        if (k == n)2 y5 `# W2 ?4 T) Y7 q$ a
                        {
: A" L* H0 g: ~5 ~                            numw[i - 1] = 0;//把在n位置数组元素的值改变了7 L2 k0 v0 e8 H6 Y' x4 _3 N2 M
                            k = 0;; y' X0 Q/ r4 s1 c, g) L
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小18 G! W8 L% ]: j1 _
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, E; l0 P2 D/ ^: m  i% C% q3 f' K                        }8 K. x& a7 z6 m: M5 G2 U( z' B" p- @
                        else//输出暂时还没有改变数组元素的值  I1 [- ?. S% X5 o7 }- s# Y
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
: y6 w% l! a( V% }                    }7 c( Z& y, q4 W; V8 B$ m
                    else
" c5 ^" u8 s% W0 j# I1 ~$ u8 U                        i++;//数组元素为0,直接跳过,不计数。。。3 P: i$ x7 F- h2 D7 G! o8 Q) s
                }
# i$ d8 {; S  D5 x: l ' Q8 g, V" Q9 }7 p
$ \: j% z, s5 M/ ~) K" L1 D# N
            }//结束while循环
/ L3 r/ Y) Q# U# H% E' [            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦5 {3 G" }4 e- M
           
" m8 ~8 x1 A; g$ \. u) D* t                if (numw[i] != 0)8 J5 c- d! w, o- |
                    Console.WriteLine(numw[i]);
! ^* l8 R' @! s           : C/ r3 O; {* M& }8 _- @" T+ g$ Z
            Console.ReadLine();7 r0 m1 w% H" h; K) R  F
        }
+ V9 H2 _. l' }/ U7 h8 q: q) v    }
3 o: p& m$ P5 `4 r}8 w! H9 ?( n2 G7 P8 j+ x! k. L
小甲鱼最新课程 -> 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-3-10 09:37

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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