鱼C论坛

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

猴子问题

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

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

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

x
大家好!
% n8 ^/ T! C% B这几天我在忙着编一个问题,我用了一种方法编出来!0 @/ u5 ]- _+ x
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!  X  `% s  k7 K, r, y5 L
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
/ `  A# k/ p: n# p7 m- l
% C1 B: A. ~& X3 H5 j3 s3 U1 F( m  K, T
                            题目
* k. f! d* U" Y" n6 {2 ~7 X& v( ~山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
) q9 n- L1 i' q6 e第一种方法:利用循环链表, @. O( [9 b* g
#include<stdio.h>
( h& V2 M/ c  A1 \7 }#include<malloc.h>
/ X7 K% I  B3 G1 W; T/ }- h3 f! @#define M 8            //共有8只猴子8 [% Y6 P- R8 e  T4 a
#define N 3            //数到3只时退出第三只
3 n0 K* S" V) Q2 m: L$ V2 ntypedef struct monkey
* I( L5 g2 E9 m{int number;- E# ~% U6 L% k5 X
int flag;. ^; @. i) G" p& S3 |9 g; H3 M& N
struct monkey* next;
  b% r" z9 X) a5 B& l8 y4 W}MONKEY;
0 n: H0 k9 O4 m9 c) e+ X. amain()$ A( r, m5 h+ r  q6 U- U; o/ e1 p1 m
{ MONKEY *head=NULL,*p,*s;7 j8 N. e  z) I
  int i,sum=0,count=0;7 O" M) s: T& A
  clrscr();              //清屏; W5 e  Y2 h9 F
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
# V1 d5 O- [9 o8 X4 v. ~7 K  p->number=1;p->flag=1;
2 K7 X5 Q% u! V6 z2 Z8 R+ i* A4 a1 Z' ?  p->next=head;! M9 w! f6 s9 ?- D) q3 N+ a
  head=p;* ?" C4 K0 ]3 K9 d0 H
  for(i=2;i<=M;i++)
, E) k/ A- m8 U7 T7 ?+ k# u    { s=(MONKEY *)malloc(sizeof(MONKEY));
3 G! l* E0 V$ H6 Y     s->number=i;s->flag=1;6 i' e9 J  Z+ r3 n- U: P) Y
     s->next=head;) ^- b/ G% T3 P& @/ n! @6 F; g7 r
     p->next=s;p=p->next;
' E7 x) ]! J) C7 w4 r    }
$ o3 @3 F8 D+ p    p=head;
8 e2 Z. O9 b2 u3 u   for(;;)' ^: P# g0 w3 W8 u2 @
    {if(p->flag==1)% ]# n" F$ k% e  m. `
       count++;
