鱼C论坛

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

猴子问题

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

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

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

x
大家好!
- X9 b2 J( ~4 ~: b这几天我在忙着编一个问题,我用了一种方法编出来!
9 F+ L2 u  y& E但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!4 n( y9 V2 M1 r% M
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
/ y) H6 D3 B4 d; B( j
1 a+ Z% ^# l4 S1 w: f3 Q
7 C4 I7 o7 J! G' o$ w
                            题目
4 \" E' i& Q4 u) j( R山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
6 N' T4 L3 \3 t4 K4 X第一种方法:利用循环链表
  ?, w/ N9 L7 }% [  W. w#include<stdio.h>
4 W% J4 N% j5 l3 w8 E7 `#include<malloc.h>
$ i: S9 n: {/ Q; ^: W0 q# I* |( Q#define M 8            //共有8只猴子
0 V/ u" L$ @% L; t#define N 3            //数到3只时退出第三只
& [0 a' N0 Q( ^6 j& x! itypedef struct monkey
: r2 P0 _0 w1 O0 S' b5 L* {- \* ]1 Y7 d{int number;! n2 g7 _2 P3 q) n4 ~
int flag;
+ u( V+ [" H: N$ c) d* V) b; v$ ~8 xstruct monkey* next;
2 T& F. Y! [6 I) T* Q% O}MONKEY;5 F+ a* o- f2 n; g6 i. N! [
main()! w# @5 X  g3 R2 t6 i8 m
{ MONKEY *head=NULL,*p,*s;7 |, \' c. P( t' O6 B0 x( J! \
  int i,sum=0,count=0;
7 i# W# @. L; ?$ z4 l  clrscr();              //清屏  L8 u* H, j; G0 x! E
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
0 @9 z) y0 ?# e+ B1 ?5 J  p->number=1;p->flag=1;
6 [) E/ T1 L6 k) _% s: F& Q  p->next=head;2 h  @6 H, H! u) `0 F4 l9 E3 G0 d
  head=p;  y9 |* V; \2 L9 ~0 q9 [: R
  for(i=2;i<=M;i++)9 n+ V  q& ~* ]6 f
    { s=(MONKEY *)malloc(sizeof(MONKEY));* T/ \/ e+ h# \7 N1 F
     s->number=i;s->flag=1;9 C" c2 K  R+ u4 w' n! A
     s->next=head;
% ~, q" E8 f* r  |/ O; ?6 U     p->next=s;p=p->next;+ w& T9 d& o% o9 y
    }
: M7 O2 Y$ G: \) B    p=head;& n& U, i0 T7 Z) h
   for(;;)" M0 e$ ?* U, R3 O/ d# k7 A
    {if(p->flag==1)
, w5 R$ j- k; l! g) v% G) K1 t       count++;
5 q$ ?0 s& M0 H8 c! }) g     if(count==N), S2 w. B7 F# c( ~  m5 }
        {p->flag=0;
1 l- }. {  i3 x0 O$ ]5 Y         count=0;
6 p$ L( b+ j% f         sum++;}
: x  ?/ P; h$ T3 B; C     if(sum==M-1)
9 ]) q8 q* n5 s4 X0 g1 Y/ C! c. L( m        break;
# q5 A0 _$ k; {3 z( s7 K     p=p->next;
& {- v# S6 ~1 {. K    }$ P. J' ]5 m! ~% z
    p=
1 G. G; f1 e. W" Q/ V    head;
! k# ?: H) U8 e" G" i( a7 b4 l0 F4 Y7 Y    for(i=1;i<=M;i++); {6 e8 M+ p/ Q
    { if(p->flag==1)3 a% ]) x8 _3 ?9 @/ z0 ^5 O/ o7 L# A8 v
        printf("\t%d",p->number);6 x, r: ~1 F( b. g2 d
      p=p->next;2 N( L5 z) C7 R: J5 c0 k
    }& \& w7 Z5 m; R/ I- V
$ b+ t# j& J* Q

) P( y, Q# [" ^! ?9 N
/ g7 H% H2 U: ?4 N! ^* S3 _}
* Y. q2 }& v# T
第二种方法:数组
$ k& n- R5 `8 c5 a+ t/ ~#include<stdio.h>
  }1 [: `* r: J9 ]  K#define M 84 p+ ^# L( f0 S' C; {3 k! v
