鱼C论坛

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

猴子问题

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

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

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

x
大家好!3 h# B9 v1 L( e; ?" h
这几天我在忙着编一个问题,我用了一种方法编出来!
3 w  P# z9 M! D; q; r- h0 O, a' C但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!1 n9 o1 G2 B1 _& A8 F/ R7 n
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ; L2 _$ l$ `. |( O) o
- V9 i. t6 H5 _& x/ a3 V

5 a/ [2 @/ B9 k( B' F; b
                            题目* T. \$ x# `) C
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
+ }7 o) ?+ O* N/ K" \# |7 Z第一种方法:利用循环链表5 x( [0 u; E- R  Y! a% \
#include<stdio.h>
* B, L$ E3 \, h( V#include<malloc.h>
4 G9 n4 d: p2 o  z#define M 8            //共有8只猴子4 Y* c6 M+ Q  s& \$ Z9 `
#define N 3            //数到3只时退出第三只
- F& ~9 C6 m. K; M  u4 `3 Htypedef struct monkey
. N# x  J% C4 p+ K  _( ^7 x' I: E{int number;1 o" M& a* o1 J
int flag;/ H7 P% q5 b- `7 @  p! V
struct monkey* next;. B5 t4 @; {1 h: r" G/ D
}MONKEY;
! w7 j1 i9 q  z6 t+ U1 {3 A& S( S" `main()
0 @: S8 k' |+ G* T5 {: h- ^{ MONKEY *head=NULL,*p,*s;1 ]' q, q% G% _% X
  int i,sum=0,count=0;
2 G$ Y8 m( @( z7 i  clrscr();              //清屏
2 [( r, x* e; {  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
  U3 {# T$ A2 |% `# H' [* q  p->number=1;p->flag=1;  J' v9 }: C$ p2 K
  p->next=head;2 H- @3 f) b9 q3 K
  head=p;
# d! p- H' x4 M1 h  for(i=2;i<=M;i++)# f% l( w; R9 c' i) V8 @  [; S4 {
    { s=(MONKEY *)malloc(sizeof(MONKEY));0 R# M5 d( {( q1 ^, _+ P) {7 I" Z. f
     s->number=i;s->flag=1;
  C' n! [( R; `% U6 p5 e     s->next=head;
6 n4 P6 s- D0 v& e* V2 V     p->next=s;p=p->next;8 ?$ |# J3 ]# t
    }
; i* v! b7 J  b! V    p=head;0 k7 w1 P8 O) Y* V# d, e6 L
   for(;;)
$ e  c( }# ]. \5 c% Q. Y$ W    {if(p->flag==1)4 v5 B5 S/ I: D
       count++;6 y0 f; L$ I, r
     if(count==N)9 m/ T+ b! C6 n. Q( d7 Q
        {p->flag=0;$ l& k+ V0 Z. T1 S7 w
         count=0;8 P2 L: a1 h. o8 ^, \/ `
         sum++;}( W4 d6 V$ B# a& h: N+ a1 x
     if(sum==M-1), N" d" V# O9 l* ?: S. f) t
        break;
5 ?: _9 u1 F5 ?. a9 Q     p=p->next;+ t: b3 r" q+ [
    }6 S$ ]. o7 V% [! f
    p=$ m# S/ P5 C" U, p! E3 F
    head;; Z/ O  p$ V; c, C9 b4 K2 K" z) G
    for(i=1;i<=M;i++)5 A5 \7 W: S0 X& l; H2 C
    { if(p->flag==1)9 H3 v( m8 q$ D6 L. n2 _
        printf("\t%d",p->number);
( y- A: W3 p% d& m      p=p->next;
1 k1 h" W: I2 T, c! g1 T( P    }
9 Y( v# I2 E3 \& V; f% W7 d! h. G
; ^7 W4 P6 M* m' P3 U6 D) m$ m' v8 z, e  Z! P/ L4 H( S" ?7 C0 n6 \
5 o/ G6 {, d& ^' S( A% h
}

/ J; p7 K  d- y, T5 d& n第二种方法:数组
3 p$ D& Z7 n( l2 p#include<stdio.h>
8 C! i; t  J' x& t8 A) [#define M 8+ ~: h) @$ V& w# [
struct monkey
/ r3 O8 e/ ^; {* [8 l6 ?{int number;
& X( K- N0 V0 B  U6 {# g, u2 @3 H" Oint nextp;% u& e9 f$ B9 x0 E: A$ G  r
}link[M+1];
3 [+ r+ }2 J# z7 c# O
- w1 k+ N5 G1 [% x4 n3 d. l! n* \void main()& u& J1 b" h* k: S. \" A" K
{int i,count,h;
+ P: |7 f+ j  ^" k1 ufor(i=1;i<=M;i++)
/ R$ x; ]3 J. t' x3 H1 m' O+ H! f, F7 l{  if(i==M)9 e. f9 ]. ~; a
   link[i].nextp=1;
: X2 N+ }( Y0 }5 m; }   else
8 R( Z* d4 C7 @: d* y$ c! B   link[i].nextp=i+1;
9 X" V; P2 A/ R7 n) F! b1 n1 P: e  link[i].number=i;- e( q8 }& Y" @8 L2 \! i
}
6 {5 |+ b6 U7 s; Sprintf("\n");
# Q; k* h# g3 J9 K" g( }count=0;) R6 X8 C, _: {: e
h=M;- c0 v' t5 {8 q# ^* n9 q& y
printf("依次退出的猴子: \n");
; n# }* y1 e+ N6 d( s. u. @2 }; Swhile(count<M-1)+ A% _! }* n% A: d$ w4 C
{i=0;
( p2 s, Y1 i* s6 R% \; ?while(i!=3)
1 I4 L# x* v6 W, [' A6 b1 y{ h=link[h].nextp;" G$ G+ n& e5 {! c1 o
   if(link[h].number)
( s- v8 S- ]+ ^0 T. p1 u  A     i++;}
) e& z: u7 m9 y3 J9 c9 {! x2 X" ~/ m, e8 U
printf("%4d",link[h].number);
$ f) s8 F* ]9 |1 f+ Y- w5 G) ^link[h].number=0;! L; c: |' P, p; U; v( H% Z
count++;2 y0 i* q' d% R* m
}8 e0 Q6 B% g9 v
% E2 N7 k) t9 A/ s" ]. g2 R4 z
printf("\n大王是:");
. v6 ], j' m3 v0 ?; b) J/ C  for(i=1;i<=M;i++); H# F+ k* ?' p+ S
  if(link[i].number)
; ~7 W* Q. c# m4 @    printf("%3d\n",link[i].number);
2 W2 S$ U& P1 S. t+ P  ]: ^& Q% P9 Z. b, |7 t0 G! L) G3 _

9 T" r2 G5 b" f. v5 Z}
% S6 ~  n2 J- z, ~, n# q
第三种是普通方法for循环
8 n( j( X" Y+ l: h; s* a
#include<stdio.h>/ L) i9 V/ I2 r
void main(), Q1 C+ F& q. |( S( L. j6 Y
{ int i,k,m,n,num[50],q,*p;) p$ y! H( T: J
    clrscr();/ [0 D; l& o' S" L. X
   printf("input number of person: n=");# j! r- l0 K- d/ C" F) v6 x
    scanf("%d",&n);
8 _$ s# U# M6 s4 S1 i5 Aprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只" A# ]5 p9 F# Q0 h1 k3 T4 o
    scanf("%d",&q);
% S0 i" n. o' [3 I   p=num;1 O! Q; b$ e! a; w
  for(i=0;i<n;i++)7 }! r, o9 F' [
    *(p+i)=i+1;# f# n' e- B" y- a7 w  J9 g
   i=0;4 T; |; w; c- \& i" |
   k=0;% P# E; g, t4 w6 w8 h1 \
   m=0;0 B, g8 t1 k1 k: s  ^3 \, Q
  while(m<n-1)
) [( `/ e) T: ]3 B* }  L% m   {if(*(p+i)!=0) k++;# g$ c. Q& a  [7 @
     if(k==q)
1 |/ b1 _# n4 m; t- z! T$ i      { *(p+i)=0;  C  f! d0 `$ \2 M
        k=0;: Y1 W3 a. B$ b" z! c* J
        m++;
5 a$ ]( E- o" f5 c! u      }
# \7 M/ `: M; z& l    i++;
6 X. ~4 j& b9 h3 L) V    if(i==n)i=0;
4 [$ V7 ^8 C5 M4 ~% y) N2 }   }
6 E9 r! ~+ `2 B; k: Q- d2 F  while(*p==0)p++;
/ ]4 I0 b$ r% j/ x. }3 q# n+ c$ w    printf("The last one is NO:%d\n",*p);+ \/ J$ n# |5 V) K
     getch();3 E: U- i4 d) S; H* k' C

6 _7 \6 Q% @( e& L, A# {}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
% P5 d% D" `1 R' G5 O/ L. I: vnamespace 又费马达又费电& i4 c' O) K! K5 U  J$ s
{1 ^) D8 k* o( v
    class Program
5 z1 C) c: X' U# Z5 K# A    {
2 f0 R8 [8 z7 N; j6 r        static void Main(string[] args)5 d. k; v+ p- B7 K
        {
( Z6 k' M) P5 K, T- Z, a0 e5 m! O1 I) A# @6 Z            int m, n;
' k* P$ T+ v9 x5 R6 O/ |$ B% S4 \            Console.WriteLine("请输入数组长度");
- ?$ B4 @& C. q6 A            m = int.Parse(Console.ReadLine());//m为数组的大小) k7 j0 P, V  }9 A% d2 l, _
            Console.WriteLine("请输入要截取数字的大小");
  b% @6 |: H5 X5 a            n = int.Parse(Console.ReadLine());3 E' L  |: \' @
            int [] numw=new int
8 i% D( s. g- Q$ t% g+ p. Z
/ [/ U" l. J& f% U* M&shy;&shy;&shy;;
6 q/ ]& H6 v" _: e7 T4 `9 m# p            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数, W! C3 t9 M) `% S& k% O) q
            {# }0 Y! i: n/ Y6 A) X6 V8 G
                numw[j - 1] = j;
& _* M. B* B% u            }
1 x  R& d% N# q+ m, K' L( F( a* U            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
% @+ O8 S7 S3 T3 c            while (d != m - 1)! Y& G3 x) q# d
            {
( L$ d( V" F4 g  ~# }                if (i == m && d != m - 1)
# O2 K# X1 j) h8 I" Q# m# E                {( x) @2 T! O1 M, t  f8 W! i  @
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
/ x" x; G  M  M" n, d; ~                    continue;( c% V& {. m1 N+ U9 S) k1 z
                }3 V5 I( |8 R1 ^7 I, A
                else
% ~" P7 P; J" c/ A" [                {
% B5 v, P$ I; A  o. V                    if (numw[i] != 0)0 Q0 o5 c5 i3 s9 R
                    {
  Z3 T1 y6 Y5 ~9 N, l7 ?1 F                        i++;/ |) U4 s( N/ A3 s) P5 L. u* N$ a
                        k++;$ P7 [- H" a% J! w0 R+ ?1 U' f. Z) r) u
                        if (k == n)
% X$ ?- e0 o3 B6 x9 i' W7 Y: [' i                        {8 H/ o+ q4 f  o6 c4 W
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了. ^% g( k0 {2 a' V) F' S  Y* E
                            k = 0;
' {  J' y9 A5 K. m2 q              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
5 @" e+ b3 j* u& N( R$ H                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
6 b) d2 n6 p& E" S2 t                        }( `3 I+ M6 {- U- I
                        else//输出暂时还没有改变数组元素的值$ x$ p/ c$ v1 z( r. O0 |' x" S( ?
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);% o5 O  K) @. ?
                    }
3 K- W7 y% l' F0 F                    else: S5 O5 w) M2 `1 d8 x
                        i++;//数组元素为0,直接跳过,不计数。。。7 s; z3 D8 I6 M2 ]5 I7 X' F  o$ m
                }
* P1 E' c3 e# u/ Y* E ; ~5 \: E" D; {2 P% ?* n
0 u6 _0 X8 q, g( T7 G5 i1 {+ C
            }//结束while循环; {5 m* [, U' ~4 U7 E8 T: R, n
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦6 r8 N2 ^% |8 O7 ~
           ! T( M3 I! b* Z
                if (numw[i] != 0)
5 |3 R+ R' o/ g0 _# M" n                    Console.WriteLine(numw[i]);& L$ U- R6 E3 L0 B8 z! d  Y
           
" Q3 L/ R. M/ C- C            Console.ReadLine();9 H/ ?( \: w- u( C/ h
        }8 r1 e+ s4 b6 }9 p
    }4 b$ I% Z. c; F, |" O
}/ v% I3 @) D* F) e$ f( _2 G- D. a/ Y
小甲鱼最新课程 -> 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-1-5 16:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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