鱼C论坛

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

猴子问题

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

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

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

x
大家好!! S, g/ t+ f  C% w' Q+ q% _$ ~
这几天我在忙着编一个问题,我用了一种方法编出来!
. M, H1 D. j0 Y( |& T但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!3 j1 x/ H  g7 H) @+ M7 l) \
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 e! ]5 b% K+ P! g2 T2 r! b3 R1 S* S9 @6 F

7 ]; f8 n7 B6 v0 Z
                            题目+ A. V- r! T* A, z: W
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
( u% `: U) ~8 y- u, z4 e5 Z第一种方法:利用循环链表( g& ?- S( I$ V1 d% _4 o
#include<stdio.h>
2 s4 U7 C) \* ?$ `7 ]! w* e#include<malloc.h>
% ?  t/ [5 Z( X5 ?#define M 8            //共有8只猴子
' _5 L' |5 e# w1 N* D6 q#define N 3            //数到3只时退出第三只
' d& }* O0 v# g1 y; s5 Gtypedef struct monkey% u% _/ Z* H6 j3 A; G& ^; u
{int number;2 Z6 \  A+ Q: e% v/ v
int flag;) f% i" e5 w4 K& E
struct monkey* next;
9 x8 M" H$ r  _- W- m* I}MONKEY;
/ A4 G  f% z# V$ W% H* mmain()
0 X4 J/ e3 C, v8 a{ MONKEY *head=NULL,*p,*s;4 p2 Z% k/ L7 K' C+ h3 r
  int i,sum=0,count=0;
  }& W! C% @/ I$ [  clrscr();              //清屏
8 U2 M  f) W4 v2 S& m  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
# Y' N% H9 T) m3 Q9 C0 @* \  p->number=1;p->flag=1;; Z1 U. F$ j5 f
  p->next=head;% O0 d' J0 u/ j( H
  head=p;. k. `, J% a1 e# G
  for(i=2;i<=M;i++)) h+ I7 g2 Q0 S1 y7 k# S! F
    { s=(MONKEY *)malloc(sizeof(MONKEY));
$ k* x% Z9 Y2 N) h6 [+ l     s->number=i;s->flag=1;
* O# e( R0 c4 w2 w' l1 S6 l5 M     s->next=head;- {! }+ B1 g* x! d- t
     p->next=s;p=p->next;
! M. H7 a0 S& W    }& w' P/ q2 D1 o+ O
    p=head;
3 ~% V5 o8 n' {  @2 ^3 w   for(;;)+ K, G, S4 L! Y" L' x4 J) X
    {if(p->flag==1)  N) k% F& t# m& x: R* |# {
       count++;) g- A: l1 \; H% ]! F& k& G& w5 |; l
     if(count==N)4 F( N" M/ z, c. E+ u6 J$ E
        {p->flag=0;
! I  N7 H) j- [" N' l7 u& ^         count=0;. i" D$ `8 U* _
         sum++;}1 O' }% J7 E" T: A/ {/ b6 Q
     if(sum==M-1)8 u( C- D: K+ p7 L
        break;
; L$ z) u4 Q* y6 r, F; A8 G7 ]2 a+ n     p=p->next;
4 W  i% T3 k+ a3 G5 m* n    }
. n0 Y& q, N  V1 Z    p=
  i8 E) X( s* w! a    head;
6 c  O! K# A3 y% w    for(i=1;i<=M;i++)
" U5 \6 l2 L! U+ [: s: Q- ?% o    { if(p->flag==1)5 n% o* w: K( D6 R& \7 Z1 G) F* V
        printf("\t%d",p->number);7 [9 u( s; W* ~5 C
      p=p->next;; H# r2 b% p; {/ R4 y7 {. B
    }) q5 j% O# i& V' w! M) V7 X

  O$ M; s8 h3 g2 r) ~: T8 T# V4 u2 s. }( L/ q

