鱼C论坛

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

猴子问题

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

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

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

x
大家好!
! _; |- o/ c7 k1 b7 y9 T( E6 z! h这几天我在忙着编一个问题,我用了一种方法编出来!
. D. j' c3 _1 K. D但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!2 p( E& o2 a$ o' D# a+ B  g
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 0 b2 k6 B' t6 x* P1 }9 S$ x% r8 ]
& \+ t% v4 e( L- h' t7 o

4 N3 {8 i5 x& V
                            题目
. f& W6 d( e9 R3 ~" b& h山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
; E# e4 f) `, W! l# x第一种方法:利用循环链表. M1 I/ p6 x# v, o" m# e* ]2 k* S. c8 B! b
#include<stdio.h>* P% c5 B0 P4 e( R
#include<malloc.h>
1 ~+ L( o* L* O! I) h#define M 8            //共有8只猴子; {' a& m9 H2 W6 F
#define N 3            //数到3只时退出第三只
. J4 b( s4 a0 q* E+ m9 }typedef struct monkey
3 L- U* c4 D& \# q3 P4 T{int number;6 N# _( {/ F1 K; C9 }0 m
int flag;! N" I9 t$ T" ^- A: C. V
struct monkey* next;* G7 ]- f& J5 v' R! ]0 Q
}MONKEY;
0 Q$ }( A, b# d7 b2 H; Ymain()
3 q/ d5 A! x7 t' h. R2 A, S/ S" T4 n{ MONKEY *head=NULL,*p,*s;( R3 X, H3 \1 M$ I
  int i,sum=0,count=0;/ L: I  _- @, q$ M! ]
  clrscr();              //清屏% Z7 p  f/ O$ G# j) [( @( B
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
& |7 N; H( ^: e4 B  p->number=1;p->flag=1;
; K% y3 X; G  |* O  p->next=head;
# q2 l) M9 F6 {  }) s! W# p  head=p;7 Y. I/ a. D+ Q- E* P; B0 H- w
  for(i=2;i<=M;i++)
( D: b1 f- t  _5 p3 F4 P7 I    { s=(MONKEY *)malloc(sizeof(MONKEY));
7 [; Z; G' G7 x! t+ f     s->number=i;s->flag=1;
# X7 V4 u# e( B% ^) f# T     s->next=head;4 N! T' g" A) n. c, t
     p->next=s;p=p->next;
# Q7 B5 M7 }- r    }3 |+ J5 Z8 G6 N" a0 O$ k
    p=head;
2 s" y0 a- V" N; `   for(;;)- D. x: F4 ^/ j- R
    {if(p->flag==1), A: j, D1 @# E4 y
       count++;
7 M# P& s' d/ j" b     if(count==N)2 z) `; H- |/ J/ B, N) _
        {p->flag=0;
7 g5 |: L7 ?+ z' K& ^* H         count=0;
' Z9 K# p$ W$ b/ A7 s5 \" I' h* J% M0 D         sum++;}6 m- G  \4 B  X/ |" c/ z8 u$ p. }
     if(sum==M-1)9 L4 }* S! X& q; t1 c: l
        break;
/ D$ M$ I1 W% p8 F2 P     p=p->next;/ X: f. z6 z0 y1 g$ b: @
    }8 W) }2 q, }$ \' b% w" x2 U
    p=
