鱼C论坛

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

猴子问题

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

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

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

x
大家好!
( F$ T, H' w* V/ r这几天我在忙着编一个问题,我用了一种方法编出来!4 _1 u( e! q. U8 p$ E. G4 ?* K
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!" z& r/ I( ^9 |! f9 g2 V
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
/ ]+ }, @) i' w7 M0 [" v
: p5 }* t" _9 v' t9 R% b, Z( v  Q. V: e) E
                            题目! B7 I) f6 m7 s' d# D: a6 R3 j
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。* |+ F! T$ W5 {- e9 k4 c% ]: F
第一种方法:利用循环链表
  f9 V& K" w4 @1 ^$ {# n#include<stdio.h>
" h! Z3 G: R2 g; d* _/ o#include<malloc.h>- U: r$ C0 a8 J' b, E8 D
#define M 8            //共有8只猴子
' a1 n% n0 T2 X: Q% a3 x1 b0 k#define N 3            //数到3只时退出第三只
- a$ ]' F) I: dtypedef struct monkey# F# `9 `$ Y8 V
{int number;
; M! T) |2 X; \( hint flag;5 ~. y5 _  [9 O  p0 E
struct monkey* next;
) X+ I; ?  g3 b8 o- x' ]- s}MONKEY;
0 P( N) T; r! u2 nmain()
5 H5 D7 ^) g* G3 S* X" \" j. {{ MONKEY *head=NULL,*p,*s;5 R9 A0 c& s5 v( ~* O  t) G
  int i,sum=0,count=0;