- H7 V) K. e! @" e4 Y}
# {0 Y! }0 I, }' Z3 R6 @
第二种方法:数组
( o+ x  @" V$ t5 K0 x#include<stdio.h>
) \* ^% x& P4 a! K#define M 8
+ d" Y' N2 w4 r, e) Kstruct monkey
& j; L6 e, `2 K7 n% a; m' ~& [5 \  q{int number;
+ c; J# K9 T+ l- c' u2 m% t1 iint nextp;
2 ^9 X( c4 ^$ y6 s6 d}link[M+1];; z( K! ^4 t9 a3 p- R; A

& Z4 v$ p7 ~7 ?1 j! k2 H1 ~2 M/ Ovoid main()) M3 _# e8 Q/ Z7 }/ f
{int i,count,h;7 V+ A( x0 d/ E  ?7 M& ~& ~
for(i=1;i<=M;i++)1 Z5 V: U0 _) g7 b
{  if(i==M)
4 a& P, U, o/ M   link[i].nextp=1;
) R, W( A4 C! L; t   else
- r# y9 c/ H. u' f7 j   link[i].nextp=i+1;
! c! E7 q3 U5 P' ^# ?. t; v  link[i].number=i;
, I! w2 g2 t; T: ~2 ?}: Q8 F, R! |/ ^. [- H% j
printf("\n");4 u9 L, L1 n% M4 I
count=0;, i3 a  ^) C, P7 @( w1 E
h=M;/ a. Z4 t1 z) R: h, ^6 ?( `% I
printf("依次退出的猴子: \n");
1 ~0 n; R! U# A; k% \. x( r, I1 fwhile(count<M-1)7 {& v  N7 m  j. ]8 X$ S
{i=0;
, H5 `1 t* _. a! C  `while(i!=3)
) s% h0 Y0 r+ r' {* K6 {- T{ h=link[h].nextp;; ?, `/ Q; u* t6 a" S4 k! @: f
   if(link[h].number)
( d0 F' S' ?8 ]& I     i++;}
3 p2 z) }% {: a, O" L. o" l" h; p# _7 b
printf("%4d",link[h].number);
3 \4 v0 h/ B3 Q% t4 h  H4 slink[h].number=0;
* q8 D$ f% A- Y' Kcount++;
5 o0 t! K* }( x8 x  ]0 P! t( [! \}
: K8 T$ C% Q. S" K" B8 o. E2 v0 [5 A  o0 y+ h+ i+ v9 i0 M  D$ p
printf("\n大王是:");; s' w9 _+ H9 j4 U' ?% i. g  [
  for(i=1;i<=M;i++)2 _3 j1 W& S+ A* s& [
  if(link[i].number)1 e# q& Q% f# @2 I' h/ f% D2 C! R
    printf("%3d\n",link[i].number);6 |- e! O- w; }$ @1 C

3 O: g+ o, R/ E1 U7 p- S# Z8 f# U2 y( F
}
- f7 a5 e9 ^% y. U) R
第三种是普通方法for循环

' l0 X  v# O$ w7 h8 [#include<stdio.h>
$ A- u& ?& y! S/ }. Z' Qvoid main()
$ a" H: q) L3 }0 Z! X& G* @" b" _{ int i,k,m,n,num[50],q,*p;! a; K' y( a2 Y" y0 Y, f5 p; Y
    clrscr();
% F- S, r8 }; d9 K* Y   printf("input number of person: n=");% {6 ^, f8 v* o! ~& N7 s4 I
    scanf("%d",&n);
2 t& x: O+ N7 m  @& y) [% o1 |printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
) z- R/ g5 g- \" f* X, R    scanf("%d",&q);; g, H, `$ l# I, _+ e
   p=num;3 R/ U! T/ u# K$ B! z( L
  for(i=0;i<n;i++)
. a1 I8 D5 R  e' i2 W    *(p+i)=i+1;
- t) ~+ X5 l1 h2 E3 Y* J: ?3 G   i=0;
, k! j5 G0 F; d& p   k=0;8 h. O: L7 J* z8 |  o' d5 z: v
   m=0;' J" {0 Z; e* ~) v( y5 D$ c
  while(m<n-1)
' H: l" o7 \% E* A9 R6 h   {if(*(p+i)!=0) k++;+ p0 S6 S* }# t- u9 A
     if(k==q)
1 I/ z1 l# B6 s      { *(p+i)=0;! @) @1 D4 I, I8 K" ^4 P
        k=0;
- |1 V; e) G  K# l% U        m++;$ W4 V" l$ c9 D+ j4 l; Y
      }
% G6 p/ l8 E1 U2 R    i++;  G# j3 d* T9 S* o: B7 y) O' d" \
    if(i==n)i=0;