struct monkey
9 V3 N' R3 |4 i) j{int number;# [7 o& I# k, q( u: [
int nextp;
4 R( ?" a* Z/ U: t" a}link[M+1];- M3 A# w# F, c- _) G+ B/ H6 p

1 q: W: g8 v5 i, i" h2 Jvoid main()4 p! c; C. A9 N
{int i,count,h;7 H, b( Q; G# |1 x6 d, l
for(i=1;i<=M;i++)
: M  K& u, @$ j* _& y{  if(i==M)
  |5 K* q3 B) l. H. u( k   link[i].nextp=1;, Z2 O8 }* T9 p1 L
   else
- v$ k& q, H6 N# R: [' ?' N   link[i].nextp=i+1;! m5 n) j+ \# V2 b6 q+ Q# c
  link[i].number=i;
! h7 d4 H; c8 }}4 M5 e6 ?1 M1 X* f* o( S
printf("\n");4 |6 c2 ~( t* q! k5 r3 \* ~4 L" F
count=0;' k7 t$ v( f* Q# o9 n
h=M;# E) p" L% j- u
printf("依次退出的猴子: \n");. c& |, w% ]6 ~9 G
while(count<M-1). T6 Y. C- |6 q" O4 \
{i=0;; t5 K3 z+ z+ h
while(i!=3)) a6 m6 @, c# ~4 b: {
{ h=link[h].nextp;
5 r0 \6 W" j5 d# i, L5 w: A   if(link[h].number)
5 B* G# j3 q" C! P     i++;}) y, X  W, m2 v# y- W( s
- Y" d* L+ `4 ^' u+ [1 K9 ^
printf("%4d",link[h].number);8 d0 p" u, n: v3 ]
link[h].number=0;' d& w' U: i% |- W" v
count++;
5 u4 M$ S1 R1 E$ m3 v}' a/ w9 S9 R+ ~& I; u

