鱼C论坛

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

猴子问题

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

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

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

x
大家好!
) J3 e$ y1 N* Y' p& |1 _这几天我在忙着编一个问题,我用了一种方法编出来!" i. D( P/ r4 G
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
% O6 M2 B& z* i1 z& L" k注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
( F$ \( {! z3 o: P& ^' l! Q
8 l! L8 X6 ^9 u: J$ I
$ V! q" ~" o" s. h) L
                            题目
: M# E6 S# V, I! P4 e4 [9 L山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
% k. A9 V* [  I! ]第一种方法:利用循环链表
3 M! ?1 I* W# H#include<stdio.h>
0 w* c8 r8 I3 }" O5 J#include<malloc.h>, a9 C9 ?! R. a( y+ `8 k
#define M 8            //共有8只猴子
+ u. G7 k- |4 s' i# P2 |, U#define N 3            //数到3只时退出第三只
3 k! d( R2 k$ Q+ \5 F) v/ E) g" Gtypedef struct monkey
$ R, w9 k9 G1 e- i4 `{int number;- g* d9 V; r1 E1 W
int flag;
6 Y1 ?3 x5 c# A' S$ ?) qstruct monkey* next;7 B2 x0 T  [4 h' y: L) u( H
}MONKEY;% Z0 O$ J0 j5 J: @
main()
5 ^5 g0 M7 }( q' ?5 o! h. y{ MONKEY *head=NULL,*p,*s;
/ Z% U+ l& K& e& I8 ~* h) r. D4 }  int i,sum=0,count=0;
3 p. C$ y6 y; V9 i  clrscr();              //清屏
2 K' i) o* X' k* I. A* _/ x% C  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存% t% f& B) u3 I0 a4 A  U
  p->number=1;p->flag=1;- t; f! r, `4 B0 U; _# o
  p->next=head;4 X+ ~! L+ m" K
  head=p;  t% u6 [# }9 d% U% j2 e# D3 [
  for(i=2;i<=M;i++)! F, t1 j" S) U% ~4 P, q. ~
    { s=(MONKEY *)malloc(sizeof(MONKEY));
* ~) K2 @& l% s; s3 i! }     s->number=i;s->flag=1;
9 M. f" P, |6 `, u     s->next=head;8 J2 a2 x9 v; t& ]/ |3 g7 R% M
     p->next=s;p=p->next;/ R7 S2 y* N( L. D: r
    }' W9 i; ]% }. k/ b+ t; r
    p=head;, I/ A: }2 I; v
   for(;;)
9 E% h9 x7 w8 U( q    {if(p->flag==1)8 j. _( ]/ t( D. Y2 V* ]; j
       count++;, }3 }, j# t, X
     if(count==N)9 ^3 I8 e- x2 A5 a9 G/ J7 h1 j( G
        {p->flag=0;# _! m0 S: L" o
         count=0;5 u5 \, w- V& ?* y# S
         sum++;}8 t8 ]2 G8 \" m5 U3 z4 Q
     if(sum==M-1)! G/ q) |0 ~5 H" v* n
        break;
. k) @* a: a/ S7 S  a+ E     p=p->next;! ]+ S+ ?8 V' `7 @" Q# Y5 T! ]
    }
