鱼C论坛

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

猴子问题

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

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

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

x
大家好!2 I+ }; Q$ J+ n4 v8 u5 k
这几天我在忙着编一个问题,我用了一种方法编出来!
; p* ^& t' L" V7 G7 p但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!3 @8 \+ f9 a% u' R2 _7 Q
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 % H: T& B$ E) s. ]3 v' x) R, `" _$ u8 S

0 H2 G( R9 l: V- T7 ~$ T! s2 a4 I% l# U- z/ @
                            题目' J' T/ {+ y7 e/ v# Q# ^1 {0 q
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
; E4 l3 w/ [4 F+ a1 M! l% h第一种方法:利用循环链表- g' n$ P* O+ |) k- D
#include<stdio.h>2 p0 c7 x+ h( R8 _6 K
#include<malloc.h>
1 A3 G8 T$ E1 p( u#define M 8            //共有8只猴子
" ~9 z8 }! d/ w# `8 R$ _, U  L#define N 3            //数到3只时退出第三只
5 _1 ?: ]5 n  T! ], {typedef struct monkey, Z+ i# b4 r( h6 t
{int number;/ n" r0 I' c! x
int flag;
& M/ B  x, D/ k1 y9 sstruct monkey* next;
& K* ~$ N: X# t! Y}MONKEY;. {" D8 _! ~/ m( w; e" F
main()
9 n# ~3 W9 q- n5 g{ MONKEY *head=NULL,*p,*s;1 Y( v6 o1 I! h; F" \7 b
  int i,sum=0,count=0;$ @0 Z6 q! e& R
  clrscr();              //清屏* c: E2 c2 g: t( c, [9 k" E1 M( ?8 w
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
0 N" s5 z9 U7 j  p->number=1;p->flag=1;4 }0 j+ W5 r* F4 B( y
  p->next=head;# ^1 D( p0 b) L/ @0 e/ E
  head=p;
5 r8 a2 k: y- x0 D( v8 O! a$ q- t  for(i=2;i<=M;i++)% n6 \- G& c' `8 Z7 T/ q. `" H
    { s=(MONKEY *)malloc(sizeof(MONKEY));, x2 n9 g4 K( Y) L# b# o* t  k
     s->number=i;s->flag=1;3 t  O, ]! i3 o! E
     s->next=head;; U6 t5 u! N( k# d( Z/ ^
     p->next=s;p=p->next;4 Z# d, f& x" n9 D' D+ |2 K
    }- u5 h8 h" `: \* ~* F! Z2 m/ F
    p=head;7 s. h' w* p& X# N( A
   for(;;)% \$ s% u. |0 Z+ `& I/ u
    {if(p->flag==1)
% x, [9 {. W; I5 w. T& @       count++;
6 T( r4 W. f' e5 m) P6 E' Y! K     if(count==N)
1 K+ O3 E# ~1 \( B* m        {p->flag=0;6 m) u9 ?! C* o, k, ]
         count=0;
& d" a2 ^6 n2 _; ~9 t         sum++;}
; \+ F3 z% p  O) g  [     if(sum==M-1)8 e) B2 b) _- L5 a* q
        break;
4 P% Y6 x# j+ [; t+ L7 X! S     p=p->next;- _: Z1 r) F+ g, q3 I2 I
    }1 I9 b4 G5 K  O6 _, g
    p=
" ]$ `9 v5 V# D- w2 s8 Y    head;
+ g3 ]. N9 j9 U- K0 j0 E, @    for(i=1;i<=M;i++)5 t+ `, U% Z: o) i, d" m
    { if(p->flag==1)
9 B  x- n' t1 u5 s; o( o" ?9 f        printf("\t%d",p->number);
& g( G; o: J* r* P      p=p->next;1 T- w7 C1 {% [. P3 Y
    }6 g0 {6 C6 U# T  d* j" F8 a
3 O0 d2 m4 Z6 |) t4 M- a5 g# a

. i, o8 }7 A: a) u9 Z" Y6 H# V; g( R8 l6 w' w
}

! @2 x1 _) G! {9 z2 I7 B: u第二种方法:数组' n5 D( F  E+ e4 Q
#include<stdio.h>* _( E7 b. x% l- C- [! x7 X9 [
#define M 89 F1 P, {- B( v# C
struct monkey) b0 F, Q: d$ V9 ?6 _
{int number;" b6 y% w, ~7 W0 W& E% C
int nextp;
$ Q( y, y+ ]) L$ {! I4 s9 a% D" q) s}link[M+1];
# e- M3 ^/ J) O/ X9 l7 b* ]; p# |. B; N) C+ [
void main()
9 `/ z$ z( E( M8 a! K5 L5 J3 Z{int i,count,h;- a! g) r- O, l
for(i=1;i<=M;i++)
  o3 E" T, T$ ?: J3 w* u{  if(i==M)4 X9 G  [. g' U4 j8 K5 n
   link[i].nextp=1;3 U# r+ k8 E2 Q
   else
* @( v8 j/ q. n8 I* b. z6 i' O   link[i].nextp=i+1;" k( f+ }6 s( z! ~7 d) [8 ^, ~0 w
  link[i].number=i;
* p' l3 \* w  D3 i( [9 E' _4 w: L}
  \. r/ g& N4 X: ]7 U0 R3 y" zprintf("\n");9 N; S  R2 F  F! f; C3 `" [
count=0;4 @* |4 \7 R1 w% m/ \
h=M;2 ]9 j/ e, R5 X' O" p
printf("依次退出的猴子: \n");
6 Q$ w. V; W8 x- Iwhile(count<M-1)
: q2 Z( ]7 E& ?8 U' Q) `8 D3 b% R{i=0;% a' E. y7 @5 I1 n+ X* h
while(i!=3)
6 U# T8 V2 n+ _# P{ h=link[h].nextp;
# h0 J* U7 a7 U2 `& u" `   if(link[h].number); A3 }& _5 G9 G
     i++;}1 J2 W1 d6 W$ W. o) S* B- v+ _

$ c) C% I' X4 Pprintf("%4d",link[h].number);+ S% W* I. J4 a% ~. M
link[h].number=0;/ D7 ]: P5 U8 c" M5 \1 E
count++;
: N0 r' ?$ A; ~& h2 p+ \}: I- x, L( M/ Q9 {6 b

* `$ N6 K6 P1 X, U! @  Pprintf("\n大王是:");# B& Q7 c; L: W) P/ ~+ J" r
  for(i=1;i<=M;i++)7 }* X. G0 C% J" c6 v' [
  if(link[i].number)8 K; G) D3 H) ?) X. Z9 @
    printf("%3d\n",link[i].number);
7 f: g5 `& S& c$ w# w3 Z" \' B* M
1 G( c; j$ l6 J. T8 z
( ^+ ^/ W' L" b  R1 G}
. E# Q1 C- j7 p2 f2 N4 U" R. B6 O
第三种是普通方法for循环

8 V3 h! p+ R& n( z- ]: j: p#include<stdio.h>$ q" u  ]+ j4 w6 R: h0 \3 ?
void main()+ S6 {) P+ h( a. W& c$ Y
{ int i,k,m,n,num[50],q,*p;
  P$ I9 u. i3 p# i    clrscr();
* V# Z9 ~$ c5 I# ~2 q8 ^# G* r   printf("input number of person: n=");
0 C# ?, i3 o0 |( A2 K, \) Z    scanf("%d",&n);
* d  @" h4 U, `printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只0 V- A: q5 C: f7 T
    scanf("%d",&q);7 D$ \: s  s0 Q3 I) g
   p=num;; K3 c! V% r5 @( I$ Q) M2 W6 L% e
  for(i=0;i<n;i++)
1 k- t6 l8 P7 [0 Z; P7 H    *(p+i)=i+1;
( C$ U. Q/ ~6 L" X0 Z  ^0 |/ k5 o: L   i=0;
( N1 j/ \: i: L   k=0;6 r, g/ h7 Q& O7 H' ?
   m=0;; o2 C/ s  t* p. ]
  while(m<n-1)8 y& s0 ?& X. D
   {if(*(p+i)!=0) k++;
  A' W9 p* |% [& O6 C) f/ V     if(k==q)) D, h" f2 @; Z& t
      { *(p+i)=0;
( B* \" Y' F6 K* v/ k( t        k=0;
+ {2 b+ t' G4 r5 t. P' \        m++;
& \3 o4 J: d( ^0 O$ d) r      }: }8 n+ }3 x& Q2 G7 G3 G; Z+ s% ^8 t
    i++;' M, A/ T7 k2 o. F" H+ p. [
    if(i==n)i=0;4 U  O9 K1 J$ T  [
   }; n- ^4 {9 z9 _' B) @. _
  while(*p==0)p++;
& R! A: f9 ~+ a6 P% U& t3 ~+ X) P    printf("The last one is NO:%d\n",*p);5 z  ^" B3 {# l
     getch();1 q: N- ~- Z  B4 t& Y7 g

) y& \+ L* _6 G3 |, k+ M' A0 ?}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
$ j7 W1 t* A: _/ D6 Pnamespace 又费马达又费电" u9 ~1 D# b; c0 K3 x, y
{% E" ~; n3 Z1 U
    class Program
1 Y& L7 I9 W$ g) ~  S) U    {1 u; [1 a# Q1 [5 O: \, s. U
        static void Main(string[] args)
- F/ t$ z- \" Z        {+ G! {, g0 T# o5 z( v
            int m, n;
- z  a$ G1 |9 p( w, g9 u            Console.WriteLine("请输入数组长度");) _: a! G$ }/ Y5 p1 R
            m = int.Parse(Console.ReadLine());//m为数组的大小; S0 R. u: w4 e! h
            Console.WriteLine("请输入要截取数字的大小");; j: k& N: l4 w1 U  @7 x- s" c
            n = int.Parse(Console.ReadLine());8 g5 D* s0 @+ |( ^6 H: t! C7 {" ^
            int [] numw=new int
8 n* b& A7 s2 K# B: d$ O( D1 z& ~$ h
&shy;&shy;&shy;;) M" s0 K  Q/ y# q! t0 _+ v1 H
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
% [$ }# f9 }% |/ Y8 O4 x+ u            {2 Z6 i" i+ s) S/ q; J9 e) E
                numw[j - 1] = j;  Z" ~2 X: C) D- y) l# w* C
            }: c' B0 C2 v. f- L4 g! @% n
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
' U- X; v# z- I6 H9 {* }            while (d != m - 1)
* n- ~1 C0 ~# D3 ?            {) I8 C/ u$ y4 ?  V* }1 R! x
                if (i == m && d != m - 1)
: U' M7 ]$ T5 Q! |4 v% f, t4 j' m                {
( J7 O% l* ~) y6 S9 p) T                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!/ {! C: }* r* M) `8 ~- h, ^
                    continue;
, _" N/ O) Q, ^) j                }' q, b/ x  P# M* {) u3 I
                else
* |! n# h1 F5 P1 M; H4 i                {# c% M2 M$ p1 t3 Z5 r. j
                    if (numw[i] != 0)
: D% [( U* n7 r5 e5 t8 L                    {
  f. Q7 ]( W6 U                        i++;( O* \; L# _5 f. x
                        k++;9 N: d: ]% M$ ^# w, c6 u+ v+ R8 K
                        if (k == n)7 }3 O4 M! U1 O: L- O& U
                        {
) i: r2 R5 D) c* G, |9 Y                            numw[i - 1] = 0;//把在n位置数组元素的值改变了9 c& ]1 d) E5 V
                            k = 0;1 z# f! ~7 `  v2 S2 r( X) `
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1& b1 \7 N6 j; H9 g/ D
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 R( [6 [6 P$ O3 _; Z
                        }. k9 F$ s5 Z" I5 ^- K5 p2 X
                        else//输出暂时还没有改变数组元素的值' D5 C- `- [7 [8 @% h6 I
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);/ g- p  H7 d( B' v3 t) W9 ^* g
                    }& q6 D1 T3 K9 i+ I
                    else: `; i+ c+ q+ G
                        i++;//数组元素为0,直接跳过,不计数。。。
' e; L) f; o. G! _* I, ?6 |                }
6 W* v# ^2 O& z; ?+ N
: o" o: I: H  M, Q/ n1 Y
4 @& O" ~: h, U. V5 t            }//结束while循环% a7 B( J' A% E, M) X. W0 o; O
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
" y! e, x& i  \8 }, J* w           ) r$ A5 D; |! ~. T7 c4 R
                if (numw[i] != 0)
! j+ u* L! {% e1 v                    Console.WriteLine(numw[i]);4 D3 X0 ]" P0 q8 D
           
6 g2 d/ D8 D1 N, {- J3 o3 `            Console.ReadLine();
0 m5 N* M: h) ?# v7 i" g) X/ h        }0 a; v" n% W3 u- x% A' G4 G6 G
    }# Z9 g, t7 Q6 O5 X/ c3 s
}  c0 C- ]9 n* e+ R8 o
小甲鱼最新课程 -> 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-21 04:07

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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