鱼C论坛

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

猴子问题

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

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

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

x
大家好!6 w5 C2 o7 `8 V6 [
这几天我在忙着编一个问题,我用了一种方法编出来!! ?! K% D8 G+ y) m( r0 L2 k( w# a
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!3 v# k0 {' H! U. q
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 7 K; R! P5 x# U# T
3 L7 P7 n9 j, W

, p( k  V! X/ `& x( r
                            题目
7 F$ }( F& s& T( q, G. t1 e$ ~6 a山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
4 t- ]5 y1 [6 f) N( m1 C第一种方法:利用循环链表
# z2 f; o, W; m: {; s6 d8 |#include<stdio.h>( l2 K, [' ^, O2 d5 J2 \# N( k- x6 f
#include<malloc.h>  m5 k) a8 o/ N) B
#define M 8            //共有8只猴子
8 y( z, ~* s: C- [) ]#define N 3            //数到3只时退出第三只) R- C4 V7 ?& Y! c& [' Y
typedef struct monkey
; @1 `" y6 ~$ C9 ]6 ~% `/ P2 T- I1 Z{int number;
  Q- U  V' H9 j% z7 |7 _9 kint flag;0 X* e, r$ n) c  q- s8 p4 i# k9 i+ g
struct monkey* next;
! h) c" W) r2 g& w}MONKEY;+ t! K$ k$ E" T6 Q- b7 {) M: A* L
main()8 X/ ~8 ]$ K8 B' v5 K% H8 h
{ MONKEY *head=NULL,*p,*s;
$ s0 D3 m" {/ N( T% z% x7 R: K  int i,sum=0,count=0;
! H  J+ v: T) Z; s1 A' s! j& G$ [  clrscr();              //清屏, n# B4 ~) C0 @9 r6 R- A
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
7 [3 d* ?" ^, c% X; h/ u# j  a  p->number=1;p->flag=1;
0 O8 x- `' N' ~/ s5 \  p->next=head;
# A3 [  U# C% o# T# Y: ?- ]  head=p;
4 z9 c$ l- n: P8 I  for(i=2;i<=M;i++)5 I7 o2 J. T% f% W# D6 a% I
    { s=(MONKEY *)malloc(sizeof(MONKEY));
, a) {% ]" j- _8 ]/ a# i5 Q$ n     s->number=i;s->flag=1;3 s# R# J, n2 P4 J8 N* n
     s->next=head;# |; h8 s' P) U) U
     p->next=s;p=p->next;
; }/ a% I, w( s; J    }2 K( n: g. F, k. N
    p=head;
/ O/ n) h; b$ r! P/ y5 }   for(;;)
. V$ c/ Y) z$ o, i8 k* f: ~    {if(p->flag==1)4 ~: p+ Y9 |( i. \
       count++;
8 k# I6 P2 c/ ^* ?: o, R6 h# W9 T     if(count==N)2 L8 k8 X2 ~; g! e. b. Z
        {p->flag=0;  i4 W9 g! |. T6 j. [6 L
         count=0;/ Y. y" f  C& P5 ]5 r
         sum++;}) u+ P% _8 m2 Z, c
     if(sum==M-1)4 u" i- A% |) X8 e
        break;- @7 J- g1 A' i7 K* E9 ]$ d0 ~7 p
     p=p->next;+ v0 e- W& F; u1 g% x) r; ]3 a) K
    }
+ V* H& i6 ]5 t6 _9 `* |; `    p=8 Y( S5 B9 b' u! |
    head;
7 ?  }* \* n5 S, T    for(i=1;i<=M;i++)
$ C! N; m) i7 Q" {+ m: \    { if(p->flag==1)
1 [' w0 {: m* l2 I8 k        printf("\t%d",p->number);+ ?9 ?/ n6 g" t' h2 e9 K
      p=p->next;1 Z( e5 r* Y4 b' _
    }
1 S1 K7 t3 E7 w3 `9 Y- D  u
8 U# j: K. i& R, z
6 Y3 ^2 z9 @  }5 J7 b0 K, t/ w1 N8 W3 o+ t! l
}
" q; [- L3 S0 p# {8 C, i/ U" M
第二种方法:数组
* ]  G/ N/ |+ v; x0 W#include<stdio.h>3 C$ O! ~) B. t
#define M 8: r& H8 R* m% E/ @/ }* B
struct monkey$ ]; E: T3 i7 B- B" a* S
{int number;
9 E' l6 U! K" L9 [9 M  m" B4 P( |int nextp;- I4 r( U5 G" _
}link[M+1];: M0 F1 b" e5 P
  x$ t, y: B2 O
