鱼C论坛

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

猴子问题

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

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

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

x
大家好!
7 X1 p# L2 V  b2 I' o& q+ P- ~9 L这几天我在忙着编一个问题,我用了一种方法编出来!
9 ^0 S6 E' ^0 G/ k% E但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
! F: T$ }& H2 f8 ?+ l$ v; M5 \' b注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 ]0 F" f; E0 l; c3 z* {- e% H: l0 |0 E! `. ?2 X) u
/ h3 r. R" ]% j) Q9 _
                            题目
6 D) K& s: k9 l: k山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
8 Y8 W! m+ i1 ]第一种方法:利用循环链表1 q. d. S8 y/ ~- }2 J( p
#include<stdio.h>
) s2 a" q# R" T2 ^; N  S#include<malloc.h>
0 x% @* Y" T2 J% u# h  O; d% L#define M 8            //共有8只猴子" r1 ^; p+ \5 N# e4 K
#define N 3            //数到3只时退出第三只
# r! ^2 o# ^  q8 Ctypedef struct monkey
4 P1 m3 W# y9 B0 F  i* W) U{int number;" V7 A% g; p2 G- m5 u3 U
int flag;
* F' r1 T: x! G' |3 @6 Estruct monkey* next;
+ r4 Q4 S6 r0 v1 K' E}MONKEY;: m# h+ K) x9 F+ e3 z
main()6 H* p' I3 R3 n' @# z6 B. ?0 T8 j
{ MONKEY *head=NULL,*p,*s;
, W# t4 D$ g; t' o6 u; h/ Y  int i,sum=0,count=0;4 r: V+ _4 `) I8 [( L; t+ L* m+ ?
  clrscr();              //清屏
6 s' y/ M7 X6 y& L  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存% K, ^& s1 E: ^% P* t7 X
  p->number=1;p->flag=1;
* o: h; s3 g5 X4 u1 E0 D0 c6 ~7 f  p->next=head;
# _# x7 ~9 W, C7 Q* d$ O  head=p;
- v! P3 F0 S9 \: B: T  for(i=2;i<=M;i++)2 B% [0 g; i2 r
    { s=(MONKEY *)malloc(sizeof(MONKEY));3 P& N0 \1 D/ h; m1 B! l7 ~
     s->number=i;s->flag=1;# U9 F% Q/ ~! z7 |
     s->next=head;% w! `: L3 `* h4 P+ ~+ V, a2 ~9 `
     p->next=s;p=p->next;$ t& `% V! p+ [. _  Q' _
    }
% t$ A+ Y6 p9 {4 y$ h  A    p=head;2 f6 P" a8 g2 p% H; M, X" p
   for(;;)3 A+ b8 A0 j7 i4 l# A
    {if(p->flag==1)
+ ]" \9 B0 Z6 q& P6 n. d       count++;& N' v+ U0 y- W
     if(count==N)
8 w* ~# T! C% P+ i        {p->flag=0;
- B2 Q3 D: {- U# Z& a* `3 A/ |         count=0;( b7 j9 r+ t  p- l9 F+ u% B
         sum++;}/ d+ r% c( R1 q6 d
     if(sum==M-1)
5 x1 i+ t: u  z# Z* ~        break;1 {' `, v' C( [0 e1 A# Z. ]4 v
     p=p->next;0 [& ]. v' M* k! E
    }( z# G0 _; i5 q2 J. G
    p=
  }8 I, m) Z$ o% I    head;
, M. W9 l9 ~' t* p, f: m: B2 F    for(i=1;i<=M;i++)( y( M7 e; @( k% |
    { if(p->flag==1)
1 g3 {" n3 |/ P6 [/ a7 B        printf("\t%d",p->number);0 v' }6 r& D4 J0 j0 p3 p5 R- G
      p=p->next;1 g0 O% m; j4 v1 c; ?/ {- s
    }
" D  Z) A  g) R2 o  ]" [) @8 u9 V# @; G$ G# h% r7 |4 H
* Q( X4 U9 i$ e6 x! X- e7 s6 O

2 D5 ~  ], m/ }7 a9 k}

4 ^7 B0 d. z; T+ M# H+ H- C第二种方法:数组8 V( G! Y2 p' D4 z4 o5 l* ?* f
#include<stdio.h>( }) v: P" o/ Z) _
#define M 8
1 [. c) }4 N/ m6 y" h, b# {struct monkey3 T2 k% G1 f9 j# N# F8 j
{int number;/ V  t! W- u# F) f0 e. m
int nextp;
% [! \2 i* d# T: N1 ]: T}link[M+1];/ D3 e2 H0 a- p; b" u

. m1 O: M. X5 [' Uvoid main()0 M" m5 v# [  X& L- u; q
{int i,count,h;
6 K6 u# P. Y6 T8 i* h( X" @$ sfor(i=1;i<=M;i++)
* L1 `( y$ D& \7 l7 b{  if(i==M)
7 [' Y' a6 o( d; u. O, w. k   link[i].nextp=1;4 m8 f. H" R1 l0 e1 j4 G5 z. K
   else
" H5 {4 W' d) c1 }& V   link[i].nextp=i+1;3 O" {0 k8 A, Y. F
  link[i].number=i;" G; x3 S! R6 p& C, Q
}
, z9 F- }2 \( o7 P$ p: Xprintf("\n");
8 u& _6 H" R* mcount=0;6 l# x5 P, d; _3 B
h=M;
, H) Q, ]0 H+ B- U6 Dprintf("依次退出的猴子: \n");
6 o0 \4 G, g, V8 S- B9 Jwhile(count<M-1)6 [, @+ U, X/ U6 V+ j$ F. m* I
{i=0;/ [4 g' \) X: G5 \
while(i!=3)
. ?+ @% V6 U+ K7 P  L& X0 I{ h=link[h].nextp;" D/ e5 Y) ^7 x. z- k  z/ t
   if(link[h].number)
) `  P1 ?1 X2 k7 v9 E     i++;}+ B& z+ H3 G) Z" P7 r
$ R. L7 ]- n) E: K: p, b8 y
printf("%4d",link[h].number);- u: s3 f  l. u7 c; A7 s
link[h].number=0;
) e1 h) A% f9 M2 t, ecount++;
9 U  |& S" X, ]6 l  w}
9 i. \  ]/ L) L  n8 {; r- x: I% D, S! f7 R( c
printf("\n大王是:");
# n; h  Z0 ~$ V' J# x6 {& g5 J  for(i=1;i<=M;i++)
; q) H- @# N4 o2 R. ]* S  if(link[i].number)
% G- D) _, q) {' z8 U    printf("%3d\n",link[i].number);
/ F7 S6 `( p! O: d, i7 R& D( W2 r6 P3 ~4 R5 f

' ]; B6 Q# J5 Q$ L$ Q}
' B, o# ^- y, w/ I4 H! L
第三种是普通方法for循环

1 R& V: n* H; |% Y! e#include<stdio.h>
' [5 y/ j6 p, |! r4 k8 \void main()3 T9 @: a1 u7 m2 I5 [  @2 ^' Q
{ int i,k,m,n,num[50],q,*p;
8 ~/ F" Z0 o! [4 t8 {% d2 W    clrscr();
. |# ?( q! e7 I! x5 g) J8 G1 y   printf("input number of person: n=");
" {# g; d+ M6 I3 P) t" S! A3 ?0 d    scanf("%d",&n);
7 ~0 x1 Z: y+ o/ kprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
' C7 n  t  a+ [' b+ n3 `1 Y7 Q( T) w) U    scanf("%d",&q);' A1 G: g2 L8 b" e2 e
   p=num;7 M; e0 @& _5 f" W7 i
  for(i=0;i<n;i++)# A& D# s$ x' |+ G6 _/ @8 w
    *(p+i)=i+1;3 d) w# s0 L; C! G2 y0 B4 B
   i=0;1 i2 V) o$ l1 B5 ~  Z; k0 t, Y
   k=0;! \) j+ S. N* U7 b/ n8 G) p
   m=0;
