鱼C论坛

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

猴子问题

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

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

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

x
大家好!( D) r/ c3 i7 ]: {& ~
这几天我在忙着编一个问题,我用了一种方法编出来!
" u- W. q5 |( P% P% O) r9 W  O  ?但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
( d! _+ y9 P5 s  ^  ]2 G+ X注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 4 i' r5 X7 r* U: @
% h/ o" a! n& @) L; D$ c
$ z7 E4 m, z  {! V- Z
                            题目
! v# }- r) R( K' k山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
! t. w4 I" O- q& j. ?$ V4 r( j第一种方法:利用循环链表
9 Y+ h7 S% \6 i) e4 P, Q#include<stdio.h>9 X/ k( R$ R; O  o, y
#include<malloc.h>
1 v6 z1 U2 H0 T* m" F! P/ o; w# ?#define M 8            //共有8只猴子
& ]3 I* P/ }; L  q+ o- g! U  V#define N 3            //数到3只时退出第三只
8 k/ ?6 e. Z0 J  N$ `typedef struct monkey, j% u8 d/ k' x% @4 t5 F$ ?( T
{int number;
1 ^: F) O+ j+ V2 p4 jint flag;
9 {  d9 [% s' r( R/ `2 sstruct monkey* next;
- k4 o" X/ D. S  s* Z}MONKEY;0 N- Y8 P2 L/ |9 Q, o& T3 Y
main()7 D2 J+ \+ y+ e' x3 h
{ MONKEY *head=NULL,*p,*s;
( k4 Y+ i3 \, s2 t2 D- s  int i,sum=0,count=0;7 x# }( ]) I* f* Q% n) V
  clrscr();              //清屏
) {' ~# a$ T) b- X  Q; |1 o6 a5 t  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
8 Q3 X1 P, V* \( ], u5 d  p->number=1;p->flag=1;
' O7 r' W% b, `% m/ t2 a3 M  p->next=head;
0 t% G: _" Y  [8 S( \( F4 a% T/ {  head=p;+ [3 a, Y. K1 n* l" ]
  for(i=2;i<=M;i++)
* R2 k2 P$ X$ _    { s=(MONKEY *)malloc(sizeof(MONKEY));
3 @) a$ q* M6 M$ M6 M: j. V3 i     s->number=i;s->flag=1;
7 Y5 d6 u0 ?% x" @4 ^) g. M1 Q     s->next=head;( [/ J" N; Q4 ^9 i, V8 I6 s* ~8 n; V8 q; V4 I
     p->next=s;p=p->next;- Y1 ~" I3 d& g% u+ ^
    }
1 g9 t6 S' `3 p: N, m& H    p=head;
0 n/ R( j7 b! d) L7 F4 S) c* H/ M% G) N8 v   for(;;)
9 t1 y4 ?- Q$ q! O' R    {if(p->flag==1)' h% |* }% ?$ U) x' ~4 J! {% D
       count++;
