鱼C论坛

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

猴子问题

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

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

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

x
大家好!! `8 r. W) G  v2 l( P0 M. s. R( H
这几天我在忙着编一个问题,我用了一种方法编出来!
0 T/ }4 |+ p/ _' N4 z, Z2 H5 I但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!' e2 V1 D# n. Q* J/ u4 _; J, o( p
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 O" v4 C# @* J4 [  c4 {4 @- E/ \, c; T6 l. }3 d8 o

: r5 u/ V4 e0 [: A+ v/ l
                            题目
- `) a3 r' k% C/ D" w$ }! f/ L) r山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。2 K7 o  t1 a' d; k2 O
第一种方法:利用循环链表
% H/ v3 n8 c" j5 w8 R* h, l2 Y#include<stdio.h>, \* I1 C& d" o3 H1 i" e6 z8 M
#include<malloc.h>( a( t2 N5 |- n  ]. V
#define M 8            //共有8只猴子* e8 v' m6 d% F: @
#define N 3            //数到3只时退出第三只6 E% s. J- b0 q5 D  A  o- N  {; w
typedef struct monkey
' l* l  D% H! e! Y/ |{int number;
( _2 H; ~, {$ _- H! z5 z0 u" _int flag;0 t$ S1 p8 @$ t8 @* }% g" R
struct monkey* next;
/ Y$ K' Z; @8 L$ W! Z}MONKEY;
; V6 l# T% ^1 g  W% emain()% s& y: X8 V* r3 c0 V6 f$ k+ ]/ K
{ MONKEY *head=NULL,*p,*s;
3 R' a/ T+ O  o6 h6 B" g, v  int i,sum=0,count=0;
! R; `8 V) \: H# U  clrscr();              //清屏* n' w" @5 _. S5 G2 q; |
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
: z! K% j+ c  x+ g; R9 B  p->number=1;p->flag=1;
( @: I, q* \' Y- s# y* B  p->next=head;
2 p( C- R# T, _+ b" @! q4 z$ H  head=p;
2 K7 X! S/ S! n: l  for(i=2;i<=M;i++)
7 ?- _1 K6 M5 C' L+ c8 D6 E    { s=(MONKEY *)malloc(sizeof(MONKEY));, p" D( h6 _% c* q9 r
     s->number=i;s->flag=1;
1 B1 h" c8 {- c/ F     s->next=head;
, D( ?( ^2 M% T( d0 m) ~& x5 Y     p->next=s;p=p->next;
. v7 k: x( S( ^8 _. d! A. A4 R    }
3 S# X) b7 X7 k3 r' s6 H  b    p=head;
3 t) b4 z6 U% p   for(;;)6 m8 F5 p. `7 {+ E4 t1 ?
    {if(p->flag==1)( N" h( ]# Q! A7 @; {
       count++;
# w# r$ |6 j5 m, o1 b) N     if(count==N)- l5 o: s+ x& J: k+ ?' L/ w
        {p->flag=0;( r4 L. U. C' v
         count=0;8 h" J8 n- q: R! c. X& i+ |
         sum++;}  d) v' X  \' I5 Y: ~
     if(sum==M-1)
2 ]- E1 g0 D0 T) u6 c8 Z4 L        break;
& w2 n2 N( c0 ?7 b4 m/ }* [! Y5 v5 t     p=p->next;) @" p  `/ }# s, Y! X: H0 U: Y
    }
: U; k; y4 \% ~+ X/ E  c3 @    p=
$ j- G) Q# Z0 X$ y    head;' m- N# H; G" q/ [
    for(i=1;i<=M;i++)
8 O# |1 x* T( ^8 @2 b    { if(p->flag==1)! W# b( ~0 t8 W6 I; e& j
        printf("\t%d",p->number);
" w1 n# N% ~5 x* t+ O      p=p->next;: B- U0 x4 c" a/ U7 _& e$ _. y
    }% R" [- c! t# [0 z8 F( e1 a9 E8 P
+ L1 ?* ~: y# a

3 V! L+ d+ d; K9 \2 o( [/ ]# A( [. c' E8 N( l
}
: i' ?* F3 M! s8 l$ I( d  R
第二种方法:数组
6 m. C& h: l4 X- l9 c6 i& o#include<stdio.h>
# @. n& w( W$ ^: @  }0 G. e8 ]#define M 8
  l: i+ t: ]& {struct monkey) D! W8 A3 `+ V6 U% Q" ?
{int number;* k# {/ M5 Q( I  {$ @9 W
int nextp;% z4 t! T. f( Y: [* S) `7 f
}link[M+1];4 F+ z+ W0 o% G: t2 }. |
! o' k1 b, b, d' C' `% I- k: v
void main()
4 c% {+ k+ G4 `+ U{int i,count,h;5 T  ?9 o7 A0 B5 a; Z( p3 W
for(i=1;i<=M;i++)
5 W- x1 z- s0 B4 b: G3 n, @{  if(i==M)! A; g& Q  ~0 A, P" ^3 @  r
   link[i].nextp=1;
( y4 i, V# l1 e5 H  q   else/ C9 C( c/ s5 N5 l( ?
   link[i].nextp=i+1;+ k* l3 X0 _* P& H
  link[i].number=i;
" X7 f" N$ ^+ d# S. _% v! |}
! o  d$ F2 z' ^( X: tprintf("\n");
6 N% I+ B; C( v  V4 acount=0;
& l/ H4 ~# ]" y9 t3 o7 Rh=M;
) Z. c- L  v5 `$ O1 l3 rprintf("依次退出的猴子: \n");
$ o; p& I' z7 s! L9 b' }+ q* Hwhile(count<M-1)
/ C& P* y2 l0 U3 u{i=0;
' ~8 }6 U4 {$ g" Y  X, @8 Zwhile(i!=3)
. Z# P' P! `; q* u, j# P* r{ h=link[h].nextp;
2 Z2 U% Q, ^5 d' n/ f  F   if(link[h].number)/ H6 l7 b2 W9 T0 Z! N
     i++;}
