鱼C论坛

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

猴子问题

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

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

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

x
大家好!4 K( k. k& o! Z) h6 L
这几天我在忙着编一个问题,我用了一种方法编出来!
. V7 D# m  ^2 `0 {. Q  I6 H$ G但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, I3 h! b; {- f  K( H2 G. |
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
0 G6 E% W' p" p% @
, l7 d4 C. B* w$ r2 m! A
* |7 H$ G" a$ p3 E
                            题目
: `) E2 R' c- M, Q& g山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
1 k% O, v# A: }. B5 X: [% ?5 P5 g4 Z4 I第一种方法:利用循环链表
( }# b6 W) X6 J7 ]#include<stdio.h>' a. v- B9 v! L9 Q& Y+ y
#include<malloc.h>* K8 g3 x1 T( R
#define M 8            //共有8只猴子
7 {4 A- u' Z; X$ A#define N 3            //数到3只时退出第三只2 d; E" Y! a7 \
typedef struct monkey
8 m) [8 q- e( x8 O2 D{int number;0 f: z% I3 U! N; m4 w7 d' M
int flag;- l4 I- q( J4 y8 }5 x& |3 n
struct monkey* next;
: [. l3 i) y0 m' _}MONKEY;
# O9 [, O6 @6 C2 Hmain()
: j5 @$ {. Y% f' ], z" E8 Y2 j{ MONKEY *head=NULL,*p,*s;
2 t$ v: _3 A8 d0 P+ }  int i,sum=0,count=0;+ q2 W* d6 i# ^4 {# p# {' Y
  clrscr();              //清屏4 l. }, n* n. f" I
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
- w) @: f  U2 G4 l  w  p->number=1;p->flag=1;
/ t0 f  Q2 R" ]" A  p->next=head;+ o, ^" z0 `. S7 a
  head=p;  j; a+ y& @1 `
  for(i=2;i<=M;i++)3 n/ b! M  W  X
    { s=(MONKEY *)malloc(sizeof(MONKEY));! s! ?- s) a9 q6 G% G( e
     s->number=i;s->flag=1;: ~0 T3 ]9 ~, U$ E1 d$ i" }
     s->next=head;
* }6 @$ F0 h0 u2 R! o% f     p->next=s;p=p->next;
  Q" X2 b) t; P+ T& ]% p' W    }6 H+ ^$ \& k; a0 ^" Z1 K
    p=head;
  }: R% N& ^9 F7 F/ ^   for(;;)
* k$ _) N6 N. V; ]    {if(p->flag==1)! H; t' _+ r6 |% L$ j- ^
       count++;
% J) v9 f7 x: ~) x     if(count==N)8 q* s% l8 f& T! H2 k
        {p->flag=0;
# }* f& I: M3 A' u; a3 e0 a         count=0;; P) H" W* A( W. v" j
         sum++;}
2 C6 Q0 F% B; u4 I/ a     if(sum==M-1)1 `1 [; B" w6 N! `0 a* w( a
        break;
6 o0 Z: t2 V9 x# t' x     p=p->next;1 I0 ^) q. f% w6 G$ y
    }