* G1 f0 z+ V; u5 vprintf("\n大王是:");* m9 G. t0 R( ~" s$ A) ?( |
  for(i=1;i<=M;i++)
' i% f. x8 p% j, ?5 ~+ I  if(link[i].number)
7 x8 {2 h! p' u4 {" h4 I" X    printf("%3d\n",link[i].number);
7 B  ]2 o( B* h: ?- [  l4 h/ k! {: q4 N3 [
9 I2 t9 J' U% {& E2 ^3 ^) n
}

/ z$ Z3 W4 w$ P( G: G* |, y: \& F. L第三种是普通方法for循环
: M* X1 i9 G3 u% I) i/ v
#include<stdio.h>
$ N) l1 y  A, i6 U4 X  z- u9 Bvoid main(): A& P* a! U8 r1 Y( j7 `
{ int i,k,m,n,num[50],q,*p;
/ f7 D0 V: r' G- n9 n  j: c    clrscr();# k+ ?% }7 X$ E7 v
   printf("input number of person: n=");
& F: T: r& w6 i0 v    scanf("%d",&n);" J, m' ]$ n- s
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
$ B2 I' p: C1 J( q9 z    scanf("%d",&q);
. G: W/ P$ `+ G6 H$ ]   p=num;3 n+ c* [! ~7 K4 L$ s, n
  for(i=0;i<n;i++)
1 D7 J) g0 F6 o, L9 h4 }; S    *(p+i)=i+1;. ?! n6 z# p* x7 K& z6 ]
   i=0;
5 F6 O& x! u* v: @; r, [; y/ _   k=0;" v+ v$ j7 R+ `+ H) x1 m1 o
   m=0;% k, X6 _. [; f1 S6 b; t5 J
  while(m<n-1)% O  d( X3 `& M; o! L, p$ @3 E. x
   {if(*(p+i)!=0) k++;
. N& D; s: s- R2 o9 Z1 P     if(k==q)6 Q2 b5 }9 r3 B3 X5 F- W7 d6 |
      { *(p+i)=0;
1 c+ ~% a2 i1 s+ c1 M        k=0;
2 ~6 u; E5 W4 ~- ^- X; m  j+ ~, S        m++;/ j+ t* |" M1 `6 O$ V* `2 L/ [$ g
      }
% z6 j/ o1 q" N. P    i++;2 m- w  L4 H/ X
    if(i==n)i=0;
9 x8 M. Y! n5 o( h   }8 U: d+ _  Y: R
  while(*p==0)p++;
6 k8 f; t2 }1 w* z* }- F    printf("The last one is NO:%d\n",*p);
; Y2 j9 G% B8 F3 s) P     getch();' C7 G1 T$ l/ d- k# f  N( Z
9 Y4 i/ E: k  D  X+ F
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
3 F# w2 ~" l# W" P  l6 L  r8 Unamespace 又费马达又费电
& f8 w2 q! z8 H4 |* H: i{
$ a; T( ]2 i  A. p. R    class Program. S4 d% G# G; t1 B3 G
    {
. O! D' ~, E! N        static void Main(string[] args)
: J8 H8 E6 z9 X        {
( a1 J6 w8 W3 u) y5 |            int m, n;. W7 {7 Z8 i- t
            Console.WriteLine("请输入数组长度");+ U+ u# z8 V% U1 ]7 F# ^; @
            m = int.Parse(Console.ReadLine());//m为数组的大小
* ~" y, x( s; [7 _5 a( \: l* X5 @            Console.WriteLine("请输入要截取数字的大小");6 x; n+ S  F2 ~. o% f8 {4 `; s
            n = int.Parse(Console.ReadLine());: |- y' S$ k' T. p' r
            int [] numw=new int: v. ?; s* b! z, }, o" n
5 m/ H  v' T+ b; d9 {
&shy;&shy;&shy;;
8 U+ d/ `7 ~/ @. @  Z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
: b, o# H( @/ D7 w9 }* Z' b            {+ M' P  v$ Q6 R6 Q! H9 T9 M
                numw[j - 1] = j;
- }7 Z1 k# q! J8 F            }
$ I, V/ T1 ~" G- `1 P            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
3 D) k1 i. }# `5 R( G1 J# ~- o) G            while (d != m - 1), x, B5 M# @* a3 Z
            {
' f& _5 G8 e/ [7 e; P) ?                if (i == m && d != m - 1)( J& T3 z( }$ g- x6 I( W1 a! C+ _, n* y
                {
7 U6 t/ e9 i# W2 S$ `2 q) D                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
% A+ Y8 B8 h- a                    continue;
- J8 o+ J. t/ W: _' `                }' S5 O. |7 k# B4 n
                else1 J9 Z! N; E3 v2 N0 _2 ]1 M. _2 ]
                {# T- `6 v5 s- _# p& X/ e
                    if (numw[i] != 0)/ B5 o. A4 |% I1 x+ n5 t" d
                    {, `8 j  g( {; {- O' C: U7 J
                        i++;  K/ T& U+ [$ }% S
                        k++;
" O# z# C; m: h) _9 Q7 ]* o1 g, a                        if (k == n)% V8 M. P# s7 @7 u, M, y9 @  J
                        {( |* L* U$ ^) b% `$ p& p
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
3 a5 z2 N2 C* ~                            k = 0;
- E. t: Q9 F2 K! {- r) I              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1& ^- V. @% o! B, \. K
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
1 a5 c4 C: K& J- @& y$ J" N                        }: b) W* }6 j, m  q1 S
                        else//输出暂时还没有改变数组元素的值4 P, L: \0 b  s8 F* L3 b. W
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
% [; w8 {; ?9 ^' Y; D                    }6 u5 l& W( z' f: n. U" y, q7 ?! H
                    else9 R+ B8 v0 J6 r
                        i++;//数组元素为0,直接跳过,不计数。。。( x, @7 s+ c# h- X! Y( i2 T8 L
                }* c0 _( ~& n8 C7 G! Q1 j

& U9 \& t$ N$ L% W1 w+ ?  i; i0 ]! b! m- d, x/ ~
            }//结束while循环
. ]4 O) b" @! z& H  m9 n/ x            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
" C" }# K7 m) N# j( r           
, ^3 M9 C% p9 z                if (numw[i] != 0)
  [' n6 M$ p& u5 A                    Console.WriteLine(numw[i]);. e6 ^5 H- t, S
           - j5 E: ?' o' ^2 G) D2 E" o9 V# @
            Console.ReadLine();) [# n4 k. a- Q" w) r: x- l4 F; x/ E
        }8 G! R$ i  M  x5 v- O6 j
    }
9 \1 |' S8 N1 F. P$ ~}
4 T' u) m1 B' p/ C* y! i9 U/ p
小甲鱼最新课程 -> 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-7 21:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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