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

猴子问题

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

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

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

×
大家好!# ]3 q# a, a1 M6 _6 h  ^- p6 F
这几天我在忙着编一个问题,我用了一种方法编出来!' ?& X7 h2 z: j; Z- o
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
2 \. H2 O5 e7 Y# [6 W注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 6 t2 r8 _! I2 q6 d; G/ Z# O
: l% a# q) a) ^/ o) I
" l. H- B  S+ U( P
                            题目
: C" ]- n  {/ n7 B山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。8 U2 }' r5 E9 }
第一种方法:利用循环链表: O2 S2 w$ ^0 p
#include<stdio.h>: A1 E4 P. l, b7 K( l
#include<malloc.h>* Q+ h- x1 }+ \
#define M 8            //共有8只猴子6 U  n: v' L5 P& L' Y1 g/ v9 A
#define N 3            //数到3只时退出第三只5 K$ V7 f, K5 B4 f0 [. d, J
typedef struct monkey
3 s1 Z$ l8 |* v* U{int number;
3 q/ m5 l- X$ tint flag;* J8 h9 g. {2 T* T8 c6 E& ~
struct monkey* next;
% L+ e; c* p8 v! |}MONKEY;
" ?! Q  U; F5 ]* z9 |main()
9 a8 c/ P: y" q0 K" Z7 a& g! j{ MONKEY *head=NULL,*p,*s;. j! Z; M& {" d* q5 h5 B* R7 y
  int i,sum=0,count=0;( G( z& T- S9 G$ G$ N- u
  clrscr();              //清屏
4 j( s" S3 z* O: @, w3 s  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存  ]5 X6 n" X0 ^* x8 q+ N
  p->number=1;p->flag=1;
; R2 }* H, R. G: A% N1 {  p->next=head;$ S) N$ K4 r/ |
  head=p;
7 O7 V) g' ~! C: X' f' U  for(i=2;i<=M;i++)7 e; w: G- ], `' E; ]5 d+ a( F
    { s=(MONKEY *)malloc(sizeof(MONKEY));& ^' }3 @( k) m' ^) U' l
     s->number=i;s->flag=1;
1 |. Z4 z5 \' N" I3 f: ?) w6 ^) L     s->next=head;
: F# u: X% {* z6 S9 Y! ~     p->next=s;p=p->next;
( ]- q, X0 N+ P- p: C6 h; u    }
, z; V$ v- L, t    p=head;
0 \6 P3 M9 E/ F  Y8 b   for(;;)" [6 z0 X: f. k$ t( A2 H
    {if(p->flag==1)1 }$ l- S  M. g1 E- Y/ F, k' Y
       count++;
) B: D3 R  E4 B* S     if(count==N)4 N3 M% |: t6 ?  r7 P$ W
        {p->flag=0;
  z1 m  A7 A  b* V$ R) ]3 k         count=0;! y  t. x5 Q+ G: I% ?% k2 {, a7 z. T
         sum++;}/ v* d) B& r; n  z
     if(sum==M-1)
) E/ y3 c; }6 r- t9 ~+ S1 |: X        break;
" Z7 S7 }5 `$ _8 \     p=p->next;
' v( u9 `2 E/ D, A7 E    }
3 B3 V7 F4 Z# P6 _3 k8 _- l    p=
1 L$ M6 e- |4 m3 L) Z+ O5 y- @    head;
, d( B* f# @1 G* C    for(i=1;i<=M;i++)% B' A. t% h. w% g$ u" Z
    { if(p->flag==1)& O! f4 A9 v+ a+ n
        printf("\t%d",p->number);
7 m4 Y$ q2 H# t: b9 E      p=p->next;) ^' q- n0 z* x! p2 H
    }
/ l$ x- T2 D; R. Y1 K4 U6 C- u4 R) x2 n- e' B' @8 I

