鱼C论坛

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

猴子问题

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

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

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

x
大家好!
+ Y1 ~) A  Q+ y% Y* T这几天我在忙着编一个问题,我用了一种方法编出来!
' g5 {, Z5 `9 l但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
3 D" @3 F" D; z7 O1 ?6 Y" m7 u注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ! h# r$ J( Y; S9 @. D
8 k/ Q0 e( M1 ^! }5 d

6 T+ i" T" k; j9 U) A$ u5 |
                            题目
$ J- d. a" J! U3 t山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。" y9 X9 `% z9 G: A; g3 R7 L3 V
第一种方法:利用循环链表
9 P  c' z, T. q& ?1 `: y+ ^' r#include<stdio.h>4 x. v/ s9 q- e+ e8 B  l4 y+ A
#include<malloc.h>7 o' ?, L! i0 z3 m
#define M 8            //共有8只猴子+ I7 q- [! j6 s9 W7 a& r9 u
#define N 3            //数到3只时退出第三只
3 g* L. ?/ _+ H( r3 p' M8 I: otypedef struct monkey
( Q1 V9 O! ?1 p! Q: _0 ]8 x{int number;
- D- ~& Y9 }( U# D  [4 Dint flag;
5 M) |: I  ]& b9 `2 [; Ystruct monkey* next;
  w% L& h  O1 w1 \}MONKEY;
+ a% n0 M  j! \5 H0 H1 e3 {main()
3 j+ m/ E+ t5 |0 Y  r{ MONKEY *head=NULL,*p,*s;
0 L, M. Y3 K" Z  J  int i,sum=0,count=0;
( Y: Q# C7 t# o- s  clrscr();              //清屏4 Q% l  ]* v' T* [* d. v' z$ s1 X
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
; p4 }: `& R1 W+ K6 p4 L: L( r/ J# ?  p->number=1;p->flag=1;; ]' t; n4 K' E7 i0 i: l
  p->next=head;
9 |' [9 A" W3 t  H0 e: [+ v  head=p;
! b- a) F* F( C) G  for(i=2;i<=M;i++)
% Q2 w: E0 Q" l  B! e$ R) h    { s=(MONKEY *)malloc(sizeof(MONKEY));
7 B! o" }% m8 A8 ]( Z% }! q     s->number=i;s->flag=1;
- Y8 j5 P3 {& f. e8 V     s->next=head;/ c! t7 T  o: Y6 y
     p->next=s;p=p->next;$ {! }% o( N, z. _8 m- |
    }
, F. e) A- c1 n( N6 ^. ?3 p8 q    p=head;4 L: D' z5 G4 \! z* @; |
   for(;;). N* a# f$ D: n; _4 W
    {if(p->flag==1)% i/ I' \7 G9 z+ v8 x8 N* @
       count++;
8 _3 c" N  t0 Y: _* [( f( k     if(count==N)
. v, x$ H7 M" s4 c& H4 j9 ^$ X$ G9 O        {p->flag=0;$ F5 \7 t9 Z! H' d
         count=0;
# K" d0 J8 b' I         sum++;}7 V1 v' {) ]$ L+ X
     if(sum==M-1)* H* ]$ ^3 }7 o! r  b
        break;
" X+ b: u* y* G- J6 J: ~4 [     p=p->next;
3 @# v- V; C9 T0 x8 [  X    }: r$ M# o; y8 w$ M6 t3 W! Y
    p=2 f$ F- d) P# j
    head;
