鱼C论坛

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

猴子问题

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

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

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

x
大家好!
( M! O3 g  I- T( v8 W& W% K0 A# M# r这几天我在忙着编一个问题,我用了一种方法编出来!, n( h" m7 B; E5 V
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
3 ^" u+ z: R2 x1 O5 H$ t# s注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
% b2 n  H; e+ j, R9 K& [3 j: l+ f: ~

. {3 T4 v) b) C
                            题目
. d; F+ x1 S' ]8 l5 w山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。$ \' E, F# i) X$ g
第一种方法:利用循环链表( H; G$ v& i3 }* Q2 e3 \5 o, M1 l
#include<stdio.h>0 [- v, Y7 H% Y+ y/ q. u) Y
#include<malloc.h>
4 |, [! l. W# t) X, T- d#define M 8            //共有8只猴子
& k4 }: U- E- [7 n#define N 3            //数到3只时退出第三只. I0 W) c$ A# N$ |7 c7 U/ d- O
typedef struct monkey0 q* }" m) @$ f4 r% D3 U# V3 R
{int number;
. _7 `) @' |" r" @4 g; |int flag;6 Z; U3 j% `9 D0 ?$ M5 R8 S2 h8 }
struct monkey* next;
! T' q+ q) K  }6 d. c6 n}MONKEY;$ p- a  q. A& m9 {3 ?
main()
5 V( `( M9 u  B. ~{ MONKEY *head=NULL,*p,*s;8 f5 q& S( J) q8 l8 f3 C
  int i,sum=0,count=0;
  g. l; w. v. x) s" N+ c  clrscr();              //清屏
- {7 {6 q4 e) w- y( S) ]  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
- k; M% \( l  H# N  p->number=1;p->flag=1;
9 b  c( u* J( r4 D6 @  p->next=head;- e" o+ S; _- E) B: R
  head=p;" U& k; z% U8 O6 a
  for(i=2;i<=M;i++)7 Q/ x' ]6 n2 j  e- J8 f
    { s=(MONKEY *)malloc(sizeof(MONKEY));
  x9 }" M3 X- n- g* {* F3 x" p     s->number=i;s->flag=1;& x0 R% k7 t4 R; N
     s->next=head;0 Q9 _1 }: }7 {
     p->next=s;p=p->next;$ I) Z/ {8 T8 W/ z- z7 }
    }
! E" J# U0 U) z+ G: }, ?  n$ t    p=head;
  F  E* p$ g5 M3 c8 V2 K   for(;;)
" F, Y# r9 y1 c; U- k    {if(p->flag==1)* Z- {2 F( C3 d# p6 e2 ]5 s
       count++;
8 e" p( H2 ]1 x. ?6 L) Z7 f, L8 A     if(count==N)
. o0 w$ \; `3 P( S* g1 m. v        {p->flag=0;
9 r1 ?! d+ \, ]( D5 R  ^& O8 F# t! f         count=0;. ]% D0 V; ?5 S' b% C
         sum++;}$ t! u% q, l& ]; A4 Y! A1 p# E3 N
     if(sum==M-1)2 x6 m9 v, N( t" B5 D; h! N
        break;
- O8 K& N. Y2 }# l: t2 s     p=p->next;
2 z# I' i- Q6 v# r& V2 k, D    }$ z4 G- D; x4 b) p& f3 ?3 i# _
    p=
: e7 L/ E6 F4 y3 Z9 |" l    head;: B: Q5 a: p' L# L
    for(i=1;i<=M;i++)
( A% a# h# S2 h$ k    { if(p->flag==1)* T9 \6 L. u9 p& h7 F) f- Z
        printf("\t%d",p->number);. `( R% }0 [% B3 w6 ^; y6 Y
      p=p->next;
2 P% g  o" s+ \6 C) b0 D# w; g    }
! f* u! x6 }. P9 D  v. ^
, d9 e, O, ^4 q; w9 O
2 }6 m" G% H+ Y6 s4 E" T9 E" @& S9 w+ `9 ]
}
: ^2 R' ?3 P( v3 W
第二种方法:数组
* A4 j1 r" f+ n% Z#include<stdio.h>
! Z- Q* [% y' O7 Q$ I0 o#define M 8
* d; S( b$ E- U; n: b; ?struct monkey
/ V, j- R& s/ r' C2 g: }" z{int number;) n) d. T# v4 i6 w7 Z5 _
int nextp;$ M# P5 g' V" l5 I1 u  r
}link[M+1];7 V) B0 I# ?# P: q7 e* w" m$ z

- z# E# I( Z. X( s. Tvoid main()! O& @! [. |! p# r4 O: E
{int i,count,h;( B) P& e- ~6 I/ O1 d1 J
for(i=1;i<=M;i++)2 L4 I; n) c9 Z% H' y( [7 M
{  if(i==M)
$ z8 e( w% t" E* D9 @   link[i].nextp=1;
1 Z- z7 ^3 K. K. L' d   else/ L5 n9 g2 y! {/ l. p) Z2 [- `
   link[i].nextp=i+1;0 E. `, v* a, W% Q2 ]( l
  link[i].number=i;4 ~# q  C* U3 {0 K
}
# J7 s2 V8 m" L8 c+ pprintf("\n");
1 A, s3 G# O2 a4 \: i6 acount=0;2 ?( |! w  H$ z
h=M;" k/ L; L% q& f8 P5 x5 y
printf("依次退出的猴子: \n");3 ?/ {0 H, K4 i; ]* m4 }) V0 J5 y
while(count<M-1)  w4 Q. \. f/ ~/ J0 [
{i=0;
( |* x8 s& ~& g8 pwhile(i!=3)
. t" {  _/ [# Q) r) R{ h=link[h].nextp;8 h! t7 t# g( r& c5 O# t
   if(link[h].number)7 O* @  ~0 L8 ]+ W
     i++;}( O6 Z5 x. ]. m! @

# Q3 ?9 I" F: B4 f7 b8 Y7 N; x) mprintf("%4d",link[h].number);$ x* M) o" B3 |
link[h].number=0;
7 m- o% z8 F; P1 |2 Dcount++;
3 A$ o4 }0 N; Y5 V5 G7 j}
. W4 K  O( a, U0 Y' ^
+ v# u! ^$ u& E1 v. Hprintf("\n大王是:");
7 w7 M" V4 Q* r2 H$ i8 s  for(i=1;i<=M;i++)
3 x( B. M: |$ O3 R! }3 X7 i$ B0 E. P  if(link[i].number)
+ ?% A% [* W" L    printf("%3d\n",link[i].number);/ d1 p. g- d  y/ d
$ L! ^$ V6 ^. P. @# d3 ^9 j; ~+ f3 o

+ f, i8 Z- V& r6 e' W6 S}
9 \1 o5 w7 T5 J4 P+ D
第三种是普通方法for循环
& U* ]3 B2 G' c* E
#include<stdio.h>
0 U$ D  |9 }2 Y8 ^& h7 k' evoid main()
1 a, H5 {- v7 b% c4 Y/ |% ]. h{ int i,k,m,n,num[50],q,*p;7 H# m9 s; ~% _
    clrscr();3 R1 W' o& I% o7 Q
   printf("input number of person: n=");4 D' N8 F- w( a0 b( O9 N8 Y( f
    scanf("%d",&n);( A: W$ B" Q# h! Y
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
9 c: ~9 ]" T2 o7 g    scanf("%d",&q);# E; Q( T1 Y6 `
   p=num;
0 V) R  W' |7 i& V. L  for(i=0;i<n;i++)+ Y) S0 G& k. _
    *(p+i)=i+1;
8 \$ R0 {' e& P5 E# @   i=0;
. |2 |% f' Z# x& Y1 b   k=0;! E% w) b3 X0 L7 Q
   m=0;' I2 y' D5 P, q
  while(m<n-1)) E! I( P; ^4 g8 }" A5 t$ ?' j' c
   {if(*(p+i)!=0) k++;) p, B. ?- a' q0 E
     if(k==q)* L1 Z* B3 o! t* g6 D2 H$ }. b
      { *(p+i)=0;
2 i( U; P+ Y& b$ z        k=0;% |$ x7 N( F4 M7 T
        m++;. B- G7 {( V  C6 r
      }! M5 b; L: p  A* _2 Q# I3 d
    i++;5 u4 @9 \- ?. [
    if(i==n)i=0;
  z3 |, P$ s  y: D   }6 k9 t+ u( y% R3 I( F+ \3 d9 H& N
  while(*p==0)p++;/ l% ^, t) j# q* G+ \/ f
    printf("The last one is NO:%d\n",*p);3 D3 ^3 _/ y1 g7 V5 ?' {2 k
     getch();7 @: J+ Z) m9 L1 x' p3 ~

- p5 z; s% A: ]2 @# W6 V9 ]' L- S}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
& m# f. ?! H# R$ A, z* W" Q/ qnamespace 又费马达又费电
5 l/ B; Y! W: G" x# K; _0 d# c{% F) b2 _; K! {
    class Program
( s& p, V7 |7 j    {! o; M8 k* b7 z; ~, W
        static void Main(string[] args)! [5 P/ ^! X, C8 O6 R3 Y9 A. I
        {
+ X9 x5 P1 A- c/ ?2 F            int m, n;2 T+ E/ U/ j8 B) i* S
            Console.WriteLine("请输入数组长度");
2 Y- g2 B8 d; S) f$ G6 y            m = int.Parse(Console.ReadLine());//m为数组的大小
( m5 z1 S; J, o6 t6 {. r            Console.WriteLine("请输入要截取数字的大小");' {' l6 w& ?  i, I# s" L2 F
            n = int.Parse(Console.ReadLine());2 ^7 @2 s8 x. Q
            int [] numw=new int+ X: @# J' ~& c: D
; l. D. l0 F! }, I6 A9 l
&shy;&shy;&shy;;
) k9 {% g" }: r2 O8 F) O+ ^4 k/ s! q            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数0 q7 h0 j& t' j3 w0 ~
            {
4 K9 G1 k- _) A) E! S/ o                numw[j - 1] = j;5 i& [- q' y/ F* A
            }
: [/ H9 L4 }2 q5 w2 s+ D! d            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!7 H+ o" T$ U) k" U
            while (d != m - 1)
% c5 Z/ _2 T% t5 N+ z7 K            {0 N+ k9 s# ~: {" ]
                if (i == m && d != m - 1)1 z; c; d3 |9 o8 n
                {
1 L6 _3 h& i  }                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!- E* d- P- a2 Q8 n6 q
                    continue;
& ]' ^: P! w/ S0 A( P5 ^% e                }3 M; t; I; K7 D9 I: G" M
                else8 |+ N/ T2 A8 K" N6 N4 V. s4 D" b
                {
" ~7 B+ R! @" |6 M- s" }4 `2 P2 r( Q; r                    if (numw[i] != 0)
  m# s* d' I0 C7 f  K+ l                    {
  q5 w3 w, Q  v6 r  Z                        i++;
# t/ q6 b5 m) Z0 p5 E& A                        k++;7 J# R) p+ N! m4 [
                        if (k == n)
3 i) h# w  B+ i& C' m4 S                        {, G: h& J' ]# V. x5 k
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
7 Q$ O- `" O: Q* f  I                            k = 0;
7 l* P: v% w# ]) S              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1- S4 [& q8 {  D5 l( x
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);4 S) @; x' X3 a8 ~/ I/ [& p
                        }& w+ U6 J, M2 ?! T$ ]$ V2 `: ~/ f
                        else//输出暂时还没有改变数组元素的值5 W5 E" e2 ?: i+ z
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
$ k  T+ j, R2 S7 G( q/ Z3 z9 W                    }
$ l2 X; O8 o% N# v                    else2 Z* @, b; k* y; U2 R8 \0 v
                        i++;//数组元素为0,直接跳过,不计数。。。5 }( l4 g& j* X3 E* N
                }
$ y6 `1 q* e' Q- W: C
. Q+ S8 S* Q# B6 Y# i2 ]; \- {" C1 E8 ]$ v9 a
            }//结束while循环
2 [8 {; I$ H# T& F" i            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦  ~& d3 V, q# }  q6 X7 I- |
           
* C9 d% w7 p$ ]$ b( ^% V                if (numw[i] != 0)+ n& \: Z, z- _8 E
                    Console.WriteLine(numw[i]);% I: {/ U0 }' X2 O& U5 [
           
/ m7 v! U  a$ ^            Console.ReadLine();$ i6 L" f$ q/ p3 O% l+ F
        }
3 t+ n, k* E; |    }3 e2 L4 [" t% p# |* g; M1 `2 L
}, P' o. O! V; k
小甲鱼最新课程 -> 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-8 19:48

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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