鱼C论坛

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

猴子问题

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

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

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

x
大家好!; i0 R, U, D8 s/ V
这几天我在忙着编一个问题,我用了一种方法编出来!4 O/ n( B' H: y2 K
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
  x6 v; `. b; L注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 " m' r' j% J9 m% Y
+ C3 g: [* }3 N& J: v

% r( x# r" @* Y7 e; Z+ `* Z. L
                            题目
8 y' ]' ]- ?; d$ f山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。- O+ X( u. F' b3 u) L9 l
第一种方法:利用循环链表
- c; G3 ^# t3 i. a3 i; ^#include<stdio.h>
& }7 ^$ a, Z2 V( ^6 O- e#include<malloc.h>
( c: u# e, Z/ J' C  j#define M 8            //共有8只猴子
8 L7 U* B: h: Z/ B% r) [#define N 3            //数到3只时退出第三只
3 v- t/ S4 T/ j3 Dtypedef struct monkey
  v/ y4 Y$ Q" X' z9 y; Y0 v{int number;$ `! f- }! ~+ v' h# P4 Z  ^" M
int flag;
- {1 ~* w/ [* ^' ^/ F6 H2 o' o2 Fstruct monkey* next;4 ^2 D/ g! M( u
}MONKEY;
& ^; H- F# I9 W% B- Fmain()
: L0 P4 S5 y5 D# K/ M# c# P{ MONKEY *head=NULL,*p,*s;0 A7 Q; o" c5 W# R3 E; R
  int i,sum=0,count=0;
/ i- M+ O& h* Z) a% g+ d, F) P5 c  clrscr();              //清屏5 v& J( \0 e6 H5 D' p) ]
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存$ L5 T0 v" b+ v! B9 P- ~. b
  p->number=1;p->flag=1;
: i8 g# I$ B! g% K/ y  p->next=head;! b) U0 o& E8 y
  head=p;
; T  l. o; q3 F) C( @  for(i=2;i<=M;i++)
( x, a- v2 f( v9 ^/ M, g    { s=(MONKEY *)malloc(sizeof(MONKEY));* o$ O' U# @$ h& f, g9 i7 X! N
     s->number=i;s->flag=1;8 @9 v& M3 S3 H! P" k3 o9 P
     s->next=head;
7 I5 t4 B- O  S2 z; a6 b& D     p->next=s;p=p->next;
5 h0 l' w8 ~/ v9 F0 A    }& [% x& z% {& M& B
    p=head;' X" L* k6 l; Q$ ~" D
   for(;;)8 U7 B, Z6 }: L# A. F
    {if(p->flag==1)/ \, ~7 |8 s# A% q, a2 ?# I) G: w
       count++;
' z' W" d* \1 f     if(count==N)! L1 C5 H# f/ j
        {p->flag=0;
$ G# |& p2 H1 W  J         count=0;
: y$ E8 a& ?3 G# T  v9 g         sum++;}" }/ b, @; _4 p8 K* |
     if(sum==M-1); i6 o) |7 q+ k# f
        break;0 f; I5 E+ O* I: r/ H3 j
     p=p->next;
% d5 l$ _6 q' ^    }; g2 U* P$ T# b* Q
    p=# Q+ C. [7 W# g" z
    head;9 j& u, G9 Z2 i9 x. n' F0 x
    for(i=1;i<=M;i++)2 Q  S, h  f3 C. s
    { if(p->flag==1)
7 @$ j& Y) S) k        printf("\t%d",p->number);( }3 o5 U" J2 b. N
      p=p->next;! m1 s5 \7 u- t: ~% m& z6 z6 p" ^
    }
6 m; B8 Z' c4 Z# Y% a% l  Q( `/ H) Q6 ]7 ~1 [/ j
! ?; O) x6 o6 b4 {! M8 b; U" r

  x2 b/ {+ `: a}

5 ]- P+ [0 @  `5 R1 V$ L7 o3 q第二种方法:数组# a; K& m7 e" |% q# T' G
#include<stdio.h># v0 i  N4 a$ d2 R- }% i+ l
#define M 8
6 |0 L; g6 I3 h: I7 D5 j4 wstruct monkey
7 e( K  @" ^  r- Z3 E1 u{int number;" D. g5 }, ~# z( G
int nextp;* m0 b# C& [  t  q$ |' C+ \& j
}link[M+1];
1 [( s' J# `$ j8 C. D# Z; J
' d" \. C3 I# `void main()) H7 Z6 ?+ S% ?" I
{int i,count,h;
2 s/ R8 @" f2 N: Mfor(i=1;i<=M;i++)7 X4 X% y, K' h7 w: I
{  if(i==M), Z- v8 j* Y# ?1 m
   link[i].nextp=1;
- r& e4 L2 F: k   else
  |2 ^; J1 Z* Q9 }+ r   link[i].nextp=i+1;% J2 S, O8 {3 w. V# Y
  link[i].number=i;
3 N+ h. E  z3 T: y5 V+ v% W# u}, z! i+ L$ i7 L5 S4 ~
printf("\n");$ t; j7 \7 ^% t
count=0;
0 a: M- F  s7 l  N6 M' ph=M;" u5 d; X" i5 M) r& M
printf("依次退出的猴子: \n");
5 f. u& C2 b% Y. H7 [1 Qwhile(count<M-1)
1 F' @) [& r. S$ ~8 g, Q! C; L8 N  F{i=0;8 W& m% e# Z$ e, w) Q1 m
while(i!=3)
! ~) p% D- T$ a2 Z+ C. ^+ r4 v{ h=link[h].nextp;4 ^) T4 ~3 t% h: h# x0 @3 a
   if(link[h].number)# H2 b+ ]& I# Z# G/ k% `
     i++;}1 D! S0 o, k4 h- H

4 c. o: j2 }1 ^+ U  ?9 _. V# vprintf("%4d",link[h].number);% v9 S( j' F- g. r5 K% d2 p
link[h].number=0;
. w5 @: t; S. {; P' K  D3 N! lcount++;, T# _3 A/ z1 ~2 y& ^: Y- N
}1 }9 |# w6 S1 s& |. q' Q4 M

8 v# j+ a& d$ ]2 U& ?! t# kprintf("\n大王是:");) u8 ^- i$ H: ~; W, o# Q
  for(i=1;i<=M;i++)
1 k/ Q' }) h6 U+ n  if(link[i].number)
5 Y6 `0 }5 L/ _- c& K8 |# p    printf("%3d\n",link[i].number);) T* p+ O+ m: d" [/ S

5 a, m: h5 d. I* w% l: K8 S5 k* [" z
}
+ o. E3 ]3 A8 b  ]
第三种是普通方法for循环
$ d3 h, A5 Q1 G" v8 Y3 B
#include<stdio.h>  D  o" _& ?9 }) B; i4 x( l
void main()
1 H. N3 R8 X$ R7 Y% h! ]{ int i,k,m,n,num[50],q,*p;4 M' k" H5 d# e6 r4 R6 n
    clrscr();
) B; t: Z6 y: f; U   printf("input number of person: n=");8 l$ ?& Y$ J3 a# N' S
    scanf("%d",&n);$ s  W; U  d1 k) @' r
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
- M0 M/ d8 |) ^/ Y    scanf("%d",&q);. u& H$ `$ u9 _" s8 t3 a9 V( H! z
   p=num;
$ _* S: R9 Y2 v4 O7 ]: |4 g  for(i=0;i<n;i++)
5 Z, @" c6 Z1 _* k2 q    *(p+i)=i+1;
, J) x2 V) t/ ^+ G1 m- `   i=0;; I4 q( w: n# b: n7 U' S
   k=0;4 z; K- w- [# r0 _/ r& z) J
   m=0;1 m; T# E0 H  R! j: M7 l% k
  while(m<n-1)! F$ H+ z7 [) ^" ^( t( |9 H
   {if(*(p+i)!=0) k++;# Z- t& ]# G( p  O) \3 h
     if(k==q)/ Y  N, k; ~- R4 f. Q+ t/ O' `
      { *(p+i)=0;
3 X0 }9 t' V( d( N        k=0;
( h, {  E+ ^$ a        m++;$ p; M0 f9 P2 `5 X2 q4 W
      }' T/ ~4 a% F7 U3 j2 i
    i++;
1 h; t2 C8 V7 F! k) [    if(i==n)i=0;) x  U/ E0 f* Q. R8 B1 V9 _
   }
0 g, N6 _2 T, k  while(*p==0)p++;' M: P5 K7 j- ]6 C% Q+ U5 J
    printf("The last one is NO:%d\n",*p);
/ X  w( L' m5 g# o     getch();! B  b' _! k: r
) m$ d$ ]6 d' ?5 n9 K
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
* ?  C. ^% n1 u4 V: b9 s: J, [' Ynamespace 又费马达又费电
7 [$ c5 t4 r7 ]8 b0 x  z: J{; l" B- d' ?9 q  G+ F
    class Program4 I0 c- U( k9 Z0 j  i3 G
    {' {- w$ s5 z* M4 M! k
        static void Main(string[] args)
, l$ e9 [* W% K1 z3 F' V8 n        {/ T- E- J* e2 M+ d, p1 _& ~
            int m, n;
, g6 {1 w% j/ Y2 ]) }+ u; a& W            Console.WriteLine("请输入数组长度");
! {1 h: \1 M! L/ b  `' E            m = int.Parse(Console.ReadLine());//m为数组的大小7 {, `9 J+ W. `5 R2 h  ~
            Console.WriteLine("请输入要截取数字的大小");0 `7 A2 `$ F4 o( [9 o" B$ G
            n = int.Parse(Console.ReadLine());
" \! u* u: v- |  K* B            int [] numw=new int
+ z  l8 m. x% k% p2 d# L# F7 i1 Y' H! X$ Y. m+ U. J
&shy;&shy;&shy;;
6 L0 R: _% g( H* M            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数# \6 g) [: F5 S- D# v. Q
            {
% C: l" c- W/ f: ?/ Z6 h. c                numw[j - 1] = j;! S. {1 R# T- j& |' X( P2 [* r. D
            }
$ x; M/ t8 W) c& J5 q& K) ?            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!1 a3 n7 \/ R+ B
            while (d != m - 1)
2 \& Q0 s- b4 R            {$ t9 x. ^) ^5 U& [6 Y
                if (i == m && d != m - 1)/ ?9 l% \, C' O$ N
                {/ {" f7 {! s8 A4 b' [: N
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!% ?8 `2 k: F! B3 i7 U
                    continue;0 r7 z2 U! a6 a! |  E' l- M4 U
                }
' @* S' j  J7 f                else* I0 P- @. ^  v6 x$ |
                {# w# q' k) q. x5 }4 Y  l
                    if (numw[i] != 0), E9 }0 _2 ~  y/ H/ p
                    {4 `- ]' `5 f5 ]; D& G
                        i++;
+ Y8 }0 `/ X( x# o' M  O) Z& z                        k++;
  H2 a$ g% E9 [5 O6 }  D$ U# c" q+ b                        if (k == n)
4 x$ I+ L& o" Y% w                        {; _2 m+ x: H, U- \& N0 c
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了6 U/ S: X' O4 E
                            k = 0;
* T( W7 }# f/ R( V              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小15 A% L$ ~$ m$ i8 Z! P3 Q% X
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
# N5 R* c9 i# t  f+ e% B                        }  L* N# r5 r; ?. y
                        else//输出暂时还没有改变数组元素的值+ y8 B7 F3 L/ D2 G" ^3 W
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* A3 \: y5 O. g- C+ c- w. F8 z
                    }
9 O) y2 z5 }. f+ O8 D" Z                    else' p+ a$ b* o: ]# d1 W" e* U8 G2 Q
                        i++;//数组元素为0,直接跳过,不计数。。。
1 K2 i9 l. O% a! V4 j8 K4 _                }+ H' `$ W+ \7 Z4 M' C: g- s
1 V$ Y9 u) X8 O
0 d1 h& m: @% D0 a0 ]; {
            }//结束while循环
! @/ ]( c) q- G; X* M( P. K* }            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
. ^8 k4 n$ \$ A0 O7 d8 ^3 P           
2 V2 q; i& f/ c* S0 T                if (numw[i] != 0)
  {, y" f3 F8 U/ X: X% ?2 g                    Console.WriteLine(numw[i]);7 r0 q6 C7 J: D+ o, @4 E
           
( a) b2 {/ h) C7 r            Console.ReadLine();
% w5 i4 {/ @$ h# t0 M) c0 U        }
. J- d3 V  S! [6 n- W$ h* M, B3 n$ ^    }
+ Z" c8 `* R/ d1 M, t}
! W. r* b5 r/ z" V
小甲鱼最新课程 -> 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-6-18 02:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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