鱼C论坛

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

猴子问题

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

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

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

x
大家好!
; ?; `: n% c7 {' C8 x: Z这几天我在忙着编一个问题,我用了一种方法编出来!2 y' N2 u+ P" H# l/ t- b, |/ d
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
* O7 e8 E, M/ p9 ^注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
& Q# g: ^# C! S# \5 \4 X: y: p! {
% L& }+ C: y. \6 t6 v9 B9 F, }+ m1 B  \1 _0 R5 I2 ^. M
                            题目1 D) A, P: Q  ?9 h8 R( u
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。+ \6 t  p  |  f& N" D8 {
第一种方法:利用循环链表% d/ v9 L, q; m! w3 X
#include<stdio.h>
  g  H; M3 w4 l( X& z" R- S3 ^% J#include<malloc.h>/ X; ?' `3 R) i7 w' s  x2 s
#define M 8            //共有8只猴子
0 J7 ]' x% W6 l! G" n5 k5 U#define N 3            //数到3只时退出第三只& @* ?; W+ N# a8 s5 u
typedef struct monkey
; ~) w: W# a/ F) S7 ~{int number;/ t7 |+ x# X: M: Q6 l  _' Z
int flag;  Y- h, ~3 A5 W' v2 o6 [
struct monkey* next;
+ O/ b, R( f0 j7 i; a& n}MONKEY;% Z: t+ O$ R- x% C6 [, o) b' h. R
main()- i. ^1 W" X) s/ ]0 Z1 ^: C
{ MONKEY *head=NULL,*p,*s;
* Y0 U$ v' q3 S) s3 e  int i,sum=0,count=0;
+ q% H$ u/ A. I7 g( d  clrscr();              //清屏& `  t/ o6 i; U1 s( ]% Y- O" G
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存# l' Y; S7 x6 ^0 H$ i/ s
  p->number=1;p->flag=1;1 Y) Z2 O" f# p( {/ |9 ~
  p->next=head;
3 e( Z/ m5 A! _4 i- X' x0 S4 _  head=p;
" A+ x8 U3 r7 S* }3 s9 I7 m+ r' Q  for(i=2;i<=M;i++)
, A1 y' |  R4 C, ~# X& x' y    { s=(MONKEY *)malloc(sizeof(MONKEY));
, m: r! |. I) `/ X0 w7 D2 k     s->number=i;s->flag=1;
0 ]; U+ _% j9 O+ Q  d& n$ R     s->next=head;* x, q. e* q( f4 n, E/ i2 p5 r
     p->next=s;p=p->next;$ }' P: d( Y; j+ `
    }
% J- F( G7 x- G* F2 e& j+ [    p=head;
# I( A) a3 P5 f" t   for(;;)
# A5 }( c, {* y: Z: A    {if(p->flag==1)& u. c& ^" `/ A1 j- B( z4 x
       count++;6 M) |, v9 y& f+ M9 B: K9 A
     if(count==N)* b/ w3 Q, v* T! K- s( ~' O
        {p->flag=0;
7 `/ }/ K- x. p& g  [1 d         count=0;; M! m* ?; v+ F0 B- C
         sum++;}! j- P5 x5 k; D, y
     if(sum==M-1)
6 V0 v6 o. E5 j3 [        break;
- f! S: O3 W* {3 Y  c( v4 ^% C: n2 j3 Q     p=p->next;
, S2 ?0 f- Z3 V7 P2 U    }( N5 ]! F) ^" S+ h* D( W/ Q
    p=
1 d4 x' |, b/ N. h+ I1 J    head;9 V, u1 R$ ~  M, g3 S* {5 `/ ?! M# P
    for(i=1;i<=M;i++)9 O, D: f) D$ a* j2 v
    { if(p->flag==1)
$ i# q. }# h. g: G$ q        printf("\t%d",p->number);
: N: \- _+ J5 K7 @% c' x      p=p->next;
0 T9 V0 m& F! b    }
! X- R- o! ?6 |1 |, }& o! x: i" v. u% a  U% g( N5 u

: P; O3 c$ I  ]/ A9 Y6 E: a  g5 l# U4 }$ L, e' [: y
}
  e3 Y. P; ]: k2 d7 i3 l