4 S0 m, K0 e7 s' Q0 `! d2 g8 _% x) _     if(count==N)0 p2 J8 z' e) I0 h
        {p->flag=0;
2 R0 O% f3 W0 L) Z  N         count=0;
% z) N* ?( Y* x; w         sum++;}% t( q2 \9 F# D+ b' x
     if(sum==M-1)' a: n6 {. t$ d) q2 L  {" Y
        break;$ D% Y8 S) u# o' w0 ?) q
     p=p->next;, N5 w5 a  N/ l8 W2 `
    }  S7 k- T8 j: b2 @
    p=0 J4 w/ T" I3 A' V% e* L
    head;
5 R1 R0 I$ W4 o; H! v    for(i=1;i<=M;i++)
; c4 |2 h9 t$ b& e$ u    { if(p->flag==1)! N& \) w  l% y! Y) F  b
        printf("\t%d",p->number);9 G! K: u1 h: M5 @$ Z
      p=p->next;
; |" v2 M* j# v- V  c6 Y7 q    }
( u: Z. s+ \! y! M
6 T' F+ j% X/ B$ y! e  G2 J/ f) g

0 Q- ?5 j% o# |}

3 w! x+ y' m7 |. t% F2 m第二种方法:数组
+ H2 T2 H  s! m#include<stdio.h>$ K7 Q. K, m8 i/ k
#define M 8' N; u1 l3 ~+ f2 k, G
struct monkey" {5 O" ~' g- f/ o
{int number;
4 L' q2 h6 O* J8 qint nextp;
$ z. {9 d5 D* w}link[M+1];. h! M  U8 \0 j. s

* i# j6 W! h7 L) l. Svoid main()& ?7 k9 y2 n8 K1 A" `
{int i,count,h;
* m. w  y% D1 O" Ofor(i=1;i<=M;i++)8 d# z4 b4 w$ Y4 j; X1 e
{  if(i==M)
! V0 Q2 |0 P' @1 j' K6 u& G   link[i].nextp=1;
6 `  L$ h/ e9 C2 Q% O( ^: I   else9 H* u- J8 w$ Z& B
   link[i].nextp=i+1;0 j7 X9 x* q( U! H
  link[i].number=i;
) O) E) W1 f6 [$ h3 u- c) j}$ D( l, c- ?" t$ ~, F
printf("\n");
( i) g/ _; _4 G$ u) ^count=0;% E: [: n* L; F9 C( \  s
h=M;3 J1 P& b, a/ y6 l2 i% m$ b' F
printf("依次退出的猴子: \n");
: V# n  L( G% a0 s- swhile(count<M-1)0 J) F# D; n' r; u6 ~
{i=0;* B3 r6 S8 E& G, }$ p% I3 n2 s
while(i!=3). X4 L  ^# d1 q; k( z  b
{ h=link[h].nextp;
! M+ @9 a1 O2 k4 M0 l& v   if(link[h].number)
- t) T  H0 H# B8 A, `& i: v# P+ S     i++;}$ S. A& |" L7 a+ o8 V  X
0 L3 v2 o! ]5 q7 Z# I5 j1 J2 \+ D
printf("%4d",link[h].number);: D/ {2 x! g+ _) b7 i  h0 h
link[h].number=0;
9 b  |4 ^, b2 N( B. Q5 Wcount++;
5 V# C) h0 _% \}* M* [( P- B6 c( e
$ |$ w1 B6 O" H; N  ]- z! D
printf("\n大王是:");' v$ A; _* I6 \$ `" t
  for(i=1;i<=M;i++)/ n3 P, |: k4 v3 ^
  if(link[i].number)
) b; i6 q' Q4 b3 X0 R    printf("%3d\n",link[i].number);  ]' b% K6 F( w
4 x" J9 Q+ _+ r" i6 x& G9 c" B

3 b: G/ X/ H+ B. }6 m) t}

5 w/ P+ j; E9 T# R* w8 s/ A第三种是普通方法for循环
" D* u7 o' W3 {, h6 u( a3 m4 X
#include<stdio.h>
1 A/ L! s, f- B; \, g- ]8 J& R2 `void main()8 V( M; {5 K: R& L
{ int i,k,m,n,num[50],q,*p;8 O$ U- `  I/ z$ j/ r
    clrscr();: S  J1 T1 k6 k
   printf("input number of person: n=");- m0 C9 i2 t( r
    scanf("%d",&n);
' s# k5 J' }) I7 ~% Zprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
# g! W& ~6 r) |' p4 m6 h$ W9 \    scanf("%d",&q);1 x" e3 q5 x$ f' l
   p=num;
$ O* n- a, o% @! l  for(i=0;i<n;i++); m4 I# E; o  z) r& F2 F
    *(p+i)=i+1;
; `/ \( d8 k& a# Q$ X   i=0;1 p6 u) j6 Y- {8 W$ F/ ?* f
   k=0;
0 \( n7 ^( y2 a3 ?+ e   m=0;( H1 p5 D* v' Y+ u" q4 Q! ~
  while(m<n-1)
+ h. J- D$ Z. H% p6 g0 O   {if(*(p+i)!=0) k++;$ A+ Z, B( y7 D# C
     if(k==q)( V* _8 \) v" w! c
      { *(p+i)=0;
; K  J$ w# t: |, F        k=0;
( A+ G9 [6 p2 a9 |$ @        m++;' h. x( v0 G$ f/ A) U# u, z
      }9 h: ?4 Z  \; ?" q
    i++;
9 d; M0 h1 Z4 P  m/ Z    if(i==n)i=0;
! g; u( }' d; R  V5 M7 k   }. N! s, R, C0 u, X1 j) l
  while(*p==0)p++;
7 p! e  p5 r, w" o0 k( j& E0 `, V    printf("The last one is NO:%d\n",*p);! Z2 i+ X/ O3 x# `: O1 D3 G  n
     getch();
