鱼C论坛

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

猴子问题

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

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

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

x
大家好!
) K$ ~' o' C& c: M) r- j% W这几天我在忙着编一个问题,我用了一种方法编出来!* b: I9 {; J/ t6 Q, s4 K
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
, y( u0 _6 Y' T* v, r注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 7 @# o+ D* ~( u2 A

' c2 ^  Z* Y4 M0 ?5 ^  v
5 ]# {( |: q: o* g- y; u* a3 I
                            题目* ^" K9 h4 R4 K8 l% J6 W% o' W
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。5 I! P/ x$ D, J/ T& ?2 g; `
第一种方法:利用循环链表9 n5 ?/ ]2 }6 i
#include<stdio.h>
# m" h, F( r) y1 n# r#include<malloc.h>
7 r# l6 [! Y* ^) _) \* a" y: s! b#define M 8            //共有8只猴子9 {0 V( i3 ^6 L& ]# t! f! f% ]
#define N 3            //数到3只时退出第三只
, q5 J5 W, Y% B: ~* g- Ytypedef struct monkey; ?5 ~( H; g9 F7 G  Y4 K5 g" }/ `
{int number;! i' O0 v. B/ A0 e( v  B* n
int flag;% J9 r: b5 C: M' D3 m2 D
struct monkey* next;7 q# W9 `7 r( h& _. B
}MONKEY;
2 ?8 X2 U$ ?. m# }( wmain()5 l5 P. H, w' \+ \! S# n
{ MONKEY *head=NULL,*p,*s;% R( N0 ]# l$ u1 r9 g: P; M
  int i,sum=0,count=0;
& }  c3 ~7 K5 ^0 m  clrscr();              //清屏
+ [& P' \! d' v# z" s! u  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
  P: j" v7 {# r6 c5 E  p->number=1;p->flag=1;, k( N# G' v. D8 }
  p->next=head;
& m8 Q  E" D" r7 s' i  head=p;
2 N" {- z5 f5 ?, Y  for(i=2;i<=M;i++)7 g8 e; ?7 B" |" F9 L7 y
    { s=(MONKEY *)malloc(sizeof(MONKEY));0 g1 z! _; \. s8 N
     s->number=i;s->flag=1;& |) N) t3 G+ V, Z) ~
     s->next=head;' v5 K/ B( K2 Y
     p->next=s;p=p->next;
( I$ T+ y( q: E. I3 y8 P  c    }
* z6 n- B3 @( U" r6 c5 n    p=head;
: _7 Y9 T- f) `% m2 \   for(;;)$ F" f, G9 O# v3 }$ N5 W0 ?. v6 j
    {if(p->flag==1)
1 M& N. s3 `* O% E+ U! y( |4 s) z! B       count++;
/ C+ n# T/ P/ ]+ X     if(count==N)5 ]- `- A2 Y3 d! W9 i- Q( T0 c
        {p->flag=0;, V0 L$ w! `# m- s
         count=0;5 M2 l% h, _0 j7 t5 j! x7 J$ A
         sum++;}1 x5 L! f6 R; C0 I! s) E, l% `
     if(sum==M-1); F" ]& c& B3 V: q8 E8 i; ~
        break;
7 j9 q% u* f; D: z     p=p->next;( V2 M8 Q/ C# z" j! \
    }( A  W' [" h- A( Z9 g2 t0 n8 @  }
    p=1 C) V7 u1 f4 _. Q
    head;8 a+ T/ C6 p9 }; j; J% x
    for(i=1;i<=M;i++)' w) P+ w3 N2 k! u
    { if(p->flag==1)6 @; L0 \4 e  G$ h
        printf("\t%d",p->number);( U% ^) o2 g" z6 u0 S: H
      p=p->next;
7 A2 ^" ?  m' K7 ?+ z    }* p0 J' W% U# r3 L' X
! @, R- W6 J0 n; h; `  Y, r
2 p  J/ I5 ]6 ?* z
  ^+ R; U# g' x/ w% l5 a+ |; y; R
}

; E5 B8 F( e7 G) Q# f, a6 t第二种方法:数组2 \4 ~+ }0 p* x7 N+ n% A* u5 |4 _. Y
#include<stdio.h>* }0 M& Q" T" q2 Y* `1 D
#define M 8
+ V9 `: D8 W* M. Pstruct monkey
: k; [" [' O$ `" m7 u{int number;5 ^2 ^  N# X. p3 U
int nextp;0 [( ?+ C6 z% W) n- E" I4 h' n5 ^
}link[M+1];: m$ @$ u& X- v! t$ X* P) F) @