% ~  Y& g/ f! k3 H# S0 d$ t8 [7 q# f) h8 _, c
printf("%4d",link[h].number);
6 E2 T" W7 c. p1 u" k- Olink[h].number=0;  b2 P" _8 s0 B( Y
count++;
8 T0 }; K% i3 C6 I0 o  q, p}
+ `" _% \9 g: o. s7 [" d" M4 t& m. P% J4 x7 R2 ]6 t! K2 N* j
printf("\n大王是:");
! ^/ R) k: U0 P: T' [  for(i=1;i<=M;i++)
/ d3 Q, {& v4 p1 e: z  D( V! `  if(link[i].number)' M" p$ O$ \2 F, h  W( e
    printf("%3d\n",link[i].number);
% t' ^9 v# T2 k7 ^' f$ B( I
  B/ J$ J7 L! h3 s3 W4 Q9 }+ O4 h3 U: A
}

& K) Z' b" S3 \9 p第三种是普通方法for循环
* H, i3 Q3 G9 u
#include<stdio.h>$ Y; m+ f- r) [2 L7 C$ I3 `
void main()- z& p7 ]8 _; j
{ int i,k,m,n,num[50],q,*p;
/ A- r% X2 V! q' z8 \8 j+ ^    clrscr();
& O- o* \$ u  v6 b   printf("input number of person: n=");
; f4 ], k3 Y3 z    scanf("%d",&n);! h, |! C$ l, u" w# ]
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
  f, t" g9 G% W" [. X    scanf("%d",&q);
6 q; y. J7 O. G$ s# I  y   p=num;
! m  A7 B9 m  p. o' i" x  for(i=0;i<n;i++)
# {, K+ ^8 A" _: a/ t. }/ T: v    *(p+i)=i+1;( w( j2 U1 |0 A: f
   i=0;- M1 J  f! \1 L0 @9 y
   k=0;: k& Z3 A+ N( [% Q& A, d
   m=0;0 N) Z( l  F1 G2 T5 s- _% d
  while(m<n-1)# ?6 d3 A5 |) j. f. m9 O: |
   {if(*(p+i)!=0) k++;5 s( f7 V6 j2 ~3 @/ J
     if(k==q)
* o3 ?6 ?2 b% h      { *(p+i)=0;; y& h: ^, n0 D8 |
        k=0;. `; ]; H" \9 i: [' Y
        m++;$ q! X# K# x& w1 x1 U
      }; W6 O5 b* ?( l$ R3 q+ S
    i++;0 ^$ z$ u0 D. C) `! {
    if(i==n)i=0;( J9 p2 s) G# N* `
   }
9 `! M8 d' m% a0 W2 O  {2 z7 d& J  while(*p==0)p++;- c: a4 [) H+ k% }  f+ _$ N% N$ d
    printf("The last one is NO:%d\n",*p);( d  o# S3 S" H( S, U' E6 I
     getch();
) i2 @+ j8 x- w! X+ V& U- j" R3 C6 Q# A* S1 n4 z$ g5 m
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
5 O: [! I# A/ t' Snamespace 又费马达又费电5 ^6 `' O, P" V- u) @
{6 ]/ S$ ]6 M& _+ Q
    class Program
" `6 k) S* e& m% a2 ^& |    {5 x" X( a- g! c* G
        static void Main(string[] args)
7 G6 M+ `# ^& z- [* c: H1 ]+ t        {
6 L) t" `2 A+ P% s) E9 m( `0 B            int m, n;: r: j2 V/ w8 \$ v0 M9 X) C  V5 O. A: y- z
            Console.WriteLine("请输入数组长度");
$ _/ P0 p1 d. A- P/ H1 y            m = int.Parse(Console.ReadLine());//m为数组的大小! `% m0 R: H: W; L8 ~! I3 e
            Console.WriteLine("请输入要截取数字的大小");+ |2 c+ I) [" I7 W& \6 W' }
            n = int.Parse(Console.ReadLine());2 n" q( \6 R  ]) g  M* V
            int [] numw=new int
- r4 r0 k5 X; ]) l
) n" N6 ~) u" N) e- E' _( A- n- Q&shy;&shy;&shy;;4 s* c) Y& u7 _% E- W" T
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数& X- A+ [- s1 Z9 f- V' K
            {
7 {# r' k6 _; H8 D                numw[j - 1] = j;+ V& g) \' y+ s" Y: k5 x' U& ~
            }
  ~/ i+ s: c% s- _+ G, k) v7 j: ]            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
) g  Z6 {) ?: d- a/ w  o            while (d != m - 1)
8 {- y7 m' W) k0 G            {
& m- M9 z) ~% Y$ @9 r6 _                if (i == m && d != m - 1)
* \3 E$ x; I9 A                {
" @4 g7 W1 h9 C( r" W                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
  _) Z4 w" Z% g3 A5 J, `( V! n                    continue;
' x4 g. q( t1 Z/ L' u                }
5 [, n) p7 x  ^6 O4 h: `                else$ `9 H& P) k' i- C+ `& V+ _
                {
* v2 I; J& M+ s! t% s0 h. R                    if (numw[i] != 0)
  E% E& S# E4 u8 w                    {9 a6 t  t* ]" K8 s6 ^! x7 {
                        i++;/ S$ f2 e) T  d! e, U
                        k++;) s: M: X( M9 k2 |& q% {6 L
                        if (k == n)6 H* @( V- m# u9 y  H9 t
                        {( }# r$ K+ _& _; w; S8 a* d
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
: ?3 [" `+ i0 R3 w; ~6 ~6 E                            k = 0;2 U& J' t/ J: F4 S7 j7 O- I4 f% \7 J
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
1 M; B% X  a4 {: T! O                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);0 l  m  X2 r7 \  F# e
                        }) m- f' d0 q8 ~. R; x, J4 y8 r
                        else//输出暂时还没有改变数组元素的值
1 c5 S+ s9 w9 M4 x5 A$ ^                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);( e4 K6 O2 n+ D. v6 o
                    }
) X- f$ w  O% J% e% L                    else5 \: Q$ I( F0 ?$ j3 V
                        i++;//数组元素为0,直接跳过,不计数。。。
" i$ j: ^0 Y: h" G( s% g                }
& T5 Z+ C* e' s# U9 ?. C0 _
) {2 r+ b) u6 H5 e1 I8 U0 _& H! K3 B( s0 F( ?& h7 Y2 z
            }//结束while循环, a- f/ a4 m2 H6 D
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
' i/ L, L7 I- `           
% O7 y3 [) N/ ?4 F4 T( ~                if (numw[i] != 0), f  k, g5 u* Q3 w$ t  l& [
                    Console.WriteLine(numw[i]);- m# H2 h2 _/ f! N  V2 @# M. ^
           
4 S/ a4 N7 m9 [4 Y            Console.ReadLine();: b4 g2 ^( x% _$ o
        }) \# G/ v8 V2 }5 W' x; @6 i0 W
    }5 z4 g# a; p( v& L' x
}& q2 i' I' W, W" A% N8 x
小甲鱼最新课程 -> 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-3-31 09:21

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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