7 Z! _8 i+ a$ Z! J. s    p=6 R" Q: U5 ?! g6 J- k; z! O8 ?
    head;
) e9 s) V) P& o. t: }    for(i=1;i<=M;i++)5 T5 g5 w/ A" U3 C, `7 `
    { if(p->flag==1)6 y* N  y8 M- [0 E% ]. U
        printf("\t%d",p->number);1 k! a' z2 f$ N3 U9 r! Z
      p=p->next;: X7 H7 \/ e( {& K- W/ [
    }
$ `; L3 T5 ?9 L  E7 [3 z1 J* m. D3 f9 ?9 c

. C" l$ `  }1 I) p  Y) ~
1 Y" C1 p0 `# {% x7 q+ ]! j' @# X}
# e& U, F  M) a3 w* F9 R
第二种方法:数组
+ F) t" A6 `; l% y  v#include<stdio.h>
2 x5 R/ e- ^' J9 H1 t1 W#define M 8+ R7 E5 [7 m+ D2 K
struct monkey
! w  y& B1 M0 x, k{int number;4 i8 }5 H: _5 P- G  s: g8 |; l
int nextp;, @; _$ B8 p2 R1 C  |1 d$ S
}link[M+1];9 j  g$ a; F8 t* m5 k6 g; M: F
/ g. k% T, p, ~* i% r* h
void main()9 x5 C6 L( {3 H; C
{int i,count,h;9 U& p- e& P, j( q; H  p
for(i=1;i<=M;i++)
# e' \% [. _, N* B7 f$ F7 X1 W* `{  if(i==M)
& m! i! Z2 e0 _! c/ l   link[i].nextp=1;
4 U$ f" `8 O. O" i   else' l/ k4 j3 l  x0 R( c
   link[i].nextp=i+1;
1 u8 k" U& ?9 J2 ]4 I  link[i].number=i;
6 b+ |; D+ D+ x4 W1 p7 K}
0 t9 I" ^; S3 R' ^+ \$ V- Gprintf("\n");
4 ]; n) B/ A7 B- Vcount=0;6 h: i7 w1 [9 U' i; u& ?3 {/ b
h=M;6 `: x, B/ Z) I  A  o* M
printf("依次退出的猴子: \n");
% A& R0 I% q& b( q5 Kwhile(count<M-1)
& K7 [  [6 @, V( v{i=0;
5 S* {+ j$ E# n# F" u. \, e6 iwhile(i!=3)% K+ I* \* ~# ^4 n  U
{ h=link[h].nextp;
( W# b6 u1 H! L- u4 r2 F- J/ P   if(link[h].number)
1 g" ?1 B1 f$ b' b" P     i++;}& P  m6 @+ ^; P2 _" e/ @
) z/ T7 {: L& {; k
printf("%4d",link[h].number);
% Y6 `. o. [5 J7 o' E( Y9 }% R' ^link[h].number=0;: b$ O7 [! N0 p# v
count++;% I+ p9 J0 {9 W# ?- l: V6 r
}' A+ N! S+ B. d( _

) _3 ~& }2 B- [printf("\n大王是:");3 a0 s/ }# s1 G, O) V. Z" D/ C- F
  for(i=1;i<=M;i++)+ \- j; p7 E, D) Q( z
  if(link[i].number)
3 i* U, N+ j, N. A' o* N  Y    printf("%3d\n",link[i].number);
# K0 o! x8 B' R4 G- _# _# k' Y3 n( j* _& E, d1 J9 J

- E0 \" }* w" ?3 |2 Q}

$ _. \% y8 G0 p/ [( o第三种是普通方法for循环

4 t, W( e5 E/ J+ S#include<stdio.h>* f/ L" L9 j  O  ^9 f
void main()1 p/ u* N. `+ r3 J$ ^( L& Y3 i, h
{ int i,k,m,n,num[50],q,*p;
  x! A. Q3 h7 y- p% x$ _4 V% c    clrscr();
' I, I7 a  b9 p% V1 k/ ~9 f   printf("input number of person: n=");
. A9 m8 Z# r2 R+ `& w    scanf("%d",&n);
: e* z8 [6 D8 o, G5 |printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只  m0 {& r. U' X! O' w. A
    scanf("%d",&q);+ {0 N  w- b0 A% g- P
   p=num;/ O2 A+ S6 G2 n; k( E+ `
  for(i=0;i<n;i++)5 A8 M; o+ m% f4 O# D! {
    *(p+i)=i+1;! S8 i8 M1 i  x8 s1 a( d" O
   i=0;
3 F4 U" @- j. T& F% V: C   k=0;
; l/ h  l" k( w! C4 B2 P   m=0;
. F) z3 g. {. x" ]9 H! B  while(m<n-1)
7 F$ z3 l* g7 K8 E   {if(*(p+i)!=0) k++;( x! W0 M7 M0 Q5 |1 z
     if(k==q)& M( G! l, T2 P! Z2 `. t5 l% F6 z
      { *(p+i)=0;
- \5 ~" Z7 Q5 }: s  u6 F" x' P" \. ~        k=0;
6 k* t4 C; Y6 ~        m++;$ [0 D2 i" _3 b& R, R0 j
      }, g6 M+ a1 ~1 U( E2 x
    i++;9 t, q0 X3 e' |- S: h
    if(i==n)i=0;
. w6 y0 Y7 N: w0 d' v   }
! `5 {* f* e- n7 }% p5 u# J0 g+ f  while(*p==0)p++;0 e+ G: Z5 p) n5 Z: m9 r( n" n
    printf("The last one is NO:%d\n",*p);
8 m+ x& ?8 X; r5 f: P2 t0 g) h     getch();$ K, F  ]( h- B3 [$ ~9 z

+ D( g/ K* q% b6 l: n1 N$ @}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
  r1 O: A, T! Hnamespace 又费马达又费电/ q6 C/ o5 o, q( d9 K
{
2 Z7 g) z# B9 D( \    class Program
$ }# A9 Z/ Y! N3 l# q3 G    {
; n# Q+ U* X& |% [. {  T) J        static void Main(string[] args)
# C& @. N" Q# w# c0 J3 U: D        {2 x' [5 ]2 W/ o; K; k0 b0 C9 |+ B
            int m, n;
9 l& M0 U3 ~  z- S0 D            Console.WriteLine("请输入数组长度");" `( `+ ~3 ^3 [& v2 }
            m = int.Parse(Console.ReadLine());//m为数组的大小6 f; i* h* p, F
            Console.WriteLine("请输入要截取数字的大小");7 C  R  H# z0 |' B0 {5 J( l/ B0 d
            n = int.Parse(Console.ReadLine());1 ~% r: p# ^* c  [
            int [] numw=new int" i# b$ v( P3 L0 i6 K. D

1 `; B, K, G+ B  U&shy;&shy;&shy;;
+ |7 A# y3 V- f5 k/ v! H            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数9 K! \$ P$ v& W8 j0 O/ Y
            {
; `5 Y$ p- P6 g                numw[j - 1] = j;, \3 M) l/ j) k3 `9 Z+ [9 q: ]
            }- B: e" ^3 C# C# _/ F
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!0 n" F4 W( D7 G" U2 u
            while (d != m - 1)
5 O+ j, C/ C5 e            {
' y  z9 ?& {4 n: w                if (i == m && d != m - 1)5 y  w' C7 V( [, ~
                {
9 {) S6 M" {5 A! u5 _                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!+ |9 Z. K! P1 J, |5 R& S/ F' Y
                    continue;
9 u* w4 `- D; y# h, A                }6 P9 ~- K0 l4 V* O5 F
                else7 E$ K* a, S8 d+ k, o" z" o( `
                {
4 M5 |' j) a2 d6 n8 T                    if (numw[i] != 0)% C5 ]  U2 i9 g6 l* P1 a) H; j/ m
                    {  i' I& r  v: H) |# K
                        i++;, R& W; y# K) l# \% y
                        k++;9 Z% T3 v: a8 S8 |' T- S5 _/ F
                        if (k == n)
6 ?. Q1 ?9 d3 |7 Z/ H1 j1 _9 ~* g                        {
; R- l$ E* _8 @                            numw[i - 1] = 0;//把在n位置数组元素的值改变了2 M  E6 C, {5 A, A8 V' t1 p7 G
                            k = 0;6 a7 J& r) s+ m& x& I
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小16 R7 P4 s. G& C! k6 A7 J, Y
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
( P( p. ^. m( {0 S                        }
5 r4 }9 N* [( `1 t                        else//输出暂时还没有改变数组元素的值& m' u# m5 u: V2 |1 h& P( v
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
( F; s0 O  B$ V) g3 M0 `" ]6 k                    }6 ~1 P3 Q  V$ k' c
                    else: p+ {- n" W6 k/ M; C* t' E
                        i++;//数组元素为0,直接跳过,不计数。。。* Z% L- w' g$ N; b
                }
6 O* G' b! q, `! ?8 Q( R1 | , g) ~/ x2 u. L
3 o3 B4 t' P: d' ~+ e3 z% {1 L
            }//结束while循环
% t5 a) I+ c! p: q2 x8 M. s            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
, F4 ?+ \2 G5 z, V1 _           
! J0 |5 {+ M- k6 P  L                if (numw[i] != 0)- H+ B) R, ^3 K# U
                    Console.WriteLine(numw[i]);0 i9 V9 W5 n8 g# t; C. K
           # M$ f. J* A" C# T8 S) c+ N
            Console.ReadLine();6 L* F, b) ~2 z
        }
# a/ s$ z0 a  R0 N; B2 S    }
8 l% m) ~  M2 a  V}
5 ~. T' D7 f: Y8 x0 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-24 09:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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