9 l' h1 q7 N: w$ _; Q" g   }
0 D/ {' K6 ^  ~& D9 [  while(*p==0)p++;
) \: {, m& g# Z9 W: X7 a+ v: }. n    printf("The last one is NO:%d\n",*p);; `5 c* z! c' h1 K: n; T
     getch();
6 w+ D, a1 o7 A1 F3 \2 Y
' e) c" {3 h' [- _7 Q) [5 x}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
. X( \/ J) O3 B. znamespace 又费马达又费电: t8 [* ~) t! i1 u: K0 T( m1 [
{; Y+ F" [8 d/ P% r% S3 a# n$ p
    class Program) n1 a8 q0 y9 u- `! F3 p
    {
& t4 h1 ?3 K( z1 u" S7 O2 Q' O        static void Main(string[] args)0 J3 E4 }4 x# ~. a2 x* X( O
        {
5 {) }) D! |, k% c; v            int m, n;5 ^" a/ h8 E9 z
            Console.WriteLine("请输入数组长度");% q( _8 F0 |- Q% r3 B) X
            m = int.Parse(Console.ReadLine());//m为数组的大小
* y9 s) ?/ g3 r% o+ o% U* w            Console.WriteLine("请输入要截取数字的大小");
! }6 Q/ v2 ~5 c8 Y            n = int.Parse(Console.ReadLine());" q* h" |0 k1 ?, {
            int [] numw=new int3 X& v3 T. c8 ?9 T- T$ @0 E

; w: H! c% h2 J: ?&shy;&shy;&shy;;1 z2 a3 |, J/ _5 N7 |& q
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数! m2 s# S4 s1 C
            {
# b1 L8 T' B# d  W5 B                numw[j - 1] = j;
' D, D2 G- r7 U            }
3 p2 e' ~2 S" l, O/ {            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
4 Y6 w  C0 r( r  T' i            while (d != m - 1)$ m5 P8 @# i( @. p
            {0 i8 c$ O+ r2 N4 Y' {- M
                if (i == m && d != m - 1). e- i, ?4 f* C: c$ ]; R5 D( T
                {/ g  l. A7 G+ c- _4 k" ?
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!( l6 y+ ]- y7 J
                    continue;
0 H8 o+ i  d4 ~( B$ m/ j* [                }$ W: p, @( j+ k8 `& V$ c: p, A
                else4 ^+ p/ L, c' z
                {
( h7 K4 Q( w; a                    if (numw[i] != 0)2 j3 I* F- A4 C- q% c3 S
                    {
  ?# x; v5 r; l                        i++;' N' J, t+ K: R
                        k++;
: q7 c. r0 l0 g5 R8 K                        if (k == n)  |9 t& l( g3 b  L
                        {
3 k0 ^, B* G. A0 F                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
8 C+ w2 i  p- e5 U                            k = 0;/ ]3 y& D" \* U1 I% d% {
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1( ^2 A9 s% x8 h* F  ~
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);- R& |' |- H, m. b
                        }
/ G" @3 s$ n/ @) {7 Z0 g. \( l" b                        else//输出暂时还没有改变数组元素的值
7 C& Y: b8 {! z- M0 S, p( \                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* k. f4 I9 o7 M$ f
                    }1 v& o6 H* Z  h2 ~( ~' H: G& V
                    else* z4 O% X9 b" J$ e5 u# M
                        i++;//数组元素为0,直接跳过,不计数。。。( X2 r( Y" P# M# v9 d) L) ?
                }: A  }2 L& v; m$ c" x% ?- q8 p
6 P& v. ^% y7 d/ B9 L- m; \& T" _

3 E5 C; |; p% X4 W0 F0 Q            }//结束while循环7 h- i8 q+ r# n" A% g& f
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦7 G4 p/ |% m8 f1 q. V" H
           
; w' A1 ~2 ~5 Y4 s7 G                if (numw[i] != 0)
' F: L- f5 \( r" v. \                    Console.WriteLine(numw[i]);. R3 p" H4 G' Z1 `6 N
           % P( M0 Y% J+ o8 k4 f
            Console.ReadLine();+ u$ u, A, T2 n, [
        }
) R% _" [7 S. x5 ]5 u- I  b$ O    }
( K! t+ D; `3 K1 ?1 h  ?% U}( ?$ k* g6 K4 _( K4 |6 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-20 14:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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