鱼C论坛

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

猴子问题

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

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

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

x
大家好!4 n# L" H2 G4 _1 J# [  r! Z7 m
这几天我在忙着编一个问题,我用了一种方法编出来!4 G+ s' n. d, r, ]
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!8 h/ `( R: G2 Y" d" Y# p% e
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
: l& R0 v, ]& F- |8 ~6 k; h% r3 T3 k, ^

* t9 G0 v4 e/ F+ }" d- B. x
                            题目$ {9 M: X& M8 I$ `4 {) q# P/ W
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
- _9 D  f8 K" a第一种方法:利用循环链表
/ @4 n# i8 U: S#include<stdio.h>0 j# }7 R2 a: W
#include<malloc.h>
$ T3 C- R) C& U( ]% y* ~7 v#define M 8            //共有8只猴子5 n' K4 R# Z; V" c5 A# V: e
#define N 3            //数到3只时退出第三只
" ^, C6 `- I# Dtypedef struct monkey
8 ?* _0 Q2 ]  G2 P) w* n{int number;
; ^( Y' N- T. s) z' ?  Vint flag;
5 h# m' Y9 F7 y* J# F4 n2 }struct monkey* next;# g) t4 b( _2 {2 M/ X& D
}MONKEY;
3 q" I5 g1 |# C5 k- jmain()' b1 H5 F. @4 P; T! J$ V) [
{ MONKEY *head=NULL,*p,*s;9 T1 C5 }" T7 S: X5 W' `8 K0 Q
  int i,sum=0,count=0;5 j0 J8 @' Z; c5 ~0 ^2 K
  clrscr();              //清屏2 G1 R! K$ C/ r: p* C$ s
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存5 G$ w* T- c1 V
  p->number=1;p->flag=1;, h; R1 ]: \, l$ f5 m
  p->next=head;0 C, l& d. F- O$ O2 T& \& {
  head=p;
1 J  P$ D3 }# p" q8 i+ W4 W  for(i=2;i<=M;i++)
6 W7 C" J+ A  E- V+ x6 N    { s=(MONKEY *)malloc(sizeof(MONKEY));
$ t5 _$ T( `7 V5 E; u! ]     s->number=i;s->flag=1;  K- [& g" ]  w+ _; `! ~' J# q
     s->next=head;
; D) N* p, k0 X' i# p8 [     p->next=s;p=p->next;
) L9 n0 m$ R' A    }
  ]* T9 P+ f4 n    p=head;1 _! v1 N; Q1 ^, Y
   for(;;)
) R8 d1 g* l! ?; u+ L    {if(p->flag==1)
* |, h8 x6 V8 W5 h2 c1 u       count++;
7 Z* e8 [( j) U9 Z# V! z5 z     if(count==N)
. ]; T$ u. b0 |& `        {p->flag=0;6 w4 d# a: x6 R8 K
         count=0;$ n& Z" h- r5 \
         sum++;}0 n: |8 I/ L: V* U
     if(sum==M-1)
; W( n4 C6 u) ]# I        break;
+ `3 V( J+ n6 M. e     p=p->next;8 o" S4 t* b- U# x& L" V- C0 r
    }
3 A3 Y" R# e4 g- [# F    p=+ ?+ Q3 B/ I  {) q
    head;
* ]  e# i. R, i  J7 t2 Z1 ], m    for(i=1;i<=M;i++)# l7 I( o8 c  ~, m8 {
    { if(p->flag==1)
2 x; K0 Z1 X/ M0 ]6 P        printf("\t%d",p->number);5 Q" o# H2 Z; ~* ?) _2 {
      p=p->next;
