鱼C论坛

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

猴子问题

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

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

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

x
大家好!" k1 x2 P& \; R% z5 P
这几天我在忙着编一个问题,我用了一种方法编出来!0 h; R+ m6 A; W8 U8 {- Q) S5 v0 {
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!9 W2 _. R/ ?& g1 E7 ]$ Y$ T
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
' A2 V$ ?( V5 c$ N- z/ C7 k) [3 w! B& S3 P# Y* @9 g

: w3 y3 V" J- h' ]6 l4 C9 F! x
                            题目
8 _+ I  a0 ]. B7 q6 @山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
5 v  V# g- m6 o2 p1 i' q第一种方法:利用循环链表
+ T2 f% P1 I/ T* ?$ k# w$ L#include<stdio.h># B2 m8 I# g7 f; z( N: c
#include<malloc.h>/ q4 ^( M9 {3 J2 r' F7 f8 _
#define M 8            //共有8只猴子; X* a$ N4 U' X( t  z
#define N 3            //数到3只时退出第三只  j0 k6 h( e5 ^9 o
typedef struct monkey8 ]8 |. m& `$ \0 Y2 k$ S& o7 v: R
{int number;
) f# g, w& X  O; U+ S& I+ c+ jint flag;2 y3 J% H& y9 L! P0 v4 t3 q# s8 ~
struct monkey* next;
. H* V( o2 p( E! q' J; G! i6 l}MONKEY;7 D" g  Q: R" R4 @- S
main()7 Z% P8 x6 O( v. R  H/ A. [
{ MONKEY *head=NULL,*p,*s;5 K7 [+ R! Q& g: h- E# r+ t& D
  int i,sum=0,count=0;% X, s3 x+ V) {$ p
  clrscr();              //清屏& m- F! r0 a: J7 c# b
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
1 y& M  s0 y: ~' w- B4 l8 p" `  p->number=1;p->flag=1;
* [6 h. Q; |. _$ l  p->next=head;
% Z9 z8 t0 l3 A) t8 i  head=p;. q4 v: m2 @' R, j$ {. C. F
  for(i=2;i<=M;i++)1 y: v1 V- D9 x/ h
    { s=(MONKEY *)malloc(sizeof(MONKEY));
# }; d8 q- p- E' Q2 U     s->number=i;s->flag=1;* w2 [, V3 _/ U: ?, a
     s->next=head;8 K) I, g, h  C1 M) P# d
     p->next=s;p=p->next;
7 g) Q" T; T- v" ^) N7 C    }
4 U' @/ H, \9 l/ B% ~    p=head;
$ y  L, ?* c& J  N) b6 `, E   for(;;)
/ j% e3 o# h' w, [# @; v! H; o, B+ e    {if(p->flag==1)" d9 b+ I5 Q7 N/ Q  [
       count++;) y8 o  F% ^8 G' V9 \8 f$ [. i2 p
     if(count==N)- _1 Q) s- l. k' a  O
        {p->flag=0;
- _# r' y' O  d* g. V         count=0;
( v6 z( {4 _: f2 F         sum++;}
3 U( P5 J% N# M4 a     if(sum==M-1)
" [! D  @8 d, ~/ I3 ^) |        break;
! Z3 @& c# i% `# [4 d     p=p->next;; n0 B& R1 v% I" O% J& V4 I
    }
