鱼C论坛

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

猴子问题

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

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

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

x
大家好!
# \; c7 D6 `8 e这几天我在忙着编一个问题,我用了一种方法编出来!3 {2 b- [2 R* ]5 m" f, m: g) @$ N
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
  j: @$ F6 c4 V" S& ]' z注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
' o0 B5 D' x  n8 T2 G
  }( p) X" Z: P3 W# b) |3 O3 I: u* ?* n5 c$ V% i
                            题目
: ^' R4 o2 g/ U山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。+ e* l8 N, U. {1 b
第一种方法:利用循环链表
) r" i1 [' B) Y; L, f+ D#include<stdio.h>
. H/ W/ ^4 r# L5 h* v. I#include<malloc.h>  n1 S" T; B7 u/ Z; I4 V* D
#define M 8            //共有8只猴子3 _" _4 @# f! T0 Z
#define N 3            //数到3只时退出第三只
$ n( i$ P: O7 V6 T% J% j: E6 xtypedef struct monkey
% S1 q  P6 @: z- R3 N4 _4 @) s) w{int number;
2 o2 ^" D3 ]. V9 K! _int flag;
/ c$ @* r6 D0 p6 Y- `8 X( B! |. c& i/ `; rstruct monkey* next;! i! i5 q$ k2 _5 N+ U4 I* {" z
}MONKEY;
! K: n3 {; e+ N: Hmain()
; J6 s0 p+ }& Z6 h  Z  f" C{ MONKEY *head=NULL,*p,*s;
( }. C3 ]; v; r" d1 t: Y  int i,sum=0,count=0;) K, n/ }/ F; A- M3 v
  clrscr();              //清屏  {9 A; E% c- R
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存1 E& G+ l* C$ ?& {! @: h: W7 J4 \
  p->number=1;p->flag=1;
5 d+ K1 d9 B1 g* l4 U  p->next=head;3 D+ x+ C# h/ }$ E0 A3 D7 q8 i
  head=p;. O" h5 W! Y( }; E( D+ g' r
  for(i=2;i<=M;i++)
0 n3 P  u6 t  U1 a$ G  R    { s=(MONKEY *)malloc(sizeof(MONKEY));
8 v# S8 t- f' T- {5 D6 J. D: N% n     s->number=i;s->flag=1;
& V" D) X( D% A8 \9 ~     s->next=head;8 a. \4 L: G! @0 \  `
     p->next=s;p=p->next;% Q: K4 m: C8 r2 r& d
    }
% N" n  g8 M5 U4 i: n  p    p=head;8 w9 J6 c7 [$ `  p7 b  @" u
   for(;;)
9 E# |6 |# R7 W4 O5 C, |. a    {if(p->flag==1)
. s3 O& f( i3 n: A% l       count++;
, V" q  T$ k+ l" ~% @. I( V; {: \- \     if(count==N)+ N! i8 L$ N7 u
        {p->flag=0;- o8 z) \5 U" G/ F' t
         count=0;& V, h4 @2 R; s
         sum++;}
5 b5 L! @$ ]; p7 d. u- A     if(sum==M-1)* w8 d) b: [( t. H( ^2 R$ I  e
        break;  r4 N; O" H2 W9 ?( S4 R
     p=p->next;
. z' b5 G5 e5 f5 m* o    }- R, r, f# I+ \7 z1 m& u- I
    p=4 v" W& R4 }3 u; l6 Z  y
    head;
8 r- _+ a# N8 i  C3 k* B" G    for(i=1;i<=M;i++)- @  h' }" C& L9 a) R: O2 z
    { if(p->flag==1)
% z, v2 a& w9 X3 ]  |/ k        printf("\t%d",p->number);( B+ S2 q2 M/ [; Q# a8 g4 o* M
      p=p->next;
, e3 f5 g/ H+ X6 ]. B    }
8 M$ n1 H+ |+ T, [) m! Y2 q! @4 `8 c1 N9 D8 J% X: Q7 Y: V

+ c/ q, C! p/ S0 r: A9 y! Y6 F% `* Z9 q- n' p/ C" a8 C' G; V
}
* }# E* r; P4 Y
第二种方法:数组
1 ]7 z8 x# m& q& e' v, V#include<stdio.h>
( |$ S8 v2 p0 w+ F7 H5 i: E#define M 8
; f0 g* B1 u& v2 i5 t1 Z( x+ Ostruct monkey8 R; z! z. `8 ?5 X- F
{int number;4 D; k- P, F$ [
int nextp;
4 x! l% U! H; e  S}link[M+1];, v7 @2 _' e5 q4 U; \) U/ A

$ ~# O3 T5 N- i3 D* p5 A/ \; mvoid main()
; w6 j6 ~  t/ x6 C. e& N. u{int i,count,h;
7 X9 u. x  J$ Dfor(i=1;i<=M;i++)
+ b7 _7 M; s4 M0 G7 c7 F  t{  if(i==M)/ L! x4 C% w# t
   link[i].nextp=1;$ J. [1 U- P# K6 s7 `: `% X8 s4 H
   else
- o% j+ j& z+ H* h) E7 J   link[i].nextp=i+1;
- v2 k( t# m2 X3 J7 ^% k  link[i].number=i;
. v6 n. }& S9 E2 u7 w}  b  ^' f+ u+ i6 G
printf("\n");8 Z: o. m( u" O) Q$ |  ?
count=0;) P) L5 B4 U3 c! M4 ~
h=M;
9 _' U2 ~; Y6 ?$ O9 h  o! O" Vprintf("依次退出的猴子: \n");
& e" t6 E5 F! L! ^while(count<M-1)! g% r( i' Q8 l
{i=0;  ~+ |% W1 k' h6 ^/ W6 U
while(i!=3)/ \) n! ~1 Q+ n& v5 B1 a2 o
{ h=link[h].nextp;9 b& Z/ e4 j8 q- z9 H
   if(link[h].number)  l% j6 Z. ?  z& [9 ^
     i++;}4 q) H4 _: b; G* F7 K5 j

2 M( K+ ~  e4 q9 p+ Bprintf("%4d",link[h].number);
) j8 u  k0 ~8 u1 I# \link[h].number=0;" S  I+ q7 }* S
count++;' X5 L- K2 @8 v: S0 D9 ]& e
}
, R' P, r9 w7 ^! M* R" k$ z2 k$ N0 k! p
printf("\n大王是:");
7 w2 d1 s& L* f" j, F- i( y+ C4 L  for(i=1;i<=M;i++)3 `. O; `1 Q- X0 ~/ E
  if(link[i].number)0 o) c' a  a( Z  m: h9 W
    printf("%3d\n",link[i].number);
  z, [$ y( X1 L4 b$ ?' o, S
! _& I& t' u: M$ y
1 g5 w+ N2 u# l' e7 v# }) f/ e( X4 T) z}

9 g$ {( N. E3 @4 E" F& e第三种是普通方法for循环
% R) r" P6 ]4 Q% x- q
#include<stdio.h>
* F) f% |" f$ ?4 X+ e) Bvoid main()/ J* S. [8 x* |. ?$ v
{ int i,k,m,n,num[50],q,*p;0 b; u7 R/ J9 K: ^
    clrscr();
' G: {  v; t+ X: V   printf("input number of person: n=");* A) s9 [+ ^, b/ i; Z" z" F/ g9 F
    scanf("%d",&n);6 k% {3 x. I  @  P0 g
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只! u  p4 P; V5 V5 j
    scanf("%d",&q);
7 J$ @0 H1 C0 }* ]5 w   p=num;/ Z2 D! p- q' W9 \
  for(i=0;i<n;i++)
4 B3 E) k3 j7 A, i9 M* h9 ?' C% n# H    *(p+i)=i+1;/ Y6 O% ?+ a2 B; b. Y, L4 Y
   i=0;4 s# {  B- J! U; V- _- f$ y
   k=0;
$ ]8 u' x& X  ?: n$ {   m=0;5 u% B$ Z; J. C) R& k
  while(m<n-1)& N: H) X, {6 x4 A) p6 _% p  ?
   {if(*(p+i)!=0) k++;3 I  F. Q4 r- c4 P+ j% U/ V5 A
     if(k==q)
! s. e' i" |1 W* E( j8 Y% C2 T2 T: X      { *(p+i)=0;$ [' M* U* [. g8 p8 W
        k=0;
) G' X: G. n( C; R' l3 V        m++;
+ x% h5 R. k& I, R      }
! y7 t, P2 K2 d, C: `    i++;4 L" E( \, \: F! u
    if(i==n)i=0;, {; o& R( e3 V+ P/ ?! `
   }; T2 n3 F. G' V) L6 W
  while(*p==0)p++;- b8 [& c2 b) o" g  X9 O
    printf("The last one is NO:%d\n",*p);
" e2 J1 R9 w: d     getch();* w$ a8 W- Y) ~4 w
9 l9 E; v) B, [) b
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;: }2 g' ^. X+ [$ C& M
namespace 又费马达又费电
0 x) K) j% T8 _; v7 [  m1 n4 |{9 ?9 K( D# _8 @4 ^8 s
    class Program% u' n0 M, i2 {; S3 Q) r+ M
    {
1 t: l* M( R/ [        static void Main(string[] args)7 P9 {( v9 V! s1 M0 [% m6 M* k
        {
8 M  o3 T4 ^9 R- ]$ g; v) r            int m, n;
% r5 g+ e9 X* U" u            Console.WriteLine("请输入数组长度");
. i, n7 X6 F: }4 P  j" r2 h; ~3 F7 m3 J' P            m = int.Parse(Console.ReadLine());//m为数组的大小
% b1 z( b2 J0 ?( @  p            Console.WriteLine("请输入要截取数字的大小");
* x& A# h* r9 m( x            n = int.Parse(Console.ReadLine());
1 r& c0 l' p8 o            int [] numw=new int( B1 X9 k; C! A- P0 Y

% A; u0 q8 W# _/ h9 v' }# g' J&shy;&shy;&shy;;
# g9 @1 j/ d4 P) v9 ?! i            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
' Y- m" r* a; _- D            {
4 U# Y- A% [4 [" O& `5 x                numw[j - 1] = j;
/ Y- a* j! N' Z            }+ s1 o9 j7 N9 k4 i' N
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
6 ^5 L5 k5 x. L( s% L, \            while (d != m - 1)/ R4 W5 [$ K# t# J8 N: ^- U. D  L4 L
            {; y+ z# k% j' e2 Q( p
                if (i == m && d != m - 1)
% e* C# x( P5 ]- y                {. m0 U* z: A" V' Y
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
8 z- O) V; [! s1 K                    continue;/ U/ a4 g' f, n0 T- |/ u  w
                }* e5 `1 ?1 r% N
                else
6 N6 ]9 i+ u4 g. s7 d0 f8 r- ], ^                {
# W3 q7 v" V0 Q  p" m                    if (numw[i] != 0)$ h5 Z3 z( I  P1 ~
                    {2 }1 [/ v5 S1 p3 V8 s, T
                        i++;* `8 C; U& @) x6 f, h/ q
                        k++;4 B% O1 x. i! P% |0 `, S
                        if (k == n)7 f: ^( i( O- `7 c: Y" ^
                        {, ^9 T6 A6 a8 p& U/ e: l
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了" J* P* d2 ~' x9 j, ~4 s
                            k = 0;" W5 f# V0 O6 W% h
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小13 a% X! w) q1 f
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
4 ?4 K  C1 O, z0 D                        }% C; b6 C5 J0 ~. X6 z* H& H
                        else//输出暂时还没有改变数组元素的值. n9 r* N. q$ m5 r# R
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
! r0 a1 o/ \- \) ~  [$ q0 I                    }
8 M7 ^2 M' J; [6 K6 g+ Q& ~                    else
, e+ N' j7 ?4 L  w, }                        i++;//数组元素为0,直接跳过,不计数。。。
- p$ N: N% O! _6 _8 m. Y: M                }6 n6 |2 {- Z# r4 l4 q' v
' ]( F& ?$ J- Y# c/ S5 w

5 n+ F8 u  p3 w( H5 P            }//结束while循环- O3 A1 T0 z, G+ ?
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦. Y3 N9 f. g; J3 s4 }
           # q; I1 ?6 p- L3 }
                if (numw[i] != 0)
6 T! Z/ M+ z; o                    Console.WriteLine(numw[i]);/ j/ Z. E  {7 x: ^, g6 }8 Y: t  P
           
" y3 x" l% K" p( r* t/ u            Console.ReadLine();9 m5 J7 x) d3 p, v9 z
        }" s+ J4 a' T, z4 z
    }! t/ n' g% M) J. N1 ^" J4 P
}
( @  c  }" G5 N/ u  A
小甲鱼最新课程 -> 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-5 06:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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