% |: D- p1 g3 V: w8 m# ]    }
! j- R4 ^: k- w) k) A: o0 D
& W0 E: y+ |$ b
5 S; b9 B' @5 Z9 i  ^6 {5 X* W" @3 q/ n% G+ I; b
}
9 c1 O! k9 f8 w: f  K- v! c8 f
第二种方法:数组
) f# O4 `8 b3 `2 X#include<stdio.h>! I+ j! R9 C9 E9 f  L
#define M 8
, N! L) M% x. Pstruct monkey
2 P# A3 @' E$ j# E0 i/ ]- R{int number;
' t8 v5 E( S' X7 w" W2 sint nextp;
8 H7 X% F  }  F7 `# b4 i}link[M+1];% c7 I, v- V% c" E' r) Q6 B, v% N

. l0 ]8 F. _" c, N  t8 V7 q% Uvoid main()* p4 ^5 Q( M$ ]+ v$ x4 z
{int i,count,h;6 t. z+ C: ^) B$ c; e
for(i=1;i<=M;i++)5 c4 ~4 c* i$ o, \
{  if(i==M): t, i, i6 u" e4 @9 w$ g
   link[i].nextp=1;, J5 n' u2 L. x
   else
5 g. L$ ^: e0 y1 z/ p   link[i].nextp=i+1;% D: V9 h* ]: K5 E7 r9 o& G1 G
  link[i].number=i;
. _; w4 Z8 v/ z$ `  Q}
" A1 d. E, M3 H9 A! S; L& pprintf("\n");
( q' r" z+ ]) H7 F! Ecount=0;
; O1 g) E3 ]. u" J" d5 Ih=M;9 J  _  s: Y8 V+ u
printf("依次退出的猴子: \n");
3 X. e0 {; @# U& hwhile(count<M-1)3 v% \- F0 F, I- d
{i=0;
" ~; F, @$ ?( p5 H& Iwhile(i!=3)
) @3 ^% e$ j. K{ h=link[h].nextp;; w0 n" w7 r% D) K* a
   if(link[h].number)3 D5 @9 O3 Z2 F! e* i1 t
     i++;}
; V# Z0 h; d3 Q4 _7 a6 m4 L
4 G, F" g1 j7 E" Nprintf("%4d",link[h].number);9 t6 O( H7 o6 r# e/ q: V
link[h].number=0;
1 y' u% [+ P8 ycount++;
+ w' L  n& z. [, l- L) Q}# h: u$ W1 _8 U" f

' h; q' q7 g- Cprintf("\n大王是:");
8 y/ ^9 L# `$ ]7 v2 F/ M5 F0 ]- g  for(i=1;i<=M;i++)
+ H  ?* _0 R8 B4 i- b8 Z3 z  if(link[i].number): z1 s! o7 f2 \$ E3 \2 {0 G. e
    printf("%3d\n",link[i].number);
4 A5 `3 q0 s, `* ]) J+ @
$ l& t' x- \4 o' _$ C- `; M7 O, g0 y( P9 g! r: i% p$ y
}

. ?. C1 L1 S: W第三种是普通方法for循环

, d) H! d; K8 C! ~. h6 M/ i#include<stdio.h>
+ H8 E, z/ F0 l1 _void main()7 g7 F! v: q( S7 G7 P" A; B* i
{ int i,k,m,n,num[50],q,*p;+ q! _0 f0 Y( m2 F
    clrscr();4 z& s7 ~& ^' {' [
   printf("input number of person: n=");
' D; Q+ _3 v- a. V    scanf("%d",&n);
# r4 Z4 `( u9 hprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 R3 Z4 E4 r: @: p. }9 v( l    scanf("%d",&q);3 X! J: t$ v3 {7 P4 W
   p=num;; Y& b( W- t! C7 R. r% s9 ^
  for(i=0;i<n;i++)* O0 Z4 U( I' k
    *(p+i)=i+1;
9 H" V& H5 ?9 S5 V+ p) W   i=0;
7 I( O  K) G' |" t- v# b) j   k=0;% R: _( p& ~1 n: c  e4 h* I" q
   m=0;
4 x' u! Q; t5 i2 I  while(m<n-1)( ^* f8 V0 G3 m# q4 J6 w) l" Q
   {if(*(p+i)!=0) k++;
0 f/ ?5 i. D, d+ F1 [     if(k==q)# x3 R+ d: j, M$ M
      { *(p+i)=0;5 Z# k3 A: S9 X7 L
        k=0;
) J3 @( f/ V& H. G; @2 v4 J3 y        m++;* D+ _3 G1 d0 R
      }
9 L) P9 I. ?7 V: |$ N    i++;
! A3 ]( u6 @5 X3 J6 u    if(i==n)i=0;# X9 S9 y  l! `$ X
   }8 s  b2 ]' [' Q) c
  while(*p==0)p++;4 u5 r" C! y% h6 y: h% H
    printf("The last one is NO:%d\n",*p);1 {9 o. T* m) u- z9 Y1 w9 w
     getch();2 F8 Q$ V, I# |/ i8 E, J

0 C' D  m& X% G3 N- `8 U0 m}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
) N  I4 h+ f) Q8 }1 Z1 _. m$ fnamespace 又费马达又费电6 C/ d+ z& A+ U1 T0 u) Y" k3 y4 f
{
+ V  z+ o9 ]' V; a3 J) G% @    class Program; s* ?" F8 D  D+ b' `
    {
( W0 R. Y! F5 X5 y- F2 i* `2 g0 K' R        static void Main(string[] args)
( ?; F+ A( Z, l" A5 X7 g% n6 i        {
7 D% V9 `( g; x- j            int m, n;" u" L4 V+ z. f. P' x' ]6 C& @
            Console.WriteLine("请输入数组长度");* l, Y1 u% R6 F0 N6 w* c7 K
            m = int.Parse(Console.ReadLine());//m为数组的大小7 F, M$ E5 w; H* p7 i% p9 N5 X- s* g
            Console.WriteLine("请输入要截取数字的大小");6 j- @; g: V. R/ x) Z' O2 X! }
            n = int.Parse(Console.ReadLine());+ Y' }. @0 L3 L4 l5 I
            int [] numw=new int, |# V6 J2 K* \* y8 T
! S; t8 G1 K9 f& M- Z3 F1 x
&shy;&shy;&shy;;# N3 Y2 m- B6 W1 h
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
5 F1 F' Q; r* e+ Q( f8 \& ~            {+ T; w' ^& \" x: ?2 Y& W8 L
                numw[j - 1] = j;
* J) ^: l: Q0 V1 n9 h' ^            }- Y4 ?% G5 Z3 n% F
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
) L2 n3 X- z' W$ N  K            while (d != m - 1)
1 n' R4 ~8 J) C/ [+ s4 e9 B& k1 v: `            {
/ ]4 r2 y9 _5 t+ y: H- H" Z) k/ m                if (i == m && d != m - 1)
- _9 U3 p* d; a                {: Y" x; n3 e: {+ B7 n# Q
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
0 }+ H  @# v( }' N* q2 C( [$ W                    continue;
2 h3 E3 `! }! r' ~                }* g+ {" ]$ n8 b" }
                else- y1 `7 l8 [8 |# j& w
                {; K4 {! c! d) C, d6 z/ N9 o
                    if (numw[i] != 0)
* G- }5 ^- A. P- z                    {. [6 \3 E0 L& j" ^) i, P. n
                        i++;
2 }& J0 c0 x- k  w) ~                        k++;# s7 l. ^) G* Z9 q8 M# B1 h
                        if (k == n)/ c$ v6 Y/ M/ T
                        {
; i& }5 `6 l5 J  r                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
/ P! z: |, x+ q. ?( ?( n+ M! F( \                            k = 0;: d- ]1 N2 w" x+ o
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
7 L4 c3 y% B2 E+ N1 B) k                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
- F6 q/ S# ~( o: E2 k. u                        }0 d- h) R. s4 M+ n/ Q/ `9 C
                        else//输出暂时还没有改变数组元素的值
  s5 J( e- ?, Q                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 e* Y4 g+ h2 F4 ^' y( i: ]- f                    }
) P4 ^! _; C4 R; d7 e) z9 D                    else
3 c' m, M6 I* P7 l9 e                        i++;//数组元素为0,直接跳过,不计数。。。
; s/ C7 G6 @3 a; S7 ~                }
% H) W: H5 d* a2 ~- n
0 ]3 |  C  [. X' J2 x3 y" }
# t; ?7 T5 R9 Y8 T* [            }//结束while循环
. L2 A0 t! ?! P( W! j$ N$ V; H            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
2 E; @; C  d9 ^- E( N4 h           
+ Q& c9 B6 R( l                if (numw[i] != 0)
- g+ C6 I) a1 \' o5 d# `                    Console.WriteLine(numw[i]);, E) G: r  M8 E; P, J7 Z& o
           + I8 F- R4 A: o$ u& h) a
            Console.ReadLine();
5 M% \2 D* {+ `, G; p( C        }
/ `) B6 d" S  l: W/ a0 L: u) d3 G    }
) M# R" [( I+ H( }% R}
+ r1 ^% R( _# v( ~
小甲鱼最新课程 -> 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-26 15:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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