鱼C论坛

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

猴子问题

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

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

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

x
大家好!
3 m! x3 V2 P, q: R+ ?) P这几天我在忙着编一个问题,我用了一种方法编出来!
9 ?3 q9 W; w" b% \但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
" q' B! m( g3 a6 ^. V注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
, R( p1 S7 \' N0 e
4 e  @5 Y( o( y5 h4 u+ x: X2 n* P: |4 u2 k0 c
                            题目
$ ~1 d/ E$ n  P" n山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。8 M. A3 o/ _- ~% \! C  ^
第一种方法:利用循环链表
( p# t4 m2 g* V- e/ x#include<stdio.h>
8 R+ X2 _; U  \% L! E#include<malloc.h>
! k0 X8 ^* @8 p1 W; Y! [#define M 8            //共有8只猴子# T1 U# `$ Q# I6 z1 n% y6 w' t
#define N 3            //数到3只时退出第三只; b: {- t+ Z1 T  w; W
typedef struct monkey
! p  K4 W3 x9 b{int number;
( b% B7 M8 ^: ?# A; \int flag;
2 m; M' Y3 R" f0 ~7 @- i+ \struct monkey* next;. R9 Y9 M  o7 P7 v( ]9 K  B) z
}MONKEY;6 Q! o+ L( a( R2 ~
main()7 X" s. a; ~# W6 x2 G- x) Y
{ MONKEY *head=NULL,*p,*s;
/ j. Q% I3 K7 l! v7 N: D  int i,sum=0,count=0;" J6 y5 b1 `, x/ V
  clrscr();              //清屏4 E+ H( H7 `9 ~
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
0 p! G$ I2 j1 b2 b0 j4 v6 S7 o  p->number=1;p->flag=1;( p# @1 U/ g+ `: s# X
  p->next=head;  ^" ~! l  t8 A& n- A. {
  head=p;
5 z/ R3 s) Z, [- {$ C: J  for(i=2;i<=M;i++)
# S9 K& y3 y6 M    { s=(MONKEY *)malloc(sizeof(MONKEY));
7 a3 ]3 G" }) z; `- @! n" {     s->number=i;s->flag=1;
. D$ K% e! F6 Z7 K, W     s->next=head;
+ m4 t. M& j0 |0 U; e- t' U     p->next=s;p=p->next;. t- n* w0 K. v& Q1 R  E" X
    }
, o! n6 i$ A. Y2 E) K    p=head;$ k. m7 ?! o! g, I
   for(;;)! Y, M& \3 o5 A; y( J
    {if(p->flag==1)9 j  V9 S$ c* b8 X- |. `9 n
       count++;
* P/ x1 l* G& [  {     if(count==N)
  |: V6 ^0 ?1 O9 X5 z+ b* }6 ]$ N/ D        {p->flag=0;
+ `0 \" _1 a0 Q' d- r         count=0;# z- i  @, x3 l* h) u
         sum++;}
7 {9 D$ d+ G) i# r8 q" o7 [/ c" s- `     if(sum==M-1)
& d; N3 Q- k2 p8 w# ]        break;* Q6 K. j1 F) n8 b2 S  `$ j
     p=p->next;3 x& C( @5 ?4 c% P, }6 o, _
    }: ~) H; c/ E, p4 \( z! P0 _4 T
    p=
1 o& n* Q! G' a, K( I2 Q    head;
; J1 f1 x8 }3 i/ c& n    for(i=1;i<=M;i++)
2 {8 M% ^8 V& v7 M1 m9 T# d    { if(p->flag==1)  R7 L' ^9 ]) z* o9 ~' x
        printf("\t%d",p->number);8 Y- s2 _; f8 v$ {# f1 j- v# q
      p=p->next;2 Z) H5 V2 t7 c0 ]/ B
    }; m, u  v0 R5 ]5 b
* N) n" n5 W9 d" V& u0 `! i' H5 N5 v

8 H) I* {5 R# v. ?7 B( w
: ]& P( ^! o# a9 e6 u}

0 o, q/ t; P! \  s" W' ]第二种方法:数组
4 x, t5 c, j4 n* Z#include<stdio.h>
+ O- d8 X' T% L; {! R#define M 8
8 w1 o' L+ ^3 q, j5 }# w/ dstruct monkey
& S: A5 n: r  C{int number;' A6 {* q2 i! B2 H# [$ B
int nextp;1 |5 s: S2 ~! o$ m+ ^3 D0 K
}link[M+1];
1 m) \& h! [1 x4 Y# M5 `/ ~) N0 N& d3 W6 b* h' u
void main()" w0 b" d+ `5 x/ [) @( ~0 n0 h7 j
{int i,count,h;
5 r5 q7 ?- l+ w% `3 @2 f: p2 y5 P7 Ufor(i=1;i<=M;i++)
  J0 A' {, v  z6 f6 W; |8 W{  if(i==M)
/ b' v6 `8 B0 u" b4 E, x7 P" `   link[i].nextp=1;0 x8 `, _" r5 A) Q  A, y4 Z8 {0 U1 u
   else9 b* _5 s; D6 j$ g4 ~0 ~. N
   link[i].nextp=i+1;( Z. Q' |7 G. u- w$ ]
  link[i].number=i;
3 b5 h+ {0 H6 @% O6 e# E  F3 {+ t}
: g+ m; O# P3 T! h2 |printf("\n");
. m  c) x" d. \+ S5 ]# Z- @count=0;( _8 g- w+ z7 H
h=M;# x( p, d2 u8 B0 N1 S& }7 O& p8 B
printf("依次退出的猴子: \n");  J1 x( ]7 R: F: c% ~
while(count<M-1)
# Y# C3 a9 M% E0 i8 {( z{i=0;2 c9 d( f3 i# {, Q& `& e& `
while(i!=3)
' t+ F9 N* K# H- b2 r; m, z{ h=link[h].nextp;+ O# {4 z6 _2 |7 L8 @
   if(link[h].number)
9 w. v, ]8 O# A3 p# D     i++;}0 O; P; z7 Q& \0 \8 p7 ?
) R$ O, _5 S3 H4 L$ b
printf("%4d",link[h].number);
, z6 Q; w+ X9 V& m7 t2 ]. K/ u# F: flink[h].number=0;* Q0 `: R' ]' V8 v# C9 P2 I
count++;
9 d, s2 y/ B/ I* F: M1 _- i}3 [9 |: [$ C. ^1 N$ J* S' u0 t
4 F3 b$ p8 q: D7 }. D; |
printf("\n大王是:");7 v; l, r( B" n& D
  for(i=1;i<=M;i++)
4 v- G" G# n' Z  if(link[i].number)! s/ P) n+ O* Z( }- [
    printf("%3d\n",link[i].number);
) ]* h+ b3 E, y  m2 L/ n& {% A0 W0 E9 m' A: q% I

7 l9 @3 |" V3 l; f( v& e7 D}

' {7 ^6 p$ m" J) J第三种是普通方法for循环
* M4 j- h1 n% O3 l3 z! F
#include<stdio.h>
1 l( ~1 S; Y" u8 Yvoid main()
: K4 \5 v7 N  `; d{ int i,k,m,n,num[50],q,*p;9 f" b8 I. H9 O+ n) l. x
    clrscr();, k4 L( C, R$ c% G+ h( ~
   printf("input number of person: n=");6 i" I- M: _8 H' J9 V3 O
    scanf("%d",&n);
0 h+ l2 Q% e* {: y$ a  t* gprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只* w1 B/ Z# W& r! W( b) A( _7 K
    scanf("%d",&q);
8 L! c1 s6 D+ d2 j% I: J   p=num;
$ W4 N! o& G" P& e; o9 x3 ]6 t  for(i=0;i<n;i++); W( F! S1 h) `4 c" _- v5 {
    *(p+i)=i+1;
, o9 ]9 r; C! q6 e  d0 S9 r   i=0;
8 }4 x* n8 A9 G. B% L$ [+ e! U   k=0;5 j( K" Y/ [& m1 j1 w4 |( f2 t
   m=0;
& _4 V: G0 |( f9 m: [  while(m<n-1)$ s4 j" g; m# i! H7 t
   {if(*(p+i)!=0) k++;
2 G0 {  {* y' C# B, N- |     if(k==q)
& w3 Q4 j1 {8 q, R% r+ A# W      { *(p+i)=0;; Y* x8 I8 T# R/ \: w- l$ W
        k=0;! W' K6 |8 `1 H
        m++;
) x/ M: E  f. `. c0 c      }0 y& @3 H! O9 J- c. [5 g
    i++;
  [+ p, n! b  G' y5 U% m# f) |4 m    if(i==n)i=0;+ N, i% b- h; Y, N2 o
   }
4 l5 m: {9 e% x/ u5 i  while(*p==0)p++;
1 B/ ^% D) F: t! Z" Y0 m3 Q! H  f    printf("The last one is NO:%d\n",*p);
% {0 z$ Y- y/ R* r6 T! m     getch();
8 G" y7 }' V. R4 N- r
1 P! t, {# a6 \" g  R}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;3 h6 I+ C# n. b- z* p' R- @
namespace 又费马达又费电& ]/ C# C  N' K
{
7 E( \3 G% w; \$ h5 ?/ z    class Program
+ M# A& i; B0 i2 ^- D9 l& T    {
' o6 r; m( l; y0 h# |$ ~. _        static void Main(string[] args)" u3 y1 g' N/ X" p
        {
0 t9 q  R0 q3 e' J! N# U, V7 y+ q- {            int m, n;
+ f$ b9 y$ d' F' k9 ]# ?            Console.WriteLine("请输入数组长度");
# b" v$ X  G+ u1 g0 l) n: ]9 p            m = int.Parse(Console.ReadLine());//m为数组的大小
3 @. e) ^* P) C$ H: _            Console.WriteLine("请输入要截取数字的大小");
. z5 ?  `4 ~  @            n = int.Parse(Console.ReadLine());6 [8 O9 u6 a3 _  w2 l- [
            int [] numw=new int, K+ Y0 E1 c# E& {1 |% A/ X
# J; ]; Z  }/ H0 I
&shy;&shy;&shy;;
6 ~" {3 _& V2 t& P* q            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
0 C. J" A: q- F* s/ p            {$ H- w0 y+ I1 n5 G) W
                numw[j - 1] = j;; a' |6 {$ D4 w! c4 U2 D* t5 B
            }
& G* O* [! C" C8 M4 A            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!1 P$ w4 ^2 Q/ y* r6 k; y- e
            while (d != m - 1)  \5 ?8 Z- Z# ^* c# v5 B6 z
            {
. D. ?. ?4 x! \4 F5 ~& g                if (i == m && d != m - 1)! Y4 d- f+ v5 _0 c' O5 \4 R! N
                {
  h& J. L4 [' R& |$ M                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!4 s8 Z) q( _: f3 [8 x4 D
                    continue;' T: L' N& A: Q/ \/ {
                }9 I7 [1 P" O, H8 Y4 I# ~9 s
                else
+ |7 u  u* _6 H2 O9 H+ d                {. \/ C- i. M# }7 c
                    if (numw[i] != 0)- Q7 K) ~. H. P' N) [! |
                    {
- |6 U/ g; s% \& F+ q! @                        i++;
$ N# V( b) N" F# M) V4 q2 X                        k++;
0 J# F0 _( j; i& P2 b. H8 b# s+ U4 ]                        if (k == n)% a5 S; L9 \% L, |
                        {( F1 H* N, Q# E+ d2 r. Y
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
" c5 O3 a- h6 ?% M% D. U# ~3 v6 D                            k = 0;, l8 V( S3 f8 C' N4 i8 s; z1 M
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1  f; V& U4 M! {$ G+ M7 B3 f: b
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, F- x' E  Y3 O                        }8 k( {) v7 {" q4 g  ?" G
                        else//输出暂时还没有改变数组元素的值' r2 L8 G" q# x( h" _
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);4 [: H4 j1 |5 R7 d' d0 {
                    }
) _5 K4 N4 a' L& }, R# r                    else
1 }3 ^* r9 j  L                        i++;//数组元素为0,直接跳过,不计数。。。
# t' T  V4 z1 w; S# `                }# p2 e4 h0 m8 p9 O
  m7 A; U: X8 M
+ g3 M5 r9 V$ w* v+ O; Q
            }//结束while循环& _/ \5 R1 C- u0 [) B. ?# X+ P
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦4 n" o& s9 F' }7 Q) I% u
           
9 ?! S& q$ N/ O  p8 s- @                if (numw[i] != 0)
$ c* ?% a, O7 C  R: ?, }  H5 ]                    Console.WriteLine(numw[i]);
$ n# f$ C6 N* V  t# R1 `+ q           - J; a9 G6 w, S" i
            Console.ReadLine();
. ~! N5 ]0 M; B2 p- S        }
# R0 \4 M6 Q3 \  {* y) i    }
  B3 R' }$ D, v# o  a}
' Y% k. k. k3 |: X1 ~0 j; D2 b
小甲鱼最新课程 -> 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, 2025-11-14 16:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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