/ Y$ [, c9 t0 c- D    head;
6 C' y) L( |# p0 T3 Z/ M    for(i=1;i<=M;i++)
& C8 u3 O, R- H7 ]8 h, C    { if(p->flag==1)5 ?* O( |8 X. ]' c; `: K8 y
        printf("\t%d",p->number);, k0 S6 w- w- G3 [* U
      p=p->next;
$ T" A1 f6 f- @    }
- P6 v( p0 x4 q9 w. x9 D+ Z+ x/ \! }, a- b2 O* D; }1 m( l
2 F+ S/ z6 V7 @4 S  k

% ~7 I* Y6 _! O  m. v) w( E/ B- N7 y}
- ^- l, c  }2 @/ C* X$ u% ?1 z! T
第二种方法:数组! k+ R) u4 T$ g& k* y% h# ~
#include<stdio.h>
+ M) a( j+ o7 e#define M 8" V6 K6 ~. o4 J6 I5 o
struct monkey
) Z# u3 w# U$ A, I{int number;3 \3 g0 P/ n7 X( h0 P9 v. o
int nextp;& y7 F8 h: K) Z! T$ T+ b& r
}link[M+1];3 R1 S, b& W$ R7 L+ [2 T, n% R+ O3 M

% P7 ^2 d" m$ t6 Bvoid main()
4 r+ q' W4 ^# S$ I' {# R{int i,count,h;6 N0 i' t- D, d" k3 `
for(i=1;i<=M;i++)
0 _0 j* f7 k: s# U{  if(i==M)% w/ E0 t# t& {0 X* q. Y
   link[i].nextp=1;
9 D) ^/ o& f% d3 @( U! p  C   else
" k$ @# j% a7 h0 ^) I   link[i].nextp=i+1;. U$ ~( D% j: h/ S! b
  link[i].number=i;
- p- p+ u$ N1 h}( `; \% ], h$ p  `2 Z( T- k
printf("\n");- p. {" [( |+ {) r9 a! l
count=0;
8 p# J* t- O( Q8 b$ j! Hh=M;
9 l, h. `% {4 y/ }7 qprintf("依次退出的猴子: \n");* v* L5 b- r& h" f
while(count<M-1): D- m0 E5 c% W- {4 F$ F* V
{i=0;
% \- J  G0 k% ]  B6 W: F4 x7 [while(i!=3)( [# \# Y; l0 o- y" f
{ h=link[h].nextp;1 V: R, \2 e: _
   if(link[h].number)
( v3 I+ t3 U6 u: m  O     i++;}/ {  W% y& ^- B. i: Y  M  c

  ^: p5 C' Q3 w- E9 Tprintf("%4d",link[h].number);8 b! x" ]+ b8 b8 r# B+ F
link[h].number=0;
7 w$ {* W- S9 U* ?2 Zcount++;+ z/ n9 Q5 u- f$ g3 B# S& }& O
}
) K3 R6 q7 M5 M7 G1 V. A" s6 ]+ Y
: _  D( `- d+ H, p9 Q: d: d$ vprintf("\n大王是:");
, Q, M2 G9 h( u/ ]; I& x, N+ O  for(i=1;i<=M;i++)7 A* S& F4 U8 c( b9 Z
  if(link[i].number)
& w* i5 }0 y/ j0 @- {    printf("%3d\n",link[i].number);8 ~, ?; B5 p- T3 l! x
* K1 Y: _2 C/ b2 X! G& k% w+ h
: Q0 Z. [6 s8 g5 k* b6 s2 ^2 f
}
/ t# ^( S+ M/ v4 {
第三种是普通方法for循环
% G9 m! j/ m' H9 C. D* n$ L! H
#include<stdio.h>
: z4 t1 R7 F* p* E; @; v$ E; Ovoid main()
. T- g7 N: }0 |3 h2 [7 j1 X5 ?  E, Y- B{ int i,k,m,n,num[50],q,*p;
) f, c  w6 I2 A7 a: u" E( `    clrscr();
+ ?8 V8 k8 L7 b9 q0 f   printf("input number of person: n=");5 ]0 J- X7 ~- }- d
    scanf("%d",&n);
- D5 O& P/ B& D2 f3 Uprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只7 r) ^5 o9 g0 ]9 M; V
    scanf("%d",&q);$ {4 J4 T1 _/ Y' \; x6 l( u
   p=num;2 h6 p' v. p1 w& F
  for(i=0;i<n;i++)
( Z( s8 P8 W; G+ {4 L$ }% \, ^    *(p+i)=i+1;
; i8 @7 r" }$ y2 N1 b& }1 g$ c   i=0;
& ]( x* w) k* m: ~* E0 D   k=0;( i( V* u& o6 ^
   m=0;  J" n2 L3 Y+ Z
  while(m<n-1)2 q9 w) g; A8 J! T0 h
   {if(*(p+i)!=0) k++;
* r( E& q  `6 w, B4 P$ m" y8 ]     if(k==q)
4 P; W# Y% m7 m, E! ]      { *(p+i)=0;
# X" `4 i) s- @+ s& q! ~. m        k=0;
* \/ a+ J) I2 A0 L0 F, U2 \        m++;5 }/ H) r) Q# ^) u0 w. s, }% Q
      }
% f5 W$ t/ R! v+ e8 E$ t) i2 o    i++;3 N8 o- J6 X, R' P# ?' W5 i4 s+ D0 Y  e
    if(i==n)i=0;
