鱼C论坛

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

猴子问题

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

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

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

x
大家好!
- W6 w3 ?  G+ z9 c: ?; y/ ]3 S这几天我在忙着编一个问题,我用了一种方法编出来!5 A" \5 j5 L7 Q/ `; m3 g5 N( C  K. h
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, Y' n" j0 n! r9 T2 b9 E
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ( h: i0 ?; z8 v
0 g) z8 i/ i. j: y6 e4 y- P- `( [
+ v) \, C6 L. a; b3 i
                            题目
: n$ ~: N: A, D' ]9 i山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
9 a. W9 U4 W1 ?( E& K8 [1 A第一种方法:利用循环链表
5 {4 ?# u3 v0 L. a% z& B' f#include<stdio.h>
- B$ @3 c6 k  U2 c! Q# i9 S#include<malloc.h>
1 {! T/ U5 F0 H/ ~/ b6 B  d, _) A#define M 8            //共有8只猴子1 U# a0 T3 D0 S* z1 `: y/ v( ~: I
#define N 3            //数到3只时退出第三只4 @! r$ p5 R1 T
typedef struct monkey. ?7 h0 y7 M' X, D
{int number;: D5 i! N+ G/ z4 {/ \6 e
int flag;
, l1 g3 `  Z5 {, Dstruct monkey* next;. N/ L& a) z! r/ k" d" H% p
}MONKEY;
9 R& U% }( o; ?0 zmain()
5 C3 F3 n) U1 V. ]7 V- p: {; e2 N{ MONKEY *head=NULL,*p,*s;9 |! Y1 `6 I8 x
  int i,sum=0,count=0;( R+ B2 c* S2 L1 K- ]+ R5 F
  clrscr();              //清屏" W1 S& |& [. j$ ~
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
- W6 ^) ]% m0 h  p->number=1;p->flag=1;0 w, f7 n, b7 x6 c
  p->next=head;% O. ]; x- Y# f1 H
  head=p;
5 X" R+ T$ D- |+ l) i' j  for(i=2;i<=M;i++)
, W! L4 M  `2 `$ H" X6 Z* i    { s=(MONKEY *)malloc(sizeof(MONKEY));
+ Q1 M9 ]6 x9 q2 I1 o3 k" ^     s->number=i;s->flag=1;( M# O# \# ~+ G5 |" X2 M+ ?" Q
     s->next=head;
  l4 }3 V! v% m. Q7 y     p->next=s;p=p->next;