2 \. f4 w. [$ E; y$ s+ O3 _+ @     if(count==N)% b: @$ D0 U" C5 r5 f: E2 \
        {p->flag=0;
1 R! {8 e2 c  t( D* `: M         count=0;
: M4 \4 }8 s6 i9 C         sum++;}: d) P6 F2 t2 V; f
     if(sum==M-1)0 N$ \& R0 J, d8 V9 r4 H
        break;
: |  g5 U( v8 ~2 d% H% r1 Q     p=p->next;
; T' m7 u% E' X* P    }2 @* u5 M0 I% k4 g& p0 ?1 E0 b
    p=
: |0 U! F% a4 H    head;" m4 _1 L3 {; x# S' O9 O  A  I
    for(i=1;i<=M;i++)" T' F0 q* P3 Z3 ~/ q) ^& V
    { if(p->flag==1)  \2 o8 ~( L( G6 b. i
        printf("\t%d",p->number);+ Q( {$ v4 X3 J/ T8 K! Q) I
      p=p->next;; d( l" K% B1 i
    }4 G. G4 ]+ b! f  b3 L  Z# b
; w. y, \# f& q7 Y6 D4 B4 Z' K
) E4 }" k) D' I

+ K, s9 @8 B; ?}
0 `8 b3 i/ z2 F, k
第二种方法:数组
+ `; N7 N1 P- j0 C% H4 z#include<stdio.h>, V) j, S9 x/ V. \/ Z( A
#define M 88 F; N2 c1 r: {7 N
struct monkey1 k  _; d6 ?: b: J. |$ l$ w& m$ \
{int number;) F5 `+ [  F9 `( H* C4 _; n. J
int nextp;6 q! g% T! f: y7 }' Z' R' e8 q
}link[M+1];
0 ^" U5 k" m; C& v! {
; k! ~# d7 K/ }3 o. q5 `void main()1 s; F/ G) i2 p. U( K4 {4 Q8 W
{int i,count,h;
% [2 g  B! A% A( R3 w9 T0 Zfor(i=1;i<=M;i++)
" ?. l  L; C# s1 a+ X$ W{  if(i==M)
! f/ ?. k* f' I7 R' {" [) O0 G   link[i].nextp=1;
" k$ g" v- D7 L& _" M( B) M   else/ |6 U. C2 b4 ^0 p
   link[i].nextp=i+1;
' a/ O9 O  D5 `  link[i].number=i;6 P* l. m! u/ b# @( Y
}, z: R% g$ u, q6 m1 u( E
printf("\n");
1 \# b/ q8 r) C2 Qcount=0;, n7 K; d/ K. `/ ^! p6 f/ B, ~* b
h=M;
3 z2 C* _9 F6 I( wprintf("依次退出的猴子: \n");5 n2 ~0 c' T2 U: z
while(count<M-1)/ S- x/ ]+ {) {* _) @$ H/ ?# h! Y7 [
{i=0;( m+ }, a  ]/ V3 I
while(i!=3)
4 @1 z# g9 O* [6 F. y{ h=link[h].nextp;1 i/ e% a/ m+ J" C/ H7 |0 L8 Y% M/ w( N
   if(link[h].number)
! G, ]! I9 |) z; B9 V     i++;}. ]# w" f4 S$ l8 [* O1 j
( s! J5 F( W7 T8 p0 V, U4 W- F7 B! d
printf("%4d",link[h].number);
& r) c% i2 |% Q* t" X8 Blink[h].number=0;
& D0 Y4 u1 C1 J4 P4 Qcount++;1 [' T2 I  y$ b  N! I
}
. ^0 f/ [- {$ {5 W0 ?
% r/ M; T0 e6 Z0 l0 }' yprintf("\n大王是:");2 Q4 e& B. ~  Q' }/ U6 \7 p
  for(i=1;i<=M;i++)9 c7 {/ _& D3 q$ N8 C3 E
  if(link[i].number)
  y0 J5 ?6 {- y  d8 |, Z: i+ j' I    printf("%3d\n",link[i].number);
  z: s4 H) K: n% j
' R  Y/ ?2 T: a6 O
$ L4 P2 P) C% n3 z& \/ c9 `}

% _) z% W' N4 x( X) G) @+ h第三种是普通方法for循环
: L$ w' a& b8 k
#include<stdio.h>
4 W$ x& S0 A9 cvoid main()# i& f3 ~/ I7 Y$ f2 K% B
{ int i,k,m,n,num[50],q,*p;
' U/ W/ Y6 ]# t! J( r    clrscr();  h8 K2 q5 a% k+ B6 [
   printf("input number of person: n=");
2 k/ G/ N( r% }2 r4 i5 u# q    scanf("%d",&n);- E$ r+ ?. l0 @1 `& F
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只# ~* O+ E+ n7 }
    scanf("%d",&q);
) r+ L) x) `0 \0 g, B( J: _   p=num;
1 _% n7 i1 I3 v/ }2 \  for(i=0;i<n;i++)
; d- ?; _  Z/ J5 _% V1 q4 ~    *(p+i)=i+1;
% X  R0 l/ O1 m( G" W' I  w   i=0;: i4 \! C- {. e5 _' c& X
   k=0;; m% T+ h: [' P2 f. ?, R1 U
   m=0;/ @3 Y7 Q2 Y9 L" y! h" j  Y
  while(m<n-1)( v  c/ D( Y3 @; c3 o' u9 E
   {if(*(p+i)!=0) k++;
( Q4 r. }/ r, ~, L3 l" Q) e     if(k==q). C1 S- d" w" v% m  C
      { *(p+i)=0;  t8 l' h2 d5 ~& C9 s
        k=0;
- Q: ?) A) c4 D        m++;, r2 A3 l. k4 O# S0 R+ l
      }2 Y9 P( B( K: ~- S1 R- i  B
    i++;' C0 _" R7 @' Y
    if(i==n)i=0;
* E4 X5 H1 g/ B9 ?* P4 g4 U   }4 t. f0 H% a! F& f; x$ v8 P: M# f/ Z
  while(*p==0)p++;
% ]: w3 W( Z8 t; w9 z# b6 V    printf("The last one is NO:%d\n",*p);5 q- r% ]" b! v! H1 Q
     getch();
& L' \+ f/ R3 W: A- ^5 K$ C$ u+ n0 q2 ]: w# T8 c
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;, [# {* j9 x: U+ L9 R7 ]  w
namespace 又费马达又费电
$ T) V6 n5 g8 j4 [' a{- T! s, }9 o4 k+ [/ F' N
    class Program2 f5 J' \2 D$ y
    {1 [& I* c% I# `
        static void Main(string[] args)
" H+ L% G/ X# f. j& F        {
. J$ f% ]$ T/ J$ Z" `& L- E1 U3 x( x            int m, n;& Q+ t( ?& j5 V$ l
            Console.WriteLine("请输入数组长度");0 P* F! g; y* b2 |; N& A% I  j
            m = int.Parse(Console.ReadLine());//m为数组的大小
" G$ t2 c) S0 F, c0 Z            Console.WriteLine("请输入要截取数字的大小");
5 ?3 @- G4 K0 E5 D+ W            n = int.Parse(Console.ReadLine());8 y( x- T- A# e  A* k: J, `* a
            int [] numw=new int
( ~% q6 d9 K- a6 T8 B+ z- d/ K- q9 E. l/ o  @4 i, B: S5 [
&shy;&shy;&shy;;
/ O$ g4 u! J: G" v            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数% N; I& j6 L" H- l2 m0 X  p
            {
& W( p" Y/ j6 H                numw[j - 1] = j;
. \( H6 Z6 j# W# V9 f3 b            }
% w: Q9 a+ @/ d1 a' D            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!& V- s  \0 _/ m: j
            while (d != m - 1)& j8 w* e# m8 n$ C3 ~; C
            {
/ [% g6 g; A8 a& |0 h                if (i == m && d != m - 1)" q( x' m2 l  ]! t0 @( O$ r" p
                {' J- K8 ]6 F. _$ |
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
( Q7 U0 @/ C3 n) x/ H$ p                    continue;/ Y) w1 ^1 l# m! y! t
                }
6 J# L7 L* j1 F                else
2 j' S' C+ j2 Q0 ^3 h, h  N! `1 W                {  V$ Y3 I7 d" v8 I; z2 F9 `! L9 `
                    if (numw[i] != 0)6 `9 W; |9 m1 M4 ~  M3 E' l
                    {
4 @$ a4 F! J- o0 O: ~8 {+ C; Z( ^: Q                        i++;% T5 w- {( S5 ?. Z) A/ ~/ R
                        k++;8 b8 G5 S# y+ g. t8 U
                        if (k == n); R; U" A9 e; g
                        {
9 U7 i4 T/ h% C, b                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
  i# z- J/ D0 P+ Z) L: V                            k = 0;
- t, B# o# I% N) i7 A, u1 f              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小15 a$ G' v# g" b2 G4 _4 y
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);# F# Y1 w" O4 D
                        }$ }6 |3 w  k: N3 k
                        else//输出暂时还没有改变数组元素的值
4 L: I2 u+ _6 y! g                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);5 q; |/ S8 L( n/ E8 P! f
                    }+ ], c. n4 Y" M( u% ~& z  N$ `
                    else
( |$ s' R' Z& n                        i++;//数组元素为0,直接跳过,不计数。。。
. J$ T5 k' I: t! y3 H6 Q1 K& f1 |. X7 k                }
- D( R7 ]. b9 F8 x ) I- |  Y# R  b' ?# U
# T7 A# }6 u& |; E' \. o
            }//结束while循环
& I" ~6 s4 E* E0 i, X9 O7 x8 t            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦  E+ n6 }: h, R0 q- ^( s/ X
           
' P. W! f8 t( G. Y2 @% o4 @                if (numw[i] != 0)% ]0 _: m2 {- Z3 \( z% ~/ ~
                    Console.WriteLine(numw[i]);8 w. d5 p7 C0 K, R4 s% [
           / b! \& G( h1 X+ z: N+ V" d+ J3 h6 F% `5 `
            Console.ReadLine();* m6 p7 E9 H+ a5 a6 t. x0 s6 ?  `
        }
. E: i0 M: L6 O: j& o! ^    }3 T" r: w; I5 Y- `
}
. o; R. `6 d' i: F6 A6 \
小甲鱼最新课程 -> 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-4-8 02:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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