: D+ ]/ r0 J' _7 @6 k/ H) C8 ^* O3 v) E. N* X  A6 y
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
& L8 L/ F/ `% qnamespace 又费马达又费电4 I$ `  d% g0 ~% t' l
{
' _6 J9 P! h0 N    class Program! w. {/ V& n3 Q2 u! ]5 K
    {+ p/ p/ j! M, w, u0 N2 N" C
        static void Main(string[] args)2 }( `. a* L) E$ |5 ?% }
        {5 r3 i, b7 n3 L* J% p# p. Y5 `
            int m, n;- m$ }: g& L* j  C  w! p
            Console.WriteLine("请输入数组长度");# r# U! U( [! s: r
            m = int.Parse(Console.ReadLine());//m为数组的大小/ [4 y5 L8 A* z) g
            Console.WriteLine("请输入要截取数字的大小");
4 G6 d/ T( T4 f( H4 R            n = int.Parse(Console.ReadLine());6 x8 P% [" J8 P
            int [] numw=new int2 R* F4 Z. j/ {
+ s! Z" i3 R5 ?9 f
&shy;&shy;&shy;;
" T) i) M/ z8 |' {            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数- ^5 ^( x5 }, I
            {
. q6 W/ j  |+ P% c; B1 |. K" G# U                numw[j - 1] = j;
7 ?* r" d+ c. P: _$ o            }
6 K2 W* S; P# l1 @  O/ {            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
7 @) ^. [! b" z- P/ C5 t            while (d != m - 1)7 u7 E' h3 \0 Z, H, a6 D
            {5 Z2 V7 ~3 [4 ^3 U% B
                if (i == m && d != m - 1)% X# f' j8 F4 D
                {9 X( l5 F" o5 z+ X) ]: y9 }- x
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
, u% A4 ^+ f# R                    continue;
- h, S& }, }7 \' Z# o, Y! D                }
1 |& X0 d3 F5 L- a( h0 ~' o                else+ `" B& F( D% i; ~
                {
0 R; G0 s" q+ N6 n                    if (numw[i] != 0)
9 Z: p7 ?  O  r) ^% a                    {
  X$ h* [8 v( R: j, h5 D                        i++;
& T. }8 k7 K- P! j7 ], K) `                        k++;' O8 J. C5 P) q7 Z& c+ i
                        if (k == n)" K% \5 \% J  z+ f0 X0 Y; B
                        {8 N; d/ u# F" K" `' ^* u  }
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了8 g) h/ n3 |; z
                            k = 0;
% R3 L/ M; E+ u; c              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
& `- k* j0 @8 X' _                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
& X" `3 H' s. u3 g3 S; D7 G4 V0 Q) e                        }
5 f% n1 x' _; I% F                        else//输出暂时还没有改变数组元素的值# m/ X/ ]7 K) ?% U' h
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
  L0 v3 h/ q# S% X& G9 v                    }5 K. M; n, K3 r! P( g
                    else0 @# X* g( K/ l, a0 c3 `' R( d
                        i++;//数组元素为0,直接跳过,不计数。。。% d6 {" |4 i" ^. X5 ?1 {
                }
# q# x2 d- D: t9 r# p. S
# r7 [2 E3 c( @( s$ p  J' Q' C% D  K& }
            }//结束while循环/ l3 `! k. K4 c  R* K
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
2 A: B! a2 M% F6 y& @( H0 p           8 e8 X: `& g5 c  O1 f
                if (numw[i] != 0)1 r# X# J$ P" t4 \0 D0 ?
                    Console.WriteLine(numw[i]);( E3 C" {$ B% ^" V5 o
           
; q6 j1 N) J& K! `$ L; ?- K            Console.ReadLine();
$ T- R) w, a! ~  ~        }
/ M: F: z+ E8 }; o/ a, I+ |* m8 _    }6 k5 t+ g6 L5 Y+ Z9 d- p
}) F! c3 ?1 F8 ^* u$ h
小甲鱼最新课程 -> 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-2 07:11

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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