鱼C论坛

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

猴子问题

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

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

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

x
大家好!( N5 i% {9 j; i$ m
这几天我在忙着编一个问题,我用了一种方法编出来!$ L+ V8 X8 F9 h4 L$ j
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!# T( D# |! X4 ~/ F- L" T- M
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 7 Q5 Z; o7 [  i* Q
. @  o5 k' r3 r: ^5 @; {6 M/ X: o8 w

* B" `0 [$ t  r6 N, x- ?' Z
                            题目' h  ]8 b$ I! p5 c0 W
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
( f+ M9 |0 l% g7 _( D9 }第一种方法:利用循环链表! I& h- K% e" A  r/ X& z
#include<stdio.h>% @% x. K7 c2 r
#include<malloc.h>
9 `# q6 w8 i, H: H#define M 8            //共有8只猴子
! V; i& d! b& b$ [: K#define N 3            //数到3只时退出第三只
/ ^% S3 ?: Q/ c4 C, ttypedef struct monkey- W7 A" D' V1 A# A
{int number;
7 p& p- g' R: S# R8 W) s# p7 ?int flag;
  ^7 Y) p4 B7 V! ~  m+ B- estruct monkey* next;) k* C5 Z! L% R# {! P# W
}MONKEY;# k" `7 w+ V8 S7 {! S5 g' J
main()( Q9 |4 K" `" \5 X
{ MONKEY *head=NULL,*p,*s;; f# I) i4 R" Y. U
  int i,sum=0,count=0;/ g. ^) O$ m5 a& ?# N5 f( Q& g
  clrscr();              //清屏
1 y0 i( q! b  u7 X" \# M% n  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存. b2 X# x, w0 _) F
  p->number=1;p->flag=1;8 `* j, u: ~) A- r0 H& `4 ?2 r: E% p
  p->next=head;2 p" _% u1 ?) k, e/ _/ o
  head=p;; X# \' |2 I! H# m4 ]6 }0 w0 y
  for(i=2;i<=M;i++)# F$ ?( {- L2 w7 G% j1 N$ ~
    { s=(MONKEY *)malloc(sizeof(MONKEY));4 O# \* H* n* y/ z5 }! ~# O
     s->number=i;s->flag=1;
9 O+ N6 d3 F; _! ]; k7 o3 Y     s->next=head;0 c& ]3 Y& H. O% s4 b' I; e' Q# W3 Z* p
     p->next=s;p=p->next;: ]9 E4 X& ?+ D7 q# Z
    }
: ^# U1 M$ m& V- i$ e& m    p=head;
5 n& `7 Z2 n8 s' X, _" ]   for(;;)# b; z3 \4 S7 R" m8 G3 y0 x! }
    {if(p->flag==1)3 K( o- r. `3 {' w. D
       count++;
/ l3 p8 v0 z. s& Y& E) q8 b     if(count==N)* V" J/ G# s! W# p$ ]( O: b
        {p->flag=0;, k  R1 J5 k: f: N
         count=0;+ c( ^& Y! c! E+ g# q
         sum++;}4 S4 o5 _" @7 p4 o
     if(sum==M-1)
9 J6 f4 ]# s7 {% T: J/ x3 H- c5 d/ T        break;. B/ a% r( f* _" }
     p=p->next;* \& V* k4 [7 s4 r6 W
    }4 b9 p( D2 Y% E
    p=
7 Z# t2 \' }/ V5 V5 S3 ~    head;
3 t2 A  N1 c5 `  R( J: h    for(i=1;i<=M;i++)
" Q0 r) L( M/ \    { if(p->flag==1)6 r' E: w- o' E* p" ?0 ^
        printf("\t%d",p->number);
6 @; ^7 S7 R5 u, X' c" x      p=p->next;
' P0 c. m* ~, U, n    }) I  g% H$ f9 W8 W& b

* J$ H  K# }' t
  Q+ R1 l+ ]# u1 `; M: a. X
" j9 ?* Q$ W4 h7 V& r1 A}
; y1 y4 Y- F& Z! }, y; g
第二种方法:数组# f. `! H! L- ^8 t7 p: a
#include<stdio.h>
$ S6 Y& K$ X. {4 ~# O#define M 8! u1 G$ v# i8 W& ]$ j( [- C* Q
struct monkey8 s1 i& j2 G( D$ l6 v$ q
{int number;
% p1 O, {2 q4 x' x3 ?/ i" x$ c! yint nextp;
: \5 p, |1 M! U" T  f}link[M+1];$ [0 c' c3 P2 h( Z( n/ t  O
5 `* \+ l2 A) U0 H- h
void main()( q6 L* c, {7 Q, N2 C
{int i,count,h;( ?7 v# M; z; e6 b
for(i=1;i<=M;i++)
0 F9 r, U$ T, g/ y{  if(i==M)
8 J0 z7 n. j; Q, u   link[i].nextp=1;
& \. r& X& w4 W5 m  s  m9 f' O: P  S   else
+ m: u0 g. V2 S7 x) A% P   link[i].nextp=i+1;
+ y' |0 V& b+ _" y  L  link[i].number=i;" q  v9 X2 ^# H4 S7 d& A5 G  ^; d
}
2 ^+ c' X0 g, T, O' pprintf("\n");# l. C% x, m( {: P
count=0;
2 z# S- N5 u) I* _: z3 W. Lh=M;
0 ]( J" ?6 A3 T( n3 Uprintf("依次退出的猴子: \n");
+ w, r$ X  X3 M' w4 _while(count<M-1)
+ W! y, a$ y) G; E  \) r) T{i=0;
; e2 O2 i+ S5 h* c& Hwhile(i!=3)
9 I) C( h: r6 R- B  a$ O3 X{ h=link[h].nextp;
* _9 C$ E: @" R' d2 x   if(link[h].number)
% A5 J3 L* ^3 x3 G# W     i++;}
" b; ^* v: S# [7 P0 P! O! i( L( K8 w2 w+ N- c' A' |
printf("%4d",link[h].number);  F) I& r& n7 ]* c7 E0 l
link[h].number=0;/ R0 u  i6 k6 D  a* C  o
count++;
2 N* G" o& K& ~4 Z}
. f! Q! X+ \) z: ]0 M8 @: ^
" L8 C+ S1 {% ~printf("\n大王是:");
5 f+ ?" K7 R7 }, h$ k  for(i=1;i<=M;i++)) h8 {2 w1 ^$ T5 U
  if(link[i].number)
$ r8 m  \& b! A' ^" _$ x; h    printf("%3d\n",link[i].number);$ a3 L4 b6 q3 P& V. e! o+ y2 l: i% V
$ e. C2 c' l! \. E" J6 E: H

2 Y1 _: k; A0 @2 f+ H}
8 z5 u5 O. ^( ~3 ]% C  [( Y# A* F
第三种是普通方法for循环

* m) l0 `( Z# J# s#include<stdio.h>( Z0 Q1 b$ o1 R3 W  I* \
void main()5 D, A' n) \0 E* o
{ int i,k,m,n,num[50],q,*p;
8 Q: E" H' a2 k    clrscr();& x( L5 C6 t3 E* ^" \3 Q' w
   printf("input number of person: n=");
' E; R9 W) M5 e  s: @# @- b. ~    scanf("%d",&n);# d% w; D* t. u; G# K. h
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
: J( B& v( @! U# y2 Y. O    scanf("%d",&q);
% U/ j8 t7 T7 ?   p=num;
8 \& N0 ?( ]8 e3 f9 L" C/ o  for(i=0;i<n;i++)! H4 ^5 v( X- W0 o9 h' p+ D  \, H
    *(p+i)=i+1;
) W6 L8 W8 O+ x4 A( w- g) ~7 N* D! g   i=0;0 K- U2 M+ Z$ R4 j# H3 U
   k=0;4 p# \  K+ }: M# z, D* P
   m=0;4 q6 P, E2 [0 F& o/ U/ P
  while(m<n-1)6 E# Z& h5 V7 ^4 H
   {if(*(p+i)!=0) k++;
. l3 ?: d% Y8 m: C0 r     if(k==q)
! Q4 ^4 m8 o' O, L$ x' n0 d; r      { *(p+i)=0;- F, c5 Z8 n2 m  g- U9 X- ]
        k=0;( J. A7 O: q7 Y' t! ^* {
        m++;+ y" Q9 S1 H7 g% J: K0 h$ ~# U- ], A
      }% x1 J+ _) Q: ~5 q* f5 W; B
    i++;
( k: r: H& T0 L, b    if(i==n)i=0;& V8 C# N* ~: C4 ?2 q# L
   }
; Z* f- |; _4 s) v* a8 \/ N% f! `  while(*p==0)p++;1 n: u; S. P( `* _# K7 u" j4 A
    printf("The last one is NO:%d\n",*p);
$ V4 R6 _/ s7 \5 J     getch();- r4 F- w  t9 _: W- p/ W. }# O

. z0 C+ s4 a  i; K) F- ?/ h}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;" ^/ a: j2 C  @! z- M( @) Q
namespace 又费马达又费电0 V3 W' @/ \7 ~( j) E6 Z
{
; k" [+ t) k: c9 V    class Program
+ a# L6 k8 {' p    {
5 X  E) v1 S7 m$ R        static void Main(string[] args)
, h# F. m1 |; s0 m& p+ \        {" \1 P; u8 U# `
            int m, n;4 n+ S' K5 `2 b2 c" M$ R
            Console.WriteLine("请输入数组长度");
( e/ l9 }8 L  S; F4 Y+ a) r6 }            m = int.Parse(Console.ReadLine());//m为数组的大小
# k' M9 b6 p3 {& n' B            Console.WriteLine("请输入要截取数字的大小");( V- V  Q5 O1 \5 Q, U. o, T( z
            n = int.Parse(Console.ReadLine());
8 ^" s6 d9 H0 G5 R            int [] numw=new int
1 |/ \& s) o* o) @% Z
+ x" H3 ]( l8 A&shy;&shy;&shy;;, q: O( E% }  n" u5 q
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数$ L" s+ {9 m" D5 @/ J
            {
" F/ J4 k! I# y. l& K, h                numw[j - 1] = j;
& y, z+ B) b$ N! b  s0 \            }
0 P- F* R0 l4 w9 J5 ~            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!" Z+ s  q& L/ k  F( N
            while (d != m - 1)
0 U2 A) Y$ {0 P8 @  L, _            {' r0 D& h  @! c7 e
                if (i == m && d != m - 1)/ @/ y# t3 |& }2 }& [, U
                {
/ P; m0 {* i2 \! }& v) v3 j9 g                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!* P- |" a! g& P) H, F3 y
                    continue;
3 }+ v$ j; Z4 i5 I) J) o                }" `3 r7 m- B. D4 ~) j2 c
                else
