鱼C论坛

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

猴子问题

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

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

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

x
大家好!
/ N# B0 k& r  j$ ~" r8 R3 w1 f这几天我在忙着编一个问题,我用了一种方法编出来!) o% A: n; f( H( N
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!+ z0 T6 ]  q1 \
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
$ e8 y, l* H9 w1 G
1 J) `7 {+ x: q. `6 _  `( M
5 e; @  q! N6 K  a7 ?0 Z, n& M
                            题目
' U4 k) s8 N+ |+ z* w( k" ~山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
1 }0 ?/ G3 x* r1 t3 O第一种方法:利用循环链表7 Z0 X+ W- H8 T2 q5 }9 S6 q
#include<stdio.h># N* d  K* V% |
#include<malloc.h>
. |, r" r% R: m#define M 8            //共有8只猴子: `+ m$ K# x% G/ [+ z3 P1 J
#define N 3            //数到3只时退出第三只
0 O$ j. V+ r7 jtypedef struct monkey
. n5 @0 I* s% M6 p{int number;4 |) R: S0 q% r
int flag;
6 p+ ?$ j9 H# u+ X! f% tstruct monkey* next;' b- h, W9 h" M& n& }
}MONKEY;9 `& W, S5 g7 _+ R  N, w
main()
) S+ J3 I" `' I! h+ q' F) P5 s{ MONKEY *head=NULL,*p,*s;
8 O3 @6 {" Y- }+ t  ]% i  int i,sum=0,count=0;8 L0 i4 k# \( n/ |
  clrscr();              //清屏
% Z, ~/ d1 X& N0 `9 U; ?, G# r  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存0 `, S1 Z# W/ g! w& u" c4 p
  p->number=1;p->flag=1;# M: x* |$ }7 m. T: V+ D
  p->next=head;. v. z) J$ I1 {4 A# d6 _: @+ h
  head=p;
  z! M% g& @/ `* _$ s  for(i=2;i<=M;i++)
! \. `. s! v" \! \    { s=(MONKEY *)malloc(sizeof(MONKEY));
% w) [2 k' C* N0 m4 s3 A     s->number=i;s->flag=1;
% K1 B4 R3 [4 S1 `; T4 \8 e     s->next=head;1 \. t+ H# f$ `$ C, r4 c4 W; G
     p->next=s;p=p->next;/ `8 r. x& A1 W7 k5 o
    }6 G% N* N  n& f" |# z
    p=head;* c  f# d4 G2 t& {
   for(;;)  U* P  z& ]% @6 Z
    {if(p->flag==1)
9 L+ [' }+ q$ R; u1 F6 a/ ^       count++;' j. R# Q; N0 X! K
     if(count==N)
/ V! E* Z* C) X% R# A        {p->flag=0;
! Z1 ^, M# B9 E- k7 l) J         count=0;0 O* f' f0 h' K# U! p( m  h" R
         sum++;}
3 m3 I$ I3 o- \/ F- T! E' [3 z     if(sum==M-1)
; k. u" e) n6 S* ]1 i2 n        break;( a6 y& h& B1 t9 w1 p  O7 e" W$ L
     p=p->next;
3 K  c0 m1 m1 R! k# r) i- F4 {    }  W2 m5 A' M6 o* b, w; E' Q- b
    p=/ G; P, Q5 k1 W3 g0 E5 g4 T
    head;
- I3 u) I& t, m$ M+ w  J5 d- x    for(i=1;i<=M;i++)6 J6 J3 m: v: j7 B+ B1 Y; y7 C
    { if(p->flag==1)( u9 l/ s1 G0 r; t2 R  e, D
        printf("\t%d",p->number);
8 Z/ D$ M# ?- F9 H6 z$ |" ~      p=p->next;, y6 n4 k' J5 k* }7 _. K; q
    }: s0 W7 [  L1 [& Y& J! m/ j

5 D; E2 ~  n. @% X
2 i7 n' H+ ]5 l! G+ X: y- b6 U
% P, j1 g+ m3 P( x}
% g  h* P& T: t6 U  v# x; f
第二种方法:数组) l3 L8 T6 c4 }+ j
#include<stdio.h>
8 O: E* R- i2 ~#define M 8# B$ a4 h8 n* V) ?. h9 v
struct monkey
$ Q$ w( g3 `+ a1 X% ]{int number;
- M" D9 c3 X0 y$ ]* r+ e9 Z, r/ ?int nextp;
: ~$ c) C  p6 f}link[M+1];# t3 S) L5 N& F8 t

3 o$ ]) Q) t% E. ^" Cvoid main()
* @- p2 j- H5 w6 ^: {3 n" @/ i{int i,count,h;
9 q; @5 r5 G+ H% ]/ ~for(i=1;i<=M;i++)
/ s6 `7 t. ~, G) n3 p' {2 w{  if(i==M)
9 R  S7 f! v4 T" J. E" r   link[i].nextp=1;# U2 i2 |% L. I
   else7 o, S3 ~  {- O1 Q
   link[i].nextp=i+1;8 P+ P, |3 z: E' f
  link[i].number=i;$ U: q) Z* n  a0 W
}
6 `- Z% M5 p2 K7 F: h9 lprintf("\n");
1 @( q4 X8 j: M7 ncount=0;
: ]9 C& @! n9 X% S; ~8 \, }8 P1 y& f+ Oh=M;7 F. C+ x! _0 B7 E; n
printf("依次退出的猴子: \n");
1 j3 p4 l( e4 Z3 ~# Cwhile(count<M-1), h0 s* q7 I, e! Z
{i=0;; l; X1 ]& C6 a* `% M/ }
while(i!=3)
8 C0 q8 P- N7 C+ j7 L5 Z{ h=link[h].nextp;% y  M; u  ^% @% m9 s4 T, ?
   if(link[h].number)
+ h) L2 e) x- j% }+ s     i++;}7 l9 P- l$ ]" ?2 v

; n/ U; q1 ?! F: J6 Z8 oprintf("%4d",link[h].number);) ]2 C2 f( _1 s
link[h].number=0;2 P# G- i9 c7 L9 m; j
count++;
4 t5 Y3 c5 u7 c/ R# u}
4 h- ^5 T7 U6 P# X& @3 W
4 W0 ], `5 U  ~2 \- @& q3 Zprintf("\n大王是:");+ p* W( a; Q$ Y# @& X2 w
  for(i=1;i<=M;i++)2 `  L2 c: e1 k6 {' t2 S. _
  if(link[i].number)
) |# f& {* J( X( x  O    printf("%3d\n",link[i].number);+ C4 [9 K) {4 L2 b7 |3 z: Z

9 m1 r+ p: O2 G) ~2 `
1 f5 W/ S5 e2 p% H}

' P6 V$ W& r5 e) A7 u# p; P/ P- J- Z第三种是普通方法for循环
8 I8 M  z* w9 P/ b! A
#include<stdio.h>9 h1 C8 h3 q: Y' }, l4 e1 I+ e
void main(); c: ?) l, R5 W% t/ G: t- {& I
{ int i,k,m,n,num[50],q,*p;
) A# x% V) Z) e- f    clrscr();
/ n+ E) u3 Z# t5 L3 w* C   printf("input number of person: n=");7 \, _/ l" V" Z& n( v6 m
    scanf("%d",&n);  |# G! Y0 ~2 w: [
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
' E/ y  n1 s% Z; a    scanf("%d",&q);' C3 E# g% z0 A2 ]5 D/ T
   p=num;