# ^4 r% j; |4 i1 x. B: e' b3 @( t    p=
7 c4 w; Y9 u0 L0 g( H    head;
9 J) h" y! d+ ~/ v    for(i=1;i<=M;i++)
; N; Y% p7 F4 a( |4 W" M    { if(p->flag==1)  W$ P+ ?, Z4 Q6 F  O/ B& g  a
        printf("\t%d",p->number);
; {( G" x+ |% [+ R* Z      p=p->next;# r) s7 [6 \5 ?6 U% _, u4 i0 Y
    }' s* Q2 `& X2 F& P% ]5 z; m8 l
! p! @" J3 \0 e0 }9 h+ H' J

, S2 w' Q$ G5 B* E/ p! i
; W2 u5 d. l# X6 i' [}
1 y# `# s* j2 W! U! o
第二种方法:数组
6 B/ ~9 T( I. e! o( v! C#include<stdio.h>/ H3 Q& n) T2 \# W
#define M 8
* A" p) i  W* q# V) L" e( kstruct monkey
0 a7 H+ m1 ?  h3 z{int number;0 Y8 T- z* K1 }8 r! J/ z  E. k7 m/ o
int nextp;  l3 e9 z5 D1 M4 y% s( C9 `
}link[M+1];& z* J, \7 N5 h# Y

& v1 `( g+ C' g7 H: Xvoid main()
: t1 `, K: a) x& C{int i,count,h;
. l. r0 S5 s/ P: I3 e4 w5 y0 F) ]for(i=1;i<=M;i++)! P, u8 t3 V* _+ j7 k! x4 g/ Y! U
{  if(i==M)' a, I6 O% B, \) k
   link[i].nextp=1;
1 e* @: H2 Y7 d8 X+ K5 J   else
  U' P# p5 G" D   link[i].nextp=i+1;
8 A/ Z6 i2 B1 I  Y/ t, a  link[i].number=i;1 J9 w6 _% E9 b( Y* p
}2 g2 i2 L( F  ?6 t: d/ ~
printf("\n");- Y) B8 j$ s* b0 k1 W" Z" z/ }% A
count=0;2 _9 t: E8 B. V
h=M;
! a4 k1 K9 }! ]% Zprintf("依次退出的猴子: \n");
0 H3 s$ h2 |$ F5 }while(count<M-1), `% ^, }" C# x+ O& g
{i=0;$ G3 V1 v( a0 V0 ?$ B
while(i!=3)0 G- q0 E* \. @
{ h=link[h].nextp;8 o5 [. ?+ A5 H$ b0 x/ }3 |) K
   if(link[h].number)9 O, T# |% z' a! I4 C4 @% s
     i++;}
! y: X2 B- [3 S9 F; I3 M' ~* D6 [) i
printf("%4d",link[h].number);
+ k/ L+ u3 r9 b, ~link[h].number=0;  f# m4 O+ a# q. k! \
count++;4 [5 F: N" Y8 t; R2 r0 F
}. x- f) v( Y: ?/ ]# D+ k+ U

# H  G# `9 F  e8 _' n8 Mprintf("\n大王是:");
/ n: P" Y$ \& g9 Q+ G0 n  for(i=1;i<=M;i++)/ d, ]" b5 I+ D/ w
  if(link[i].number)
4 s9 _, o# M9 P8 }( J3 ^8 t2 G    printf("%3d\n",link[i].number);
  g7 C' @8 Y1 _3 w( H" ~* X" E
, i$ W. H- a4 ]0 N& G+ n0 V8 o( k) a/ I+ \" a" S
}
8 g+ P1 p( @) K+ C" u
第三种是普通方法for循环
4 \9 v5 V) G" i8 T6 l) ^- I% g
#include<stdio.h>8 p, O2 ?+ H; r0 @5 ~
void main()
7 B7 ^7 J: ~! M; Q1 @+ @8 [( t7 q{ int i,k,m,n,num[50],q,*p;7 C" R, e' S! R
    clrscr();
9 `1 Q3 W7 v; k+ b7 ?   printf("input number of person: n=");4 i; r; T; z4 O0 G6 Z
    scanf("%d",&n);* C& W9 `6 a- N( K- _
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
3 G- Z0 N+ W$ s4 ]6 f5 y    scanf("%d",&q);
2 t( I# h" B. t+ P' l3 k  {   p=num;
1 c( ^) q- ^, f! {! p, }  for(i=0;i<n;i++)% B4 Z, E8 M. o! ?3 i3 P* b: E4 T8 c
    *(p+i)=i+1;$ F" B: Y9 ]8 h" @
   i=0;
# z8 p, `0 X7 \   k=0;
  w* y1 t1 v9 s2 R4 Y# y  K   m=0;$ d# H7 Z& K4 G( c1 |" m" _0 H
  while(m<n-1)
# I" J/ g7 N0 B$ ^$ `" a1 x* Z. D% u   {if(*(p+i)!=0) k++;" z# c$ n% \7 e5 c, e) b$ b5 U2 J
     if(k==q)* L, n1 v1 z- b. ?, s: Q
      { *(p+i)=0;
" _) ^. R- Z4 G4 \4 n        k=0;
/ t" i  {& s# {2 j: ^        m++;# b& j" x* C7 t- c  n" h& P; u
      }
* l' Q3 t' C8 h: J$ @, n; O) u& c    i++;2 k! @, A" X' S. Y$ w7 S- g
    if(i==n)i=0;
! T) ?1 W; Z7 W5 i) F& g$ u   }  J3 i! p% Q, B/ \
  while(*p==0)p++;  r" i- U0 ?1 Y, j3 O
    printf("The last one is NO:%d\n",*p);" ~0 d" U1 g7 L! Z. H
     getch();7 u: S4 E% R/ U& X7 o

/ M) A/ _# Y: ~: ?9 X}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
+ s1 l1 x1 v: Snamespace 又费马达又费电
' [  z# H/ E% ~{) x7 l" t( ^& E! f: c
    class Program& w5 l/ w" M6 x$ ~! ~% X( j
    {  y/ p2 b& C% Y8 g3 j7 A
        static void Main(string[] args)
; F  ^( L2 ^6 W. y- n        {/ y& b" f( [5 r. y% x
            int m, n;% T, W& k: x; Z$ o  N
            Console.WriteLine("请输入数组长度");
5 x1 @9 s# r6 R& F3 f            m = int.Parse(Console.ReadLine());//m为数组的大小0 F' L- I" A! R) W2 a
            Console.WriteLine("请输入要截取数字的大小");
# |, X6 l3 R+ j6 ^            n = int.Parse(Console.ReadLine());) s3 c* S4 |9 n1 ~/ p& s8 o
            int [] numw=new int
) `9 ?! V$ x: `( ^6 b; {7 M
" W1 E( G, @1 B) d! E&shy;&shy;&shy;;
- c9 p9 I8 e, r; |            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
& Q( Q* o" Z  A* p+ O* C            {
2 j/ d' y1 ]7 \4 C4 a- \  a% i  a" C                numw[j - 1] = j;" J- {. n. R; T1 [; q6 B
            }* |7 x) U/ {3 D8 Y1 b' [
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
& f0 w1 W  b! N# I            while (d != m - 1)
% i, k7 p. d8 n8 e, S1 I            {
" s# [) `( d, Q7 q' ^3 h# K                if (i == m && d != m - 1)
! d+ E# H; t1 f" k2 z8 p. u; k                {  F) v% G$ ]5 T+ M& D5 m
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
# |. a8 z0 n% n# W, W8 J4 M3 \  g3 K                    continue;
! l- C1 }6 O1 W1 r                }
2 f# u7 X) u9 ^% @3 p$ F                else
: r' v0 y; l* F3 q                {
. A/ x; E, ~0 ]  r8 V                    if (numw[i] != 0)
! t+ U! W  Q! Y: R                    {
/ z4 Q8 w, b0 D4 Y; Q9 I                        i++;
9 i2 f1 J6 S3 U" x& ~/ S) v3 ]                        k++;4 y1 Y% _6 t% R! f( l' k
                        if (k == n)
3 b$ y2 I: I2 R2 Q" F8 ^                        {$ M. \( h+ c5 F  [* K$ b
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了  f. W% e9 v4 m9 C  K! [6 P
                            k = 0;
9 p& {; ?5 ~1 u2 H              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小10 `4 I/ u4 v2 S7 x
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 j* F+ ?0 {5 g+ L2 O" O
                        }
' d+ {# L9 W) G4 _$ b5 @                        else//输出暂时还没有改变数组元素的值( G) n! {" v& E) A& ~
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);5 ?% i3 f1 C9 ~8 p5 {. H# ?3 E
                    }: r7 K. h4 o' ~  t0 M2 U! w
                    else& m) Z! h9 |  `8 w& b
                        i++;//数组元素为0,直接跳过,不计数。。。
9 J8 e# x+ S5 r3 y; U$ y                }
3 I" V! K* M2 e4 j+ u
8 j, @8 j) N1 }, X! y* ]* K9 Z! g$ W2 C) s
            }//结束while循环
+ V5 P. N$ w! s0 v            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
4 L$ h8 Y) q' a/ h8 Q$ i. e           
: i/ X  i( k$ U1 S  B5 b+ X- g$ P8 G                if (numw[i] != 0)
; }2 {0 u# W7 h( x1 k* K% {                    Console.WriteLine(numw[i]);7 J) |0 N9 G4 Z& O6 s: Y5 c( J
             R4 M( |: l) N& Y$ \$ f
            Console.ReadLine();
* d$ _) e: r* h+ q. E8 B/ Y        }: `5 S5 |" Y) L( x: Z! n" f
    }
* A/ `: ~# G/ D5 m! m  Z}. U1 J6 p' O5 E0 g7 [3 ]! |& B+ K, d
小甲鱼最新课程 -> 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-7-9 16:30

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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