鱼C论坛

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

猴子问题

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

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

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

x
大家好!6 K2 k7 w# ~& R) F7 i' M
这几天我在忙着编一个问题,我用了一种方法编出来!: C$ D7 a4 B' Q: ^0 ^
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!1 x- k6 W$ L' w4 x3 A3 y
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 & r" i- ]8 ~; f; n

7 m0 h" z+ J0 U6 @8 |2 f# B
& c2 W0 `8 w, Q& d
                            题目9 h! T; V4 o1 @1 }
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。. X$ q8 r9 A0 t' h3 m: L( |1 {
第一种方法:利用循环链表9 F+ E3 j& k1 s0 ]% k
#include<stdio.h>
! H: {! E/ |/ R- t#include<malloc.h>
4 t! Q. p+ d5 g) i; P#define M 8            //共有8只猴子0 F, d* j. ?- l. p6 d$ ?' I- P
#define N 3            //数到3只时退出第三只8 d  S8 y( w* M/ t
typedef struct monkey
" P4 q$ R4 c: }( a" L+ S  S{int number;5 R1 e; i0 f' u; |- P" R) F% E
int flag;
2 D+ O* P% K% U( v, I2 c) dstruct monkey* next;
8 l7 ^- E* P8 n- T3 V- ]}MONKEY;7 Y7 x6 e, T  o+ m6 J% }6 e
main()3 S1 _: C! Q& q. a1 |6 b
{ MONKEY *head=NULL,*p,*s;
0 V1 F, o% s+ a1 T3 a. l* C* Y6 C  int i,sum=0,count=0;
( {. ]1 v; _/ |, ]  clrscr();              //清屏0 O  a5 _3 |' k( \
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存+ a* s, [7 |  B3 y6 s8 u" t# h8 O1 C
  p->number=1;p->flag=1;" _$ a! q8 q) s' E3 l& f+ \
  p->next=head;6 `* W, q& @' N3 S" D
  head=p;
% C; k8 ]( h/ p' s( P) c  for(i=2;i<=M;i++)0 }# O0 H( w1 H$ R7 \5 d& R
    { s=(MONKEY *)malloc(sizeof(MONKEY));
) u  `3 b% q3 ?6 k5 @, w     s->number=i;s->flag=1;$ M) M) w/ n/ q5 I
     s->next=head;
# Z  _' g5 k5 r# F7 _     p->next=s;p=p->next;
7 w8 j$ s1 `8 B8 |8 B) F2 Z    }$ k3 K6 `  P3 U4 A& `- _
    p=head;9 |. _7 b* w- `. u
   for(;;)7 D& Y( z+ Y: Y9 i& z, q
    {if(p->flag==1)* P) x5 K! B; f3 G, O8 H: R
       count++;* x/ p  i# x! ?3 X4 B  u
     if(count==N)# ]& P. Z: m, m+ G. G7 U
        {p->flag=0;
$ m6 O, f% Q" ^8 z" o) A+ x         count=0;
8 @2 {5 I4 C9 ]8 W3 H         sum++;}
. W2 `$ S* o9 ]8 _, e     if(sum==M-1), ?1 M  S7 Q* ^$ ]
        break;2 g' V  V2 A8 ]5 O! X
     p=p->next;: E$ Z  j$ G: s
    }" L' _  s! m+ {# y+ T5 l
    p=