1 i. E! \+ T0 F  clrscr();              //清屏) H9 N; o# K5 d/ P) {
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
  D$ G# U$ d7 W' Z! c/ |0 |  p->number=1;p->flag=1;, f0 t2 ]' p% i
  p->next=head;7 P+ ~, Y. x- z9 d% x+ L
  head=p;5 ?2 i: b* n2 Q* t: z0 ]' y
  for(i=2;i<=M;i++)' O6 a! H9 [( `" N/ |- J# @  [( {
    { s=(MONKEY *)malloc(sizeof(MONKEY));0 J" {% C- d! N+ B# G
     s->number=i;s->flag=1;
( P" l1 [5 v2 O" d( F5 q     s->next=head;% p* P, \/ t% W0 Z. d3 O
     p->next=s;p=p->next;1 w7 Y+ K6 |5 Q; u0 h* P
    }* M; a4 f5 M. |3 S' t! \  [; ~
    p=head;/ Z: T# u. \- J; B9 }; g
   for(;;)
- M5 v. X4 ~; ?+ q6 ?    {if(p->flag==1)0 u1 `2 [5 |5 y9 ?+ Y% \- y
       count++;( v1 x2 u4 L: L1 j
     if(count==N): P/ w3 @; U7 r/ B+ P& H
        {p->flag=0;" K8 j; |7 `$ f3 z: N0 N
         count=0;
8 v2 D, M2 h( H, l$ {3 a& _         sum++;}0 H( |0 k* `6 T2 v
     if(sum==M-1)
  G1 f/ T$ v) U+ ]0 x        break;5 _& R5 S6 u1 k" r
     p=p->next;
, v- d4 S9 D; _: @# F' S    }
3 N" H+ Q  V$ m  h    p=
. G) z4 w  Q: u  o    head;3 C3 m, r$ }. i  }
    for(i=1;i<=M;i++)
  L6 y0 n( y8 H, L! U( `    { if(p->flag==1)
- e) @* e: ^4 |4 m* `- y        printf("\t%d",p->number);$ X! ~' z5 l2 U% Q
      p=p->next;
# \5 C) |6 ^9 }' b& N( z2 j) u    }
$ P2 h, v( @0 S9 q) U
) n; X0 }2 H  T$ _( |- r/ r/ R
  g! l& @5 w) f( e# x1 B
}

: r# \0 `7 e6 R+ j第二种方法:数组
4 D6 ^! F* y4 c3 o; O#include<stdio.h>
; i) V7 @7 e& Z#define M 8. u7 D2 |, g# q! T2 Y
struct monkey
5 _& R) T6 g$ W# g, `{int number;
' n- W/ z% l8 u4 z+ {. tint nextp;
/ ]; a( `+ F2 C' J0 D% ?}link[M+1];
9 e: X1 v! i# i7 s/ `( L7 J* T% A* d+ T
void main()9 [1 m2 f1 m6 _/ @4 E+ Z
{int i,count,h;
8 S9 ]! X8 }6 Kfor(i=1;i<=M;i++)
# A; W& m6 C+ {$ x" I{  if(i==M)( j' k! n, v% }: X# @
   link[i].nextp=1;
, ]& L7 M# i4 Z7 \! b* f4 w8 n   else3 A) I4 ~0 @7 N9 N1 \+ |
   link[i].nextp=i+1;5 C. L, P/ {3 I; Q" y; v* }
  link[i].number=i;, E4 O9 a5 Q1 C* }+ \) B) _0 p  o
}" P* R, Q) `. F' s. B
printf("\n");
2 ~. d8 N; X/ j8 \count=0;
6 T" _5 ]! g  k1 ?( gh=M;8 F4 g3 ~( x6 `- O, ?% k* }
printf("依次退出的猴子: \n");
$ C) d" a7 [0 y* a- I; h: V# k& mwhile(count<M-1)
& o3 e  k- S4 S& g( l! B1 d8 C- t$ ^{i=0;/ m6 j  D5 g! N) R* U% }$ u
while(i!=3)% S( z# S8 ~* m1 t% o" x
{ h=link[h].nextp;/ b4 b7 ]: T( h% e; x# M
   if(link[h].number)) `( N$ P6 K. \2 b( W$ k1 R
     i++;}/ d. T) J0 C. ^9 _+ y3 i' d

2 i3 K& ~# s. F8 J# fprintf("%4d",link[h].number);, Y4 B7 I; R) |; n. j7 ~# c
link[h].number=0;
! i0 Q+ p2 B, u4 ]/ I  x. ^4 gcount++;
! g2 y; t' z* k! d}, l" Y. I9 h7 s# g0 |
1 K* j# N$ \) j8 n. K1 F
printf("\n大王是:");
! N3 ]+ q- W* r8 l  for(i=1;i<=M;i++)9 L9 X3 I$ c4 G! i7 ~5 {
  if(link[i].number)
4 R9 h3 Z0 _( H    printf("%3d\n",link[i].number);
; d4 m1 r* y4 K2 O+ _  S8 C; Y( {0 C; B. b. W9 q$ [4 |# H% t
  P9 }* S9 |6 s8 w% k% W3 o
}

% j( H$ N0 W: v; L# E第三种是普通方法for循环

, p1 p5 Y0 C/ Q9 b#include<stdio.h>- M3 A/ p* Y, ]7 U, m5 |
void main(). }; v$ K  H, x1 d
{ int i,k,m,n,num[50],q,*p;6 _) y  g0 Y4 J
    clrscr();$ M& d3 b" G8 `/ i" _( L
   printf("input number of person: n=");
) o- R% t" g1 i3 x5 k    scanf("%d",&n);
7 Y' Q2 \+ f6 X8 oprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只% I0 h- B8 y  g1 b
    scanf("%d",&q);0 x" a2 u, r( ~& M! S
   p=num;
, L- k: E$ d; B% B* ^  for(i=0;i<n;i++)
# }) ^& M* K2 D* c2 h    *(p+i)=i+1;: X) Q0 p7 y3 |  ^) R
   i=0;
& G7 w+ M- C5 ]   k=0;
7 `( w' r: o- e* N4 ~$ s   m=0;
9 Q4 ]+ x9 r9 i2 q  while(m<n-1)/ Q$ ^/ C" S; H) K4 y: p
   {if(*(p+i)!=0) k++;9 X2 \" m* U$ Z& B' R1 \
     if(k==q). ]  J) X) k9 ?% v7 T" c
      { *(p+i)=0;
1 e7 A9 @1 D, P. k        k=0;
) s4 @3 ?: O: A( X. h9 O        m++;3 E8 x! c* W+ R! Y( ?  s; P4 U
      }3 D6 t; S( h3 V) x$ F5 i& n' p
    i++;' v! O9 a- v, n( J" M" H
    if(i==n)i=0;9 g. b* ~7 @8 e9 x: J) h
   }  D0 a* M1 e( [1 O' I) `" G
  while(*p==0)p++;
0 J; ]- r, o# ]1 U! t    printf("The last one is NO:%d\n",*p);* D1 i( N% Z& T  G) q
     getch();
