鱼C论坛

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

猴子问题

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

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

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

x
大家好!+ D! ?! A6 g  {/ j3 A. D$ e4 J7 n
这几天我在忙着编一个问题,我用了一种方法编出来!
7 l% x; t8 @/ |5 Z但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!2 Z3 B4 F! O. d
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
7 [/ y1 a! ^* e4 {. O( e8 m
1 p2 N! e$ @9 j& J2 q
3 X0 X5 P3 M* \! A0 a' B
                            题目! c9 {8 T; ?! b: b" ]1 k; d9 J" h
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
/ Q- i( i4 U# M; }$ h4 c' R) g- S第一种方法:利用循环链表, E, @/ l& [. Y1 a
#include<stdio.h>
1 I3 {( L: e* j+ _#include<malloc.h>
' H  z2 j' }$ A#define M 8            //共有8只猴子: Y) Q1 z' ]6 |  E% r) D
#define N 3            //数到3只时退出第三只; ^+ i. o4 h* [' \8 @
typedef struct monkey
5 J  K: P2 Z. a+ k{int number;
9 V1 m# X) M; M2 C1 X0 `int flag;
; n6 ]6 d& P( L! \$ r# j$ `struct monkey* next;
: z% c( r) l% N: d5 x+ w- E}MONKEY;0 y8 H' F) \) {' o1 X
main()2 B2 }, x& _6 t0 i" V: i- e+ U
{ MONKEY *head=NULL,*p,*s;6 c& d$ N3 G/ }
  int i,sum=0,count=0;: f6 J3 \* E: n% U" [
  clrscr();              //清屏
: I. h& q- ~3 n  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
  f2 P6 h, L; R& {' F% m  p->number=1;p->flag=1;
' H* V& p5 y! x  p->next=head;: r/ y6 Z6 e' I
  head=p;
7 J8 @( w* {* S; P; t+ g. m* A  for(i=2;i<=M;i++)
7 m: ^( y; v! |4 w2 R: ?9 H    { s=(MONKEY *)malloc(sizeof(MONKEY));9 C0 T! M; l) _7 T3 S; p" I
     s->number=i;s->flag=1;( x& k1 g' L4 R1 ?$ _
     s->next=head;) J  r: d6 R) J! ^# ~
     p->next=s;p=p->next;* Q5 U  T$ _9 k! X  @+ g4 m) x
    }# Q- X; k, N8 n( f/ S
    p=head;" x0 b4 _) d  ?
   for(;;); E# D4 K* v7 @7 t! ^
    {if(p->flag==1)
+ i0 w# h/ _. {* Z8 s       count++;* Y4 H7 u" F5 y7 e) x7 ]
     if(count==N)
5 ]+ q$ C# o3 u" q        {p->flag=0;
! b- u+ x3 B$ ?5 O6 w         count=0;
  J# T. T/ {, d" z/ X8 U         sum++;}) W# j' X. w( f& }* f& q  U0 {
     if(sum==M-1)8 m6 n: n6 p8 v0 ]0 @- R
        break;
" g" V% a& X1 X( Q8 I: a     p=p->next;3 T4 ^4 G, u% V
    }
* n- d% y4 v/ P/ O& ]; e1 e; Q    p=3 ^. v% A# x  O: n1 t5 ]
    head;8 G, a, G& b! Y+ d; _' }8 V
    for(i=1;i<=M;i++)
" c' q& z2 [% M    { if(p->flag==1)
# t- B* t  T+ X, j8 P        printf("\t%d",p->number);
; p) t6 R7 p& M# M      p=p->next;
( u$ s9 p% U8 I. q    }6 t6 }* d0 R0 v5 l9 S2 ~
! |9 d# g) v( k  S( B$ i) |

0 b" }+ n: z: }3 ], ~
& n1 B. A+ ^) J3 s& e; I}
" z& G2 P: h, n! Y  {5 n9 C! p
第二种方法:数组2 ]  ]5 ^/ i, |% n
#include<stdio.h>9 e. e  k2 o# T  D1 N1 ]% u
#define M 8
8 k* h$ X  K8 |. j! _5 H  fstruct monkey8 D* o5 L% ^: L
{int number;
5 P5 R) F) p" [5 t! m) g4 I& q0 y7 z& Eint nextp;( c; ~/ C* x' k% w% c' i& y
}link[M+1];
9 ?2 Y9 \6 s* b9 A# k8 S) l
$ l) a+ Y/ }3 Kvoid main()
  \2 j# w. {: @8 Q: h0 X* B{int i,count,h;. [6 @2 ]* ^7 T' h