4 U6 p4 g; x4 \" B7 _; G! U                {
9 F% w( d1 L( @& ?# u2 {                    if (numw[i] != 0). ^- s; J4 r) ~  a
                    {- H) {% P4 _6 s9 @/ x$ D: w
                        i++;
! V/ ~$ m$ P( O6 F+ B+ Z' ^& z                        k++;' d/ c- _- ]. t. D  ?3 Q( z
                        if (k == n)4 ^5 x4 M% a5 @5 M5 r
                        {! B% A- g) t/ k0 V
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
# z0 I; v$ E0 q                            k = 0;$ a# d& [+ L2 u/ x& R
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
, w* x+ c, \6 ?( T0 D9 u& w                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
. r& R' e* D9 d8 j: @6 W                        }# v% `! a- a; l4 O! m# ?
                        else//输出暂时还没有改变数组元素的值
6 N' {) @, D/ @9 m1 W- l                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);1 r+ H* I; r; u6 f1 v
                    }
' Y  F( u/ a9 |3 C' b5 ^                    else
5 L4 j8 k. o8 H- V& L4 ^  B                        i++;//数组元素为0,直接跳过,不计数。。。
2 n# G/ f, a1 C9 M1 j7 N- X                }
2 ~& m# N+ e* ^; A2 G0 w4 [
' l$ T0 J: r' x+ c& w  A. S3 {" }9 Y, q4 p* Y
            }//结束while循环. p% K. G  h& |6 t' b3 c5 |# H
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦' a2 S1 @4 R. ~! p- T
           ) |1 n1 F0 j3 M6 {& h  q- k
                if (numw[i] != 0)- L# n# N3 O- F, \) q% P
                    Console.WriteLine(numw[i]);
" c0 X9 k% x1 \& J           3 z0 L/ g" N& A0 q; Y
            Console.ReadLine();
: ]6 W. n3 C3 Z; Z$ {( _8 l+ c, K        }4 a; U6 @$ q8 A' n
    }6 [/ F  e& H( e0 }" r$ e
}
, t# [# ?$ v3 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-15 22:11

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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