鱼C论坛

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

猴子问题

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

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

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

x
大家好!
) d1 R! f6 b; h这几天我在忙着编一个问题,我用了一种方法编出来!+ m" r6 j9 o% t" M7 x# `$ E9 X
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!* b2 m; H6 ]& Q- |% _9 |: l: y
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 + [( h$ ~) K9 @) O1 K+ A

) a, i& N+ {. h4 Q9 {
, P8 O/ n6 w# Z; j9 ?  z# F& N% b
                            题目
3 C% ]% T6 F% b( F0 L山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。, D) P+ H% L& _& E3 z4 T
第一种方法:利用循环链表5 J4 T! a. G. z% U* q/ m
#include<stdio.h>
4 p3 ~: Q1 Z( q" N#include<malloc.h>
( j: Q/ m- x; p3 c4 N% Q3 U#define M 8            //共有8只猴子# T  b4 Y1 G( C$ c
#define N 3            //数到3只时退出第三只
) s* l0 M& z8 |4 J; b& o1 otypedef struct monkey
5 y; ]5 T( Z* O3 l2 @5 {' ]{int number;/ W. }, |0 c/ B6 }: r% U$ d
int flag;( D* |1 L' ?  ]/ x
struct monkey* next;
  K) i! ]) m( f' G4 Y: }+ s}MONKEY;
) e6 G; |$ n$ r: m7 e) v' Ymain()
. x8 Q! P7 z; m. g4 g$ n2 [9 O{ MONKEY *head=NULL,*p,*s;) G; V( c8 T  K& O. b  s- }9 B5 \5 V
  int i,sum=0,count=0;  r8 E4 V. I; i
  clrscr();              //清屏( a2 l" _! T9 r; _0 D8 S
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存" g) G; l( k1 {& w: @" k# D
  p->number=1;p->flag=1;
4 ?) z5 I( B# i  p->next=head;
- }) b5 k2 x- Q2 d1 b% g+ e) r) ?  head=p;
( X/ r# ~* ^) F  for(i=2;i<=M;i++)
6 Y/ ~. F: M" t- _; {1 \: r    { s=(MONKEY *)malloc(sizeof(MONKEY));
" |* M/ K9 I) J- {     s->number=i;s->flag=1;
% K' }; v1 _( K     s->next=head;
* F# @4 _' `. z& i  C     p->next=s;p=p->next;" k& M' ]2 n8 j$ q
    }" F& I' Y# a" T3 _
    p=head;" l4 x8 [, A  D9 T
   for(;;)/ G4 t( E$ @+ ]* u; e2 f! k) U5 M+ Q
    {if(p->flag==1)
& H1 {# F8 M! e. H( ?       count++;$ A* s$ J1 z0 a( L1 J" s) b( w
     if(count==N)
! D& w/ W* @4 n, j* v        {p->flag=0;
8 R: J) K, i  Y% t5 F         count=0;8 K8 `! u$ A( l1 S: C8 T8 G" Y: y
         sum++;}
' n2 I7 _  V4 X  r     if(sum==M-1); b, ]! P& t  F4 A$ r
        break;
5 z/ H' G+ f2 m4 K2 j     p=p->next;- v. g# o( X: S" y7 d
    }
0 J% C  {" @& X' D6 @4 C) Z    p=/ Q1 z" x" E# j1 U8 c
    head;, d. i) s8 I$ K1 R9 J+ P
    for(i=1;i<=M;i++)
+ R. V- B( P! e/ f; R: s    { if(p->flag==1)
" h5 v1 ~/ [" y1 p. x; n        printf("\t%d",p->number);0 r$ d4 e0 G- g/ Z: @
      p=p->next;1 g& O" p% A$ C. a
    }
+ ]! p4 D+ Q1 c/ F/ |
( [- }: w- o6 g- m/ S1 t7 ^* @( c# j4 ~
- A) C$ h+ b! L# o7 E- h6 J% w) {
}

. p# ?2 W( f  `6 ?$ _; z9 o+ |第二种方法:数组
& I& y- M% A/ Z#include<stdio.h>
- `0 J5 X2 z; C) M#define M 8
! O0 [% K/ H9 Fstruct monkey- p# Y$ I! [2 _! D, c* g
{int number;+ i+ s7 Y" f7 q0 [6 C
int nextp;
" X+ q0 b: N1 k7 n5 N0 x}link[M+1];
* b9 Y, J/ x: ?4 c& v4 y: F" ]
, A' s( X  g, U3 jvoid main()( }9 c' F/ f" m; k$ S, ?; D
{int i,count,h;! H$ e! O% P" c
for(i=1;i<=M;i++)1 J. z) Q- K) i5 _- y, B% g
{  if(i==M)
$ M' m: z5 S6 Y: W" H- y5 \   link[i].nextp=1;
+ W& N4 {" X" F) m) q3 k   else9 C( Z& `" e) G% {
   link[i].nextp=i+1;
$ a& V& i! Q8 D! a: A: D1 u  link[i].number=i;. O3 B7 P! h5 i2 m0 U
}
- Q+ o  G. g) a  P& m8 D0 ^; I6 b% Jprintf("\n");
7 Y" V, ^+ J$ m+ m; Xcount=0;2 }8 w) \9 R! E/ p$ o7 J+ Z
h=M;2 U) ]0 K' m" b) l
printf("依次退出的猴子: \n");5 W! d( m- [. T
while(count<M-1)) n8 u1 Y' w! d9 z# H
{i=0;
$ D, `& R' B' P1 A5 E0 l2 Ywhile(i!=3)
* @8 C: Q; P- l& t% Z4 x{ h=link[h].nextp;. B4 K% c( G# p2 Z9 j$ W
   if(link[h].number)
; N( A6 H  U; v) e7 j* C     i++;}
2 A6 `! g- j4 `: g8 R6 c  g6 x( q# F: J- h  d3 b& L# s8 w( r
printf("%4d",link[h].number);
! D3 _8 Z2 V0 ]( E3 ?! jlink[h].number=0;
: V1 M4 H- w9 j8 z$ kcount++;% o( h! n8 L) P" K
}# V2 x& g% a- \5 Q, f4 }( [" O
/ X; M# y$ z  Q" S/ Z
printf("\n大王是:");" N$ A. V; D. S& `& x: [
  for(i=1;i<=M;i++)
& {1 D% Y& ?. D# ?# B3 e8 @  if(link[i].number)2 t) D% L# [1 a, x1 Y  a
    printf("%3d\n",link[i].number);
, J3 y& w# ]% @; j; r& J$ h; h: l: Z
2 E+ k' X2 d* {
+ H& z! ?( z. K' f$ `) a}
( V. {. [: i: \: L& Y' M' s% Y! M
第三种是普通方法for循环

) |  Y# t  i' g& f' x#include<stdio.h>
2 H$ V- F2 N, |" N7 vvoid main()+ g7 E" |* `+ ^. f
{ int i,k,m,n,num[50],q,*p;/ A) E5 g5 p, U# V% [/ X8 u
    clrscr();) c# _0 Q8 y4 m# c' g+ k
   printf("input number of person: n=");
( O! M) z2 ~4 {. W    scanf("%d",&n);: J2 d( F+ t, f
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
# E) n# Y2 y' V' c    scanf("%d",&q);- Q0 v! a* e! t, h
   p=num;
* R2 `2 P+ O4 S- j  for(i=0;i<n;i++)
( V5 o5 D! y0 X* e' B" D    *(p+i)=i+1;
) O7 w) U& F; a) H2 Y( `   i=0;  m- j$ l# y' n& C+ p* T# ]) |1 t1 p
   k=0;
7 _6 F( q7 E- S( ~( h( a4 A% `4 H   m=0;0 ?# R4 X: t  @' @2 Z1 D9 x
  while(m<n-1)
. W: g6 P0 x9 Z1 @, q0 Q! l0 X   {if(*(p+i)!=0) k++;
$ d: l) U; a) b; B1 m! i6 O2 m! x' S     if(k==q)
$ W7 t; U5 M2 q/ U      { *(p+i)=0;
7 n0 W5 q' {4 [9 Y4 P' f( e        k=0;" L7 s3 h) @; x) t. f0 z( Y" T
        m++;
4 _" t% `! e" Q      }; q% i& e  Y+ D* r5 d- z
    i++;
% Z9 f- w1 G: b% I    if(i==n)i=0;& c" C3 r0 i( [' Q8 B/ ^
   }
* `- _3 [8 z8 t- h0 v  while(*p==0)p++;+ H2 I1 V# i  B) {) S# e
    printf("The last one is NO:%d\n",*p);
/ Y3 a; D0 z  i4 d     getch();
! A3 i! F$ B5 i6 u9 A- {7 n, `1 V' O  Z, Z; I
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
. p" u; l6 D4 H0 _7 d' E8 U2 ^namespace 又费马达又费电" c9 H- U7 \7 C/ h& s
{7 b2 g+ I5 S' d6 E. Z+ r6 g
    class Program; `6 H! C" e6 I$ d) z4 y, O
    {- k7 X2 l9 b# d( U5 O* m8 C$ C0 _
        static void Main(string[] args)
1 l$ f- h8 x: x5 L: b' b3 p& W        {, {5 A3 ?9 \' Y; C* M2 [
            int m, n;
: y9 x# g6 I, }7 H            Console.WriteLine("请输入数组长度");1 R  Y% e  m- w. Z9 z* {
            m = int.Parse(Console.ReadLine());//m为数组的大小- g( h: d* a5 L: Q& H
            Console.WriteLine("请输入要截取数字的大小");
7 y9 K" \* _  H% \            n = int.Parse(Console.ReadLine());
3 K/ C$ e+ K2 k1 o0 X# y            int [] numw=new int
: G) `) Q! {5 q$ c1 n4 V( X! H  i8 ]
&shy;&shy;&shy;;" F' n0 k7 [& U, g9 X- e2 M4 N8 d
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数( ?5 ^( c( p8 Q4 ?
            {
; I4 e1 k- p+ ?, s( o                numw[j - 1] = j;
# _7 B- N6 Z5 f) {8 Y            }7 j6 |5 [! m3 W' b9 @+ g9 L
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
' j$ j/ |. h9 `' `6 [0 c            while (d != m - 1)' Z% L3 a% `7 o/ E  K
            {7 b9 R# @2 ^$ F% e# @
                if (i == m && d != m - 1), l& {$ X- J; {7 U  j
                {+ I! X* Y. z3 q1 w4 e5 l2 E0 J: D
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
  }+ o. T* K' X                    continue;
/ t- F( q' Q. r4 j& H4 d                }% E( V9 F/ n+ f6 z7 S
                else: c# k/ f) T( x8 |
                {: M& v2 k% @3 {8 ?% |* v% Y% G0 p
                    if (numw[i] != 0)
# R- t) \$ T* C7 u. r% j                    {
$ P" C/ }: X5 [2 X5 D                        i++;& I) x4 U: u! k2 d/ t7 a
                        k++;( O9 T% i1 T& r, E! K7 U
                        if (k == n)3 M: d8 S" Z0 r- c6 L3 j
                        {1 g9 O9 m! N$ G7 M) [# H8 W  b
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了% X3 X: w, e9 B* M" ~/ w6 q
                            k = 0;3 s8 F0 a. g$ V
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
1 m5 [  {0 m" L3 P                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, x+ w4 `1 W9 p' ?                        }3 |  V5 x* K" l6 S+ {9 C2 c/ _
                        else//输出暂时还没有改变数组元素的值
4 t, t2 [. m4 A/ ?                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
: Y, L$ z4 |2 \; i3 g2 A- v/ e                    }; `9 _0 u+ z* t( f$ e2 r0 r/ x6 @
                    else0 L% t' e" y5 A* ~: T1 R2 U2 H' ]- c
                        i++;//数组元素为0,直接跳过,不计数。。。
% D; t8 y. Z& e/ {6 f                }* u( l/ D+ K% J1 w& N) J- @

! T5 D, `: f4 X. e, d- G3 l3 l# C4 o
            }//结束while循环+ |0 v6 [6 h1 u+ b
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦% V6 Z/ p; c% a! t
           & C* w* |, y3 B) v! m' N
                if (numw[i] != 0)
+ t/ g% \' W' I                    Console.WriteLine(numw[i]);
3 U* o  o# V: s           * a& S2 ^) j' K  B# d) }
            Console.ReadLine();5 e8 ]% W$ w. Y) e6 R7 w* l" ^# O
        }
% F4 W, r% S! O. ^' ~    }# k9 w) p5 s" I3 V1 ^6 K4 t
}
2 @: o/ B6 `9 d1 Y( h) w! h
小甲鱼最新课程 -> 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 20:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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