9 ?  e8 q5 S  [  w. K( O  d( g3 K  while(m<n-1)3 a5 E1 t+ v) G% f% Z. r
   {if(*(p+i)!=0) k++;
0 W* S& B. [" r/ J) i7 p     if(k==q). u& q9 U/ ?+ k1 F; o$ r5 _
      { *(p+i)=0;- a# h5 d9 d8 r5 w5 P
        k=0;1 G- ^8 a$ V% a, Z. ^- w" P1 O
        m++;
% {: i5 B0 m  u& j      }
3 Z2 K8 A, f0 |- c* P3 ]6 @( S    i++;
8 q1 g* f7 k" R) k- L* R0 \    if(i==n)i=0;1 b5 I6 E! A8 ]5 T7 \, ~# K/ f
   }! n8 K2 R+ Q/ _8 F8 a: g
  while(*p==0)p++;& L; ?% H' j4 C& |2 F# S, O  W0 o
    printf("The last one is NO:%d\n",*p);7 _* Y  }( P' O2 h
     getch();
4 S3 u$ m$ s+ Y+ L! r: j2 n( t6 R6 Y8 ]: B3 H* ]
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;* e6 d" S; J  T+ R+ f! k
namespace 又费马达又费电! l3 d8 z  g) ^9 [
{9 b8 b- P# A% p. J7 }' B
    class Program' G3 z) Y/ }( }) _
    {
6 X+ {3 W2 y5 Q2 D5 [        static void Main(string[] args): B4 @5 {! F; B% P9 `7 j
        {. h/ F3 }7 @* v( K9 A# o
            int m, n;
# y3 i+ d4 M# H& A  d( Z3 o1 }) _            Console.WriteLine("请输入数组长度");
7 w! w% j, c, i& ]8 W6 s7 k            m = int.Parse(Console.ReadLine());//m为数组的大小
. [  b. }! `9 ^7 }& `            Console.WriteLine("请输入要截取数字的大小");+ g4 Z' E$ N# ~; O9 y
            n = int.Parse(Console.ReadLine());
8 v# }, F+ j7 v' B            int [] numw=new int
6 e( X7 A9 V5 V7 w3 r; C2 ~3 \' J! F) W' c
&shy;&shy;&shy;;. e4 ]4 Y1 ]6 ?
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
/ F1 a- B+ ?* P6 u9 w4 }            {; X& S6 B5 B, f$ U0 m# T" N( d
                numw[j - 1] = j;8 K( X) b3 ]% w0 R2 D$ ]
            }
9 d% j) C) d: ^9 U9 v            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
( Q% w( A  R1 }. E            while (d != m - 1)& I' _- _3 R7 A, y0 w$ h
            {
( j: T2 }$ k; Q5 a, g                if (i == m && d != m - 1)
* N* `. X. A+ g! |, m, e                {/ t9 Q1 k; J2 h9 b* w# c
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
: L3 X2 n& l, t% m                    continue;5 W3 L. n/ z& [7 x& R
                }
1 I  k+ c* p- n3 w4 U) m                else- x' T6 B/ W7 Q" e3 L
                {
) w& u7 B/ V! P3 \                    if (numw[i] != 0)
3 j3 X" j% `5 z: h$ d6 I                    {" U) {; R" @$ x6 \+ B' t% D0 `
                        i++;/ X3 X4 g, Q& V) s
                        k++;" F9 [. Y% a$ e; C0 E/ m+ I
                        if (k == n)# V0 S- N4 A+ P
                        {
$ c3 }3 M  q  B: ~. d% K0 ?2 B; x                            numw[i - 1] = 0;//把在n位置数组元素的值改变了5 Y2 v7 F8 N9 Y" Q/ [
                            k = 0;
& D) V6 _. s; Z0 ?3 W: h* t              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
# f4 ^! s# Z/ _- ^- m4 Z1 s3 Z8 E9 C1 _                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
+ C" e: B- h# Z6 j                        }
' F5 m( m1 v4 _5 |6 F* R                        else//输出暂时还没有改变数组元素的值& V& D7 D* c6 N9 X. Y
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
7 Q1 Z4 y2 D9 h, |$ |                    }+ t% f, W/ n" T7 G4 M5 G" @  f) |
                    else, Y! Y0 D% q' x7 Y6 ]
                        i++;//数组元素为0,直接跳过,不计数。。。
1 W. r" K7 E, h% i- Z                }) e2 A/ Z' R, g' q! |/ X$ h

0 M4 }1 x% |5 w2 v; Q  {8 p/ E. Z5 c) _$ ?. L$ W7 b
            }//结束while循环) r: x7 y- \+ J
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
/ \$ [  l' ~6 O4 K# }4 O' [           ! _  D" v" g( I
                if (numw[i] != 0)
$ B( Y: I( {* @7 b                    Console.WriteLine(numw[i]);* m7 B  V5 N1 A: U
           
. ~# `3 v2 {' s# M6 x5 s1 A            Console.ReadLine();$ K2 ~1 |6 Z, x0 I
        }
4 Y) k) X% `4 l! t& v4 [    }
0 w+ e2 B/ E' {1 m) e3 D( x$ t}
" d3 X  g5 @) \0 K" h
小甲鱼最新课程 -> 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-17 00:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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