$ w$ c, ^$ F  j, A/ W    head;
, R* Q3 d* @4 I- i+ k& l. x    for(i=1;i<=M;i++)
( {2 }- j  W( B4 T- T    { if(p->flag==1)
1 z" i& k& ?4 N0 ^0 j1 f        printf("\t%d",p->number);
; v2 U' |0 a; Y9 R8 X5 q      p=p->next;
% d2 h6 e4 H; A$ Y6 l+ n% n' S    }
1 _- p% S; F/ D; f' @2 T& A/ W' Z
. \4 o2 C: e% B. K$ h" d* q, R
" Z- l1 u( [. w+ w8 V# |4 m% b$ f4 e& R
' D) a, D# Q; w+ c}

# p; c, \& U$ W& C; U第二种方法:数组6 c5 a; ~9 ^# V
#include<stdio.h>
. p* F4 d* N/ j3 c% v) k#define M 8
0 j( t. B* N1 n- X, f- estruct monkey8 ]" L+ Y: o7 a! i2 g" p
{int number;5 @0 D" T8 A4 E9 n
int nextp;
4 F8 Z+ u( s$ p& _9 F7 b8 o8 w8 i}link[M+1];' @" w1 x7 f1 O" Z

8 _9 [; k: l/ P" P- T1 c) Zvoid main()
/ d2 g+ m; H3 J! c/ e: o+ a{int i,count,h;3 K3 H) E9 @& ?, M" f
for(i=1;i<=M;i++)( |0 S& x! d, M" r( s8 H! H
{  if(i==M)
' D6 D& k, B' x+ m* x2 w   link[i].nextp=1;0 h" z6 K/ h8 n/ G' s) x
   else: k8 p9 }& ^4 K5 I
   link[i].nextp=i+1;
# D2 v; h4 Z. I) }  link[i].number=i;) x% ~- p: b# U* i
}8 w" T' J1 Q# J6 G6 |
printf("\n");
  b: r" \; J0 @* C9 L, N% ?count=0;
' x& |9 N! f: zh=M;: r/ [9 g/ M6 I. @0 I; c, R" {8 g
printf("依次退出的猴子: \n");
2 h( H: B/ x* ?% v2 rwhile(count<M-1)& k) Y( _& x, v6 }' W2 R+ a: d. d
{i=0;! v2 N5 Z, \' n0 N
while(i!=3)
  |) u2 V+ l( W0 \3 Z! ^{ h=link[h].nextp;
; [8 s0 z, |( j0 t9 H+ J7 U2 _   if(link[h].number)" Y" n5 D5 h- {) }5 }
     i++;}2 Z7 V; Y) U0 p5 c1 i
6 W1 D2 ^" ~( S$ z8 X  {& U, _
printf("%4d",link[h].number);/ ~. u; c; t) o7 D" ~! [
link[h].number=0;
! V7 N( j7 K# R0 h6 r! P. G2 c" _count++;  p3 S+ Q; Y: [- D' U# U. c
}
; Z0 N' s- [; F' P. G6 Q7 w
& N: }) ~" S3 O8 aprintf("\n大王是:");2 C# |% t" z: _) n; F
  for(i=1;i<=M;i++)
/ @- ~+ W. `- ]( r3 K  if(link[i].number)' K8 L& I6 U/ K" G; r" H! H
    printf("%3d\n",link[i].number);6 G6 d) G/ A; L0 H' m! p2 H/ `+ ~

