鱼C论坛

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

猴子问题

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

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

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

x
大家好!7 ^  U/ W8 g; V" F2 D
这几天我在忙着编一个问题,我用了一种方法编出来!7 C# L/ n( `# _9 n
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
/ v. P; A. |/ A% O. @; K注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 K  @6 N) h- J) M* i4 [4 P! I9 c
9 I) r0 _, i  o( j7 l) {. c- ?8 W- [6 f  O+ {
                            题目9 [. F; o& }. k; q3 Q8 G
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
0 S- ^, P. C8 N/ c1 q& p7 H第一种方法:利用循环链表
; z, C7 x7 S5 e. [7 r( L3 l#include<stdio.h>4 U+ l9 W8 L  ]1 n
#include<malloc.h>2 \8 c' X% U% Q* |4 R: x2 N
#define M 8            //共有8只猴子# x# g/ R& x: \/ T& d1 z+ z
#define N 3            //数到3只时退出第三只
, T8 B  u( ?. y* stypedef struct monkey5 `. E, U& @3 e4 d
{int number;6 i3 q7 Q& ~' }4 \
int flag;
/ Z" i& ~  y6 |7 t; zstruct monkey* next;
5 T8 |3 M" ~) z1 U4 V}MONKEY;# v; T8 m( k4 f
main()2 {2 I7 s7 P6 S
{ MONKEY *head=NULL,*p,*s;
+ r: e: C" x8 Q  b  int i,sum=0,count=0;
4 Q! r6 T5 e) i; M  clrscr();              //清屏
6 }2 z# p  f8 W4 s  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存. S/ a9 M( e( a$ d- H% E
  p->number=1;p->flag=1;
) F# R( m% U- G. `6 {  p->next=head;4 D0 B- R' l* H$ C, F  E; q
  head=p;3 q" g3 f' L# W! t. Y& M, `
  for(i=2;i<=M;i++)
$ r5 S) b* `* g5 M2 C    { s=(MONKEY *)malloc(sizeof(MONKEY));
# k, D) m' x& N. X     s->number=i;s->flag=1;
5 n3 W* }% D9 m4 R     s->next=head;' K+ U4 y; s  i
     p->next=s;p=p->next;
7 o4 x8 x% z8 @2 w' P" \6 y) x    }- n2 A' q6 n, D5 A8 O: D
    p=head;
2 I! t  M% Q% ~/ P: o   for(;;)7 J2 y7 U) o) Z( q: ~6 s# y
    {if(p->flag==1)2 A+ W/ p! f2 ~% D
       count++;* H& l: Z$ ~0 F* s# M/ C2 v
     if(count==N)
5 T* V' ]# U$ [  Z        {p->flag=0;: R& n. G+ B% g* d, J
         count=0;3 u1 a2 |' ~$ H
         sum++;}
- }( _/ X" ~$ h) T4 G3 f* n     if(sum==M-1)" K8 j" R# {/ X3 f- c, Y% k
        break;
6 _2 R$ \9 s" d, O, ~: m     p=p->next;5 E  I1 u: m3 u4 x
    }
0 ^/ f& [' o2 \. r( d    p=7 d7 O8 x# C1 Z
    head;3 Z2 L; h' D: a* E
    for(i=1;i<=M;i++)- D* l& @' \+ K7 B; ]4 o
    { if(p->flag==1)* [: Y. i5 @6 n: O# F
        printf("\t%d",p->number);
% @, O7 h& M5 p# Z" V3 E. \% a      p=p->next;
9 h4 {9 d5 d% Y+ H! `3 C    }1 m9 g* y% n3 V6 z% b, ]: ~4 u
" e1 ]4 _2 e. ]- N, N

( N. s* R, z2 E6 m. u$ {4 o" ~% N' o
}
. c7 m, Z! d, ]) r; Q4 \( v; R
第二种方法:数组. W! C& A6 P3 D$ p
#include<stdio.h>0 L- i2 k, X1 ]  X$ V( F4 G4 [
#define M 8
  ]: ^# N, j6 ?+ q& u4 sstruct monkey3 U& r2 `4 u+ l5 H+ q
{int number;; J6 c4 H  U7 K  ^
int nextp;3 h: `' v2 u  n- X- z0 u5 n
}link[M+1];5 l" A6 A- \+ C$ D1 z* W

8 j/ F4 c, o. j- p7 N' O$ D1 @void main()
3 |( Y1 Z& ~- H{int i,count,h;
/ q7 E2 z* X  f* u" p. k4 E$ Dfor(i=1;i<=M;i++). K( W+ G: [: `9 h+ J' F
{  if(i==M)! n  J  ^5 p& a! G0 i5 U
   link[i].nextp=1;7 X! P" S9 R7 p5 C
   else( |: E2 K* ^5 U" Z1 f- _
   link[i].nextp=i+1;
0 t- Y5 T/ w8 c: W, u6 V) s3 X  link[i].number=i;
9 D4 \" |, H. ]; S$ p# {3 V}  ~. ]9 C( F* `! n7 x
printf("\n");
, \2 o4 D4 B; [5 j+ f# y8 u- Pcount=0;  c, q7 u- q; ?: o! c. d& l
h=M;) n* H! R4 ?5 K. F1 R0 X1 E, r
printf("依次退出的猴子: \n");  T- H+ {+ h0 i5 H2 A7 k/ a: c
while(count<M-1)8 V% E+ @" V0 a8 P# f' r$ }
{i=0;( n+ x0 |4 A! T- C1 [& F1 T2 o
while(i!=3)
9 k+ V2 `. x3 B2 ~% d& Z# d{ h=link[h].nextp;4 W% ~8 n% M- c8 K# ~! j' A" [7 x
   if(link[h].number)
0 Y  k+ d1 {% r% l3 Q1 [     i++;}" L0 `4 d7 B$ _- S1 W3 H

' Y* w! T  b. G, J! D" K! n7 v: uprintf("%4d",link[h].number);" V$ q; l7 x  }9 `
link[h].number=0;
% N9 w& J; S2 Y) s) Y# Y# v. ?/ dcount++;) Q6 G9 O$ w5 S) m
}
* n! Q- p7 L4 @6 ^, {
2 m# i  Z* f! |* Fprintf("\n大王是:");
. `0 [/ B8 F& A: A' b  o& \7 R# i  for(i=1;i<=M;i++)
; ^8 q7 \# N  q& [% `$ T  if(link[i].number)* h0 F8 {/ @$ a, B; H+ n+ w3 {
    printf("%3d\n",link[i].number);; D! f; e1 G) d

! V0 ?1 G3 U$ e
) _3 Q* E4 p( R+ E! A; C2 o+ T}

4 O, M& u/ O4 B( \: _第三种是普通方法for循环

! O8 n5 d8 U2 L( |0 ^7 f/ `' b#include<stdio.h>) N# D8 r; L8 Q
void main()0 F: k( R, j" E% J4 E
{ int i,k,m,n,num[50],q,*p;) Y* q- j# g* l; N$ d/ O/ H! u
    clrscr();: z, f; z' S: [; t; G7 B' S
   printf("input number of person: n=");8 ?/ P& \) x  e% z' Z- q2 X
    scanf("%d",&n);
8 L2 U: V* E+ ]printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
- v9 Z7 Q+ J7 [% T) i; E& _: o6 F    scanf("%d",&q);
( q2 E) v9 V% k) q/ ?   p=num;
3 h( Q* j' L8 a% U3 r  for(i=0;i<n;i++)
  f; y. B: G: H! `" [' N: p    *(p+i)=i+1;
) f3 }, Z( t9 _8 q$ c   i=0;
; ]8 N8 E* O: I3 u3 c, ^) z   k=0;2 h+ ], U' @/ u& G. p! Q
   m=0;
# B/ S2 s8 q* b9 K$ l/ L! R  while(m<n-1)# W* N' j0 n& G; q4 @
   {if(*(p+i)!=0) k++;
9 P3 \4 L7 _5 K* _! ^' n" G1 I     if(k==q)
0 A/ R8 W- T+ v1 b      { *(p+i)=0;" d& I4 z/ d9 J% ]& }
        k=0;! \* B5 Y- `& a0 u$ A# F
        m++;
. c; d5 T3 J3 ~; u      }4 `7 ^6 ]: G: e( k1 O6 J6 V
    i++;5 x0 H8 R( l6 \  h- E/ w
    if(i==n)i=0;: B- H: X0 j+ f# S
   }7 Y4 k/ T5 [8 f' p" _- F
  while(*p==0)p++;, n% O/ a- ?& W0 L
    printf("The last one is NO:%d\n",*p);8 J+ r$ Q' h- s% I9 U- K$ ~
     getch();
9 \4 t- k* V# @; o$ b# E: @. n0 a0 ^8 e* i9 u8 w& m$ E! _4 f& r
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;$ `+ j4 }; X4 O" z& o& n7 X$ t( |
namespace 又费马达又费电  S" I/ r. n: o4 i
{* C! N5 S! W8 y1 a( S
    class Program
( i& Y; ]. R! g, h  Y2 F4 Y4 m    {
1 i8 P$ N4 V* o; E+ r8 G        static void Main(string[] args)
1 w, {3 [& u! e' u        {
4 |8 V$ Y$ @2 _6 K; E            int m, n;' W. [, W) ?8 x. J/ I! R/ A/ }
            Console.WriteLine("请输入数组长度");
; v. q9 y# G3 w2 l0 E( {. K            m = int.Parse(Console.ReadLine());//m为数组的大小
9 E- o& v+ C0 t& V            Console.WriteLine("请输入要截取数字的大小");
  ~9 M0 Y! b; H: ~6 E            n = int.Parse(Console.ReadLine());. y$ v# B( F# p+ z9 \) C
            int [] numw=new int
1 q; B/ {1 l% d# q, B* l; j6 W# z, X, h+ e
&shy;&shy;&shy;;# N* f: {/ D. \
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数% K& k1 F  D+ W$ J
            {* F+ C/ @. C. R" N- [
                numw[j - 1] = j;$ y# s" }4 |6 \
            }
  X3 S/ v7 r/ e& j4 L; c( k            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!3 h6 W4 K7 E) C  g' h$ P/ Q
            while (d != m - 1)
5 _! ^0 \2 q1 [& E( I( N            {
- q9 ]( a+ |+ p* K$ i                if (i == m && d != m - 1)
- B- e6 _! Z0 ]$ T                {/ c, Z4 M" ~. b
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
: R9 y+ q. }' ?- e- h0 Y- j6 D7 g                    continue;% E' G5 j$ ^1 T3 y; k$ k
                }9 M, Z- A& [  l& G! G; a# y$ L
                else# H" x' o8 @) m5 j% G5 w
                {7 b2 \  E9 z4 a  ]$ ~' I4 x
                    if (numw[i] != 0)
( N' I. r0 z" M# s7 p: c* l, d                    {
& v  h" l4 ]3 n' ?& S2 s/ {                        i++;
. ^; p# f5 e2 U- K                        k++;
2 }" h; z- t1 x                        if (k == n), H4 c! N  C4 n, ?2 g4 x
                        {& p- ~" A9 z$ J
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
! A: {6 z$ Y. N1 C* s                            k = 0;
/ R+ c6 A' i5 v- o              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
7 b7 e$ J# g+ r% _# W9 C                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
4 f. n1 B- _7 @( r% l$ h/ D7 G                        }
1 ]1 a( r2 ~) U) [9 _& u                        else//输出暂时还没有改变数组元素的值
6 ]5 q6 W% G# w7 ^* Q  C                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
& Y$ B$ y% N6 t5 o$ H                    }
5 {% e, W$ U4 q- j% A                    else
! r& T, \5 ~, V  x% K( x                        i++;//数组元素为0,直接跳过,不计数。。。  {! Z- l$ q8 A; n
                }; f+ y: Y+ Q; z9 i* C  n
0 [# _1 o7 F# i$ K/ k& h

3 z: x: P$ g1 X7 T) U, S            }//结束while循环6 Q( n' w3 _  W6 R
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦  R4 t+ |9 {% [) A
           
& I7 ^; Q! }+ p, p" V; p2 N                if (numw[i] != 0)
% X% ?* t& X2 p1 Z/ `                    Console.WriteLine(numw[i]);: A: @% _% E% Y( }' t
           
) p/ S6 y3 ]1 v4 }/ ]/ E            Console.ReadLine();
4 q* L) @9 F+ q  y- q3 E2 f& W  F        }
& Z' o9 z9 |5 \5 P- a    }
) u3 l6 l1 X4 t+ z/ o}6 s8 l/ C4 {6 c5 i1 f' n
小甲鱼最新课程 -> 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-24 02:02

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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