: G! J- A  t! ]: p    }: [' y& A9 N( J5 a. }
    p=head;" i; H8 ^+ I4 v, t) y/ t) Z
   for(;;)
% B7 W# W2 K  U) |; v    {if(p->flag==1)' h% O6 h" M' s9 v5 g6 H& H, U
       count++;
. S! M: E$ |% z+ R5 A; w     if(count==N)
: ^! ?: l% |% r0 g        {p->flag=0;
' k% Z4 o+ o- ~+ y         count=0;- ^9 c+ v; Z/ j. b* c/ m% T5 Z
         sum++;}- H$ D+ r' Q( `8 D9 j7 C6 Z
     if(sum==M-1)
& I. y( {3 h, C        break;
  Q$ X9 L, Z9 |     p=p->next;
+ Q( w: I  w7 ]8 q+ b& `    }' `/ H! L+ d! V$ O& e7 n0 Q- {! \$ e
    p=
* s, O+ C! y# f" B2 ~    head;$ \" ^# y$ ^( K, k9 r7 _/ u! V) a
    for(i=1;i<=M;i++)/ G+ w  e0 t* S' b
    { if(p->flag==1)
  C2 |. s" Y  v2 O8 O9 X        printf("\t%d",p->number);
( N$ [& K3 B: F8 d! g' T5 Z5 V' W      p=p->next;
. @/ d' q9 Q3 U' n; k1 F    }
0 e3 `) Z1 q6 W/ r: C5 E+ A" P( f: P& d2 H9 c6 S+ Q0 m5 i
0 k, M; q7 H# {- f3 k

+ k7 t" v' F# i- E4 _* T}
+ W& n# F+ e/ h, U/ ^; p% l# F
第二种方法:数组
7 C& C5 ~5 d% q* I$ H1 M/ L#include<stdio.h>' w* |5 x  H/ f
#define M 81 W+ c  O5 |7 U$ ~( c
struct monkey
& q4 n& v  q! }$ s( e{int number;
8 S' z' G3 f! @& G) u5 D  Yint nextp;
3 E2 F& s" P- P% V}link[M+1];
) R9 z" p3 \& ~; w1 i# k& M' C
1 Z; K0 X, q* Y8 vvoid main()# N/ P0 ]+ ^+ Q( T+ |8 I3 @# [* q! [
{int i,count,h;
, X0 G( X) b- m  c2 v4 u, m* Nfor(i=1;i<=M;i++)# Y; Z4 M& i, f6 r  \! o5 [' z
{  if(i==M)- O$ h* Q* k; |# Z. g; v  s
   link[i].nextp=1;
. b1 h$ d5 t6 q0 s2 n* O3 o4 [/ D% ^   else
. j' U, O& T6 @7 K5 Y) `   link[i].nextp=i+1;7 T5 F3 o- _) T  N/ @7 N% e
  link[i].number=i;! N: Q5 F2 k3 C, ^5 u4 i7 _' R
}
: b: _8 I# v: t7 H9 W, cprintf("\n");
; {$ D% E* u3 \8 o8 Wcount=0;
/ ^4 G! T7 c! n- Qh=M;& u5 h, B3 f* ?, ?2 E) O
printf("依次退出的猴子: \n");$ B2 d* f4 B1 n/ p& K
while(count<M-1)/ Z3 k9 s, t" {0 Z: t& j
{i=0;
5 [. \8 H" P" Bwhile(i!=3)
# d+ z& g; {+ y* w" j- B/ x4 |4 x{ h=link[h].nextp;
- X* [: q: f* R1 P* @- q   if(link[h].number)+ ?( U' d6 Y* q/ B
     i++;}2 ]' w6 m; G, H) [: f  f

; c$ c; Y$ h" S" N0 ]6 P( _* W1 bprintf("%4d",link[h].number);
4 X* B$ I* W) n2 O, A! Vlink[h].number=0;5 C$ G% f; e; `# h4 P
count++;
$ e! j# T5 ^" }- e1 k& ^; p1 ^}3 {7 N8 d7 x0 ^' F: Z. @7 g; `! L
5 f& B+ m: G* R, o: y# e0 B& g
printf("\n大王是:");; Y0 k, ^$ m& ^2 v+ X* Z
  for(i=1;i<=M;i++)4 C# l! H, u  B
  if(link[i].number)
, Q  n, P' B5 B- f7 E8 g    printf("%3d\n",link[i].number);
' z  k' Z' `, b$ p" b' Z. l2 \; k/ u; {4 q4 o: u7 l# i2 i
- q& ]0 m2 P7 ?3 ?6 D# l
}

% H0 ?* e* C, l第三种是普通方法for循环

0 P# u# S7 F9 e: n- ?5 ~% K#include<stdio.h>- Y, i+ F6 F; D  s/ L
void main()
7 X6 c/ C1 u. Q, D/ i& o: \{ int i,k,m,n,num[50],q,*p;
" C5 q- I5 Y$ Z0 O- X5 {    clrscr();
4 E  R1 e+ S' N8 \   printf("input number of person: n=");
( D. e8 L- u: @- B$ A    scanf("%d",&n);
# h( _; K% v0 u; m* x$ i( zprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 ?: h9 F  Z% \$ Z  a% ^1 Z) B    scanf("%d",&q);
. }' p0 P! v# ^   p=num;  u& b$ k4 S4 n: \( u/ g
  for(i=0;i<n;i++)
9 L4 q# E5 \: I* R6 p4 M1 Q, R    *(p+i)=i+1;
$ n) W$ Q& H: Y4 g2 E) y   i=0;
9 y: s1 ]5 c. l" ^5 l4 b0 G1 f8 P1 r   k=0;) Y9 u9 v0 p% `5 l6 M$ G5 ~+ L, |
   m=0;
( Y4 a0 s+ T" a% n% |- @  while(m<n-1)
* Q3 N9 R# A3 F4 A" K* t/ R) J   {if(*(p+i)!=0) k++;- v2 K! W2 Y5 P% g. w) L8 C
     if(k==q)
4 n/ R/ [: h9 }: \- L      { *(p+i)=0;: i" H, r3 r; V6 y+ W
        k=0;" Z. ^$ O  W0 B& S
        m++;  _) T: J& Q0 Y" A+ G
      }8 D7 Q0 R' h5 `3 u) a! m; b
    i++;+ o  x: {" @. A; {" D; C; n) b
    if(i==n)i=0;0 z) e% z$ [! C0 p3 H' |. ]5 j4 R! V
   }
5 C3 p6 F9 j6 v; R$ o" F2 z  while(*p==0)p++;
$ `+ w! J- V2 K; i- Z, o  u    printf("The last one is NO:%d\n",*p);/ k" W4 d# h4 x3 b( a9 j0 e5 t- p
     getch();' F) X% R) g2 i/ i$ u
" r9 f1 b+ L# i. |
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
* o3 P, @! h- G, c3 h7 Snamespace 又费马达又费电/ \5 W5 |% g: M/ O
{
' M/ ?/ T1 N- v; Y$ w$ [" K& B5 Q4 _8 H    class Program  L* y( k0 k- L: c5 y5 q
    {
. v) s2 g) ]6 s- g/ r! E3 Z. z        static void Main(string[] args)) U$ @1 `' X4 a. A% g
        {
& v8 t/ z! K4 ]5 v0 ~' k( ?3 |% e            int m, n;
% k/ [/ {' Q& V& V            Console.WriteLine("请输入数组长度");' A5 S, I  \# Y) \  O; `9 t
            m = int.Parse(Console.ReadLine());//m为数组的大小. u4 C$ Q% x& r' H( {" y
            Console.WriteLine("请输入要截取数字的大小");
  M+ ^! Q9 L) G1 q9 p5 M7 q            n = int.Parse(Console.ReadLine());2 }0 [% u* D6 b
            int [] numw=new int
- n. L+ `. I3 m7 u- y5 I. u3 _) z
$ d# g% w1 U* L0 V0 Y9 E&shy;&shy;&shy;;( d; P% f( Z* }; V. x6 p
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
, _+ X$ _* r3 g1 A            {: `( ~  |& o& a% @; Y6 s# {
                numw[j - 1] = j;0 G: s; z) k% C  o2 m
            }, J3 d1 L5 c$ V* p6 r  c3 o8 O
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
1 Q% _8 G& ]! p& Q3 w: [% {            while (d != m - 1)
+ I& H7 N* N+ i- x" q; `$ _1 A            {
' r: s7 j, E) A) }                if (i == m && d != m - 1)
  N7 g6 k) e8 H) i" J% Q                {5 y$ W' S( P, C" M4 [' h% l0 N/ I
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
# R, L7 V4 |( f8 e" t6 D                    continue;% `2 v& G) U% i+ J- J( K4 x
                }- ~4 H( t) Y' p
                else* ?+ T+ r: G0 H$ p1 m5 a
                {
: _5 p& D2 J3 c) P. F8 L  q                    if (numw[i] != 0)& R: D$ e( \. b2 Z2 u- M8 ]6 D
                    {0 T* g! f% o; y# Y
                        i++;
0 g: w8 l. f$ x                        k++;
5 u) W0 s  z" W/ d                        if (k == n)$ @% B9 }( U  k( I0 C! C: ~5 h
                        {" @3 z9 b. a! E0 ?3 w
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了( `$ n% q9 J2 v4 P" F
                            k = 0;
( V' n) T4 Y3 I7 R4 G              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
7 r* Y2 F& j% a4 w1 ?1 R, \5 E                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
- r! R0 }/ N9 E. D8 q! c                        }4 e: I6 @' k. }! ^
                        else//输出暂时还没有改变数组元素的值; l' T& T' e' u3 _3 n/ |; S
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 J/ n0 U2 {  V, X0 P# e0 b0 b% S
                    }
" v2 Q0 ~2 E1 l2 d8 C                    else  ]  R1 ^! q7 C- z4 d
                        i++;//数组元素为0,直接跳过,不计数。。。
- h0 T- g/ O! F6 O2 r                }
' E# l! p  X9 I- V+ L" o* E9 i 6 U9 ?( G. H' O; W9 }3 O5 ]
9 n6 z% C! }; u
            }//结束while循环1 z8 K# t# J/ r1 C8 I* Y
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
$ f& n9 \& U6 e9 K5 z' {0 u             E- A0 O0 W# [
                if (numw[i] != 0): R' g9 P2 [8 m/ w3 R7 }
                    Console.WriteLine(numw[i]);
5 Z& Q, E+ z$ R* R9 Z# R8 u           2 y& N7 X8 Z( Q6 ~) u  A) t9 y
            Console.ReadLine();& ?( A) Z! Z4 h$ b: g* @
        }
4 V' ?5 }( s& z    }& P9 _* `* Q  }$ ^8 r) R
}$ ]9 o+ L) y4 x( r9 s" N
小甲鱼最新课程 -> 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-22 03:08

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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