鱼C论坛

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

猴子问题

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

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

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

x
大家好!: w0 r5 I) U' K5 A2 s  S- C1 @
这几天我在忙着编一个问题,我用了一种方法编出来!7 L, s, U4 t* K2 d0 U' a- t
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
: [, D" R3 [6 r9 {; k2 X7 L: s注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
. r) z% g/ ?8 K% H/ R  C7 V8 D/ P+ H0 ?1 D6 @9 e
  A$ ?( R0 t3 L; }7 `9 i# T
                            题目
7 K9 K! n" q+ I) D* l山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。# \3 V/ v$ {0 T
第一种方法:利用循环链表$ ^( Z) N& C/ G$ Y
#include<stdio.h>- d# a1 S' D5 Z3 r9 o! c
#include<malloc.h>
- e. v1 x  O) \5 p. j#define M 8            //共有8只猴子
" T# f3 I" s( K) h: q#define N 3            //数到3只时退出第三只" N, Z* j$ z  Q5 D
typedef struct monkey
; z  L4 ?$ R9 U- `7 ^" R9 X{int number;: L2 W# f& {3 p/ L/ |! O
int flag;
- f/ d8 D9 r& |( T2 R9 C" r7 S2 `struct monkey* next;( n" [0 a5 m( Y& H& {( x8 D" g4 e
}MONKEY;
& q, R) H* ^9 j* G+ Amain()0 S5 V+ ^' O& l# x
{ MONKEY *head=NULL,*p,*s;' [6 Z; e, S6 I7 V/ I) I% y
  int i,sum=0,count=0;
; E$ V3 ]1 k# L  clrscr();              //清屏
3 t: b# X, L! U5 N" v1 m1 s: @; X  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存. W" ^: w$ J% K5 Y# a9 g" X, X
  p->number=1;p->flag=1;( @' O- B0 W& H* `3 ^
  p->next=head;4 `  |8 j! K) K) u5 _0 M
  head=p;
* ~3 k4 Q* c; s9 X7 I6 u: k, M  for(i=2;i<=M;i++)- i( I' Y$ E8 |6 U1 Z/ C1 N
    { s=(MONKEY *)malloc(sizeof(MONKEY));
. U: f6 C$ Y) i& q6 p     s->number=i;s->flag=1;1 o/ `& d  p& C/ x# u
     s->next=head;1 w- Z6 H' B8 e/ ~# `
     p->next=s;p=p->next;+ q+ S7 {$ L! H' W7 }6 }. T
    }+ W" H0 y7 h; f+ p  j
    p=head;
0 C: r% u" p/ u" N- d   for(;;)9 Q  _& m% e2 E: }% F" }
    {if(p->flag==1)8 N# w/ }$ D$ w: O1 z, v
       count++;
! d+ n# h0 P1 A9 Y7 r     if(count==N)
2 @% |# c1 K- _$ j        {p->flag=0;
; s0 {/ u2 |# N! l         count=0;* P/ }" Y( H& q0 j5 C' L
         sum++;}* F8 @) g! }& j8 b. @" d/ T7 m6 ^
     if(sum==M-1)6 b; N) r) ]4 T7 J9 S
        break;  Z1 e3 z5 X! K( D$ o% |
     p=p->next;
6 |4 x- S4 c' X0 \- w, ^    }
0 _5 `6 s/ x9 H$ @# U, w    p=
- m+ Z9 r8 J8 ?4 W    head;
1 q& d' K7 ~* h& t, J9 o    for(i=1;i<=M;i++)4 N  i. h, M3 z% U8 d
    { if(p->flag==1)
' k' [& a& _5 u7 V; p        printf("\t%d",p->number);. _3 X% N4 S# f! [8 E+ `2 F
      p=p->next;
. v# p. d6 e# M4 j    }0 Q  P% k! z+ D  u, U

- A6 _) ?% v0 u9 W
5 T: ]" \. v. h' p. t1 t/ C! F0 _+ \$ V$ z1 H
}
3 w, t" o3 K6 m6 N6 T0 x
第二种方法:数组& N% r4 @# Z% Q* y( [1 O
#include<stdio.h>
  z/ i/ h! |3 D#define M 8% f/ A& a- k/ a) L