7 X* {2 i+ I% }( o6 m8 `    p=
) w8 i  _7 A$ e+ {    head;
( t7 _2 M' ~8 Z- ?% y. f# _    for(i=1;i<=M;i++). q3 w' I9 u0 p0 g
    { if(p->flag==1)3 c; K+ j2 d4 `% @
        printf("\t%d",p->number);# o/ M; a4 f) I0 `
      p=p->next;
5 K. o8 R  _! R, `. N8 B8 s    }
* B' H- [7 E+ Q' h& q3 r+ ?3 x- t8 u# g+ d) g% g

3 V3 v" H2 {0 p2 B* i7 K3 A5 K+ g, a
' v! Q" [" X, }# _# ]% V}
3 L, J6 x, n4 q5 l/ ?
第二种方法:数组
' G  d' Z# T. ~1 a/ o( C#include<stdio.h>
3 X6 j+ a5 s- R! t/ T, W: ]#define M 8
8 Y; L; a5 s; K* D! h$ x3 M8 _struct monkey
+ Q9 G0 X- b" i$ ^{int number;& ]4 R/ w' ^9 C
int nextp;
$ }& \6 p! {3 g2 p; |}link[M+1];" A* ]/ a/ Q0 v7 x# |$ c# r6 x6 x

/ B4 l( j( u& {/ M6 wvoid main()
$ I  n) S2 W( [6 h$ Z9 H& A{int i,count,h;
( ?. H3 k& J4 u3 C0 c# I- t) ?3 O7 W1 Cfor(i=1;i<=M;i++)
; H+ u/ @* K5 }# v" k; u{  if(i==M)' b# q# F8 N3 m0 f/ ~
   link[i].nextp=1;0 w9 t7 h" u) N
   else, V( f9 f0 n$ U. S7 e
   link[i].nextp=i+1;
  }& b: e: o$ ]/ ]& C/ A% ^0 O2 S  link[i].number=i;: I. `7 |: C5 W* |- O
}! _4 |& X" n* D' y& s
printf("\n");% U: _$ s# T8 B0 M: @
count=0;
# ]2 o, u( F) r5 r  x7 \& eh=M;
, o9 s) N; N2 O; M2 j. Tprintf("依次退出的猴子: \n");  T- B) B$ J4 m( h) Z
while(count<M-1)
+ N9 |7 N3 @5 y! w6 q0 L& q{i=0;$ W' n; a! K9 |8 j* R9 ?2 S* N
while(i!=3)
" Q0 W+ C( m. G* p( ^{ h=link[h].nextp;
4 b1 z5 h. B7 A1 v, o' ]4 n   if(link[h].number)8 o4 q' l; _# @
     i++;}
. C6 q3 y8 x$ J2 O5 N# C
& U, [. X( k, m7 S! J: p: Iprintf("%4d",link[h].number);3 v, w. L8 w- w; `- Y: a4 q/ S$ z
link[h].number=0;
5 d* X+ _; D4 T/ _( q& b) _& P( ucount++;
4 n' q. S+ f- @* Q0 l/ w}
6 T1 N  t) f+ G2 O0 Y2 [/ W; z. d
printf("\n大王是:");
0 c5 c2 t5 Q4 J0 }0 q' Q  for(i=1;i<=M;i++)  p# l. j- }1 {! i8 p4 U4 f
  if(link[i].number)" {+ ^8 k2 q4 ?" p3 F6 e
    printf("%3d\n",link[i].number);. u3 c/ j- e! ?+ H) W9 f' {
4 g. T7 ]) q& Y
7 T( d: J0 ]" L2 V4 E. h2 r& |
}

3 l1 i% N( b. G& y第三种是普通方法for循环
, a$ o. \& e7 F) o
#include<stdio.h>
& n) l. N3 P+ {" {void main()8 o1 P; ~) Q  W. o. [" v& i! |
{ int i,k,m,n,num[50],q,*p;
2 o' @+ k* V7 s4 R    clrscr();
4 ~% u6 ~+ f4 X+ P% G   printf("input number of person: n=");' T5 P; v" G* m& e' e' J
    scanf("%d",&n);9 O% w8 M( C4 L' Q
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
& {3 ]8 C. T' @- n6 `* t    scanf("%d",&q);
2 o8 c: V& Z8 V1 r1 X9 y   p=num;7 U5 H- |' [0 p+ z3 w- f8 J! N
  for(i=0;i<n;i++)3 g6 p* y4 d) ]" X+ u* Y
    *(p+i)=i+1;& c8 F; n0 r8 d0 ]0 n; b8 W
   i=0;* e% P7 U( l9 }; V3 ]
   k=0;2 n' y. `: @$ X2 T1 [% P
   m=0;# _0 L: w; x; ]/ p; Z) N
  while(m<n-1)
& y' S. Z& U% X6 i) |   {if(*(p+i)!=0) k++;
: V8 Y5 p' y$ F. L) w     if(k==q)
0 X% a- l# s( b& G6 E/ }      { *(p+i)=0;
, M& ^  r2 _' n6 [, l5 n- a4 f        k=0;  B3 o+ l+ V( `! Q2 e9 K
        m++;
, e# x0 p3 ^3 _6 v      }. @! I; C# |, ^1 |% T
    i++;$ D& o, G5 p! \, @9 A8 Z( h- v! E  k' f  T
    if(i==n)i=0;1 M6 t% Z8 a7 l
   }