for(i=1;i<=M;i++)
$ T, t  I1 v2 J; i* @{  if(i==M)
; M, ^9 A. C% @1 Z$ ^6 ^  Y* |   link[i].nextp=1;9 w. o7 w% p1 Y: J0 l
   else: u5 M. ?$ D* t4 ^- n
   link[i].nextp=i+1;$ U& A7 \4 |2 e& M
  link[i].number=i;
$ I& ^+ |- {4 ?1 m0 s3 J}* S. d/ v0 ^2 W- `5 u6 s
printf("\n");1 M% B! a* |1 |0 R/ \/ h, x7 w
count=0;
0 }! \/ Q1 t6 c( d# a6 M- `: x, W0 f; N& Yh=M;: U- R- ^8 B! L( b+ k) q
printf("依次退出的猴子: \n");
( f+ H6 i+ X/ V0 m- M( Cwhile(count<M-1)/ A0 Q& R4 o) H' v3 I% h
{i=0;
& ]! g8 y3 @1 n1 @; uwhile(i!=3)7 J, R3 D2 Y- @
{ h=link[h].nextp;9 u6 O4 S& h, `: x4 s' C
   if(link[h].number)
: ^4 z- \+ f2 n, h     i++;}
7 W8 m/ |+ ]; q+ [* J7 N! [! n! p) Y, }
" V! ]; H5 z% ?' ?* T! \: v  i- t# h" Rprintf("%4d",link[h].number);
/ f, p! q- @5 e6 Y3 x0 Mlink[h].number=0;
* Q  E$ r; h1 X1 bcount++;  q: f: A3 A4 \; \) h9 g
}
- K* I+ c5 ?0 c, D' {
) W6 b( G$ W8 @$ W  i* C) ^printf("\n大王是:");  u( b+ d5 D" B
  for(i=1;i<=M;i++)4 j# c- N* Z1 t
  if(link[i].number)) _0 m7 K9 K# N+ \6 ~
    printf("%3d\n",link[i].number);" }9 @) ]9 R" _3 [
8 y- L" c0 t8 ]
7 L% F6 }! I3 F  P* `7 G
}
" l/ Q2 E' c, Z" L$ C/ T  S
第三种是普通方法for循环
$ C+ m- e/ s1 ]7 z5 d! M
#include<stdio.h>
3 W! p$ E* ^& A- Z4 Jvoid main()1 C- K6 @& ]. s
{ int i,k,m,n,num[50],q,*p;- F, `1 J' n3 X/ s* K+ o
    clrscr();
' s3 l/ d7 x: h( w2 d2 P   printf("input number of person: n=");+ j7 R3 ]- o3 C( r5 A( N# V
    scanf("%d",&n);+ r4 k/ b$ _% `4 n1 h
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只/ x4 l$ o+ ^& B1 d. F" g1 p7 v
    scanf("%d",&q);" F& Z7 _- L- s! r+ q5 ?: s8 N
   p=num;7 P) o- |1 K$ D( ?( {/ t( x# w
  for(i=0;i<n;i++)
8 V0 w' I* t0 U3 q1 X4 A    *(p+i)=i+1;$ Y' w8 D: G9 q
   i=0;1 O5 n. w+ Z& g5 @& l8 Y
   k=0;2 A. ~9 i; D1 q0 |' \
   m=0;
* u: K7 J, F& K  while(m<n-1)
& H$ u$ d& s: B' r   {if(*(p+i)!=0) k++;, k: J4 l& H6 }6 [: {6 H7 P
     if(k==q)
+ ]  y1 Y3 ^! v2 t* [' n      { *(p+i)=0;
( d7 x6 `6 E) r- V3 u        k=0;% v( F0 ^2 n8 ?' E
        m++;
7 T$ E# k0 v, I+ [      }
) I+ v/ Y8 j0 j( O2 a    i++;
- B$ b4 C; s  d' Y; C7 D! A    if(i==n)i=0;( x2 a* b5 |5 `% u8 z  |+ w4 I
   }& E, V, \8 b, N+ v( U, P4 N
  while(*p==0)p++;
2 |& k; {2 d$ R: H/ V& S    printf("The last one is NO:%d\n",*p);0 l4 K' m/ ?0 \
     getch();2 x+ J3 v( Z  [) e
' h$ b: A6 z. o3 U
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;, _0 P% ]3 W- T3 g" F) m6 c' c6 Y
namespace 又费马达又费电& [' D5 y3 N5 w1 B
{
) v$ a0 K% d' k5 j, G3 f- K    class Program5 n0 a3 p3 |: I. ~: ~# ~" F9 u$ i: Z
    {$ m2 }9 j$ U4 r+ G7 T5 m( s/ r
        static void Main(string[] args)
# r% x/ e) W2 w  |6 Q6 Z        {/ }. k7 {) J6 A+ n  ~5 ?) P
            int m, n;& I! ?+ @- c6 J0 P
            Console.WriteLine("请输入数组长度");
% S8 d( P3 ~9 f) Q3 W, V            m = int.Parse(Console.ReadLine());//m为数组的大小9 b+ m4 C) d8 B% a9 Q9 P" g5 E
            Console.WriteLine("请输入要截取数字的大小");$ d, w8 [( L+ ]( I4 ^' U4 ~
            n = int.Parse(Console.ReadLine());
% m/ \! e9 W' h( P9 v: a$ z            int [] numw=new int* B: ~/ Z; F  j. m& D( f" q
; ^+ q* ~/ o. J# t
&shy;&shy;&shy;;$ U1 Q# {1 I+ }
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数9 H) @: G& v( Z. y) u; M
            {+ R" ~0 I0 a3 x
                numw[j - 1] = j;
4 F5 ?  Y0 j: R" {& O            }
7 x. K/ l+ Y( N" D            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!2 d8 b( W8 m' f! R
            while (d != m - 1)
; c- `, n3 r1 _5 ~& e6 f            {
* L3 R$ p2 L) t9 f                if (i == m && d != m - 1)
& ~" \2 {8 j2 T5 z                {
' g% i0 v% y3 _2 B                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!9 x0 \: o! @" M( r
                    continue;
+ U7 }4 E: P. f                }. F& B  N. V) }
                else
- {: F% r% [$ ?8 J1 R; o  v# M                {
! Q' c  O0 r0 _1 N                    if (numw[i] != 0)/ d3 X* ?: E, G" E1 Z" r
                    {
- y# l0 j( B3 n; J; a                        i++;
' \/ _  C7 `! G0 u; C, r                        k++;
2 @  ~) [9 f& b; _1 X3 o                        if (k == n)
3 B" L2 s5 U% A7 ?; }/ h5 u/ C                        {8 p4 l! \' `& F7 t
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
! i. @6 E  W0 O1 a" [# S3 D# I) r                            k = 0;
# h; y/ N+ L- B! B              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1# n, W3 P" c# P8 w, w1 E
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
; ~. D/ \: M& i$ m                        }
, O9 |" n5 @( e8 Y+ X; ~& I                        else//输出暂时还没有改变数组元素的值- ]# Q2 x1 M' n, E" p
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 P5 r2 ~: u$ V* Z$ [# i' A                    }
2 Q' V4 \$ R2 k* y- H8 d6 v                    else
  i5 ]4 i7 x. n# }( i. q                        i++;//数组元素为0,直接跳过,不计数。。。
0 d7 `5 d$ V/ E                }! `/ [- f4 w: K4 U, g

7 p& e; g1 c( t* i  d
6 v! i" Q( n) ]2 r9 `6 g            }//结束while循环
+ E6 e; q6 s- p            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦# \2 ]9 }, R' G) I
           
. ]; a1 b7 a  w' w' ]9 \' N2 R5 ?; z                if (numw[i] != 0)! K6 s& \9 g7 j, i/ j+ w
                    Console.WriteLine(numw[i]);
1 q! i4 f+ f7 m( ?$ M* ?1 S; p           
% m: N0 P, d2 q* m) V: J9 f            Console.ReadLine();
1 C* C! i5 b' L        }# Z% O. Z7 I' [6 M( D
    }7 L* w5 ]# b7 i, w2 U1 ]
}  p5 h, t; W' q6 }8 R+ G. F) o6 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-2-20 22:24

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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