struct monkey3 G# g6 y: O+ |
{int number;! I; n0 K7 n0 L+ A! w# p* A
int nextp;. [2 P" h% r% [2 x. O; d/ d- p! x
}link[M+1];
; ~( s* ]2 w6 [1 ?2 t
- d, S, z% ?, p$ M( J; X8 F& Tvoid main()" U* e# i, i- ^
{int i,count,h;
! h) d# J6 T4 ]- H& O8 J7 K' a) f$ _for(i=1;i<=M;i++)8 I& v# @( \' `/ t
{  if(i==M)) U. i0 ~& K/ }
   link[i].nextp=1;
- g9 \- j& Y' P/ r# s; n4 ]; p   else5 g6 W+ O( V  j4 w8 L3 e7 r- b
   link[i].nextp=i+1;
4 ]4 f5 g8 ?/ r8 g2 m, J" U  link[i].number=i;2 [9 I9 |& ]( N+ C7 ]3 h8 t
}
% i! P4 o( o. s- Eprintf("\n");
7 z: }6 ]3 P6 M4 ~: z6 }count=0;% [* `% t6 B. ~* X- C3 E
h=M;3 A  W0 l$ w9 C9 K/ Q
printf("依次退出的猴子: \n");
' T) ]- A4 P3 G" ^& Ywhile(count<M-1)
( n0 C7 t1 \) G, z8 x' f; d1 V{i=0;! _# a* |1 p- M; w9 y: E9 O( w5 C
while(i!=3)0 A. A+ ]0 F+ n! `7 i, p  r
{ h=link[h].nextp;: {/ p( d( y' k& ]  B$ s9 Q) \
   if(link[h].number)2 _* f+ c5 r: U; E3 w9 ]
     i++;}
& S- q' }  n  F. s, v+ W. n+ T/ u6 U
printf("%4d",link[h].number);  q6 y! x, v5 F5 i9 x' S: H) T$ N
link[h].number=0;
0 ~* @/ f+ z8 _6 i# i/ P( L: Y% n+ d8 bcount++;" O! B9 [" G7 }% b
}
. q2 U6 u! [' k* B9 ]: x' x0 ^! {( s2 W! p4 j0 c9 R3 Y' ]( p
printf("\n大王是:");" Z7 h) o7 r4 k) J$ E; R
  for(i=1;i<=M;i++)6 R5 K6 ]+ e  M: m
  if(link[i].number)
8 g6 J7 ^: K3 |- e    printf("%3d\n",link[i].number);
7 x& ?! O4 `7 c6 i, l6 [
  B) w' l$ x8 j: h  }! J. G; J+ ~$ F5 P7 I9 ]
}
$ V. }) e) P# R: t
第三种是普通方法for循环
# Y6 F" @. U; m0 E( i
#include<stdio.h>
$ D  |# j9 b; ~7 P% N8 vvoid main()& f4 A; B8 F  {% Y  @- s* @
{ int i,k,m,n,num[50],q,*p;( O9 j/ a. _9 u+ {% z# u
    clrscr();- N: y- q- r* U( S
   printf("input number of person: n=");3 }/ L  b( ^, b; f
    scanf("%d",&n);
5 g* _5 a/ ^; F; Fprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只: C; q' P  c" h+ W! G' o/ s
    scanf("%d",&q);' A! C4 Q0 f. @* @4 J6 `
   p=num;
3 r- L0 l1 B/ Q  for(i=0;i<n;i++)
' C: q: r% M+ S1 H    *(p+i)=i+1;2 Q* `& M+ ~$ B: \& L. x- M- n4 Z
   i=0;
8 D( U3 B7 V/ K9 }' a# F5 w1 p7 z   k=0;
& N7 r$ g; C# O, V. c5 I   m=0;
7 w# k0 e1 O4 \* L# Q; u3 x  while(m<n-1)
; }1 X* M; F) t2 J! R   {if(*(p+i)!=0) k++;0 r+ y, |1 e! z$ Z0 z+ n" O  u
     if(k==q)% A% p& n. J9 D- \$ Q+ s
      { *(p+i)=0;9 o9 r3 W, d; B8 z6 h
        k=0;
: I$ Q8 g6 M; A/ ~        m++;
$ H9 J& S/ b& f3 F      }5 x2 o, Q8 d- Z; t, n
    i++;8 b! h0 ^* H6 A& T+ U+ L
    if(i==n)i=0;
9 |$ c& |# T) M   }
! X; Q3 a3 U% i4 C, U6 ]" v  while(*p==0)p++;
  U$ s) _$ b" z' ]  e- m2 z+ Z; \    printf("The last one is NO:%d\n",*p);
3 ]' n; H/ C; G     getch();. u: X  n6 u( @/ c+ ~
! Q# i' }$ l. l8 _! f
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;& \5 b+ C: W8 Q! `; W6 u
namespace 又费马达又费电; U+ r7 s" \- c5 l8 P
{/ ?/ m. Q$ [" ?6 n
    class Program9 k- H7 \" D  S8 V. w7 `
    {+ d0 o6 I& Y& p# Y
        static void Main(string[] args)
& h) _& N" Q$ o! c5 c. F7 X        {' [2 t! ?0 q+ \
            int m, n;+ c) ^, a: X2 R& z5 @
            Console.WriteLine("请输入数组长度");
* B0 R3 X* g9 s3 P* b( h- d* L' x            m = int.Parse(Console.ReadLine());//m为数组的大小
' G( b) @+ I" f( w, L            Console.WriteLine("请输入要截取数字的大小");
/ s% x+ W! o! C0 R            n = int.Parse(Console.ReadLine());% I& N+ q! U+ b; _+ E
            int [] numw=new int! P; ]) b% U+ i" Q1 Y5 i5 N