' n& P$ O! i7 _( o: v   }
0 g: G- W, O' d' y% q  while(*p==0)p++;
& x/ O# v& }% U% ?* X8 a    printf("The last one is NO:%d\n",*p);
! O# w6 Z6 H7 ?+ v; V     getch();: ^0 _- E& D: _/ g1 |/ I
& k% S* d/ g0 o. j8 o( _5 U
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;7 c2 P; _/ Z1 s7 ?- f* ]
namespace 又费马达又费电" t% t: o: W/ S9 Y2 m
{
+ Y- w+ ?. e3 d* K; ]/ ?    class Program
, c8 {3 V6 K. T: b! }; Q* t+ i    {
# `( s# N2 ]* y2 J3 w        static void Main(string[] args): S7 F  }2 s- v
        {9 l- c% c7 Z: ?; ?3 G+ |! ?4 b
            int m, n;
, D; x* @0 L& t5 G+ O; X1 ^( J            Console.WriteLine("请输入数组长度");. Y) X- X, y, E
            m = int.Parse(Console.ReadLine());//m为数组的大小. O+ V: W, \1 h: |. i( C
            Console.WriteLine("请输入要截取数字的大小");
% j  E6 _9 ?" h  ~3 I0 F- o1 |$ r            n = int.Parse(Console.ReadLine());5 R$ e  G2 L( ~$ d. `& x
            int [] numw=new int
0 B; Z) r* L, h! }/ m( E
9 e3 z, o# I/ ]) Y  |7 A: o0 E2 d&shy;&shy;&shy;;7 D0 N3 c: ?- k( G
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
9 g- B7 c- A9 G: W            {5 V' n0 c, N: n6 d. c( t
                numw[j - 1] = j;
% W. R+ A1 k7 Y" J/ `            }
& c$ u# O# Q( w# Q            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!2 I" s: H( |' b8 |! A, @  D0 O$ @
            while (d != m - 1)
' w! T8 l5 e7 g' A, F: B            {( M4 y5 A: a$ A3 h; v
                if (i == m && d != m - 1)& A: M- @! J' V% l
                {# U3 [, }* v8 C/ l6 |! a
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!' i" ?' m" f- [5 i; b6 P# w& E' F/ \& U, K
                    continue;) z! }* d9 _1 z& p
                }- n; j: ^  G1 D: i  {" g
                else
. u; @& p1 G* V: U# V                {+ w( p) N/ k# e
                    if (numw[i] != 0)
3 I- ?1 }3 ~8 O9 `' e1 n1 i7 P                    {
3 U, p2 I* |& b% O  o2 \/ [0 ~* \                        i++;
+ W: R( k8 e: {9 X* C) C                        k++;
) ~  h7 s! |% I                        if (k == n)- Y' h+ I+ @  b8 }1 S
                        {# ~8 c( m; ^- s5 J
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
- e4 R( ]2 f) }; W/ X6 F7 S9 C                            k = 0;
( d) O4 T, I2 B: D              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
( x9 H' m% m4 D  Z2 t9 n5 X: m+ O                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
  K; |) q1 ?( X  t" F7 _                        }8 g* f. q- b9 w5 L7 B* w4 o; G  H
                        else//输出暂时还没有改变数组元素的值
/ O' [& a- n# R. |+ Z                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);! `/ G( e" k4 A+ @+ O
                    }+ k5 d6 s! ]- I8 a9 Y; @3 [) j7 t
                    else
; q& ^7 O4 U" L' D1 j! m* l0 t: Q/ ^                        i++;//数组元素为0,直接跳过,不计数。。。  H* }( O' |- \" j: B1 K3 \1 W# V- c
                }
6 E( u5 W! A  [/ y
! q: O5 p4 S# V  ?6 `$ j5 R. V* h. r4 b! z& j5 t, N7 G- y" X
            }//结束while循环5 D3 U2 @+ i4 S9 H
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
) L' E! X: y( v3 f7 q           
2 E! s: h. R/ C! R+ `8 j1 ]                if (numw[i] != 0)% {9 x3 ]3 ]% h+ i. G7 n
                    Console.WriteLine(numw[i]);
# X/ L; u2 a8 p- ^+ v           / z; g' q+ }. |
            Console.ReadLine();
5 S% R( F: Y8 i6 x- n/ t( n        }- s6 {2 D: q+ J
    }
' U. h. G9 l8 Q% Q}+ J  {& v. {0 a# P0 r3 I+ M5 b
小甲鱼最新课程 -> 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-10-3 04:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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