鱼C论坛

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

猴子问题

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

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

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

x
大家好!0 Q/ X' j4 m5 A( z( x
这几天我在忙着编一个问题,我用了一种方法编出来!9 r: A) M2 V0 y  F2 i
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!9 \( ~. d4 N1 o' d: r* R9 A
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
- `, A3 o0 p! ]0 y5 t, `
" x+ a6 r2 U' B! j* s' t
0 J, [8 K( c; M8 }$ c
                            题目" W; ?+ `2 i; j2 C2 }! N
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
  V5 j- a- `! J) J0 w( D第一种方法:利用循环链表
) h1 _3 E7 K/ K8 O( [% k+ J4 L: t#include<stdio.h># F; O$ J& E, M
#include<malloc.h>0 m) W6 b& j2 m+ m/ {  Y
#define M 8            //共有8只猴子
* u! ^! \" L& r# d* x#define N 3            //数到3只时退出第三只
: z( K" P+ ^1 U- ^% \9 g$ n9 otypedef struct monkey& _. Z- Z9 ]3 S% X9 k/ o# s
{int number;
6 j/ t! g+ K6 L$ B* f" ?7 wint flag;3 z6 N1 [& S$ W$ t
struct monkey* next;  Q8 b  ~/ |' ^$ c5 n% z
}MONKEY;' |& x  Q3 P0 v& h* _0 n
main()
$ V) a& p+ ]  O, F) ^{ MONKEY *head=NULL,*p,*s;. b8 {& J; L+ z7 T
  int i,sum=0,count=0;0 L$ y$ M% U4 B
  clrscr();              //清屏
4 u" c) @! Z, b* v5 ^  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
0 B/ i; S' F2 B0 @: |" n  p->number=1;p->flag=1;
0 t: M3 Q  q( P! x' E( n  p->next=head;. |, V. H& i3 {# g2 z8 q8 T* M
  head=p;3 I/ W; d- G5 u& j
  for(i=2;i<=M;i++)
9 c9 e: o+ h6 Q    { s=(MONKEY *)malloc(sizeof(MONKEY));+ j4 N( |+ g/ x
     s->number=i;s->flag=1;
4 j% w0 B7 x' d     s->next=head;6 d0 ]4 N( L8 @* m; G0 q
     p->next=s;p=p->next;
- N% Z+ y. _" `1 [, L  t    }# I! A& H4 L$ N- c3 P( {' }
    p=head;
, b* o; w, x9 P7 B3 o- {4 F   for(;;)3 C" R0 }6 c5 N- I
    {if(p->flag==1)( M' ~! L+ a% z+ Z4 H
       count++;: ?8 @: \% S. A/ y1 T
     if(count==N)* }1 w4 m5 s- f
        {p->flag=0;
: K( ?* {) g: `2 \4 Z1 T0 O9 L         count=0;
: g+ c" K& e2 o& _8 S* ?1 q7 }  S         sum++;}# O3 X+ l% }) ^9 j
     if(sum==M-1)
' Z! G! I3 |) i, l( G9 ^, R5 j        break;8 ]- h" ~7 v2 ^
     p=p->next;, g) {% f" Z% o2 ^+ Y, X) [
    }4 D* _8 Y' F  Y' _
    p=1 R6 v3 T7 `. L. V3 c* s; J0 V
    head;& W/ I0 Y2 B" ?" R
    for(i=1;i<=M;i++)$ w! F2 {3 i# N3 i$ d. x; S
    { if(p->flag==1)
4 e. L( t8 m% d' K7 ~* x        printf("\t%d",p->number);- d; R9 D, H8 F8 p4 k
      p=p->next;
' V1 y5 G4 I$ C    }
" G/ q1 X" e9 b; s
, J% V) F" A: G. g! k8 C/ z, I2 ^  q* j) z. a1 P. _
  N4 y1 u" f! R# B3 @
}
; x" R8 Y: d. ~% D8 K, ~$ C  @
第二种方法:数组
, E$ Y" s) o) {0 H) w& s2 Q#include<stdio.h>
1 |9 g1 K( Q; M6 a  O#define M 8
( k0 N. X7 D  {! u. e% Cstruct monkey
. S$ Z% A! J8 l5 B{int number;
. i, L; J: a2 M- z- m5 ?: m% p# fint nextp;" s4 J) R. R- D1 N& a' T/ ~
}link[M+1];
: V& [+ D/ V$ W5 G) n6 V7 q6 g4 n6 {! g& F7 T
void main()" V/ _7 y. U# ~3 Z
{int i,count,h;
6 q. g7 O& J- P5 Dfor(i=1;i<=M;i++)4 `. _8 q" s: P6 f. Y4 K  i- Q/ O
{  if(i==M)
' T& i2 V, ^0 F2 R7 f" T   link[i].nextp=1;$ o. a/ g7 A& L$ w
   else% Q8 U7 N( g% x6 k' x  L# o
   link[i].nextp=i+1;
/ q& F% D6 _8 t& g% @  link[i].number=i;. }( s* k% W' t4 C& ~% x, E0 x
}4 x& z/ p. `  @
printf("\n");1 @  R. ^/ Z3 j1 H9 h+ n" n3 e
count=0;
2 C! x- J' v4 [7 ah=M;5 c/ F5 I, D) R, M# `% |+ Z9 r
printf("依次退出的猴子: \n");
4 f4 \  s" c4 C7 K+ j7 bwhile(count<M-1)! ]- O; |6 I5 P7 c9 r
{i=0;0 s$ S4 `$ R2 M" A
while(i!=3)- k7 D) H' v9 i  Y+ S6 N
{ h=link[h].nextp;  w- @/ u* m& o/ D7 r2 z4 F5 T$ B  p
   if(link[h].number)1 g+ B; T3 t. M$ E& j
     i++;}' B7 s- D$ N4 a. U
  Q$ `. N) x. |5 Y
printf("%4d",link[h].number);4 q8 Y6 X: D/ V* \$ \& G
link[h].number=0;  T6 U! L1 _; c, x4 @
count++;
' I& o. g! x2 U6 p* J: P3 m- e4 A}, i$ l. J. t5 Y8 S" f5 }' D
6 ]4 _+ p9 N' w7 y: u+ w* p
printf("\n大王是:");7 [  Z+ x0 N$ |& W9 }  |9 z7 Q
  for(i=1;i<=M;i++)  @/ w0 g9 j* F, h0 O  Q
  if(link[i].number)
4 N( M% o4 ^: g' [: d5 D- P9 X    printf("%3d\n",link[i].number);( R; ~# `) f! c
5 H0 H, g9 k% v& N' ^% u5 U) r) O

7 J) i% ^) q6 `}
& D# n. k) l2 s. U  }4 v8 Z
第三种是普通方法for循环

, T$ X6 ~7 w# W+ A+ P#include<stdio.h>
3 ?: }# x+ y! o1 P. \8 m1 bvoid main()
' ]# s( m$ {  f# Y* s. {8 H{ int i,k,m,n,num[50],q,*p;
2 n$ N; l9 e0 S8 E- W9 k! n) @    clrscr();
. p: K! Q( \- P1 U   printf("input number of person: n=");4 J- t. u9 e" m+ `5 P% d
    scanf("%d",&n);
* B4 `- o7 u7 i: {2 [3 Gprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只: Y% R  b( `. X- W; I# W
    scanf("%d",&q);
4 y8 i9 Q5 n$ g' V3 _# c/ L   p=num;
+ d6 t7 y  N. ~' ~  for(i=0;i<n;i++)
( V: E$ Y" R9 x$ ]' R! L5 ]3 T    *(p+i)=i+1;
' U+ s1 R7 b* |/ o) D1 |4 ?: U   i=0;) p! {' g6 O0 A. c% `: r% i; x- z
   k=0;
) X- B2 z. ?& R9 b7 D' I   m=0;
; j# X# m8 u( e- |+ |$ |. P  while(m<n-1)
) u8 J- I  r1 G9 @   {if(*(p+i)!=0) k++;
3 N9 A& d( h9 v, B5 |' x, F     if(k==q)
4 V0 x; Z6 P; c! g, W( b      { *(p+i)=0;
& B. w2 U3 `/ _9 I8 n8 t& {' S' c        k=0;  E2 c8 l' ^0 L0 L* L  }. `
        m++;
/ u- ?* c4 c; S, Y* i3 |: A      }0 ?) l7 Z: I4 q2 n1 O6 V' K
    i++;9 k. j8 v1 e# G) |. Q
    if(i==n)i=0;
5 G/ P0 e$ e: k( i5 Z9 e   }
$ s+ q7 k1 a" ]+ s5 O* }  @  while(*p==0)p++;$ `9 _5 [' [: A' }
    printf("The last one is NO:%d\n",*p);
5 x; ?& T+ c# c" N& j5 J     getch();
5 G& P# O2 w* P
6 o# {4 P5 O7 E1 R+ ^}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;* p& O3 Z( K' j2 j) j. a" @: `
namespace 又费马达又费电8 r3 i) Z: x# Z& I
{2 z0 S7 J" s# ~0 d: Y5 \
    class Program
% d, e$ \" U* u$ V    {; p: k1 l# J9 I; I  y# o2 ?
        static void Main(string[] args)
2 m2 {; x+ U$ U- E. h& I/ J, _% C- O        {
; S2 Z. U, R+ N1 h            int m, n;+ b6 g! j6 p' Q+ l# j
            Console.WriteLine("请输入数组长度");
3 T) C1 b* B$ C$ Y6 ]! J            m = int.Parse(Console.ReadLine());//m为数组的大小
4 Z% {% E9 q7 a            Console.WriteLine("请输入要截取数字的大小");: N% L; w  ^1 k, a! B0 u8 f7 d
            n = int.Parse(Console.ReadLine());
* L4 a2 V4 C: x9 ]8 ^0 k            int [] numw=new int
- z2 a/ h0 w6 \* |# L3 H! e5 d/ W$ O( W7 Y" t9 }! X3 _
&shy;&shy;&shy;;2 n" W! S$ V8 W+ A2 O# w2 V
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
# i: R( Q, B. s            {
8 A% n( ~0 T: f4 V7 j1 B                numw[j - 1] = j;7 B1 Q' W! x9 }& I7 d+ d* Y
            }
: a* [$ n8 [, w  i% e            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
" k: Y# K! H/ c/ Y$ T9 w            while (d != m - 1)
) [  e7 @3 V0 l            {( M! K( o  h( v0 a3 `8 i. Y0 m  K
                if (i == m && d != m - 1)
4 z6 q+ }  [/ V7 m0 t3 p                {) |1 x: T3 B2 h
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
5 T! \7 @6 G3 o' u2 G                    continue;
$ k2 _  U! |  A, W0 `' Q                }
1 r' Z, L  T+ c6 n                else
! y9 W7 f, ^0 w* M  I                {. o: |9 m! X9 q& }
                    if (numw[i] != 0)) v+ f+ ^3 I+ p4 _! y/ f' Q
                    {
/ n9 L9 P) @2 A- J' ]  G. {5 {  t# ]                        i++;$ n$ ~! J( m/ R) a/ k8 a
                        k++;
/ f% ]: u0 U& V. H- y                        if (k == n)
! z4 L8 p3 v% f7 C9 [' V$ Q                        {
, E4 u; V8 ~; @3 }& G4 [                            numw[i - 1] = 0;//把在n位置数组元素的值改变了4 e5 r0 r/ m! @7 c
                            k = 0;) l* |2 t- |" M# {
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1' V# g- b' N& V, p1 _- W
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
$ `5 [" w& w" N! ^3 K                        }
+ Q9 ~( ]4 U$ E4 ~                        else//输出暂时还没有改变数组元素的值
8 H* Y8 f& D) z) P- Q6 X6 h7 J                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);  J, q$ K; F1 g) Q) w3 J, A
                    }
# N" s8 g3 B6 i4 i- A5 D                    else; V0 M* I+ F+ P# s! L; }# F6 R
                        i++;//数组元素为0,直接跳过,不计数。。。
' t0 P0 _4 ~" y9 R7 ~: T' i2 d                }
4 D1 d; D# N1 ?0 b) o) z+ F) r
+ \1 Z3 t4 N+ r1 R3 ~- g
! v8 a5 s2 @9 y7 @3 r            }//结束while循环
% k6 X8 Z& K  {0 }# L7 n* S            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
1 S8 q; ~. F$ Y4 `' j$ j' q* i% ~           
8 C. L: M: P5 {3 V                if (numw[i] != 0)
  x' B& W- a+ @& K! h                    Console.WriteLine(numw[i]);
$ w0 ?  ]3 }! J" x& E4 g/ n) Y           
0 r. p! y. _2 I+ ]- `  S# |7 c2 V            Console.ReadLine();
5 X6 J9 \- j  J! t+ {        }! B& ?& m, Z& d
    }7 \" o* {2 D0 h* x
}. ^8 `4 O9 {# I/ A) l( s" Q& W; G
小甲鱼最新课程 -> 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, 2025-7-12 17:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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