第二种方法:数组
# C. f# C- w+ G  i2 I% W3 d3 R#include<stdio.h>
- Y. @! T; L* r* r#define M 8
' y4 |' ], h! b8 d" Pstruct monkey  _9 @+ y- l/ V
{int number;
8 @5 t% ^6 ^" q) nint nextp;( N7 W* ^. `. _0 z( f# O4 y1 Y
}link[M+1];  |) o" ?/ M9 @" N0 A
" ?( X4 v4 k/ D0 N, h+ F7 ?+ b6 P
void main()
7 v. O* Z9 y% j' i{int i,count,h;
: M' g( u6 @" n: d# `for(i=1;i<=M;i++)
$ G& e8 D( s7 i% p( |{  if(i==M)$ n* k0 T. H7 X
   link[i].nextp=1;7 a% M2 I" Z2 S/ V3 N5 x
   else
2 g; w( x7 \! i! n! y3 `/ P4 r. z' }   link[i].nextp=i+1;
; z% t  q2 N8 |/ O7 ~* l% ]7 z0 P  link[i].number=i;8 U. |; \$ X& X, B7 J
}) L( q1 `1 \- [, [$ A, }$ ?6 g& K
printf("\n");
) F. S# |1 t5 L$ G1 g5 jcount=0;
: b; e/ y0 ^- e% v  Dh=M;
( J) M: p# G" }printf("依次退出的猴子: \n");' m% a6 M! l' F
while(count<M-1)" d3 s" x9 i( }* P$ E
{i=0;
! M$ Y3 z" N' U8 hwhile(i!=3): P! q% ]2 a2 e% {9 i' j5 j; _
{ h=link[h].nextp;
. m" {+ ~5 \3 Q- j8 a! L$ B   if(link[h].number)
/ y% L" q) I8 T0 v     i++;}9 s1 Q6 ~1 R4 n! ?4 f

3 M0 K! U3 ^. D7 _2 L9 l( O6 bprintf("%4d",link[h].number);9 o+ n+ d" a) _5 o" c
link[h].number=0;; n% H1 s+ M9 G7 H* j
count++;- Q( i# s7 l; [8 b9 `
}
$ m, N6 O2 U$ R; t- Y" c! ~/ d1 P' e+ a/ O
printf("\n大王是:");
. Q4 W% o! q' `1 m" N  for(i=1;i<=M;i++)
$ p0 L; M6 l7 ?/ m! Q  if(link[i].number)
3 f4 i  [5 r9 {* e3 T! I3 t1 A    printf("%3d\n",link[i].number);
( c( w3 K! Y$ _4 b/ k7 i4 t9 g* q) J! T/ B6 s

/ y6 z! i$ m5 _$ w7 |9 Q}

' ~  H& u0 N9 y' v第三种是普通方法for循环

- Y4 G1 H/ ?1 b7 Q) @1 F0 A: ~$ g! i#include<stdio.h>8 J/ N7 l6 u  b5 V. W% o) }
void main()
+ f$ a1 Z% P( f6 R5 O. ^{ int i,k,m,n,num[50],q,*p;
- b3 r7 K: Q1 F& j8 ?    clrscr();& V" c4 S& ]2 H: u2 f% C
   printf("input number of person: n=");
2 i8 E' k% T' o% G9 O3 }    scanf("%d",&n);
* Y8 u4 Q& p1 ?' f4 _$ bprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
9 ~' y9 l! l$ J* T. `    scanf("%d",&q);; J2 [7 Y) r$ {$ c! I: n
   p=num;, M/ ^/ V( B  Z# q/ e9 g
  for(i=0;i<n;i++). ]; H9 \* M9 |/ s4 `1 `  }
    *(p+i)=i+1;- k9 S' a6 q$ W) v4 H
   i=0;3 T1 K, E9 Y/ d" e7 A
   k=0;
# s1 J. a1 h# S  E7 J   m=0;0 p( P, b' g5 X3 \0 v+ _5 a9 h. Y
  while(m<n-1)& B9 V# w! q) L" c" b
   {if(*(p+i)!=0) k++;
9 c7 v* x$ ]3 h     if(k==q)2 z2 B7 q" K) z2 z6 x6 ?
      { *(p+i)=0;
/ a: a' o  \+ E% I5 q5 P# ~        k=0;
, e$ f4 V3 j- r6 [6 X        m++;; ^0 a. h; h3 o; {5 x
      }7 ]+ \! r, b. a- g. L, \# i* e  I0 A
    i++;
2 O7 p* i6 M7 \/ v4 j1 m% c    if(i==n)i=0;( R- [1 G6 t: ?6 ^5 e5 ]" \
   }
+ B' g8 U9 [0 l' o  while(*p==0)p++;
. K8 I7 F# e6 [6 Q+ m, z- w    printf("The last one is NO:%d\n",*p);
8 k8 P) y2 R6 M& k" g7 |/ G3 S2 ^5 X     getch();4 B1 c0 X2 i$ Q; n6 A' x( y& W- V
& C. g  h: P8 @) y% a3 f7 n7 @
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
  b/ \" q0 a& n7 M9 Y0 Jnamespace 又费马达又费电
5 Q1 m3 t# [/ t9 O5 M; {{0 C- r5 P0 o% K7 ^; \" B
    class Program
  N- x7 I; ^, i) \- L, H    {
% ]) w3 F8 ?8 [: M0 |$ W        static void Main(string[] args)
: Y4 L4 a. N$ m# O3 }7 s& f/ p        {% e4 R  M* n& M7 }" S
            int m, n;; V: t- K# {4 q2 B. V
            Console.WriteLine("请输入数组长度");
# y) V  z4 T) [# r  V            m = int.Parse(Console.ReadLine());//m为数组的大小3 J/ n6 t4 T) c, ?# Q6 o. q
            Console.WriteLine("请输入要截取数字的大小");
4 |5 m8 X5 `1 \2 ]            n = int.Parse(Console.ReadLine());
! C3 H, H% J+ S. ~+ X            int [] numw=new int
% X8 o9 Y2 O5 w' Q, R( j: t  E) i& s2 V* }2 c/ a
&shy;&shy;&shy;;
; s; J$ l/ m+ b9 V' g4 ?/ |: B            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
# l$ D8 x/ m" E/ z. ~            {, ~. D/ q  p* b0 R
                numw[j - 1] = j;
; T) A0 w! R) ~- ?: \            }+ r( @2 X" |6 D, _, b
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
4 b& t$ p/ a( P8 a6 s+ p            while (d != m - 1)2 U5 i8 ^( ~# z( S9 Y6 y
            {# Y4 R; V, J% i. |* l1 b
                if (i == m && d != m - 1)
/ U% ]" R0 S: D8 m, `% l                {
! |7 g) O! D: ~3 H! i9 n                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!2 h  }7 O4 x: ~) L0 R/ i
                    continue;
- C" a' L" X% m3 f( e                }5 K; H$ A0 z+ a, F- m7 v
                else5 Y7 j( N6 k) Z) ]2 Z  c
                {
" w5 `8 H; |8 c/ q                    if (numw[i] != 0)5 T# x) P' H% o! b. I$ K
                    {% v( \4 z& N/ L) Z
                        i++;; f7 I* r' B: b9 ^4 o; Y! E
                        k++;
0 U) d8 E+ s  x/ z1 n4 |                        if (k == n)
" U4 z  `5 s1 _$ O# q8 K6 R                        {4 [& T# c' [  w, i
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
3 w6 V) H6 e9 W, o  t# t$ k9 t' }                            k = 0;
0 e/ K/ d- D" I+ n& u. T              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
4 R4 k) r2 O, h5 ?, `. I                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);' c3 b0 s+ s0 S9 L. _+ i
                        }
: {; p! z6 ?8 a2 n7 B8 H                        else//输出暂时还没有改变数组元素的值
6 E" ?2 h# [9 W5 c% [: ]                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);' O  \* _* z; G( Y# w; @
                    }1 a$ x5 p1 H, I; r( D* Q3 ], J# ^
                    else
$ G; y( X1 D: _/ b3 X5 F& m                        i++;//数组元素为0,直接跳过,不计数。。。
9 i% v* r0 h* \9 L! y                }6 x7 q- G. n5 r7 X& R
& B- P+ P4 t# y
: U# C: B. Z+ b( y
            }//结束while循环
4 P6 S0 `9 \% U8 `/ x/ z            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦  J% F+ ~5 G% J* R5 _- i. H
           5 v+ A5 G  a3 w" z- X* W9 B
                if (numw[i] != 0)
! l) G  n: e& j                    Console.WriteLine(numw[i]);3 n( \( O( ]: B/ p8 @
           / D, t8 N2 B! n+ q, e$ R
            Console.ReadLine();
6 Y- |( {" _2 n. z* d6 T3 G% M" e* y        }8 s/ `- ?& w/ ]- P; D
    }
2 Z, K5 n) l3 U2 f& {% T) a& k; \}
8 ?" v  ~+ V% \1 S3 M; d3 g
小甲鱼最新课程 -> 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, 2025-7-6 09:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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