. V' k* u( Z3 J8 a' A8 E9 e+ C6 \5 o9 ^* s) b& L7 I, u9 d
}
% V2 u, ?" S' r
第二种方法:数组
+ S& y) l! j) m( Q& i9 s#include<stdio.h>
, s1 m; U- R1 O7 E/ S& E#define M 89 U# [; B2 g( k% F
struct monkey
  x% p5 d! \# W6 v) ~; i# W) @/ W{int number;# M5 @5 N( J  j+ K
int nextp;. Y6 @! K8 ]( X
}link[M+1];* @' d6 W8 C9 P3 M/ |* T
) _$ b9 e+ }. _, ]/ |
void main()- Q& C+ X# D7 q& n8 U; q7 Z- [
{int i,count,h;/ b2 a- W. Q3 Q- Z" }
for(i=1;i<=M;i++)
/ q4 P/ x6 K) m" I- G{  if(i==M), U! Y3 A6 w+ Z# ^9 l5 ^
   link.nextp=1;5 ?+ ^) {! ]# `6 P' l
   else6 M& l9 `3 K" ~8 i7 ~
   link.nextp=i+1;; w2 s, |3 a5 [1 O& H/ H0 s" O6 c" z
  link.number=i;. N1 G3 Y7 o. \
}/ I& d& s/ i; A  |" Y
printf("\n");- T/ ~( y+ [$ |; u0 T" `, u- e1 K
count=0;
* c- ?1 @# a& g& B+ Xh=M;
( z$ w8 q: `- R9 S9 a5 Jprintf("依次退出的猴子: \n");
/ B" H% f: o. F$ i8 K7 ywhile(count<M-1), U3 s1 K9 g7 |- ~5 m. {
{i=0;* T0 l& `4 s+ P9 q8 s
while(i!=3)5 J! n4 V; R/ U9 Q* A
{ h=link[h].nextp;
" V$ F. v: X* H7 J& O2 S   if(link[h].number)
( ], \# |1 ^& T! M9 V     i++;}
( C% A* ^1 n8 h+ u: B# z) F
, T, Q* y$ x, Q+ h2 o6 {printf("%4d",link[h].number);
. d5 [: b) ^' U% g$ W$ }% i/ Nlink[h].number=0;9 y2 e) x' x# z( ~3 l
count++;
1 ^/ p" S  n0 I}( @5 W+ G! M, U4 `4 X9 X% _4 H

0 l' P* T9 X, [  O# }. A3 qprintf("\n大王是:");
/ \. x- \3 z% P4 p) m9 ^. z, @/ Z  for(i=1;i<=M;i++)
! p5 b' y: ~0 [" A" Y. w  if(link.number)
* S7 C2 c+ w5 o) f; m( O8 F    printf("%3d\n",link.number);
. |. ~# U. N) c0 @3 r3 F5 m& y: Q! k2 p  }; d

* I0 D% D# B* S2 u/ S}
2 v; q6 Z; m8 q8 D6 g
第三种是普通方法for循环
6 A6 g5 ]4 j' g
#include<stdio.h>
5 z4 r0 I: C/ b( |( Lvoid main()) @6 G( c- k: ~
{ int i,k,m,n,num[50],q,*p;
; H  a' n; }5 Y7 b+ T8 H    clrscr();$ i, O& Q4 ~2 X' Z! |- {
   printf("input number of person: n=");
6 x* j' ^" L( ^% r* o6 |    scanf("%d",&n);
6 X/ G+ D, a0 F9 Z. _' M. q) `printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
4 I! Y8 D% _0 ~  f4 x) X& W7 S    scanf("%d",&q);4 \) n/ C% S) G) G: R, O
   p=num;' t0 R, {; u# K* g/ D) Q* b( I" }
  for(i=0;i<n;i++)0 a( E3 p8 o1 U  c' {7 Y  @
    *(p+i)=i+1;
& x+ ]* w7 U7 n! O1 s' G   i=0;
$ m' u* @7 J7 t) f5 C" Q  h/ [! n0 o   k=0;
& i% a$ W9 o  ]1 L0 t! j+ u- }   m=0;
+ ~) G& H8 Q6 E  while(m<n-1)1 V- y( v- a9 m- n4 w3 ^* p
   {if(*(p+i)!=0) k++;( i* c9 ?0 q, x* s5 Q- A
     if(k==q)
" t& _3 k4 y6 a" {8 r* _      { *(p+i)=0;- \0 z/ |4 }; j, w5 j) e0 K5 B
        k=0;5 v4 U4 e. r* U& a- `
        m++;
  {/ @) q9 ^) x7 s# F+ A8 l1 e% d      }
  a, w  ?; ]" \. }1 Q* X    i++;6 U  I  s( F. ~
    if(i==n)i=0;' v6 v( O7 ~7 t
   }0 F+ {" y; ^8 X2 ]# ]
  while(*p==0)p++;
) k# N" F5 l4 ^) k. \    printf("The last one is NO:%d\n",*p);. N* ]& l" l8 d/ E1 }8 _& U  v8 D
     getch();
% C3 x" S5 q8 p- M7 ?7 N
, f! Q+ g% p' O0 h0 W% T: c0 f& d  B}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
回复 顶 踩

使用道具 举报

发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
6 c7 B! ~& ^0 {- t8 |; J4 ^namespace 又费马达又费电6 B* B# W- z) m
{# W& a/ V0 Z# c. ^( P, \# G$ t: T) p
    class Program
' n' W# P  V$ V% t; ^9 `; y# [& c' L    {: o' W7 J+ j) \! a1 C7 Z
        static void Main(string[] args)7 v- c1 ?3 i0 Z& S: C
        {$ _4 h: r+ W3 S2 c0 C# P3 s1 G
            int m, n;
  s" |9 Z4 G1 z0 f2 v& a$ }            Console.WriteLine("请输入数组长度");
" K# c5 p: n! K) P- s; p6 _            m = int.Parse(Console.ReadLine());//m为数组的大小
# L' U8 Y9 R5 N3 G            Console.WriteLine("请输入要截取数字的大小");- x$ H! U% N2 ~  X4 [
            n = int.Parse(Console.ReadLine());
) X9 X5 H& h3 m- p, I4 q            int [] numw=new int) t+ L* L, F9 s% _7 Y+ v; q7 L

! l; k5 g/ O2 Y  g. G. u&shy;&shy;&shy;;
8 S# R3 O4 ?' U) X7 o2 Z+ ~1 @1 \! J' v            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
2 `: ~0 U. f% y( p6 \            {1 O) c# f) H4 j. U2 i3 V' F; p
                numw[j - 1] = j;
: N/ [6 F1 ]; E9 v            }: s; L, y" d) d" S
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
* Q9 b2 Z+ B: a) ~3 M8 Z8 @            while (d != m - 1)/ h: K4 A( D- P9 }' k5 t3 Y2 @
            {
4 R; Z; o' R9 m  \% j                if (i == m && d != m - 1)6 ?" s: ^% t( w2 `7 b! V7 \+ R$ G0 ?
                {& R& V. m3 S. b. [3 M; T
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
6 M# T' v* e) e' X% D' ^                    continue;
; i/ `1 P' X- l* r$ R, W! o' i                }0 K+ g) ?, G6 X1 q3 L& E- ~3 I5 p
                else( O* B& M% L6 W% p# ]; L
                {2 z: S  J, o/ s' F8 ?
                    if (numw[i] != 0)) w% J5 w3 v! {" h, ~
                    {
' k, g# W' r# T* Y                        i++;0 M; A  D; q5 N1 z
                        k++;
# j# o2 a! \! \$ G                        if (k == n)7 ~  N& z; H0 v% P- `
                        {$ u* B+ N$ r. ^2 y  V% q' S
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
* X" G' G0 w' w& o( h                            k = 0;
( x, n" A) a8 X& l* z              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
( a) g) w; t+ b  ?' C8 k                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 |- N* V0 K) q  H( W4 W  N+ ?) m
                        }
( k9 S0 R# Z; C- M4 o                        else//输出暂时还没有改变数组元素的值
6 x0 I7 ~3 l  i4 P* G( h5 \3 Y                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: |6 {+ x" p) Q5 w" ~
                    }
" I1 u9 H) L9 D$ r* Q                    else% A  k( R+ ]; c0 s8 K
                        i++;//数组元素为0,直接跳过,不计数。。。
% F; `5 z0 N) w3 z                }. C* ~* M. a8 B+ i7 b& [3 v
8 C$ ]9 N6 K% A7 R0 ]

& W4 L9 c7 j# {0 E9 y            }//结束while循环
2 M' L! ]! d& I9 R# j            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
: u1 B( R, o% c2 L3 _3 }) O5 J           
/ c+ R& @7 y, p. D1 ~6 |" `% ^                if (numw[i] != 0)9 x9 I' v7 @7 E  d- W+ _
                    Console.WriteLine(numw[i]);
  i' B; P/ Z8 i* p* b& L           
5 v* }5 u  T9 h1 a3 c            Console.ReadLine();) E2 G7 R: Z  \+ p3 x! ]* T
        }! |9 p" o, b+ l7 w% U6 ~8 w$ n6 f
    }
- [7 A5 ^+ O" B* O+ X9 K}
3 n- N2 f3 C  W
小甲鱼最新课程 -> https://ilovefishc.com
回复 顶 1 踩 0

使用道具 举报

发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
小甲鱼最新课程 -> https://ilovefishc.com
回复 顶 踩

使用道具 举报

发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
小甲鱼最新课程 -> https://ilovefishc.com
回复 顶 踩

使用道具 举报

Archiver|手机版|小黑屋|鱼C工作室 ( 粤ICP备18085999号-1 )

GMT+8, 2026-11-16 22:57

Powered by Discuz! X3.5

© 2001-2026 Discuz! Team.

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