void main()
6 w9 @( b4 J  s6 _{int i,count,h;- f, T( v1 v8 C. N4 h) T* n$ M" |0 K
for(i=1;i<=M;i++)" Q, o: F5 Z- R( u; r7 Q; H7 ]  [
{  if(i==M)
6 ?$ T* W! g  x   link[i].nextp=1;* F* F7 O" \. U" R
   else- s/ W6 ?! g; t2 V# t9 j4 T
   link[i].nextp=i+1;& H9 Q$ W+ }  f/ {* J- Y
  link[i].number=i;2 O; w7 M4 _" m0 l% I  t
}4 S: t3 I8 J) x. }2 s# f
printf("\n");
4 j. l! d  r5 u' b7 \- Ccount=0;- p. @; z# d& \) S) A, ?
h=M;. v# ]$ v  N+ _' ^/ W# I- S& D
printf("依次退出的猴子: \n");
' O! ~5 k+ X/ t' O+ [2 Ywhile(count<M-1)7 r4 h- r$ A5 p0 u2 W# p* |
{i=0;
5 a2 h) p6 E. D! r- b( Qwhile(i!=3): q# F+ f! N% l- K  x
{ h=link[h].nextp;
" F' K, f3 S/ M3 q. p+ R1 A   if(link[h].number)
' {" V, S2 ^/ B% ~9 x8 T- y     i++;}4 x2 a$ a7 W# e& }

- Q' T/ a. s4 u8 S) ^8 \  o4 S9 oprintf("%4d",link[h].number);
3 y' z* s9 J) n5 \# i. `& Plink[h].number=0;0 c# a) R+ i9 \3 S+ k
count++;
# d. @" A+ {0 i- H4 o0 \% d}' G4 \2 e$ p  _. e5 I5 ?6 ^, {

% G( p$ D0 w; s) L! k9 I$ pprintf("\n大王是:");
$ D" r3 w- I6 ]' F) \' G- ^- H$ G  for(i=1;i<=M;i++)" i+ l: H7 F) X/ c
  if(link[i].number)
8 e0 t/ }1 P3 i$ u' }. w* u    printf("%3d\n",link[i].number);
- Y# o" Z1 c# H$ X7 n9 v# ~3 R' V# c3 V+ h2 R
% k0 K& d6 G  {% c
}
& l& d& y9 d+ R0 v/ j
第三种是普通方法for循环

% o/ U9 z% L+ n9 N* G( Q. \#include<stdio.h>
1 Y7 U, {2 q, u$ s3 cvoid main()
! [8 Y' r5 R) J# D5 p{ int i,k,m,n,num[50],q,*p;0 z, U! r5 D# \, x
    clrscr();
5 d. Q) n- b' J8 ~) n- N   printf("input number of person: n=");
) K+ I5 I! x  n  X    scanf("%d",&n);
( y* p$ L% o, J' T" h) E6 }* j' lprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
: a, P# D$ f$ P' b    scanf("%d",&q);
5 l- d; u0 W1 E' q   p=num;0 V4 u% V4 J' J, `( y
  for(i=0;i<n;i++)* M7 c) P1 L7 Z8 p$ A8 V3 f* z
    *(p+i)=i+1;# n# g9 s6 d9 ^9 s2 [- F9 }
   i=0;
8 M9 {4 J) \; e   k=0;
* j% ~; x  y5 ^" B+ Z: q( J" r   m=0;
" R& \! Y; Z7 G* |6 L/ _' Q9 }  while(m<n-1)
" [9 }' s6 X& i" Z+ M/ Q   {if(*(p+i)!=0) k++;% I8 [: |9 S2 N" q7 H% n$ L
     if(k==q)
) Z5 O! P  G- \6 e7 W      { *(p+i)=0;
' A: p4 J( m" {        k=0;, i* x4 s# I% z; F8 d% F" k+ t
        m++;5 {8 q% t0 n+ Y  U
      }) }2 F% z& k$ Q7 U% O" m! t: v. V
    i++;$ z9 D& p0 V4 N  e8 [
    if(i==n)i=0;7 B; O+ i/ `1 a+ m& G! x
   }! @! Y! U! t% k" y; C+ M2 j
  while(*p==0)p++;' ]4 A$ ^# M2 d  h
    printf("The last one is NO:%d\n",*p);3 Y0 f8 e) t$ r  U" e6 D0 [
     getch();3 s3 B9 V7 e0 z  `8 o/ g* A* L
  \( |8 |; a! u$ Z1 Q( p! X
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;8 x+ U( V# g* t
namespace 又费马达又费电  k9 ^& P4 H8 V
{
" F# D( v! K) m5 i- Y* O1 |    class Program
" D* E2 m0 w5 c' V    {
0 j3 @: N/ @6 \        static void Main(string[] args)$ Y0 M  J4 ]" ~3 J9 `4 W/ v! {) h
        {. h0 L- o& ]* i7 ]+ K& ?! z$ }
            int m, n;
