鱼C论坛

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

猴子问题

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

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

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

x
大家好!+ ?, `- h; q+ Q+ N. [5 A) G
这几天我在忙着编一个问题,我用了一种方法编出来!
9 _; m% d+ D  J: a0 \& G9 ^但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
: j( k: z+ a4 ]& [5 U注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 5 o0 v. q- _( `# [5 F% Z/ a6 ^

3 L) I5 k9 {" ^0 `/ o. Q# \8 N: g7 d7 ?+ k7 V% h; _; l
                            题目/ l* j; E1 l. ^' |, `
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。: o3 w! O$ S* p
第一种方法:利用循环链表$ n; K: C' a5 P" k" v
#include<stdio.h>
6 ?* W& d: }# }( l" G; i#include<malloc.h>
; E+ Z5 M: W. g4 n- f! ]#define M 8            //共有8只猴子4 q/ m( ?$ B3 c- S9 J: r
#define N 3            //数到3只时退出第三只5 h1 e7 n& |* P" Y+ B: C+ m
typedef struct monkey
6 U5 x( Z1 x6 h, E{int number;
% [9 m5 E2 f1 Hint flag;
, e+ k8 a$ ~' ?- A8 i, Xstruct monkey* next;
- x$ V" ^# p( O+ K# x' D7 x8 Z, I1 j}MONKEY;
, w1 N' O/ B) }8 Hmain()1 h. j4 }. ~6 i
{ MONKEY *head=NULL,*p,*s;
- p' q  Q- o6 O. P* [; H+ e, U  int i,sum=0,count=0;; \% w+ v$ h% q0 }$ C0 \; w! r
  clrscr();              //清屏8 v5 C7 {/ K  |* h- E
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存+ k. A. F( f& F1 ~1 m
  p->number=1;p->flag=1;" x% U, d' K% d
  p->next=head;4 G0 l4 L$ }0 u) I: u
  head=p;( W1 \; j! t" Z0 z
  for(i=2;i<=M;i++)& g' I+ k4 o+ m; U0 c
    { s=(MONKEY *)malloc(sizeof(MONKEY));+ w6 _  S1 M2 h* T6 b: W
     s->number=i;s->flag=1;# e' d- v# ~% e3 O/ E; v1 ?
     s->next=head;$ b+ {/ I4 N) \% e
     p->next=s;p=p->next;5 F- X2 ^" m6 Y1 u) [; e9 |4 j; |3 x
    }
$ S- a- j3 j) a9 ^2 S7 i    p=head;1 \* [2 l3 A' g. ^- D5 y5 B- ^
   for(;;)8 f2 {0 C8 S) }) y) y3 X' \3 |
    {if(p->flag==1)& S! f! E5 N' p5 m; L9 O
       count++;( [( [9 U# \& \7 t! Q- _5 S" J
     if(count==N)0 _; [, O( E0 v
        {p->flag=0;) r: c+ K. \8 O7 N. Z3 P7 @5 W$ @
         count=0;7 y3 E& Q8 }6 P8 C  ?! v
         sum++;}. K, t/ W7 s( I0 R) i
     if(sum==M-1)
( V$ j' _$ ~3 N) q        break;
) ^5 \9 M8 O% o4 w2 U) f     p=p->next;2 w7 {( ^3 h& k  _, b. Y+ U8 K& L. N
    }
$ I( q; v! n2 \+ w4 O    p=
8 \3 P! d" n9 K  T' O    head;
' F, ]3 b. I1 o; W) o& \! ^; |# v    for(i=1;i<=M;i++)1 d3 F. y5 r8 x9 c8 B
    { if(p->flag==1)( }8 R+ t/ R7 y3 l8 ~
        printf("\t%d",p->number);
' `  h4 e7 q% r9 |% A9 w      p=p->next;0 d* ^: C& I0 T, b: h4 }; h
    }. y* c! s* ?/ |9 M( r
8 `' I* h( o# d" S2 T3 q, ]" L+ e

6 n) x2 v6 e7 Z
  _6 C1 d& P  X0 q: h7 {4 a}
) _, T1 z6 d, v0 w: K& }
第二种方法:数组7 Q" D6 [2 F0 H6 R3 `( \& F
#include<stdio.h>) d9 i0 b5 S( Q1 T. ]
#define M 8
6 t2 ^2 N7 L0 F5 ustruct monkey
& x: r  D% o% v2 K& O& d8 E. x9 I% Z{int number;
# ^! Y% I0 \( ?int nextp;: D, f% A% \0 z. H. e1 I
}link[M+1];: b2 M7 b2 E% T. i1 W5 M7 u
$ F4 \% l  l, w, n7 z
void main()+ X4 N1 b9 d. Y2 G
{int i,count,h;
6 a9 @5 n3 o  j) R- bfor(i=1;i<=M;i++)
6 m  T8 r3 N, \9 u( i) C{  if(i==M)7 ?. }; j  p( c+ D! ]* k% m) ~
   link[i].nextp=1;
$ C4 }  }9 s% r1 x# u8 h9 X   else
8 x2 |; x( t# j& j& N# V% a   link[i].nextp=i+1;
/ V, A& N& w) d, t7 u  link[i].number=i;) p0 A7 h& Q3 c+ e
}, u6 Y( u$ [* Z! e# Y% j
printf("\n");
( }$ j' g0 {" B% B" Z+ y( }! Wcount=0;
! ?- o: U& T" fh=M;- |0 z8 ~/ d$ G. B$ l
printf("依次退出的猴子: \n");# a5 p. k8 Y' s0 I1 p
while(count<M-1); Z. W* p- i) U3 ~
{i=0;7 j- E) G+ B# a$ G
while(i!=3); J3 j! O# f) K% \. R
{ h=link[h].nextp;8 G% t* E! L, B4 w: T. [& L
   if(link[h].number)
& r# s+ r% @  D/ n     i++;}6 Z$ m3 S) y3 B: \
' `, H  I4 }# ^2 O# {& N
printf("%4d",link[h].number);/ q3 n9 i5 H6 N. |6 s9 {6 X3 }
link[h].number=0;
7 P1 C. o8 n% H" ncount++;% X; p! a: Z" l+ `, a( {
}
% ?, W4 D9 J: `. M& Y2 ?+ S& Q+ x0 g' J3 B6 T' K$ k9 ^
printf("\n大王是:");# n% `( B& I0 w$ n6 z$ s6 g) w
  for(i=1;i<=M;i++)
( n; M  k& `& l  if(link[i].number)
  \* v) d' m3 v- e    printf("%3d\n",link[i].number);+ t- {: Q7 |& k7 p( ?" r- e( ]

* p( r1 h9 _( f
6 T" I& l8 R, X}
6 L' z8 v2 _- Y- I8 h4 V
第三种是普通方法for循环

& d9 c- P" s- g; X8 t, i#include<stdio.h>
+ J6 R& x" O8 B: q) D& c* |void main()
# O7 j* o; m+ n, h" _; o{ int i,k,m,n,num[50],q,*p;
8 G! t/ w; v: ~+ W0 B* H3 F    clrscr();
! ]0 s. x- S6 m5 U. u9 T" ^   printf("input number of person: n=");
  Y, s1 k, c- r% q- C( T) N5 f    scanf("%d",&n);
' Z+ \' E9 D* Pprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
( Y% V' b( O0 o2 b  i    scanf("%d",&q);
6 {( c+ C& t- `3 |, K: @   p=num;" p7 B! _& B  X- k, X
  for(i=0;i<n;i++)
2 w& e: L" V8 b3 G7 u    *(p+i)=i+1;) S# Q7 i9 |. C
   i=0;
4 J; ?5 p; O+ E3 s+ c$ A) v, E3 C4 ~   k=0;
) L8 r! F. T# K. g5 x   m=0;
* X1 ?, d0 y  T6 J  while(m<n-1)4 [7 d; t8 g) Y& Y5 l9 o
   {if(*(p+i)!=0) k++;6 E5 }# D# K& G. I. j
     if(k==q)
1 }  t7 C3 |0 k      { *(p+i)=0;% j# O! [( x5 x& a
        k=0;) k) C: f. f, H7 b3 c: N# o. h, |: H
        m++;
  U5 [3 @$ h, a$ |      }
4 g* S# B" X8 X- T8 H/ g    i++;( O/ R. g+ @9 i  B0 N1 s0 N
    if(i==n)i=0;; \3 j6 E# Q( e  s  S+ u7 z
   }
0 ]6 E7 Z. f$ y+ r4 A  while(*p==0)p++;
3 m( D  g3 v" p& J6 L. P) m    printf("The last one is NO:%d\n",*p);
) [: D# j3 R2 u. Z  T$ M; E% P     getch();+ {$ H/ I# L  U6 w1 B

( a# J$ W: C& U4 g, |& R}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
) Y4 C* ?: [# R, r: ]; qnamespace 又费马达又费电$ I# P6 L! u2 }8 u; W
{- Q# z' S0 _# x4 `. M, K- }
    class Program1 A5 n" c  m) a9 {  W
    {
+ |5 Z4 T3 P" r" d8 q$ R        static void Main(string[] args)$ U8 L2 G: i7 A6 u
        {4 x6 u. ?% D2 @5 t0 C
            int m, n;
3 g7 o7 e9 A2 u) C8 F% t/ G            Console.WriteLine("请输入数组长度");
, c4 s8 b3 L. H& b" J            m = int.Parse(Console.ReadLine());//m为数组的大小
/ Q) K5 `* E0 U& z( V: D2 R0 @            Console.WriteLine("请输入要截取数字的大小");
, q5 W% d! k( R8 P, S( r' X            n = int.Parse(Console.ReadLine());# A0 Q* D& ]/ u% D. b5 u3 I5 S8 H0 G
            int [] numw=new int8 }' ?) z6 s% a) V( p
+ N9 k# c0 H* a  {6 Z0 w7 A
&shy;&shy;&shy;;/ \" G9 k/ q) H  [* t; S/ O; ?; C
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数& h1 D0 ]9 H2 ?& y/ O
            {
3 U+ n( G! e( @                numw[j - 1] = j;
3 G5 ]0 I& w6 {            }9 U2 n7 P. ?8 n
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
* F$ z8 m$ e+ L* S/ P# c            while (d != m - 1)
/ J* Z* a/ @; [7 Y! n            {: E. ]( X  Y+ E; E
                if (i == m && d != m - 1)+ {2 h% ?0 x8 l8 D5 {
                {5 E6 d, T9 y: ]
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
* v( ]; N: ~+ h/ c3 M" v                    continue;; m. Y5 U. ~2 u4 B
                }( \# X* A8 ^4 b+ ~7 i
                else$ ]. Q! q/ T: B; S6 `2 e. ?
                {
# R4 l' O% N5 A+ y, L                    if (numw[i] != 0)
4 Y% C) D0 s& p7 e+ ~  G                    {" j# s% @( m7 j6 z7 |6 o$ O% j
                        i++;
) L/ g& {7 e+ k$ B0 b' E                        k++;) j. l1 u7 g, i' d
                        if (k == n)
( K0 G9 F! t) E& z. B  V3 e9 ~                        {6 x& u+ z0 e* }( k- Y
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了$ R% ]: E) s( U0 `/ _+ }! L
                            k = 0;
& \; H0 C+ _+ v              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1  t+ L1 u' s; _( ^% w
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);( s3 ]9 s: A. V
                        }: w4 Y- I5 L7 d/ I+ B
                        else//输出暂时还没有改变数组元素的值
0 p* e7 D& B" [7 v                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);$ q& I7 q; s4 H
                    }% d. X" z% X8 _* k- f4 C, i
                    else
' [  x4 h- b) _1 v& ^                        i++;//数组元素为0,直接跳过,不计数。。。
, H. M1 A1 ?+ u8 {2 w                }
' G0 q6 U* h  g/ [
9 y) U" {; S% y8 L5 m, `7 Z$ _5 A" P4 C* I' b, X
            }//结束while循环6 w, l, K- v/ o5 H6 M
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
( q, g, i2 \" L# F4 j, W$ k. d           
% M- w6 ]: U' F: B+ Q' o                if (numw[i] != 0)
( I2 r& G/ P6 c9 i                    Console.WriteLine(numw[i]);
; O( M2 Z- m0 w- n           / N* ?0 E0 m" q9 ^& k
            Console.ReadLine();5 U9 w& ~% F3 g3 H/ d* _5 a
        }/ F; Q2 a# L& e+ P7 f$ V
    }. j; a5 g) v! |: _0 h" e- t
}
; u* Q: Z( F8 y  S4 R
小甲鱼最新课程 -> 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-3-9 16:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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