3 r1 N7 ~; Y* X1 t" zvoid main()
" p$ W  A8 m" f) C# i9 y6 G{int i,count,h;
% c- p6 p' b2 Q! a" s# A4 efor(i=1;i<=M;i++)+ m. g1 Z8 f7 O% b9 g
{  if(i==M)
5 g  w! R: j0 |+ X# h# K   link[i].nextp=1;! o) Z' V3 Y8 S: p- M3 j% r
   else% n6 Y) J4 h! Z+ m
   link[i].nextp=i+1;
  D" }# G! y" ?1 w3 m% N) w3 E  link[i].number=i;( f1 L% `, X) }+ g$ z3 _
}
0 f5 L% ?+ Y% H! J" Zprintf("\n");
8 w$ W  U# ~+ ]$ j1 F+ h" E' ~% Bcount=0;3 @( x6 [& S6 e. T1 G! _
h=M;
& m+ g$ d. \/ t8 {printf("依次退出的猴子: \n");+ n& z9 `3 y: W  V- Q$ s
while(count<M-1)
- N2 [5 k2 n+ i3 o1 ~  S; l6 x{i=0;
2 N# O8 w7 y1 T0 d1 _2 Swhile(i!=3)
6 \2 _! {# T) |{ h=link[h].nextp;
+ _9 ^# K: ^0 Z! c1 ~   if(link[h].number)# q3 T: f# |, L, O6 ?- I3 o
     i++;}
6 {' ]0 B/ s8 }4 W1 W/ B8 d" C& a! ]9 x+ c2 W
printf("%4d",link[h].number);4 p7 v5 I3 E7 m7 O$ a5 }
link[h].number=0;4 o8 F+ h4 A  U( z- K
count++;" Q- i/ `; `& ]
}
* l7 X6 o: Z& x
" a( y1 b% \/ Y) \/ I  bprintf("\n大王是:");
; W& @% Q" L) Y  for(i=1;i<=M;i++)5 E3 H3 |, h+ q9 U* k1 p
  if(link[i].number)# b3 R9 D9 k3 p2 v$ X+ S6 X4 C" t2 D( c
    printf("%3d\n",link[i].number);4 w! a- S( B& T! d
) F8 d8 N! ^% z" ]

! O/ e- z" \2 a}

; G0 f3 c  N" a第三种是普通方法for循环
8 f& \% I& k# w2 r& a' s0 w
#include<stdio.h>
- @' v; z; R7 k) ]6 B; ovoid main()
. y, m9 V2 P! h) T7 u- D{ int i,k,m,n,num[50],q,*p;0 k4 k# w# N% O
    clrscr();: F% q3 v* B2 O/ O" W
   printf("input number of person: n=");
/ V6 P. i4 v, H+ i    scanf("%d",&n);6 u( Q. a' E& z$ x1 x7 |
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只9 U5 x1 m) p% A+ H0 B5 @5 e
    scanf("%d",&q);$ w) j9 a9 x7 T( b. r. y7 E
   p=num;$ V0 o: f2 T- @! E+ V( B
  for(i=0;i<n;i++)
1 z% X6 H9 B' K& h) t    *(p+i)=i+1;
/ }9 j( q: P- l  n7 f& s# y/ z   i=0;1 u( J5 ~! F% t) ~. \" J
   k=0;
# |6 I* B8 x8 r) K   m=0;
6 c$ _# W1 w9 T9 j; w5 t  while(m<n-1)* L) w9 I) j# o4 J5 M
   {if(*(p+i)!=0) k++;! b) J! T4 U4 ^' D
     if(k==q)# A1 a) K, i" S, D! k
      { *(p+i)=0;4 I+ {# o: z3 J1 p
        k=0;: t0 M3 P9 g; a, r! C! \& ?
        m++;
' J: B6 ]" u/ `2 N, `( f      }
) j' y& x' c. W    i++;0 E9 o3 R4 g9 j
    if(i==n)i=0;
5 e; r4 [& X4 }2 L9 y   }& O" x. k* Z1 W& Q
  while(*p==0)p++;% r* k4 T( E3 c9 V
    printf("The last one is NO:%d\n",*p);
0 n. R. U( _5 |     getch();0 l, }7 j, Q* R! b8 d5 n. C
) F) K( A) F/ _3 v  B- \. c' p' E- S
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;. M$ z8 T. v2 P1 [' Q) E* \5 N5 _
namespace 又费马达又费电
; K! w  l+ Q" v  B* y7 _! m9 a5 H! y{
! T# Q2 X3 ?8 F$ M0 ~2 A  B    class Program" L, i2 V2 x) P! U* N$ _. i, J( Q1 x
    {
- D" q0 S3 B) V  T: I2 ]' ~        static void Main(string[] args)
2 i' U) L, C# K  D# ]% X, T        {
& `0 I1 c! X. e& X            int m, n;
; m. A& C/ A0 [  T9 J' C            Console.WriteLine("请输入数组长度");
: ?( z3 P7 l/ O* `            m = int.Parse(Console.ReadLine());//m为数组的大小6 }, v$ W8 c2 m; a: e7 i& c2 q
            Console.WriteLine("请输入要截取数字的大小");
: u9 s% x$ x& r+ m3 d2 Z/ z            n = int.Parse(Console.ReadLine());7 n) X/ L& g1 ?% K) h2 A: N
            int [] numw=new int8 Y( B* x2 @+ {: x. p: _

2 Q0 b) U+ l) m: c&shy;&shy;&shy;;+ c& |# {2 ~- J/ F( ~  _
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
/ ~+ A" P+ [8 |* t  c0 `- u. C3 d! x            {3 h! E! L7 d5 c8 }# a
                numw[j - 1] = j;$ M/ Z5 k9 X/ ~- X2 a0 Y6 D3 L
            }5 L4 D% O' Q6 y6 z3 m9 b
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
2 P6 S1 [" J' o! n0 r            while (d != m - 1)7 H  x; `$ f+ t  Y* K7 F4 H
            {$ e& w* d( `2 S5 a/ c; p
                if (i == m && d != m - 1)6 x- |% j& y- y) ~$ |; V% e
                {
$ d" |: c2 `1 A! U0 X* j                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!# M* l& f5 C) H+ n- ]3 L8 S# j; j
                    continue;) A- ~7 F5 M2 w: E
                }
5 c5 v% f% s# u5 t' l                else/ x  Z9 [6 i9 u! R
                {  j2 Z! Z( P, c$ A/ {
                    if (numw[i] != 0)
7 j& ]" \: {+ c% t$ `                    {
" D- m+ J8 D! `% t5 y' J3 h                        i++;
' H- a2 H" W+ i0 s& r                        k++;
( }" m$ Z7 V% y4 D) K2 |& a                        if (k == n)( I/ F' B# L2 e6 @4 |
                        {+ [6 T2 _4 o" t* B  {8 {7 d8 P0 n3 M
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
# O9 @( Y  ?; [* c                            k = 0;
6 W! k1 A2 b. b  k- D+ Z              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
3 G8 q( w$ S: y# {$ T8 g                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
' n: f9 I) S# P! O" f2 e0 q4 \                        }
! U+ v; i2 j3 z) s7 J7 d6 f6 |                        else//输出暂时还没有改变数组元素的值; f8 ?; |) x( S! n# i3 O! P# s0 }3 E
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: T1 M' f8 l1 n2 y/ n
                    }
9 r0 d. |- j0 n5 ]2 J" h                    else' U- R( {+ ^& I
                        i++;//数组元素为0,直接跳过,不计数。。。
8 h$ y- b3 N( R" H                }
" O4 Q% c+ s2 K 2 ]  H$ [, f' N, M  G; T

$ `; z" A$ Q2 d# e            }//结束while循环
& K+ l6 ^2 _# k+ k' ?            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
, X% Y0 c- Y2 X! q( l7 N# s2 Y% U           1 z$ ~  L/ ?) y
                if (numw[i] != 0)" p7 {& _& e9 B) T6 g
                    Console.WriteLine(numw[i]);
3 Y3 T* F/ r" }) N2 t- N# ]             @- w  y  q4 O- ]& e
            Console.ReadLine();
( n' p3 W, C3 G4 n5 \        }
/ h, n; l9 H. v' Y; \" D7 X    }# U5 ^# }8 L4 V( n
}1 P- I! \+ S7 `& }/ V# r
小甲鱼最新课程 -> 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-4-7 20:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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