9 V; s* O! D- j9 E3 b  [) Z8 {            Console.WriteLine("请输入数组长度");
* G' C8 U' O9 V- z6 m* `/ r, D0 n            m = int.Parse(Console.ReadLine());//m为数组的大小
! c3 s- _2 h. U4 _; b1 ^& j/ n" a2 R            Console.WriteLine("请输入要截取数字的大小");  H: c: W# {7 B# s+ e, r
            n = int.Parse(Console.ReadLine());
1 A8 b" Y' i( m( `8 \            int [] numw=new int+ [2 M& q9 w+ k! z0 X5 Y
) t5 u: g8 v! t2 {+ ]) l
&shy;&shy;&shy;;
! z3 T2 C3 G) o2 q  d$ \            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数) M0 t% U2 _9 X! {  p5 k
            {3 U& h& E0 t/ X/ V. R& G
                numw[j - 1] = j;8 t! a3 S  x3 Z4 z3 o
            }
$ v& m; ~- q# t5 a* t            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!7 |- N6 P" t; P2 g
            while (d != m - 1)
& q( f+ `, }! T; K3 ~( m: _0 G            {
; t* e4 r: X9 ]" H5 v                if (i == m && d != m - 1); {, q( `* F/ b, ]
                {( M5 n" m8 {$ d) r: ]) |& Z
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!* i, B* l( C1 Z+ Q2 ~5 s
                    continue;
& C- p6 G+ ]( b                }
% D# Q1 b" f. T, r& J/ _  V, w* r                else! [% x# H) n: p, |2 [0 G& B/ E9 g6 I+ a
                {4 ]7 t4 |  M) X" ^, @
                    if (numw[i] != 0)
8 {. b+ R4 L# S  }' A8 N$ i                    {4 T3 w- k% ~9 K5 m6 G0 M) Y
                        i++;
! }5 i8 B3 L8 D1 Q, l' ]                        k++;
" }5 \* ]& R. v8 ]/ r& |                        if (k == n)* n  N: r" S3 @5 k
                        {9 T: ~! c+ I$ r
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
7 k9 `/ v0 n% R- q/ ~( x6 C3 f                            k = 0;# O7 Q6 B( e/ Z. ]) K* n: o; _. D
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小10 P9 B+ o/ W9 ?4 `$ C
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);  ?# A! Y- t; q2 ^; z% e5 N
                        }1 l$ t5 A6 q, ?" @! S
                        else//输出暂时还没有改变数组元素的值" i8 i% ~+ A% a7 A
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* o5 z- y/ F7 V( D! b( o3 ~3 q
                    }! Y1 h8 v3 S7 J* ?3 d; F# G0 z
                    else
# z# F8 D  q0 O) \8 X$ M                        i++;//数组元素为0,直接跳过,不计数。。。
& f" I- m% C2 @5 r7 C                }3 C$ c5 D. T( x
: M) l3 d$ R% q0 m

& E1 ?' C* L; G            }//结束while循环' t4 n4 J! o3 j$ K' `
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦3 {' s' _4 h0 L
           6 x% ^' _5 z1 c5 Z' f
                if (numw[i] != 0)
* n8 ~2 i% o7 S+ f: b6 Z# H                    Console.WriteLine(numw[i]);6 g; [# l+ m7 x2 _* M
           
8 W0 U7 G! x& j& }, s$ l3 F8 C            Console.ReadLine();& w( L5 K/ l  a
        }
3 w5 v, o; L/ t    }7 k1 ~5 A  e; J5 e6 [3 l
}0 i8 O( k7 F' H9 e- F
小甲鱼最新课程 -> 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-6-28 06:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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