! x7 E8 {5 x' v8 W" M) {1 m$ z$ X
; ?) T# `0 X- I% K0 n3 B1 Q}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;( T( T& D2 ?; b% ]( ^
namespace 又费马达又费电
( H$ s" J6 d; B8 L{1 `' x! [/ y. J
    class Program
9 \: Y. G0 I0 O' \    {
, i) p8 L/ @3 o" q5 c7 k        static void Main(string[] args)- h: F. ], I: J; {* K. L$ Q5 l
        {
2 I" g* g  R) K& W% ]8 s, J3 k            int m, n;
: G( |2 ]! j8 @' Y" U( i3 T            Console.WriteLine("请输入数组长度");" ~; t6 T+ Z1 p8 W9 ?/ N. L# P
            m = int.Parse(Console.ReadLine());//m为数组的大小
1 a0 C; m. Z' _9 H7 m            Console.WriteLine("请输入要截取数字的大小");0 q$ K6 C4 \+ c: V% n9 ^% z! \" e1 @9 \
            n = int.Parse(Console.ReadLine());
0 d6 O  g( |3 v8 F$ l( o. C            int [] numw=new int
! V, b  c" i7 b8 o& g# {/ I/ K( m' M( @
&shy;&shy;&shy;;
  I- z5 L) ^8 Z  a! K            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
; ?% g; a& v" @/ M$ G% {0 C            {
% N8 s- L; s( E' W5 \$ B( ~0 B8 g                numw[j - 1] = j;
+ E; ^, g, Z+ \' A' v, N2 j) k, B5 o            }' _3 J3 {. n) R; y* l/ d- R7 `4 M
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
9 c3 z/ N3 N% {3 @# S6 T            while (d != m - 1): r6 S$ J. H7 f
            {
6 I% f( k& Y0 ?- m- F3 O                if (i == m && d != m - 1)1 T) A" P1 V& Z8 g5 u6 T$ S) t
                {
$ n0 X+ U( H7 F' t8 ?* @! o                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!3 W) Z: F* ?9 J& }+ x+ r8 N/ l5 |
                    continue;- P# l) j' v& m  V3 I
                }7 v1 S! M& o% H# j: F
                else/ W; i8 W8 I1 F" ^/ r$ O
                {
$ Q5 w& Z1 l5 l4 y# m. d' i- Z/ x                    if (numw[i] != 0)
# Q. D4 m& L0 ?. X) V                    {! c" C6 g1 c1 R- z, g/ D
                        i++;
* |0 t  A' z0 j0 N3 a                        k++;
. w) M. B5 r4 z: U  @& c" e                        if (k == n)6 R& ]3 V4 p3 a/ W: t; f, e- |" c
                        {
8 W) t0 z5 @' U& a                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
& c' F3 c6 A; L+ F4 M/ L7 W- [                            k = 0;* ]9 d; ?/ H0 O  h* q* Y. p: G3 z
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1; Y) s# Y. I+ o+ X. ^
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
' r" f# P# Q% S/ _4 j2 ?                        }1 [/ M( x. f0 ~' J
                        else//输出暂时还没有改变数组元素的值
$ x9 O# [1 q$ j& C$ ^) n                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 T! O1 R8 h$ P$ j( o$ k
                    }; d" O7 A' b& k! M% P1 F( b# r+ S
                    else
* r8 _& J  A/ {* ^% T9 U! |, _( b                        i++;//数组元素为0,直接跳过,不计数。。。4 D0 D' {/ \9 t5 \) k, u2 h
                }
) ]: k- Z6 k7 x , G8 ^" J) j. H: U" P

# l, w8 ^+ ~, s  B: A            }//结束while循环
7 o4 T, I7 |* X0 Z6 \# n* D            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
8 \6 a1 s( m/ L; z, b' C7 a7 V: Y. V: o           
7 a9 U% v* `5 Z0 b4 K                if (numw[i] != 0)( P- g# c) o2 {# P
                    Console.WriteLine(numw[i]);0 P, B7 _; k- E0 u. R) B% |
           
3 ]( g/ O8 z+ q& M& A, s. ~            Console.ReadLine();0 f8 x9 Q0 ]9 r' k
        }
; u6 @9 Q% J: I3 @7 V% C    }8 {! Q' T6 X" o
}
- \7 ^, E, U: ~/ I% z1 ]
小甲鱼最新课程 -> 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, 2025-10-15 10:51

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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