7 d" d$ e: ^$ O" L' ]8 S  G  n6 b  while(*p==0)p++;
2 D/ O( T9 _* `' Q) |9 S; a    printf("The last one is NO:%d\n",*p);) W9 C6 K* x- V3 P
     getch();/ |/ c* _( U& K- k* }

5 Q! n3 O' S$ R4 M$ S! T! _}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
- H. F* ]7 w/ r4 N/ N) Knamespace 又费马达又费电. `4 E, _3 g& \& E0 S" y; e  p
{
: T8 m. I/ c" p    class Program
9 i( W' K* _3 f/ E. J) @    {
+ h! l9 R6 h' G0 h9 K        static void Main(string[] args)
6 m0 ]- E4 T! F; U        {  ]& y8 E8 _" V- j& ?3 r2 x
            int m, n;. e( a) n% Q0 m
            Console.WriteLine("请输入数组长度");
' i2 `1 |4 F4 ^5 }$ O) o5 K            m = int.Parse(Console.ReadLine());//m为数组的大小# d8 m- ]9 \3 f( m1 E
            Console.WriteLine("请输入要截取数字的大小");6 O7 H# |* v3 a: ?
            n = int.Parse(Console.ReadLine());# B5 F1 V! b0 |% s1 d
            int [] numw=new int
1 m8 i9 i3 v, y/ q0 F1 i- J1 h* b# c+ U  N: ?3 ^- s
&shy;&shy;&shy;;
, a4 Y8 H3 l4 ?$ o8 n; I5 m: Z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数! j! b+ _6 X: n: H8 A+ q. S3 W# K: f
            {
( s* s* Z  _- A' o+ v                numw[j - 1] = j;
0 P6 u) n5 v5 r4 \0 k9 r            }
# l; i2 a- y! Q  e; u3 ^) i            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!) s$ ?, H$ d9 w8 I
            while (d != m - 1)3 z! t- Q. I' a& i. ]
            {
  |  D9 l! m+ \1 @                if (i == m && d != m - 1)
: `& b! Z( ~" f) y6 K                {4 ]/ Y! _5 A: i$ M# ~
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
" O1 K3 I! P  i' J                    continue;
4 f& W- \5 K3 W# U0 [; j: D& X: H                }
: A4 J6 ^6 l( d! ?$ L                else
9 l1 F% S2 c$ K" G# ]6 F                {# |( t, Z. L/ t* q
                    if (numw[i] != 0)6 t1 o5 ?8 x/ n4 P9 ?
                    {1 V' L  N% y4 g& Z7 f; S& ^
                        i++;: {' w8 }) R! ?1 M
                        k++;$ Z) z3 g' q% p5 F; w% l' Q
                        if (k == n)
+ w. t! k$ p- f  m- R2 }; S6 r- F) @                        {  ~& v* p/ S3 i# X" U
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了! a4 u8 `; |. ]  s7 k3 U8 G& W! P
                            k = 0;3 [: {2 B2 T' u4 y: V
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1/ B% W3 E& F1 `/ R
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
4 |3 l$ b9 S0 g6 `                        }
7 S( k4 L2 _9 i                        else//输出暂时还没有改变数组元素的值) A8 p2 d* L! s3 A9 ?+ i# T/ I' O
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
9 k1 x8 S  O6 \" J5 z4 t* {                    }* _: R7 C! m# o- \, N
                    else( i; E- ?) H0 j
                        i++;//数组元素为0,直接跳过,不计数。。。; `( C, S8 w5 y+ q& U) O
                }
/ N- l! H. o( L( v2 s& \5 x4 a% Z
6 c( C7 f# D& d: b, u" Q, R& q) ~: z8 E1 b* r4 H
            }//结束while循环1 O# I( F5 L3 ?7 P8 t. c! @, S
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
% ^1 [$ A* U8 j8 d* E, L. X6 D  k           
! \2 _$ u( F9 I7 d5 H                if (numw[i] != 0)* \9 y8 T$ g: d2 R9 ]4 e
                    Console.WriteLine(numw[i]);) j  U" U( O8 x
           
) V# D1 Q. S4 q            Console.ReadLine();# [" I0 F( G, `* e
        }6 C& D" W) X! q9 R8 j, Z, [
    }
1 J. x3 N& ^& r" z3 D' S( S& y}
$ @. t5 i0 A, E6 M3 S
小甲鱼最新课程 -> 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-7-31 07:24

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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