鱼C论坛

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

猴子问题

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

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

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

x
大家好!; g) ?6 K/ d# C2 p' R+ E  D
这几天我在忙着编一个问题,我用了一种方法编出来!& W* V/ G- M" ^! L/ o) L* W
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
8 I6 r. O6 T. \注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ! s& A, p" j1 x( o; d; G

6 i! J5 w% B. c. z' d
# W1 A. P2 a" Y; \9 m0 e$ s  _
                            题目# g0 h4 x- V; c! c! B
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
6 }/ U& p# }1 m) s# H0 `第一种方法:利用循环链表& Z; e0 ?" c* X$ k- d. K  n* [
#include<stdio.h>' w2 L0 Z& X1 ~* K' }
#include<malloc.h>
, l) c% l4 {9 z: R7 d- O$ t0 r#define M 8            //共有8只猴子
! h( Q, a9 {. }: r+ J#define N 3            //数到3只时退出第三只
, S6 D+ J4 F  p) |0 n8 V8 r. r8 Rtypedef struct monkey
3 ?' V' Q4 ^2 r{int number;+ s* a1 T9 p4 D5 m* j6 u4 k
int flag;" x: J6 [# F% a) }! [9 l0 Z
struct monkey* next;
; I  T$ X- y8 u' l}MONKEY;0 K" a& }, M6 R# M9 E7 u
main()# z, f4 ^. K6 v+ M
{ MONKEY *head=NULL,*p,*s;0 W& t" M& _9 Z/ I2 q' K1 j( v
  int i,sum=0,count=0;$ U1 F+ k: A% p$ s$ o: ~
  clrscr();              //清屏: ]4 e% j/ }2 F
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
; c, b8 i6 N$ c/ g9 t9 i  p->number=1;p->flag=1;
& }( S% ^1 f1 M' \2 k2 @) S( }  p->next=head;5 b' e' o  o7 z* `( M
  head=p;) R7 d4 i6 E5 W' K
  for(i=2;i<=M;i++)8 q8 r8 u" M# f! J
    { s=(MONKEY *)malloc(sizeof(MONKEY));
' ^; E% C3 O6 C% I# F     s->number=i;s->flag=1;
0 ^0 {" R  x8 V! f; L     s->next=head;& x% H% G/ x2 s. \' Q$ q7 h2 i0 C
     p->next=s;p=p->next;
5 l/ ^: r5 y, U1 z    }
( W8 S7 P7 `9 K7 Y  A" k    p=head;
, ~8 v, ~3 p; p. v   for(;;)1 h4 k+ |5 m- h! N; R% v
    {if(p->flag==1)
; u$ |! W# S/ v5 e" U5 R. q       count++;1 _( \7 X7 K' F$ M- t7 {5 s
     if(count==N)
. q) v7 r6 ^( _+ m' B% |8 |        {p->flag=0;
% o" Y7 o- m: r3 T. Z; o4 a         count=0;
7 `# r- F5 S2 H) t1 R3 s         sum++;}/ B3 a. J: u  z2 w
     if(sum==M-1)' ~/ U0 O% Y& g% V6 u3 J  @! W
        break;
* j% b! V) W* D% q# I     p=p->next;  i% z% N. R. J  `! h
    }
% j/ T2 C2 O+ C. A6 n# w    p=
) P/ ~' y, c2 x7 Y0 |$ ]    head;
5 h# C2 N# ?/ J, e' `1 K3 O    for(i=1;i<=M;i++)) r) [  y0 x# k; y4 n4 G, c- d
    { if(p->flag==1)- r& N8 U0 P1 v
        printf("\t%d",p->number);
( {: K5 e. F0 [" |& b' i7 c      p=p->next;
  W% ^% r, W" c: _8 U  r) K& ]  a    }. t% N1 H- |* J* ~( f
. F2 c- K) {! h+ c! U( X

9 Q6 k% n2 m. e( v* Y" r- C; d, H; |$ [' Z* N7 q: V
}
6 h) U$ a1 U4 C
第二种方法:数组
" R7 E' I1 f" H" b#include<stdio.h>4 G( O" E: T9 i1 h
#define M 87 {4 A" w% t& o# h" S
struct monkey
' Y) g2 @/ |: J* ?/ n# N8 Y+ Y" J9 Y{int number;
6 S6 }2 ^" e8 c- M) E; u) cint nextp;
! \- h( v; a  ^) l2 f}link[M+1];4 G% }) b" K8 w( R
: Z  j- X6 M1 F' B; B5 _
void main()7 @2 y  l) H4 B+ `
{int i,count,h;
8 d: @' y! p6 Z5 D( Ffor(i=1;i<=M;i++)
8 |. \! T; |3 k/ K4 }. `( i{  if(i==M)0 m7 n8 I. Y" m2 C2 E, g! |
   link[i].nextp=1;" {, l  p1 C5 ], E0 Q; r+ L
   else9 g3 O/ h9 G$ I9 I% B
   link[i].nextp=i+1;* Z/ G8 o2 k; }8 D( D
  link[i].number=i;0 b/ S3 q8 B- m2 q5 x! N# c1 p
}
5 d2 N- M# m5 Bprintf("\n");; h* z1 C8 o0 _1 o6 s. q
count=0;5 d& l1 S& t; P; D0 J6 r
h=M;
0 S. W) G! j4 D- P* s2 _printf("依次退出的猴子: \n");
$ z5 O0 K( d1 n" C; e8 s( ~while(count<M-1)7 A- p7 ~8 k' V) v  `
{i=0;
+ v# o) T& @6 x* {" J# mwhile(i!=3)1 s8 ]) D) A/ p6 [! _
{ h=link[h].nextp;6 |' _% j% Y, \
   if(link[h].number)
- A. g: p4 x; e' b7 I  |% {/ _     i++;}
4 E& l$ ?; a  R! n: L- R1 U7 |4 d  i2 P5 a0 J
printf("%4d",link[h].number);$ \+ J! m5 L; [4 F( |  R/ ~
link[h].number=0;* j& l6 M3 j& ^
count++;: j' r* G5 m9 d
}' y# w* L& B& ?* \) X  W5 S

8 H. I& G6 w2 R: o& U' z+ j# xprintf("\n大王是:");3 B/ R2 O7 F: v1 v
  for(i=1;i<=M;i++)
1 ?' [2 P7 y% k9 g$ i. t4 ^  if(link[i].number)
9 R, k/ L9 S% {! }9 ]    printf("%3d\n",link[i].number);! B% S6 V2 ^$ }* w
8 _. d, y' [( O; ~' ?: K0 H- K

8 ?0 P# j3 L. Q0 n5 l1 {}
* b& l6 y: F6 N: g! i1 c
第三种是普通方法for循环
) l( w6 @7 R- W3 w$ h
#include<stdio.h>
; s, `# X0 u/ _% E" o4 wvoid main()9 V; S4 ]! _3 f  _5 Q+ J
{ int i,k,m,n,num[50],q,*p;9 \, `) a* m3 _6 g8 o- p8 p# X7 [
    clrscr();+ F% t2 E/ k/ ], T5 G
   printf("input number of person: n=");- K. {3 z9 {6 q) G
    scanf("%d",&n);( r% z. c9 p0 J5 V$ _- W  h% H
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只# h, Y9 S3 {7 B4 Q* B0 ?5 Y1 k% V
    scanf("%d",&q);, ^/ J3 }. P+ B" M( S& v* q
   p=num;
, z$ `# u0 o% s8 A: S  for(i=0;i<n;i++)7 ]2 c' h$ z, F/ D) V: a* x3 _
    *(p+i)=i+1;! V% j7 e! F/ \: B$ r
   i=0;
" ?$ u/ w. C3 `& W# P1 F   k=0;
1 g; v4 C2 ^9 A$ c* ^3 G( M   m=0;( ?( \0 f. n2 _- x; @
  while(m<n-1)5 \) _+ Q9 ?+ N4 K' e& Y; y
   {if(*(p+i)!=0) k++;
: y- J5 v7 F! S     if(k==q)' {! A. G+ U/ ~8 y
      { *(p+i)=0;* c9 o$ G$ V. B% q
        k=0;
6 c( G4 o* G1 i( x! {7 ^& }        m++;3 @& I" Z* C- L9 i$ W
      }0 q- ~# u* B9 @. v( \
    i++;! ^1 e1 I, m2 G; U2 r) l
    if(i==n)i=0;9 Z) L* @8 i9 j* Z
   }0 f% C+ ^6 t! a
  while(*p==0)p++;
% d+ G& F, e5 q  s9 y( Z- E; }    printf("The last one is NO:%d\n",*p);
( |. k! _7 Y7 h7 p     getch();
3 r* F2 x: Z$ K; g. v; ?, V. `5 b  W/ K9 \7 [& _: U2 B1 f
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
8 W( S. Q" C( H( B; fnamespace 又费马达又费电+ j8 F! C2 i1 N4 y+ D
{, q( _: h( H- c/ Z) K) L, m
    class Program
# r: h: T2 s/ `2 V: O1 E+ G/ `    {# T0 a, q: S7 m
        static void Main(string[] args)
# t0 k/ _5 B" n! J- O        {6 M( x- _6 b) M1 F3 k; y3 p# X
            int m, n;- o! R: p) A$ u$ P: T5 d, @
            Console.WriteLine("请输入数组长度");
& B( n; ?, r: t& G5 V2 _4 |            m = int.Parse(Console.ReadLine());//m为数组的大小
; e, n  ^4 l1 P9 `7 J5 T            Console.WriteLine("请输入要截取数字的大小");8 D' |! p) h; U
            n = int.Parse(Console.ReadLine());  Y: `/ K- s2 ]6 k- ^) \
            int [] numw=new int9 ^7 }4 A( L$ B- D  s0 Z

4 R5 u4 J; r2 x- a& F. h- x&shy;&shy;&shy;;
* u% o0 y( J5 K# Q5 e3 I            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
3 i3 {) |& o$ a            {
9 J7 \0 v! r+ q' H7 A4 Q# ~                numw[j - 1] = j;7 a. j5 n# V) s- A3 @, a
            }! y+ V$ F: s' g6 @
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
( u, B0 ?6 [8 A9 m# k' K            while (d != m - 1)
* w% ~1 M4 X3 L: }& j. m            {1 l1 t& c  C# j5 s4 c2 E
                if (i == m && d != m - 1)- c: o" W; J9 F2 F% f, @
                {2 B, a+ U' n1 F5 y) C9 T  a
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!6 A4 o5 K# `) [9 P( E- q
                    continue;
# M7 K  d7 S+ g# a. X                }
) N3 _" {& X1 [9 `- u5 T+ ~                else
/ U3 L2 a9 Q" f4 [                {- d0 r* S1 e; M, ]. P. d
                    if (numw[i] != 0)
" h# _! {% S, R. _                    {
  S+ J  v1 o+ u7 y                        i++;
: z* k, l8 G& c2 _7 i                        k++;: E* z% l# y7 b, X
                        if (k == n)
! V, k2 J- r, Z$ S* Z$ ?# A                        {
1 F+ w1 u* ^( ]" V: ?9 l! k$ O1 b                            numw[i - 1] = 0;//把在n位置数组元素的值改变了+ C. f9 g$ }2 Y/ O$ [( ]
                            k = 0;
# u$ @7 g  m# ~5 C              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
. W  F, }6 a. A6 b2 u                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);; F( P: B8 F' ^. j9 H
                        }- R+ t+ o7 y$ m4 L, o; S3 D" `
                        else//输出暂时还没有改变数组元素的值
+ V+ z+ H" e* j3 |4 \                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 {3 V7 y2 Q, t$ Z
                    }6 o7 e# k: A% d; U1 j
                    else
/ q$ C& s1 q* o% `                        i++;//数组元素为0,直接跳过,不计数。。。9 B7 e9 x' D0 Y8 B4 a+ {
                }
7 M) C% T% P  n& E4 y) R& @7 K . n/ M. s# p$ p& i

& ]1 \( t  U! t            }//结束while循环
( [, x2 g4 }  M- l2 P! M0 ^0 w            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
3 z& t* w- j7 B% M           $ L( C# a, @. V* F4 j
                if (numw[i] != 0)
3 q3 ~- ?( ~% \1 Y                    Console.WriteLine(numw[i]);
1 _  w) u' V' B           ( L+ E* B/ i: C7 p
            Console.ReadLine();
& d: C% l" U$ T6 P        }
. ^& n2 F3 ?& x2 N' c) }    }3 {! C* r# N3 c' I9 }( y
}  |. n  r2 S! a7 b0 C- A; {  {
小甲鱼最新课程 -> 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-30 06:13

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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