% n, m# n8 G/ _. l( `8 e" d# z    for(i=1;i<=M;i++)# V7 f. A- A& C0 a2 ^
    { if(p->flag==1)
% d8 D  e8 H8 M  h" h6 q& s9 g        printf("\t%d",p->number);
* u' M( o- s7 m  @$ t      p=p->next;. v; f+ K2 O' T4 L3 [: x5 J
    }
3 \, I: q3 c$ \& t1 k  Q' S6 ^% ^- a- |" v9 F) z: p. z* ~$ \9 [" `4 M7 B, n% P
2 j$ [! B5 o$ _3 `! ]: ?! g

- B/ b* @+ _8 Q}
* r, z- Z3 m2 g7 `  \* {4 `
第二种方法:数组9 Y" h4 v2 u- J" w. W
#include<stdio.h>
. H8 x& K$ f1 N#define M 8, y( o5 ?: N0 b% T; @/ D9 L' b7 u# u
struct monkey
- N' D, i; _0 y0 F8 h5 Q3 J% h: z{int number;. d0 |. K5 y( |) {. q
int nextp;# t) i8 Q( K- }1 R6 Y+ v8 H
}link[M+1];
0 d- m: n2 i# }2 K; a+ T
% f+ j2 X8 B  C6 S6 ?; _) bvoid main()/ A; T: q. o( L+ `+ A
{int i,count,h;
' F" P6 H1 m- D! |  G; qfor(i=1;i<=M;i++)
/ r2 k7 t3 b- ]( G; g3 S{  if(i==M)
% b$ \* G1 y, {5 m  |# {   link[i].nextp=1;
$ ~7 c, Q( q3 B! ?7 v% z" R   else
% D, }, ^5 q3 }" m: k! y0 [) |0 X   link[i].nextp=i+1;' ~! l+ b0 p! \. q# s
  link[i].number=i;& n1 L! p7 Q$ h
}0 [! u2 L& p1 ^7 F
printf("\n");
% x  |: K! H; f5 `% {/ V+ Z  \count=0;
2 x, P5 N8 M  `$ A7 }h=M;
  ]1 B! ~* ^8 Aprintf("依次退出的猴子: \n");9 e' d( O3 M) e" K& b; V
while(count<M-1)% G/ n: n2 |" r8 r( v# q( V+ h
{i=0;' z5 B$ F4 g5 n4 r- F4 J
while(i!=3)" S4 N6 S$ c$ {3 J/ w7 K) s
{ h=link[h].nextp;, R3 l+ t9 U! B; B/ @
   if(link[h].number)
9 x3 W- j7 E- j, D9 O0 \     i++;}
8 \# I4 j1 |. _2 x: W
( V$ M7 B+ F: O4 n3 E6 ?printf("%4d",link[h].number);& V: M& u: d8 [
link[h].number=0;( \. U; j& b. y9 B& d% Q
count++;
; U# }% X% _) {( p5 Q}  T  }4 G0 h& P/ z$ J+ z

' w1 t! q  c6 y! }  ~. pprintf("\n大王是:");" x  a1 k) |; H: H
  for(i=1;i<=M;i++)
) J+ y- v1 w+ Y  if(link[i].number)- T0 c0 J; r6 J# H  {' f: F; }
    printf("%3d\n",link[i].number);
, V- v' H0 \: }; V/ x: u+ l" V2 l- }6 C2 G5 `/ R

* o( M  a; Q5 K4 v3 u}

& q8 ?$ s! o6 H3 D第三种是普通方法for循环

4 ]: p$ [: n' _" Z" n; _  x5 {; x- Z#include<stdio.h>0 z  j1 C& O, }9 Y0 P5 \
void main()7 g6 A: h. u& H4 l% H3 L
{ int i,k,m,n,num[50],q,*p;
+ W3 G* `" w) m) X. P    clrscr();
. W/ e  G$ f8 H+ a3 x   printf("input number of person: n=");
1 t8 D' `. ]# ?! r5 n    scanf("%d",&n);& Y4 S( n4 V5 ]
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只- Q! ?, ~2 z! ]$ f1 p: Y
    scanf("%d",&q);9 L" k7 f( u8 {* ?! z8 }0 J
   p=num;
9 M! l6 O0 {6 P0 A  for(i=0;i<n;i++)
3 j1 N! C% B: h; H; M  S+ ^    *(p+i)=i+1;
+ o$ l; |6 _5 O% b   i=0;  R/ g( I* U4 e5 Q5 n( P
   k=0;8 [$ {5 k, O! y( t
   m=0;
! P) D$ w6 c1 w/ o  while(m<n-1)
& v9 x/ [5 J1 x$ d  O4 L   {if(*(p+i)!=0) k++;
8 E3 T$ s+ h: M6 x     if(k==q)
+ l( x& F) ?8 O( j" a; P      { *(p+i)=0;* X# M1 V. l7 q! w8 }
        k=0;
9 y! G8 r% f! {: Z, m) f        m++;8 ?2 V( q. X: ~
      }1 e* a. x: J  b# a
    i++;# _! _! B! v0 x+ G% d% d3 v# W5 z. \
    if(i==n)i=0;: f; }& `/ k  }5 `
   }/ S5 j1 n- `8 o7 g# V# {, U: y( K/ |& ?
  while(*p==0)p++;
- Y( ^! F' F! l' j/ I- E    printf("The last one is NO:%d\n",*p);/ Y$ w( \! k5 F
     getch();
* \. h( A5 c  Y1 |8 q  {6 L' W4 }$ X1 ?( W* N2 M( [5 ]% ]# A
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;8 n) E7 V' b7 y5 P6 }! n
namespace 又费马达又费电( j* e; d) T" G; Y
{
% \+ X* r- ?, @5 u) C0 ?+ N- `    class Program
  w9 O: z+ N8 r4 w9 A    {0 d* I; W; k( j2 O# q' P& N* U( j
        static void Main(string[] args)
. X2 ?! X! a8 o0 C8 G0 [& E, v$ Z; G        {# z+ a. l* a& n# j8 x
            int m, n;
; C/ ], i- T6 g& _; N  ], g            Console.WriteLine("请输入数组长度");7 D0 m8 m1 I0 A% T  F
            m = int.Parse(Console.ReadLine());//m为数组的大小
; t' S% @9 T9 @$ x  N            Console.WriteLine("请输入要截取数字的大小");  {6 a4 Q) f* W
            n = int.Parse(Console.ReadLine());
1 [+ v) ]& S4 N4 g) L9 ?9 \/ a            int [] numw=new int: {8 [: ?- O0 [: v" P
4 o9 _9 t6 e) D# J: @
&shy;&shy;&shy;;
! _5 s* Q7 F0 r9 m; |2 W) {" A# k            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
) \" j" `) z3 D# m            {
+ r- h! x! ~' m( R- r0 g* t# \                numw[j - 1] = j;
, X3 C" S" O6 a8 x# _            }- T& O" q: m* X' l
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
( \, U- j* h( [) _8 G2 L# i1 ~            while (d != m - 1)
! g8 |- @0 R) {4 Y9 \" _$ h            {
& F3 m$ M. d# t                if (i == m && d != m - 1): C% j( \! n7 B1 [* t
                {0 f- u# |2 |7 Q( w
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
; a* `: R: L' O: q! Y( d- [8 _                    continue;& d' n( {: Q3 ^
                }
' o6 I& D! |( o/ R( S' P                else* u6 @1 q# x( b' B2 Z' z3 k1 d
                {
, Y% m0 R5 }0 k' ]                    if (numw[i] != 0)
$ z: X" C9 k% z( c                    {
$ S1 [% y8 |# @0 X. D6 T                        i++;- I/ p$ G3 Z% `. L
                        k++;
$ Y4 ]( e: ?% z3 B                        if (k == n)  N. B# o2 U( U
                        {
' x5 @2 a4 I/ w+ B                            numw[i - 1] = 0;//把在n位置数组元素的值改变了% s1 C0 J. n: y2 ?; @
                            k = 0;
1 |8 h) `4 W6 B$ M) M              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1, u3 e, f% L% s; l6 V9 l; i/ O; z
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 J, L% m. }$ e- F9 Z; @( I3 x  w, j                        }  C5 u% C3 n# s2 f8 y
                        else//输出暂时还没有改变数组元素的值$ t2 Q+ r7 m% e
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
9 R; o6 g+ M% G: J8 _                    }5 {% L8 F4 c. F6 e. p0 V
                    else3 K$ b& ?' a2 ^/ l7 w
                        i++;//数组元素为0,直接跳过,不计数。。。
  P2 I$ m6 f+ z8 I* D3 K                }
! D0 o5 W+ J+ d) u7 V+ W% a
: _# x1 I0 Z2 B+ C9 j2 o! O
' Y7 n+ i8 m9 I& ?3 ?            }//结束while循环2 G; U8 X  G% o# Y& B7 a: u' A) T
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦9 x. T' @2 @% }) v: Q5 V" ^1 P, v* a) t
           
( C5 ?8 M" i1 X# |: n- s                if (numw[i] != 0)+ o7 T( @) e. n" o, G
                    Console.WriteLine(numw[i]);
) @% h# E2 o9 x  w: |0 e% |           & q0 _4 e  O% C9 W8 ^  r
            Console.ReadLine();
* N" d& G$ S# k        }1 }5 ~0 D9 S3 ^/ E( T
    }
  O9 Y; T1 d7 E# w! y1 I7 ]}
" @( q! c) w) }, s, H" |
小甲鱼最新课程 -> 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-13 06:47

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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