鱼C论坛

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

猴子问题

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

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

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

x
大家好!
4 b/ R: Q( {9 z" {( ~# i! _" S. }这几天我在忙着编一个问题,我用了一种方法编出来!
. j* y& F  m( D3 R" u6 @1 f' ]; K但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
  b4 N' W: f. G: D注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
+ {5 a3 D) K; \; L: L  ]4 ]
6 w. y5 P8 H; W$ r( N; A7 ~$ {% ^% l" g% T2 U
                            题目
8 S% G1 O, Q' t- o* c5 E山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。/ A, h% o4 u1 E7 {2 S7 V, U
第一种方法:利用循环链表# Y1 Q& G' U; i+ m9 O. F/ @% v. n
#include<stdio.h>/ Q6 H: }' O: C
#include<malloc.h>7 X- w( V& y* M$ c! Q
#define M 8            //共有8只猴子4 G9 l4 b, Q' K. S
#define N 3            //数到3只时退出第三只
! L9 l5 e+ r7 ptypedef struct monkey
+ g& f5 ]) }- c. F0 L{int number;/ b9 _  h' {: ]5 Z7 @
int flag;
1 V$ j9 V. ^- `$ \* h. Ustruct monkey* next;. V- r) r0 H' {+ T; Z* V, v, r
}MONKEY;
9 k. E% O, E/ m. {( A& Qmain(): W6 n2 S$ T' P6 F
{ MONKEY *head=NULL,*p,*s;
) H% l+ Y6 }7 k0 U" d  int i,sum=0,count=0;9 b+ Z0 s& B  N+ q" T; p
  clrscr();              //清屏
% k& y* |4 u0 H# I  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
; o! ^, T9 Y* T/ j: G  p->number=1;p->flag=1;8 K0 O" c2 i- Y& y
  p->next=head;7 K, Y+ F4 u( L* V7 M
  head=p;
; Z" b5 F. D! P  for(i=2;i<=M;i++)' ~8 O+ @  a9 R  A$ a
    { s=(MONKEY *)malloc(sizeof(MONKEY));
; ]0 K- o2 ~) f- G& `     s->number=i;s->flag=1;# k: ]1 Y2 f* P3 I, r- I0 h
     s->next=head;, a% X+ r0 _# C. |, z  A
     p->next=s;p=p->next;( Z1 A. @* o9 u- ?; L9 D) }
    }
5 ^8 \- F  }0 h" e& C    p=head;4 A* H4 O. B) L) k
   for(;;)