, s1 `3 V# X+ ^# r$ ^% @% m. e% G  for(i=0;i<n;i++)+ [6 `' Q: I% Z
    *(p+i)=i+1;5 U  z. B3 A4 O4 Y3 S0 ?. b
   i=0;& K  H5 G! V' y! [4 {5 @
   k=0;0 x  t5 ^0 @) V" e% i
   m=0;
/ W- E! F1 p* r6 V' Z  while(m<n-1)
# W' e' E. W4 d. o   {if(*(p+i)!=0) k++;
4 H5 E0 U6 ?6 W2 x' \- Y     if(k==q)- f0 u  E! T% Z1 j
      { *(p+i)=0;1 ~% L! p, H* y* [/ Y8 G2 |( Q! l8 M
        k=0;
  y  d! h/ r! e        m++;0 H4 P+ Y8 o6 h2 R
      }
# H' O( p. g( _. t1 ?; C8 b! O    i++;
/ r/ [9 F$ t8 |; L0 W! F    if(i==n)i=0;0 _- w7 U# I6 t( ]  E6 m+ e
   }7 c. ?, k! u6 [( h+ q4 v
  while(*p==0)p++;
9 Z9 M7 g. {: k    printf("The last one is NO:%d\n",*p);% b% M) P- q" R1 J9 I" M
     getch();
" X+ s* Y+ T3 {% h; b
8 _) y* z/ X! l9 R4 A7 U5 x}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;6 s9 r9 Q0 f. T% B) d3 ~2 y9 s
namespace 又费马达又费电
- p3 K& X0 a5 f6 u: G# z7 m{& v. z2 E% V  |& s& k
    class Program
% E& m" L2 V- c7 _    {4 Y9 _% z+ A  p5 g. V1 F
        static void Main(string[] args)
) z" f8 e' `7 v- K1 [4 c: @0 |6 r        {- z; m8 _0 P: r4 Q% d* {7 C( X
            int m, n;' y0 f7 o- h$ B& j, k$ z
            Console.WriteLine("请输入数组长度");5 d0 c0 ~9 |. Q5 J( n6 q
            m = int.Parse(Console.ReadLine());//m为数组的大小" L- Y( Q. ^1 r9 a
            Console.WriteLine("请输入要截取数字的大小");
8 y3 d  n1 V9 v! Y            n = int.Parse(Console.ReadLine());
+ j- b; U& B( }9 B$ P            int [] numw=new int) e* h4 H5 v+ l% v& e7 O