7 z6 U1 x9 |8 a! N1 @
&shy;&shy;&shy;;; |; }- @4 L: C% w+ u" t
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数* \# h. ]8 [4 o& C0 n  O4 d
            {
0 J0 L# ~* o! I0 q! r                numw[j - 1] = j;
, s1 O- @3 [' J) k/ B            }- I$ g2 ?, u- B+ g4 P3 a
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
+ N$ S1 J4 \4 `6 F            while (d != m - 1)& U9 e% D5 ?$ s8 U: ~
            {
# v; J4 R4 r* ]6 F, c                if (i == m && d != m - 1)
8 `2 b4 t& @; ^                {
" z1 `) `4 o1 Y% O                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!5 Q9 n7 f, }* f# r. v9 E
                    continue;
! x+ w  |9 e' i                }" ?9 _5 L+ p9 \! Y2 N  H% `
                else
. c. K6 A+ U8 T$ {                {
! y# `1 l9 j; b1 d                    if (numw[i] != 0)
7 Z# a/ q8 b( v/ g3 d                    {: U! V' z1 R. q5 D# a
                        i++;
5 k# k; j' x; s& K                        k++;* C) m, o0 F8 f8 \- }3 @
                        if (k == n)
5 b7 ^& g* O9 K/ z, S                        {
# }5 C2 q/ B; E3 Q( \: j                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
- v  l- w$ U( x* {# y                            k = 0;. i( E! X( l# D7 f4 y5 n
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
8 s3 K7 \, h4 W  f# [                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);! G0 K9 j  s6 T2 M3 \
                        }
( Q  G; {: k1 k) T                        else//输出暂时还没有改变数组元素的值, S0 w; }1 n$ m
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);& p$ G$ `. ^" H3 z) B* o
                    }+ @  V5 V2 z4 `6 ~# ~* y8 A# r/ i
                    else
/ ]9 w4 M1 W$ z8 M( t! |6 q                        i++;//数组元素为0,直接跳过,不计数。。。
; A$ j. I' Y7 X7 x- m' d. h' t                }  }3 S* Y6 ?6 D+ X- P- n' G
0 p3 Q& V% ?, U  T3 o! Z8 g3 [
( K( c1 P9 x8 A
            }//结束while循环
& S/ S0 @& f2 x8 |, o- H            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
& L3 S6 p( V! j4 j8 s1 n, u6 c           
: |4 p- o( b# q4 d3 t4 y4 C                if (numw[i] != 0)
) ~9 H* s( \# o) u                    Console.WriteLine(numw[i]);
# J" L0 e* I# }1 E# u5 g& z4 B           
5 S7 h9 I/ _" k/ t9 {! f+ i, m" ~            Console.ReadLine();2 J- T4 }4 j, J+ ?* s# `8 M! y
        }6 L6 _, o3 [- \- t- V8 s$ p' d0 c
    }1 k/ U5 o" h1 n( s
}
) K. H9 Q  h4 L( I4 C
小甲鱼最新课程 -> 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-2 22:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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