鱼C论坛

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

猴子问题

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

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

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

x
大家好!4 w7 f4 \+ S8 Z5 Z, q' {
这几天我在忙着编一个问题,我用了一种方法编出来!8 x( x/ K" f6 _; z# \: R
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!( l6 j9 G9 w' X: z
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 1 u) s3 e! c; H* y
6 w  P$ I0 ?" |+ L: c2 q# R/ Q% q
+ @7 O9 ^% ]9 I; [7 B9 j
                            题目$ A" P5 D3 S+ I4 i$ z4 ]  t
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。3 j( U* S0 J# d* u/ D. c
第一种方法:利用循环链表
$ r$ ]$ f2 L4 I" T#include<stdio.h>
6 s% K) _/ ]0 e#include<malloc.h>0 Q  r5 B  l7 s7 @1 v
#define M 8            //共有8只猴子
2 B# {; ?% c  ]+ W% }#define N 3            //数到3只时退出第三只
) f8 O$ O6 M% c2 ]typedef struct monkey, T3 A$ k% l% O
{int number;
! r3 U: c! w( j% Dint flag;. X. N" B  \$ C+ H0 j% C+ d9 w3 \
struct monkey* next;& a: ?- B6 P( w" X( n
}MONKEY;* F' Z/ G8 `& p! H5 x. k  H, z
main()
) A9 g/ M1 `1 e: a" T$ W{ MONKEY *head=NULL,*p,*s;3 m# E+ K( A- J
  int i,sum=0,count=0;
6 K& Y4 \6 h. g- X  clrscr();              //清屏
! T# E6 c" I! C9 {* H% V9 T7 I  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存3 K0 \. p& K) ?; z  L1 |8 E
  p->number=1;p->flag=1;! @* Q6 B; L7 }. p6 o0 [: C9 ^9 Y
  p->next=head;9 }1 S% c4 W% c5 x; d9 ~  o7 H3 m
  head=p;0 u0 G9 ~, A  m1 n" |
  for(i=2;i<=M;i++)/ N* s) [+ h( t7 v+ v
    { s=(MONKEY *)malloc(sizeof(MONKEY));+ C- E  j' X4 w' z8 p5 X
     s->number=i;s->flag=1;
5 q$ a6 j( Y4 W3 c+ f, |0 i     s->next=head;! H( N; g) ~! G
     p->next=s;p=p->next;( V: v! E: A' B2 I
    }' Q8 ?2 W) \% V, _1 p8 l+ u
    p=head;
7 E' h. |: v% j. }$ ~$ `) }   for(;;)  B6 C3 E( N; h1 O* d; }+ U
    {if(p->flag==1)
0 [$ y/ u* O# [: a8 G) i       count++;
* s9 k# j5 X4 M6 ~8 t: v. g     if(count==N)) {% y+ P" E% O6 ]( y! ~, P
        {p->flag=0;$ B8 L$ s1 r. W
         count=0;
) j" f8 c4 S# u0 G$ W. x) I1 J$ x         sum++;}( J1 d/ I) J& S9 O/ e% |" ?) Z
     if(sum==M-1)1 ?1 w0 o7 _- P5 E
        break;; n6 `3 Q8 [, t% C9 M9 X, S
     p=p->next;
" S! n. ?; D- w+ n5 E    }% h* q7 Y+ x/ B- D+ d% D: b
    p=
) N" |$ z2 T  [/ n    head;
( S' d0 i/ G. B6 |1 t4 U9 R) _    for(i=1;i<=M;i++)
2 Q+ P7 b3 y; F* O( @. f5 u3 l3 {    { if(p->flag==1)
2 J0 C3 T" r" ^4 ^/ V- [3 K        printf("\t%d",p->number);
/ v* p, L8 y6 B      p=p->next;
+ V" \) K# t* ?3 _  K5 _6 |    }& \: Q% X" O4 c! b

0 N! m4 j% v. {( G. [& Z  K" V0 N+ s: n( O- v8 P% w/ p

" [, j, [: e8 v, ]* B}
& M3 O( G+ Z* F5 y. i2 C
第二种方法:数组0 t, c% M( v5 [6 F0 f
#include<stdio.h>
; N' v  i+ i: D) F6 T#define M 8, E/ o9 N; H5 e8 h0 K# r" `
struct monkey
+ ^  |, L1 _3 W( K{int number;
/ W4 }- r! [6 j; I2 M4 vint nextp;9 h6 w: F. B+ V) P& O
}link[M+1];$ h: r4 E6 y, ~

! O4 C0 L' H- S" i- X0 r3 ivoid main()
2 g: B; j( m( \& h% x) ]5 h{int i,count,h;
: `/ Y$ n# @/ w$ ?% J2 Sfor(i=1;i<=M;i++)9 k2 n' Q" G4 b" y0 }' x3 g
{  if(i==M)
+ m0 ]$ x9 E( y' H' s   link[i].nextp=1;
# S# Y7 ^+ f! G" m+ W   else  `5 Q$ `  B$ Y' c' S* Z/ r
   link[i].nextp=i+1;
/ _- q3 r& _/ f$ P9 t  link[i].number=i;
3 w) K1 }$ W9 g5 \7 m}1 {3 N! v1 @! z3 z: M9 S" @
printf("\n");8 E" ?+ Z8 t* H9 H
count=0;
- {7 ], Y* O$ mh=M;5 c" J5 J3 E7 `3 O
printf("依次退出的猴子: \n");
( {$ Y5 R* l5 s1 Ywhile(count<M-1)
% i# V) ^" d5 I& O  N, i6 i5 B{i=0;3 W0 G6 L6 ]4 C& `( E3 q
while(i!=3)
9 _2 K4 w4 e2 i{ h=link[h].nextp;
" W. K3 {3 t8 M" P   if(link[h].number)+ |. ~  u4 @& G! {- q
     i++;}/ G/ x; A" L- P6 Q! A

8 p* ?0 o. F% e0 m- @printf("%4d",link[h].number);
7 ~9 |: N9 u6 U, E/ z6 F( Ilink[h].number=0;
, v, E7 x  s$ E6 A8 Kcount++;
9 t; F( S$ H$ r8 f1 Z' y1 y- r}( f! J$ W! w0 w( `* `

8 q" k$ ]2 n  z- P( t3 U0 tprintf("\n大王是:");
! ~; e2 g9 o6 F' Q( f6 g  for(i=1;i<=M;i++)' H; \, e! S( y; i2 ~
  if(link[i].number)
% \+ s" e0 p4 w2 V- `    printf("%3d\n",link[i].number);, D1 v$ D+ ?' Z5 k% Y+ o6 W
9 I: D! o' j8 R, L

/ T' R( d% B$ f' G7 P" e}

# Z. O) N4 E: ~: ?第三种是普通方法for循环
( u# C1 ^. t2 i/ u) K: E* Y2 K) l, L
#include<stdio.h>
$ y- U% v* m, @void main()
1 L2 D3 k/ e/ d  K8 i2 _{ int i,k,m,n,num[50],q,*p;$ ?8 v) d" [' e7 Z8 ?
    clrscr();) ~: H0 {0 }: Y" O+ I
   printf("input number of person: n=");# a- p: n# ^& N0 U
    scanf("%d",&n);
# \, v1 H+ T6 f" ?3 ~8 Zprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
" n2 U- x( _* ?    scanf("%d",&q);
( D. E9 j4 x" [% P8 C   p=num;
- B' u/ w$ w1 n0 ~3 I+ G% W3 E  for(i=0;i<n;i++)
+ _- t  F" n+ H: Z    *(p+i)=i+1;
+ k2 _; `" C! Q( _   i=0;+ X! S+ B1 u# f0 t) w
   k=0;) `+ ~. I+ X/ |0 _! J: c
   m=0;
: E5 ~8 n% M5 y+ ~. d- S  while(m<n-1)& n' Q' i1 O& U9 w# ]- z& Y
   {if(*(p+i)!=0) k++;: N: n# [  E4 q1 M; T- O* ~8 V4 e
     if(k==q)' h- X. S$ c; Z6 t$ q. Y/ ]
      { *(p+i)=0;
3 a& T4 D" B$ x* t0 v        k=0;2 ^) ~/ @& a" Z
        m++;& P) L- J* w/ i3 a. @- O3 V4 ?
      }1 g7 m! c  s  c  k6 D8 x0 v
    i++;7 }* c1 G* G3 e) B. M
    if(i==n)i=0;
( P" X* b, h8 N, {: s- p( S! o   }
' d% @) E! C. ~+ |1 n. M  while(*p==0)p++;1 }$ P/ X' }$ I7 V; Z
    printf("The last one is NO:%d\n",*p);
" e) a0 D- g. P% D; U# S$ c     getch();& v9 h! k2 F, u# ]. e% Q+ m

  e: c9 W5 @8 x# C}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;$ s, w- ]" k. [6 j( Y; C2 @' O
namespace 又费马达又费电6 }- V: v* _0 h  q, d% F0 P5 H
{
$ g9 a# T8 V+ o1 i% O    class Program2 e/ K& ^2 [1 ]8 F2 l) R
    {
/ X1 O' K7 ]+ A, w0 f        static void Main(string[] args)
: i& v! H9 ]% W) F% E0 ^        {
# M9 ]# E! e, Y& n2 }& J( h6 ~; G            int m, n;  T% x: G: T) P+ ]6 G/ H7 C. h
            Console.WriteLine("请输入数组长度");% E6 t2 W/ n. s2 P3 W" C5 _3 G
            m = int.Parse(Console.ReadLine());//m为数组的大小
: k6 J% \4 z5 s/ e+ J8 q            Console.WriteLine("请输入要截取数字的大小");
; F, t* f/ d+ f$ f            n = int.Parse(Console.ReadLine());
7 @# {8 _5 v  {4 g3 s7 M            int [] numw=new int
# V6 x+ I0 s  }& H
- G; E6 x3 d2 A) T2 q6 l6 l&shy;&shy;&shy;;
6 [  K4 N5 e- C# v- I            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
  H3 a2 X& P) Y- Z! V) f" m9 b            {
: s' s- y" z; M! a+ R                numw[j - 1] = j;2 B8 ?" P7 ]3 r3 v( x$ l
            }
2 t3 c- A& K) ^3 E            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!/ B4 T* v/ e5 N" I3 J
            while (d != m - 1)6 z! j. u- L. X; ~1 R% M
            {
" L5 ~% U6 z' _; ^9 {$ B                if (i == m && d != m - 1)
+ ~- ^( q6 b+ X- h: F* f                {8 p% y0 F- v5 e1 S' t
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
0 O) s# g$ @# v# W$ d8 b9 J                    continue;
8 b5 n1 t0 U4 R+ C                }2 c# Q, w% C3 s, N
                else
* U( X3 s. U& b                {5 s  L8 N1 B+ J/ ?! M1 j
                    if (numw[i] != 0). u: U% K. h8 d8 H6 R% ]  g4 ?
                    {
" D* J! x5 E* {6 @# J- T2 a1 ~                        i++;) s' N, |4 s9 P
                        k++;
" l+ \" K# x+ Z                        if (k == n)2 D" s  e) Q% s9 L6 C
                        {6 b  j7 A+ z1 v' ?4 U- f4 B
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
) c; Z$ n! l/ S. B6 R                            k = 0;
, H  a/ f& q6 d. G5 C              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小11 R" W# Y$ \  d$ e/ e* k! W
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);5 P6 R! ]! m4 K; l( F; s4 w
                        }
0 f6 G! e3 K% I7 K                        else//输出暂时还没有改变数组元素的值
8 A( v# \. m) a. c5 t! r                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* S" p- ^" d/ O# b* Y; J
                    }- e  G" k: ~8 N5 Q  i, l% l
                    else8 X  |  ~9 P' [7 ^3 m  X7 |( E/ l
                        i++;//数组元素为0,直接跳过,不计数。。。$ @' U* e+ p9 a
                }- f1 m" \+ [. m' D( i

; O" U" U# V$ D+ N" x( V' E8 ?& ^7 l! m  W9 r# V9 R6 q
            }//结束while循环
6 }- H3 T! i. Q9 _& H/ m/ U; G+ p            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦3 k" T, m. _6 A; Y
           ; \# o; c8 r2 }% i; M5 O$ m
                if (numw[i] != 0)0 H5 ~+ E+ F9 z
                    Console.WriteLine(numw[i]);
$ G& h& c( S3 n0 L           , c- B5 m! [0 c$ i. m/ G: X$ d
            Console.ReadLine();
8 s3 ?4 f4 e- s& [        }
0 x% I, b$ b) D1 ^    }
6 Y4 z8 p8 ~) E}& _9 o+ y6 p( Z8 x* r: L
小甲鱼最新课程 -> 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-2-2 10:42

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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