鱼C论坛

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

猴子问题

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

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

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

x
大家好!
$ H( ~$ a$ ]! A1 g& @这几天我在忙着编一个问题,我用了一种方法编出来!
5 n6 @' o2 a1 g9 h! s3 U1 [: A但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!; R# Y/ A) g1 v' b, c1 a
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
" h8 _$ W# [5 d# {) H0 I; Y5 K
& ^: P8 Z  e! p/ T6 K5 V9 `0 l
. j3 K4 b3 p+ t- R  W  j. P  t& f  {: f# v
                            题目
4 ?* p2 Y" D1 l  p) k山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
5 N: u" k* {! D1 C" r7 S' _# J第一种方法:利用循环链表( G1 z1 P; x% }2 W0 t) w
#include<stdio.h>
' k6 A# A3 `. J/ F  R0 c+ E7 T4 L#include<malloc.h>
0 N+ |2 v1 I6 r* D#define M 8            //共有8只猴子7 x3 S8 g4 a' h
#define N 3            //数到3只时退出第三只* v0 \9 p9 Q7 |( ~9 c" P
typedef struct monkey$ X2 A- I( i2 g- k
{int number;. C+ C. L# f4 {7 {$ G& u0 b7 }0 h" n
int flag;
# h, e# H  T% {struct monkey* next;
' Q0 `" q2 G8 Z$ I1 Y& N}MONKEY;
0 a' F8 b4 A, v& {" _  ^( Smain()
# R. b! V  A+ m4 G. C) h& V{ MONKEY *head=NULL,*p,*s;: z7 Z% D1 M: w% z5 g5 Q$ m
  int i,sum=0,count=0;
( O8 D  b4 @; H  clrscr();              //清屏' n# m3 C! P. i% S2 r0 ]# h, {
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存  Z) o7 s+ T1 d' E/ f' Y3 e& b  g
  p->number=1;p->flag=1;3 J9 u/ Q/ s8 L) a6 a. x" a
  p->next=head;
2 J) \* r% L8 N! j$ f7 m7 A/ i- o  head=p;
. G' b; H. i$ d2 \  for(i=2;i<=M;i++)
  s0 h$ t1 b; D; o    { s=(MONKEY *)malloc(sizeof(MONKEY));9 ^& a. o8 p# l; X; a
     s->number=i;s->flag=1;
1 v9 C3 {$ G6 c/ B6 ^5 [& `     s->next=head;
; u( @5 `8 X" O8 L9 ?/ Y     p->next=s;p=p->next;
- k% T7 h6 U0 A( Z7 O    }0 x0 y% ]; G0 t
    p=head;" s7 X# \5 L2 M7 ^" j2 i* w" K
   for(;;)2 f: Q* e. [3 u8 M$ \
    {if(p->flag==1): }$ }2 \2 _! p
       count++;- i. y" m0 ]: Q/ u* W  L! L. o& {
     if(count==N)
; i: t) r$ d( }  o        {p->flag=0;! |  r" c3 u6 [5 G  M2 q
         count=0;
; y( P' p; @/ i$ O  P- T( ]* p         sum++;}
3 m; O3 j) C0 |     if(sum==M-1)
4 `. V' ?2 A# U! L5 `9 O- t        break;
% m% P2 Q0 S+ x6 N: S     p=p->next;
# h& P- T+ ^3 K' \) A    }
7 x# u2 J! X: }$ T- f8 y, Z, J' T) }    p=. m7 w% a& G$ e- n. P5 N1 h) b
    head;
+ l7 u+ l3 E5 d% L6 Q+ U    for(i=1;i<=M;i++)/ t2 k5 ^' c% _0 o: {: |
    { if(p->flag==1)* m' u' H7 H" e9 L
        printf("\t%d",p->number);2 \$ O2 _7 w, {+ W9 U% c2 X
      p=p->next;( U+ B! G8 g4 _8 E$ J" p
    }$ I0 G8 M0 i+ q9 T$ p; S
4 ]* L' U4 b! M( y
  |& ~9 E* Z9 r" d
/ F8 R5 T- [0 E- d" S+ O* F- y
}
2 b+ T; Y: S* ~: A
第二种方法:数组0 H; k- K! L: m, p# I. u
#include<stdio.h>
1 F5 y; o2 z- D#define M 8- [9 N4 f% @9 S
struct monkey) [1 l3 H, k' H. L% P& J8 C
{int number;2 k+ T% L) M6 Z, v7 V3 T4 b- e" l/ C
int nextp;, m0 B, x* A' L. \
}link[M+1];
4 K" B! p1 g" c/ F. t( G6 h- s6 o
  @5 m- X1 T8 ?! m& C% mvoid main()
- c- Q3 K0 w7 `. ~# M: e5 O{int i,count,h;
# s* Q( ^8 X* A2 b6 G& hfor(i=1;i<=M;i++)% ]. F& V/ N1 U* z! ~5 N
{  if(i==M), F7 Y  H6 y; t
   link[i].nextp=1;7 |' [, O8 c/ n: Y
   else
( C2 i# ?% F6 A' a. i8 d+ J   link[i].nextp=i+1;  d/ S" k+ j4 s% O4 V+ h
  link[i].number=i;
* R! V+ I6 N, Q, y# S}& w6 Z: M7 k/ \( g- b4 Y$ E
printf("\n");1 y9 H9 r: L9 {) U1 y7 K& h
count=0;$ e1 c+ Q+ I" ]7 Y) \0 S  E) V
h=M;/ R8 t* M# L! }
printf("依次退出的猴子: \n");
0 b6 W* M! d, }! Y2 }6 W# ?while(count<M-1)0 d2 X- C9 F& Y. T
{i=0;, G* J0 X' R; N2 k- b6 U
while(i!=3)' c- w% Y3 p1 c. u, S1 ?
{ h=link[h].nextp;
4 A8 x+ Q" ?9 q6 T/ }. P$ G' }   if(link[h].number)  @( F8 o1 Y0 v3 c3 ^0 H
     i++;}
: ~: L, F0 b! S6 `
7 @; G$ ^4 V# ^) O% H6 c) i2 p) [  Rprintf("%4d",link[h].number);$ g; v* \; [/ _9 p
link[h].number=0;6 I+ g8 k) x% y3 R0 W
count++;
' N7 y, B0 ]9 l4 `3 [7 L) d}
3 E) O0 h; y  q
" O& {8 F) s+ s# _4 @printf("\n大王是:");  {+ U$ @" S; k$ Q% z
  for(i=1;i<=M;i++)
  N; C3 `" u) }5 ?6 ?9 ~$ q5 M4 v  if(link[i].number)
/ J$ A2 X+ `6 Z$ O  \    printf("%3d\n",link[i].number);
! w1 B9 E/ P6 E: M9 q
" ^" F. J$ q. l2 z
; k4 |( G3 H9 d6 U4 {0 d}

2 c3 r7 D; L) t第三种是普通方法for循环
7 j% ^- R, T% h% {& b
#include<stdio.h>
/ l1 f4 \& \  ^2 wvoid main()
. ?2 L9 F2 R( x- O2 F1 E{ int i,k,m,n,num[50],q,*p;
) Y4 S  k5 w, Y0 D  x" P    clrscr();
$ K2 D1 N! p* |   printf("input number of person: n=");
7 {; j; g! b/ [. p: Q* h    scanf("%d",&n);
. [, ~) a3 L) Z" l; A# d3 Qprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只: ^. x7 e8 ?" i# [6 @' o/ f8 M
    scanf("%d",&q);
. X* u0 z% Q0 |/ B8 R* V5 E   p=num;
* [$ T' _. [( D4 k1 `  for(i=0;i<n;i++)$ h" G; n+ k% |7 J7 s6 \& h
    *(p+i)=i+1;
, c. x# ?$ |# p2 j- Q: S* m   i=0;
* Z7 [8 |! t: b% _5 A   k=0;7 ?6 k& J# X# d
   m=0;4 y. ^9 K' O7 X$ K/ r/ V/ S  b
  while(m<n-1)) {3 J( N0 R4 {( V6 u3 r4 m$ Y* ^
   {if(*(p+i)!=0) k++;
9 I# B1 Z: Z7 J# u     if(k==q)
  `) B) x: F  I% J- Q      { *(p+i)=0;
1 i( b8 _' l/ i* a! m  w. @( f$ z        k=0;
4 i7 b  H% D9 {; c- @        m++;
, r; A& R" m8 F9 M9 ]7 i2 h) S      }0 c8 u$ k8 P1 n& [7 Y
    i++;
9 _/ r0 W; a) S0 [8 I: a) {! B5 O    if(i==n)i=0;' }  S( `) z% G( W' u
   }% G2 i: b7 i2 S8 u( e' _3 ~9 p( o
  while(*p==0)p++;8 F6 g4 \7 a% w1 A
    printf("The last one is NO:%d\n",*p);
* k) q2 G# y& V. V4 e$ ~5 `) C6 \     getch();; B! ]+ L3 k' C- @( D
( n2 X& N2 K9 s' J
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
+ y/ t) m, U* X& m& r* @9 Hnamespace 又费马达又费电9 k( S' m* w0 i
{
6 [: G  D  a' `+ L4 z+ u, S  P  H    class Program
& P+ @1 j& D, D6 v! {, f! e    {0 P, d0 H9 V' _, }- D* N
        static void Main(string[] args)! `( {7 s& ?% |2 M. V
        {
: \) `+ m' \' ^. w8 t            int m, n;
$ B8 b6 m/ a* R% ^4 N: D6 [# u            Console.WriteLine("请输入数组长度");
+ I. q$ z5 i2 y9 ]: s8 `6 g            m = int.Parse(Console.ReadLine());//m为数组的大小
- b4 u0 P6 q) }# C0 ]            Console.WriteLine("请输入要截取数字的大小");
: Q  j8 W- b* v            n = int.Parse(Console.ReadLine());
; S" I/ A0 R1 U            int [] numw=new int
$ S& ]3 D& H( m4 q: p* o# J" C8 O; d0 ]4 _( m- j% c
&shy;&shy;&shy;;
% W" ?- p4 ?) }* h6 F2 O1 t            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
4 I9 Z5 O: O+ L: t0 h. r            {! Q: Z, z: ?$ M9 m# F1 f7 i. s8 _+ g
                numw[j - 1] = j;+ b9 D$ ~5 W. a2 S
            }
1 {3 y9 `- t1 K+ Z            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!! ?- S1 @& ?+ |: `. Q0 \# @9 W
            while (d != m - 1)
% C) M. e& [9 K, l            {
2 c4 U- Z( }4 ~' w- s2 G+ o                if (i == m && d != m - 1)
! ~1 F% f1 y# n5 _, u9 u& b+ m                {$ K1 P2 U" \4 R* K( n3 t" K
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!& O8 @2 }2 a( L% j
                    continue;
# X0 @- R2 \% t6 V( ^  l                }$ w0 q- f3 X) x5 v) c! e
                else. n2 R. ]0 w; W6 t; u
                {
; g, m3 j/ s  A/ R! U                    if (numw[i] != 0)8 i* ?: V% Z9 B  G
                    {: L: L1 r) V0 [. q0 L$ ?
                        i++;' ~, _( k. y& e5 G
                        k++;6 x2 @, C8 @' H% p5 T" l
                        if (k == n)
3 y8 c5 Z! ^2 ^/ F/ X" i; B                        {* W9 G- H" `" c& U
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了! e/ ^, E- E6 J4 t$ k: w- ^. w; i  }
                            k = 0;
( \4 B5 R2 F7 c5 v: T              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
' K' J) U# Z* Z, a, f/ \                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 f  d+ g* A- |2 Q9 q- s, b                        }4 B9 J2 }3 j; e
                        else//输出暂时还没有改变数组元素的值
7 f" P! m( ^" S5 L& ?) s                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
% U5 y+ r. h4 }" m; L/ t                    }
: P# k6 G9 U! s8 A, I                    else
+ ^# [- P: G. `* z                        i++;//数组元素为0,直接跳过,不计数。。。, Q  u! v! W2 \& d+ i9 k1 R( y- I
                }
& [' a$ E, {# m8 O: I! g, ? ' j4 I" v4 y, B% Y' G

- a' T: E7 d) p9 e: S# I            }//结束while循环
, A% g+ {8 t& e. B7 h3 F! r            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
& l% V& r. V4 g6 _6 n) P           0 M1 U" }  j$ `$ S
                if (numw[i] != 0)
( X! ^& u# {2 F& D" c                    Console.WriteLine(numw[i]);2 P- ^1 s! U  f/ {6 L
           % A" E  @* ?' Z/ C: I
            Console.ReadLine();
! W1 _. {% R4 ^3 h% m" d        }
9 ]: f4 ^, X9 Y    }
6 @4 j. q) [% W* `8 R# y! P0 t' c}
. t1 E5 V& u! h3 D/ [- z+ ?( g
小甲鱼最新课程 -> 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-3-7 02:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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