鱼C论坛

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

猴子问题

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

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

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

x
大家好!
/ s) M) C' k4 C- K这几天我在忙着编一个问题,我用了一种方法编出来!
. Z$ h9 j5 h# G3 N但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!' H+ F8 s) Z7 c  ~3 g: I7 H. S: E
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ' L: D: ]) c; B- b/ j

4 B: Q# Z$ n( a/ ?5 m$ {& T! T- P
6 I. j6 @6 }/ s6 e8 a
                            题目/ `8 \7 g$ l2 j2 n, n1 N- [  L0 e5 o3 R
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
; g' \2 O, y4 ?9 x第一种方法:利用循环链表% ?% F6 l3 T6 j- K# L* e
#include<stdio.h>0 b) m. l0 N4 K( `6 X
#include<malloc.h>" B. T  V1 W* \+ [/ l. g
#define M 8            //共有8只猴子- h" J+ j5 h  t+ ]0 w
#define N 3            //数到3只时退出第三只% T4 v4 H) E' t; p. R$ K: f
typedef struct monkey
, [; I! R& l& E+ x{int number;3 p5 x# o% e+ h' x
int flag;
/ J4 X) @- b8 J6 xstruct monkey* next;
. |" \4 b" ^) Z7 ]) a3 n2 y}MONKEY;4 q) |# n" u$ ?$ N* k
main()8 r3 r) l5 U0 s* R& m
{ MONKEY *head=NULL,*p,*s;
# {3 i- s3 \9 j3 }- D! f  int i,sum=0,count=0;, Q; q6 h* S  x) @; G
  clrscr();              //清屏: \+ [! B7 p& @2 n
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存1 u3 t$ a; p1 g2 h5 \
  p->number=1;p->flag=1;
2 v8 a9 `2 h, B  p->next=head;3 o- l6 D2 r( F) D) a! F
  head=p;  p3 n4 y& z# R  c' t
  for(i=2;i<=M;i++)
- j3 W/ F$ m+ x9 m+ ~2 A" v    { s=(MONKEY *)malloc(sizeof(MONKEY));, }( _3 e  h6 x+ z* f* T
     s->number=i;s->flag=1;6 d/ I+ r# N  C- Y+ Q' B
     s->next=head;
! D7 h  u  n0 u     p->next=s;p=p->next;* [% c6 `/ F& [8 R1 F
    }
' n3 t4 C1 M) Y    p=head;( z# e/ S& S5 E0 Y/ Q3 U* \. p
   for(;;)% D* M/ ^- {. S# o8 C
    {if(p->flag==1)
4 ^) A2 E6 I2 Z( m) D       count++;
' t1 \2 r" P! f% R" `     if(count==N)" H6 M+ B' ~! |+ P3 p: M& W
        {p->flag=0;7 c$ j6 S) J2 W0 Z2 l8 o, j
         count=0;: `. S+ r9 {" i
         sum++;}
: B7 k. `6 X: j6 `4 y+ c) R     if(sum==M-1). h; o3 k4 v) R# Q( m
        break;9 N9 ^, |3 z5 [* H+ z% b* F
     p=p->next;( L% I1 L- |* W/ ^) u8 e
    }, e/ H, q3 M% e5 g- ?" n/ s* t
    p=+ _+ ^" m1 o; k/ D9 {, Y
    head;
8 C% h6 X1 I) c. ^; S    for(i=1;i<=M;i++)
8 ]( l" O" |4 j& Y$ P4 e    { if(p->flag==1)' V6 n, H4 Z# l( v4 B. e  |
        printf("\t%d",p->number);9 [# P% L6 `" U$ m8 S" {5 E
      p=p->next;
7 b" K  C+ F9 r3 n    }4 s0 j8 I  Q: T* x! n

% v! t& N' O0 t; E3 r3 H+ ^2 S, q  X+ j: Q+ [- p& x$ D+ s# R$ z
* j* S3 m* B, j! x
}

: J2 r3 `) Z; Q* S! ~; b7 c# f6 {第二种方法:数组, J- n0 E% ]# Q7 U1 t& d% v
#include<stdio.h>+ k5 i2 J/ A) _1 a% S
#define M 8  A( @! ^4 v2 H5 J( b
struct monkey; F/ B5 M2 \& _- N6 e; @$ \
{int number;
4 A2 }* H# b2 @  bint nextp;
! u$ O1 j# Q. b( f* ?( p1 \}link[M+1];
  G7 Q4 E) Y' G$ z
+ ]- B! f. Q- r" H0 Q" lvoid main()
; P% ~# s) f( c0 S; ~{int i,count,h;2 A  q8 Y5 s) y+ U% M
for(i=1;i<=M;i++)  M- M" Z  a5 X9 Y8 {
{  if(i==M)
0 W, n% k. e! Z   link[i].nextp=1;
1 K/ s! c- n3 O3 K! x9 z8 R   else
: V4 n' U7 @- x* @+ e   link[i].nextp=i+1;0 F0 u6 ?6 G  v# w; U
  link[i].number=i;7 x4 l1 W: w( `! K8 I* p
}
; `' R$ L# ^7 l0 I+ w- oprintf("\n");* c9 `4 ~1 s# c: b6 I) S
count=0;2 Z: @+ W( O* z
h=M;
% v. d3 ]. z) e! u! p  h1 {( s' xprintf("依次退出的猴子: \n");
& G5 ~* z( g" m. j* F  l' n! dwhile(count<M-1)
$ Q: b$ Z- ~5 B2 M5 q- X{i=0;+ P. P# v! d9 \7 {
while(i!=3)  b- i# i% C: z. s+ Y9 a
{ h=link[h].nextp;
: p# K' A" q+ N9 o1 [) ^% ?4 e   if(link[h].number)
* O# i$ e5 U# I' D     i++;}% A- l# }: Y/ k& r3 F+ f
$ X; p! I( e4 `9 P, X
printf("%4d",link[h].number);% D6 I+ K* e& j7 E
link[h].number=0;
0 x1 A( _; I4 ^7 I0 J; Icount++;! b( K7 d' K0 Y
}3 _; q+ v" `! w/ S! w* M

, J/ S0 G. h6 s% d& u+ J0 `, Cprintf("\n大王是:");
& Y( b& J9 I, F* p  for(i=1;i<=M;i++)
7 J$ f& p4 Z3 O$ K- N  if(link[i].number)5 k0 s* x) C; d5 j2 A8 [) J
    printf("%3d\n",link[i].number);
) E6 U1 b8 \/ A4 P2 z" m( X6 W
/ I5 z' Q( X; N9 A+ R# ]; d
* C. z% S2 E; A7 k}
+ j- e( ^2 b9 i/ a& v9 P' ^) `0 c! m
第三种是普通方法for循环
/ j9 C6 q8 ~+ n$ x% e/ t% Z2 L
#include<stdio.h># ~# v  D6 e2 k8 B  L- H6 n+ }' M
void main()
5 c, q$ L. @' v* p. M  e2 h3 L" ~{ int i,k,m,n,num[50],q,*p;5 b0 T0 y5 k% A% H& A
    clrscr();
' B! W" |+ c! V5 P. p   printf("input number of person: n=");
% A  k2 ~1 G! d6 H# U4 w+ {( Q: S    scanf("%d",&n);
, c- f& T2 }: yprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只2 h- s. o4 s1 I6 b8 b. E; |
    scanf("%d",&q);
, r. I+ g' s& ?! y, y   p=num;
4 ]& @( K  i2 Q5 [: L  for(i=0;i<n;i++)6 Q" J) z2 [$ L9 R6 J
    *(p+i)=i+1;
: H3 p+ S% U3 ]- F' ~2 d8 ~   i=0;  c0 h5 N& S" u" T0 b/ S1 ?
   k=0;6 C) t# S* U8 D7 _6 r
   m=0;
+ h% [5 ^; Z5 i( T( U) M8 m  while(m<n-1)4 M- V7 B% q- @% M  ~* i
   {if(*(p+i)!=0) k++;  C  D. Y& f) P/ O4 a& }' }
     if(k==q)1 Z+ s/ r2 d# j! {# D: m
      { *(p+i)=0;8 R, s4 x9 q6 j+ ]( {5 C
        k=0;7 g! R- y8 M  j, M( j
        m++;. x% p1 T$ w* J: [! |2 v
      }
$ X7 c: W6 C* ^    i++;
* [0 u$ L8 D$ ~+ G* B& I$ K: z2 J    if(i==n)i=0;
) C" s% o+ X& }/ W. |) c8 h) S   }
: D6 v) B. d6 C# o9 y7 E  while(*p==0)p++;5 C% P9 r2 `& `2 q
    printf("The last one is NO:%d\n",*p);1 i7 E0 _7 X# T) B0 I
     getch();
6 Z4 [2 ~4 J/ ^# \% e; K. \
' U" L3 v$ P1 Y( \4 R5 S}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;/ L  {, a0 y) f, }1 m7 X0 G1 S+ X
namespace 又费马达又费电
' m1 L/ d9 `8 K$ m- `{
7 E9 a- N" r5 T) X& ?& G    class Program
+ p2 h6 l0 g$ k$ A' \    {$ C- l- G" J% H3 d
        static void Main(string[] args)
- z& O$ B4 b8 ^4 D, x+ X        {$ W* h) H# F4 D; D3 o8 |# D6 I
            int m, n;
& l) k; p% d) e$ T5 m            Console.WriteLine("请输入数组长度");
8 ?' j3 h  H* N            m = int.Parse(Console.ReadLine());//m为数组的大小; J7 z6 m$ f- E  k( Z
            Console.WriteLine("请输入要截取数字的大小");0 S- F: s# _8 ?. Y6 P. a1 P  o% M
            n = int.Parse(Console.ReadLine());
# T. t  j/ r+ V/ z            int [] numw=new int" _* N0 U  ?! `# e6 }" H
: ]5 {0 |, Q7 n6 B# F
&shy;&shy;&shy;;
( w* W7 g6 }8 A; C+ Y/ W            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数" L9 f% c% p: b' I6 g
            {- H9 [) v5 j1 B
                numw[j - 1] = j;2 }. {. V' m, ^$ R, a
            }- \- {3 f4 c5 t. \0 V, Y( g" D" [
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!! U* F- }2 G: Z
            while (d != m - 1): N" k/ k5 g/ J  M/ ^
            {& i) ?' Z6 T* M: S' Z" w
                if (i == m && d != m - 1)6 G) S7 [+ p% t+ [/ O
                {* G3 [3 T- [% l" g( e1 ]7 |6 G
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
4 |8 _7 t) V5 z" R- q& h& z8 A8 U                    continue;
. L4 n# s; h, n3 N! G& s                }
& }$ e4 Z0 v& m' f                else; w7 [* d9 P/ H; D+ b2 H
                {& v# B3 q; h" J6 C7 W& E
                    if (numw[i] != 0)
  x& I+ Q2 o8 q8 G; Z6 V                    {6 t- |7 y# ~: b  _( G
                        i++;" U" Z, D( \% Y9 |
                        k++;7 v* \7 j% ^5 W
                        if (k == n)
; Y0 A. b# x; o" L4 x% |/ P4 {3 H% K                        {
) v- n: e2 V7 B. G& o. w                            numw[i - 1] = 0;//把在n位置数组元素的值改变了* s8 C0 ^* t# s, z; T- U% d
                            k = 0;
: u/ D. ~0 k/ R2 d# n              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
1 i* U8 I. m5 s2 y6 {, J4 u                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
2 E- P" G, |' K8 u: P                        }) ?7 L% F, v: [4 l
                        else//输出暂时还没有改变数组元素的值
  X1 u; F% D0 J( D                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
# s& p7 `" m( n- b+ I                    }
2 N* r, p9 `% ?* }" i* j& J                    else5 x; y9 H2 S7 Z! E! P' m+ D
                        i++;//数组元素为0,直接跳过,不计数。。。2 n: J, y7 U+ k
                }& t5 @. W6 \1 K, s' l3 E( y

! J1 L& h2 e+ l; l6 |* Y1 \
/ {8 B% w7 V9 L4 |, D& y            }//结束while循环  t* ]1 c9 S  I  v
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦, V# {) B* G- e4 K5 F2 h5 ?
           ( Q4 i6 M+ X& v5 ~( ^, h/ V4 t. Q
                if (numw[i] != 0). o7 {! f* ]* ~9 o9 j6 V8 i7 Q
                    Console.WriteLine(numw[i]);
, H+ r9 ?: c3 [! c' S           # Q, e$ j# t, J
            Console.ReadLine();" L' s, F" x  p) D: B% ~
        }, z3 j2 Y- z; h8 u8 u7 }) q, @
    }& J9 y% s( x3 a. i
}1 R2 \! n' a; N/ L/ j1 E0 l- m
小甲鱼最新课程 -> 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-1-18 19:44

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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