/ {' C3 J5 t  C, Z&shy;&shy;&shy;;
0 c" y/ l) l# l' T2 Z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数3 O, F* G2 ~' H5 c4 z, K$ o* {% Z3 b& j
            {) B$ Q8 {4 s' ?" ^* c  b
                numw[j - 1] = j;. K/ e$ X: h7 c, G
            }
' M- |& j  ]: h# V, v            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
  M- z* v6 C( D/ O& `            while (d != m - 1): t- V5 k' N% q/ i$ I4 _/ ~8 z7 V
            {  y6 v  J: v+ z3 X
                if (i == m && d != m - 1)! x) Q" Z2 h  Q1 P1 T# o
                {
  n' |9 A/ d# J9 B; X. A# o0 ~                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!4 j) J+ _2 w- h6 W6 R5 U6 h1 f
                    continue;5 _( i& x+ |7 \" d6 E& Y0 A
                }4 }5 v/ E2 j. B+ |) f
                else
, B) ~8 m" |. ?                {
0 _8 [' R9 v1 f                    if (numw[i] != 0)" U% }, H8 S6 q* K
                    {
8 U' {/ F4 T7 @; A' K# w+ U; ?5 \                        i++;
6 f; f5 d  r' c4 _9 A1 d                        k++;
. U/ P5 L8 r+ f; `/ R                        if (k == n)# k1 X5 ]+ }& E- r/ P
                        {8 X+ Y/ S" u5 T: n
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了. T) \/ B4 M  y% K
                            k = 0;+ s, U( ^4 i: E7 E* I& {2 H
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1  ?3 N, D% n" N8 ~
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);7 q( ~  S, c1 H. C- \1 w6 m
                        }
9 r6 L5 X) {* _& ]% Y$ ]4 c                        else//输出暂时还没有改变数组元素的值
$ y. q- [" {1 Q                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
; v, C2 \( {, ~1 E7 f: y. o                    }- ]6 s9 W& y- ]. p5 z1 {
                    else
+ R- G3 }: ^+ ?+ }& A                        i++;//数组元素为0,直接跳过,不计数。。。! |% m, A. B- q8 y7 U, d
                }
$ o4 F- t. T- s2 ]; L; V: I 2 _2 d# s& g& t3 m

$ {7 y9 G/ |" z1 T1 G; K6 M- c1 z( |            }//结束while循环
8 J9 |) X* x+ X/ Q            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
: j0 n) |. e) @/ g2 j2 ]8 R* H           ! j: w8 T+ Q; r) v& z8 F
                if (numw[i] != 0)/ \+ i6 o9 w( ]. A( E
                    Console.WriteLine(numw[i]);0 L5 Y/ _* Y' s! J6 l+ a
           
# B& o+ c% R- z5 @9 H; g0 e            Console.ReadLine();
& H, z6 b2 C6 E) Y. z        }
! @3 k7 B0 f$ l# H: X    }
! X( Z! W- Q+ B" K}
/ ~  y, i  S. m5 p0 S  d5 z4 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-1-31 05:32

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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