$ H9 R2 T0 W- B; \/ A9 i
$ X1 |% V9 }, Q5 d0 Z8 @0 l}
( U2 H4 o, h1 v6 m4 n
第三种是普通方法for循环

! R1 a9 g( f; C  s$ ~( o#include<stdio.h>  n$ B6 }; X; t# q, G- D8 H
void main(); W' ~, `; D1 |( p3 S" }
{ int i,k,m,n,num[50],q,*p;" K3 e/ w3 H% g; L) @% y
    clrscr();
3 \1 C6 S. @0 X3 y) l$ x% b; \   printf("input number of person: n=");
# |( ]$ C! u- p3 p: {! `    scanf("%d",&n);
- A0 Z7 D1 i6 Yprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
' ]0 A0 f1 L3 t; p    scanf("%d",&q);
( W3 L' g( V3 |# C# L   p=num;
% O0 T/ ]- s. P# t  for(i=0;i<n;i++)
% z" B- S7 S2 A0 i8 E    *(p+i)=i+1;
7 m3 Q! D0 C8 }1 |1 t   i=0;% J  ?  I1 g% ]$ T
   k=0;( c- q+ e7 q: t# `
   m=0;/ `2 ?4 U3 B4 P! ~- u9 `& Y3 u
  while(m<n-1)- U% B5 C$ G2 m* R
   {if(*(p+i)!=0) k++;
* N6 }( _9 E; Z2 e& N  H6 o     if(k==q)
4 M( E0 s) d: g: O6 k! D: H      { *(p+i)=0;
. ~7 X$ a: l; N3 k1 D        k=0;
# L) e# k( I8 j* h, c        m++;$ T' J8 }' z& ?' u( X
      }
. v" t/ J6 X4 f9 p" B6 ~5 @    i++;/ Y, I) T5 P% {, M8 r/ T" M& k( u
    if(i==n)i=0;  T; }6 s0 W# H) f" G
   }
/ l/ {. b9 a7 k: C: g. ^0 Z  while(*p==0)p++;
& @/ _2 t7 A5 d7 n2 j' o    printf("The last one is NO:%d\n",*p);: h7 n/ V9 }4 i7 W
     getch();
8 @3 z, j! l0 n: B# k( U0 k6 W, X
; p# \& T& R0 Z! J4 @}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;) `, k* ^( P1 ], u
namespace 又费马达又费电
5 B. y6 S& o2 k9 f{3 v. y5 `7 i6 L8 y# q4 Z6 Y8 m
    class Program
. g: N8 ?8 T) i4 H3 @" M4 }9 m    {/ w% Q/ w; Z8 ~& p. a
        static void Main(string[] args)
3 A# d, Z( U' a. K* `6 }) E7 M        {
9 G! O- h. P, b0 r0 S8 X- C* H            int m, n;
. }* D1 f+ \  C' |- C2 u            Console.WriteLine("请输入数组长度");
  @% ?* G/ b8 o            m = int.Parse(Console.ReadLine());//m为数组的大小. y/ T2 k! t' `- A' x4 V/ F
            Console.WriteLine("请输入要截取数字的大小");
( l$ r# Z6 E; ~0 s7 L: p            n = int.Parse(Console.ReadLine());( K1 {3 p4 h/ ]' |( h! k' v
            int [] numw=new int% R( M! }1 d3 U8 j$ ~9 b- A

6 O# H9 }" j0 \$ }* [&shy;&shy;&shy;;
9 Q1 [, x* ?9 r( D  E5 m            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
5 b6 `. c4 H3 Y- B6 }8 n            {
0 k+ T4 `; ^# i6 O% W                numw[j - 1] = j;
* d/ U( }! r2 {! Q            }
2 ^% P, k3 z5 M' g* q7 T0 ^            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!% {6 Q- V, z8 t2 y: N
            while (d != m - 1), X' n) V! X& V- e0 R2 \1 p" u8 ]
            {! W( T# E( T' p# ]
                if (i == m && d != m - 1)
, h1 q* r2 ]. C% o# r1 y4 {3 \                {
  K' J1 P% V$ ]& }" b+ \( l& Q                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!8 i" z4 q7 A8 C1 l( i$ Z: H" {
                    continue;
( E  |/ I6 s) E" r9 D& h                }: v: w  q. n  {6 ]( i3 ^* @
                else2 ^7 G- N/ o0 u5 f4 S: U
                {
/ V0 e, V" H7 S. e: f                    if (numw[i] != 0)9 x1 R) U! \3 n6 M5 Y( F
                    {
! Y: D6 A  H( ^( h6 Q                        i++;
9 \' g9 K0 h( j6 e  ^                        k++;! u3 D# x0 z# `8 }1 u0 z% k# ]6 K) J
                        if (k == n)8 E% m5 ]2 Y. |/ M$ u
                        {
9 q$ n4 T# @. T( E( ?6 j7 \' d                            numw[i - 1] = 0;//把在n位置数组元素的值改变了  h/ c8 Z7 O6 h( R' y9 \
                            k = 0;
6 x# H+ E  l( l* e* }, _              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小17 Z8 x. s6 |3 J
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
( ]+ `! \3 s1 K! X; M+ Y4 ?                        }$ h- G8 v" T! ~) G  d# C& \  m* ?0 ~
                        else//输出暂时还没有改变数组元素的值
/ `! B- z# T/ F: n. ?                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
2 s/ D6 a7 J0 E+ z7 ]                    }
6 i5 b$ A4 J2 ~! P5 j! h3 G+ Q% O2 n                    else6 K/ g( E) P, _+ u7 O2 y! b
                        i++;//数组元素为0,直接跳过,不计数。。。% |# c) e3 t$ q; g; u. |0 \. Z$ K
                }7 e8 X" O- x* B' U) H6 P: c5 D4 s
; x6 B( P% i* t) g' l4 g

. R3 G/ ^9 P- K/ W            }//结束while循环4 R& G3 q- F- w4 X. D
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
3 Y' r' }& v: r$ c9 U1 }8 w           0 {! Q0 g0 E! t& ~. t* A
                if (numw[i] != 0)
/ R4 M) ?4 B! z0 B                    Console.WriteLine(numw[i]);
& x) B6 w( L% H: `8 @           
! i0 B" T, j- S# F4 O$ x            Console.ReadLine();, w. n5 v' F9 H4 a) }4 R# A
        }: [8 f$ Q% f$ j2 @
    }
* ^: y$ G6 s5 a, P) O6 F' |0 W}7 L# N8 c9 ^4 d; J
小甲鱼最新课程 -> 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-7-12 06:39

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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