/ L! ?7 R, u4 v2 U8 x    {if(p->flag==1)- u' \4 _' j8 I! e2 M" R7 ?
       count++;: i* b. y( F+ @: ~1 m4 e. n+ M2 [* ?
     if(count==N)
2 h  @6 h5 S1 [2 r. N        {p->flag=0;
! Q* m( k; n) C         count=0;8 }6 x( i2 X# x! {1 L
         sum++;}
8 n$ Z" Q, h; g! g     if(sum==M-1)
, ]0 i- t: X9 W6 S        break;
( M% K/ g! o5 y! S' l1 @     p=p->next;- [. A# }2 a* U, p5 S) }; \
    }$ k0 @! [; @. J7 A# N* B' A) X
    p=7 v9 B/ S6 E; H3 e1 U- S+ ~# {/ F* u
    head;7 z; i& Y1 B: c$ K- ]. `6 _7 c; M, v
    for(i=1;i<=M;i++)
5 N7 r1 @- g  S, `9 ]  n9 D- {  }, ^) E    { if(p->flag==1)
% A) a4 P& u5 Y% v- a- {        printf("\t%d",p->number);
, S9 q( z' e: L) f      p=p->next;6 p2 n3 R, Q+ Q+ \+ Z
    }
4 [0 x: w2 X8 R: Q/ w1 B' N! M) {0 S
/ }3 Z* [. [5 r; ]5 ?  ^  h" b1 ^

  h2 D9 n& x6 n# p7 M2 R2 Z}

& A( z4 L$ H" d  v第二种方法:数组. ~, a/ ?0 r7 a* W% {4 |
#include<stdio.h>- J' A6 y, L# C" h2 V  r0 z- l
#define M 8
+ ]- n: S2 `, W. J* n. k4 E: qstruct monkey
* o) s2 d! @& o# d{int number;
/ i' p9 w# ~+ ~! R! f! @. yint nextp;
) p( _. Q( z& x, [1 L" N  W}link[M+1];0 X! T5 R& P, w7 R  q7 J

% f; k' D5 o" b3 Dvoid main()+ c+ ~$ R& q1 G7 I3 ?, Q# S8 C
{int i,count,h;
4 F; _7 [2 {9 Q  mfor(i=1;i<=M;i++)
/ u! y+ g$ C  }/ k{  if(i==M)+ O9 [+ c0 Z" N' e# T
   link[i].nextp=1;
; @4 d# G2 y' F* V6 k   else
& Y/ H( y) P: `- D   link[i].nextp=i+1;
0 Y. C5 N3 l; U  w2 K) ^, m  link[i].number=i;
5 e4 u- R$ f" G$ {( e/ s5 f}
2 u9 Q- r4 q2 Vprintf("\n");4 q( }4 o/ Z8 O, Y  ~/ D0 w5 u
count=0;
. O0 Y! E  s0 p! a) Y% ^6 Sh=M;
; e; p# y9 z7 I3 U. z: D5 p2 Z% Kprintf("依次退出的猴子: \n");0 u- }1 N& x  z! b" @' J  ?
while(count<M-1)3 I0 O8 H9 v6 Z5 ~1 e8 ?: }/ z
{i=0;
, {8 ]' j$ W& \, ~6 c, P* Z0 Dwhile(i!=3)
( z! T- n. G% `5 B# v{ h=link[h].nextp;; D" Y. `0 s$ v% A
   if(link[h].number)
( z5 c: Q8 ]2 t7 T" b( R1 y( l     i++;}
. U/ L* v; q8 M8 C! a& c9 u. b9 n9 h: _- O4 i# E2 l! L
printf("%4d",link[h].number);
9 e) T4 \- T+ \" r6 U5 I" ?( Ylink[h].number=0;1 {, ~8 I  a3 r; a6 i
count++;
. @) i8 i0 A: m1 M9 N}
! y# y) O% ?# H3 P
5 O7 _0 _* V  I- W5 m& w/ gprintf("\n大王是:");3 b6 \# ^. r  Q+ s5 K1 Q
  for(i=1;i<=M;i++)' |% U4 u/ {) M( ]/ h- V
  if(link[i].number)# F+ w; Q* l* _: N7 A
    printf("%3d\n",link[i].number);  U+ f4 @- S! E( a  ]6 M
3 e  m. O, O3 R' w! h5 E- c  l! G  S

) `' R, i5 J9 b, i5 L}
% Z" T, f1 s& b( z
第三种是普通方法for循环
4 K4 z. _" W( j# f) H
#include<stdio.h>
% u# n+ j/ B( y8 o) F: b* Dvoid main()
* x$ N3 F" z( e: |) P{ int i,k,m,n,num[50],q,*p;
" a+ o) I# C! E! c    clrscr();
; U4 {3 M* n! i5 c/ g# n0 o   printf("input number of person: n=");
0 m8 }# Z( H' v# |+ a    scanf("%d",&n);
4 H- w5 L0 J/ D; S5 P1 P" kprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
0 d8 i& B% d! x3 C8 L1 H    scanf("%d",&q);2 J& f7 B7 N8 ^0 Z
   p=num;
: F7 F. N0 P3 O  for(i=0;i<n;i++)3 S" Q8 q4 Y: P' u0 e' X
    *(p+i)=i+1;. V+ e) N' `! M
   i=0;$ B3 C( Q& Y  u5 \3 d! _* L% b& S
   k=0;9 O" R2 o! i; t! C5 L/ s- R- E
   m=0;
' [; Z6 p) W2 O5 {7 r+ e  while(m<n-1)
+ w$ d. o7 P1 c/ |# j+ Y: {# z' ]   {if(*(p+i)!=0) k++;
( o6 a* [) W7 ?, D) J  D  e     if(k==q)
. l: g0 [& B5 m      { *(p+i)=0;' m- r8 ?- j5 A% J: c8 K% D
        k=0;. s2 X8 y: `* e) _& J
        m++;2 T1 Y+ B, W3 B* d1 Z% B# M
      }$ V* K" T8 \  Z& G% ~
    i++;+ g6 l4 b3 n- _  Y5 q  |  M
    if(i==n)i=0;
, Y' p& y; z5 e9 b* F) ~) k+ _   }+ g) \8 B/ t. J( U5 t9 [  k
  while(*p==0)p++;2 S; p8 i& X+ N; u, M2 ^  P
    printf("The last one is NO:%d\n",*p);$ A- ]* K  U4 X8 g
     getch();
8 z$ W; x# m# }
; X) a, M3 Q9 R, G}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;8 \! B6 I! S/ y% A% v7 a
namespace 又费马达又费电7 V; H: c% a4 y; z
{' B$ ]: h9 S2 L$ b" ~, _5 Y
    class Program. {! j+ j: }, z$ i
    {
& b* _, W) I" Q( T! J$ u        static void Main(string[] args)+ v% a+ t2 g( C6 y
        {& e% @, r. ?: d' H
            int m, n;) B; T. l5 S7 k- u0 f8 t% X
            Console.WriteLine("请输入数组长度");8 w6 e0 H, l( B8 d! T5 B9 x
            m = int.Parse(Console.ReadLine());//m为数组的大小, F8 v" X- e) B
            Console.WriteLine("请输入要截取数字的大小");
  [3 g- Z$ N4 a- C2 k            n = int.Parse(Console.ReadLine());
! l; Y$ A# H& W# R            int [] numw=new int1 s$ B1 R* R6 |+ _
; s4 @# }; e1 g3 y, g* G5 R0 ?+ ?
&shy;&shy;&shy;;
6 N  K" ~: \6 ~+ k( d( B  L            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数) {1 n  r3 M% C9 U5 @7 {
            {
1 m/ S4 g  f9 N5 r( M7 @                numw[j - 1] = j;
+ F  O1 m% h& ?0 d            }
% \9 N) h5 M6 k. U            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!( n4 F0 j* q3 x% ^: l. k
            while (d != m - 1)
! e6 `- u9 G2 e1 J# C            {" ~( l+ L; r0 v6 \5 T
                if (i == m && d != m - 1)
) a2 g4 p& J3 F) U; x$ l; l  w                {; ~* t8 i9 A# |
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!' k& s3 S7 F6 ?8 z9 M
                    continue;" B+ m# r9 B( _
                }; y3 V, c. r$ W3 A' h
                else4 o8 a5 B' [. h; {3 p0 M7 m
                {( X2 ?; c0 X5 \; A6 ?
                    if (numw[i] != 0)
; T' \. [1 _/ q+ x                    {- Y8 \% q* ?6 T1 @1 U
                        i++;
( X9 [; ~  P4 ^* `" Q7 d                        k++;$ P/ s, N: N# O$ {3 Z
                        if (k == n)/ P  V2 l! O2 |3 T
                        {
; C; l% {: {7 [1 c$ B4 j                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
9 L. c0 k! g- [: L/ i7 t! p! E                            k = 0;+ W$ q& A3 ]1 A9 m7 I3 ]
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
- B4 V* J/ Q+ u" Z6 q9 Z1 I' K2 n3 T8 Q                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
! g1 {) u1 E6 B                        }
" o* l  s$ `% E" J                        else//输出暂时还没有改变数组元素的值/ y1 c4 E) h8 H  E
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
( F6 B$ U* o7 z; m. F) d2 ]                    }# {, F9 |! Y" Y4 L" w6 ~4 J3 I: t+ S
                    else2 D( k2 P2 ~0 `; j0 ^" w
                        i++;//数组元素为0,直接跳过,不计数。。。
5 |4 i# Q5 ]2 Z) K3 E8 j, J                }9 @. P  y9 a1 ~, [, O* i: D
8 N) |7 w" W5 \8 k" O4 l$ }

) ?0 t% d: W# G            }//结束while循环4 U- @$ ~# d8 P. s9 A4 [
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
$ }7 C) p- e. Z9 i) f) B           
& i. U2 a7 N" w9 i9 c                if (numw[i] != 0)
- Y, i' X( V4 T( e: d5 m                    Console.WriteLine(numw[i]);
3 {6 I# h+ A& p$ \* Y1 j           0 f2 D! J* d+ Q6 n* W( {
            Console.ReadLine();5 V8 D' p8 h9 D) T. F' ~7 q" N
        }. F5 ]; Z8 z  H/ b, B1 [1 \
    }
. }( z# n, G# }}& [2 Y& C7 B3 `% c- p) ?& {3 P* G
小甲鱼最新课程 -> 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-4-9 14:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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