鱼C论坛

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

猴子问题

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

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

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

x
大家好!& c7 ~$ j0 g0 m- e/ X' R' e/ S5 r$ \
这几天我在忙着编一个问题,我用了一种方法编出来!
( l, Y9 {% m2 A$ E但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!2 f( K2 h3 W) {+ Y$ V' O# Q  a
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 + q; x/ @& I7 ^5 C5 {' x
8 ]( Y1 T" ?& i2 X& g
4 U. d# a1 n2 |  S+ q1 a
                            题目
. G# u; i" Z; Z3 G; n. K山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。8 q9 y5 a, |" a0 a7 y+ C
第一种方法:利用循环链表6 p" q5 f8 a6 f% s3 `
#include<stdio.h>
8 t8 {# M+ t3 s( b5 i/ G#include<malloc.h>' P  o. f5 J+ J- [8 Z/ d
#define M 8            //共有8只猴子3 ?2 D, ?  J; ]9 _/ b5 z  b3 L
#define N 3            //数到3只时退出第三只
2 h* g4 j( Z6 Wtypedef struct monkey
! r. x' P$ e* H2 U8 T0 l{int number;
; t. X" p% X' m) i& yint flag;( L4 `- g) e5 x1 b1 G  `8 k
struct monkey* next;5 N: C& s- z; n. y% N2 m
}MONKEY;0 [/ [; r9 i) f
main()
, v$ I. d7 U9 U; g7 ~/ n{ MONKEY *head=NULL,*p,*s;) {9 ~% L) Y9 ^+ L
  int i,sum=0,count=0;" W3 g9 U5 }, N/ N
  clrscr();              //清屏5 J# c) M  A5 j
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存5 G' P% h# I* G' _
  p->number=1;p->flag=1;
2 W! B$ o4 o9 ^, J; V# T7 I  p->next=head;4 k4 s% {) x6 ~$ U- X6 s
  head=p;- N6 P4 N. q2 N
  for(i=2;i<=M;i++)
; Y: J2 L# _: ~    { s=(MONKEY *)malloc(sizeof(MONKEY));( M: J! x5 A3 u  g5 w
     s->number=i;s->flag=1;# w/ L( W- j5 g& ?
     s->next=head;+ q& i: A; g% q. `( u  ]
     p->next=s;p=p->next;5 [( o5 A1 j( J, l, r
    }5 G% N& T- I; ?, {1 q2 |# f$ S6 P; U0 Y
    p=head;! ^2 B) V" z) [+ Q0 r7 B3 l+ g
   for(;;)
, m5 @4 _5 I: O0 K, |. X    {if(p->flag==1)
* q) r3 m- b* ~+ I3 L       count++;
& P# E( c0 b& {) w$ {( g     if(count==N)
  e7 v2 M5 x0 M6 a        {p->flag=0;9 u$ y* W# {$ B, U& ]+ B3 h
         count=0;3 g, {6 T8 s8 R
         sum++;}5 L( \( ?9 B; e  |0 U7 ^3 B0 e
     if(sum==M-1)' O5 v. Z& Z+ i2 \+ k1 S* O
        break;2 q5 D& J+ e: T3 }. q  L# Q
     p=p->next;- I) F7 r1 g4 V+ H
    }. a+ Y9 C0 |( F- E4 E  l+ f
    p=
: S- Y8 i% [1 L2 d( W/ N" W    head;
& m' I! E- A: u  ~- w5 X) ]    for(i=1;i<=M;i++)
- l* u% {: N+ K. e7 V  F    { if(p->flag==1)
; @3 R; l. O- R9 f+ A8 k        printf("\t%d",p->number);
+ X9 n: U( v5 r* f9 A/ \4 _      p=p->next;+ s; W+ f  N/ m1 G0 O% [
    }& Z/ N4 t/ \* \$ Q& @& }; s
" `- N! I' `) d5 K' H- @( _
1 m4 q, m3 `, I& T7 w' i

  `, _6 z* a- e# j}

7 [) `4 y1 |- W7 b  z第二种方法:数组
. i7 t9 ^/ E4 d: m% c4 Z#include<stdio.h>  S: b+ `& W0 b1 y% |( _
#define M 8
+ R/ C0 J$ @: S8 Kstruct monkey
6 B# b  ^2 J# i7 C6 J+ S+ R% ~0 o{int number;
& {' i* P) G; Mint nextp;* D( A& [' {! ^: W& z" q4 q8 z  Y$ Z
}link[M+1];
4 g" ?$ \8 i- ^. I5 v( Y# d8 Y7 ~% j( \0 \: t' L
void main()# S( Q! m) N2 ~3 k0 @
{int i,count,h;
  }+ T8 i4 m' u& [& j" Ffor(i=1;i<=M;i++)1 w9 N$ w. B. E. S: A
{  if(i==M)" q0 k  U# X) s0 m$ `
   link[i].nextp=1;3 }+ Q' r9 y- [; K
   else3 A$ P" e3 V- y; b7 d
   link[i].nextp=i+1;* }" o$ e4 V$ p) r) w0 y) I4 r
  link[i].number=i;
& @# n, `1 N2 ^7 p6 O}
6 E3 T$ E7 J4 r4 j  V7 Yprintf("\n");% ~5 ]' v2 p3 ^( {
count=0;! ?$ G# D9 l1 [$ U
h=M;
9 n& m# l6 b  _# dprintf("依次退出的猴子: \n");2 |  ^. v2 K6 c/ B" s7 p4 ?
while(count<M-1)8 ~9 G" c7 R3 H' G" q
{i=0;% y) o( F& A8 o3 X* r' N' Z6 B
while(i!=3)7 `+ f. }/ U/ _, {. @
{ h=link[h].nextp;
2 _" O# j7 m9 V# D2 Q   if(link[h].number)
: P7 D/ P# ?0 w7 {6 i     i++;}
- P7 v  q0 @) R# T4 N- h, M/ E* ?9 ^, ~) Y5 u5 O4 E: ^
printf("%4d",link[h].number);( G; h% D! L2 N+ r; O
link[h].number=0;
/ L9 p% f* Q1 Gcount++;8 w! ~( i2 O; S( C% G! K
}0 @( C/ k9 W# C+ n# |: B
% k5 y2 m, p) G1 _0 B
printf("\n大王是:");6 k% }) {& x/ d, D$ J& n& i
  for(i=1;i<=M;i++)
+ U) I& \9 c( [5 O9 ~# g3 M  if(link[i].number)" ]8 N9 }& M$ r1 j
    printf("%3d\n",link[i].number);( A! L8 t# y- T. h( V

" m/ i9 _" N% \) c+ G1 |
- {- Z7 q" k/ j7 b* n4 V5 L- D}
3 N6 u0 L4 \1 h$ {. l7 E. ?
第三种是普通方法for循环
) @: y& @8 n$ ]: }2 F) h
#include<stdio.h>4 |3 p) x1 l' f5 e' U1 k8 ?
void main()
5 u$ Y3 [8 Y9 i6 m5 z) L7 d{ int i,k,m,n,num[50],q,*p;
' c1 C% x2 m# X9 v    clrscr();+ `3 l* l/ G: A0 g: {6 a- M* m
   printf("input number of person: n=");9 R+ [; N' h3 ^+ O+ ?
    scanf("%d",&n);
: Q% ~; \! ]* z& _- T$ jprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 s& }4 t" o0 p; z    scanf("%d",&q);* Q7 q6 r/ ]7 O7 E# M
   p=num;
4 V) y) C: A' H  for(i=0;i<n;i++)1 u( F% h. {- Y- ]7 O6 {6 T$ n
    *(p+i)=i+1;! W0 ]) F, K, d; ~7 h1 w& @* S
   i=0;0 o. M' L) t$ I
   k=0;
9 q2 ~( X# Q0 ?) f4 Z6 A4 D   m=0;
7 a# i5 e1 x8 H7 f  r8 J  while(m<n-1)
; ^! I" m) C! D6 C   {if(*(p+i)!=0) k++;
% z" K9 o6 _" d& A+ j& H5 |/ {3 E     if(k==q)
: ~" Q8 p* D: a$ C      { *(p+i)=0;
) Z: W5 t% d+ w        k=0;5 X* M& W) y. }; E5 h1 I. L
        m++;
' {( y$ T# N9 Z9 B2 s9 A# D      }
: k7 T- }5 ]' ]$ f6 G$ {9 [    i++;
* l; {1 S1 m  A' d% L& O& S# M. Q1 D    if(i==n)i=0;$ ?. y& [, \8 M6 N
   }5 D% Z' w; e# |% V+ ]" l' d
  while(*p==0)p++;
. |2 e& D+ ?' R& k8 o, p  u    printf("The last one is NO:%d\n",*p);
1 E5 c" ], W* i7 k4 N4 E, n3 {     getch();$ q/ q7 ^! V6 C" b  ~9 n2 g

* C+ @( |+ F; o6 c0 ?1 k9 T}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;6 c  S+ I3 [. }: p
namespace 又费马达又费电
9 t! e( ^: E0 _1 \* \! b{7 ]+ ^8 `$ S( P2 p  b+ H; N1 g
    class Program' Q  P7 u* z* S* p, W
    {
* K3 Q, r# E6 ~$ H        static void Main(string[] args), {: X, L3 R3 k
        {
; O" ?4 j; A3 g. D! t" |            int m, n;) ]5 B( p/ \9 |% T& V
            Console.WriteLine("请输入数组长度");
( R2 C( ~, _& r+ _            m = int.Parse(Console.ReadLine());//m为数组的大小$ {0 B  t+ V. H  W9 p) b: A9 O
            Console.WriteLine("请输入要截取数字的大小");0 u& a8 B- n3 I' N( p* q9 i: L
            n = int.Parse(Console.ReadLine());2 d& F8 D/ H6 ^4 G/ q' j2 u
            int [] numw=new int
" R( e' u, h7 ^: Y8 Z9 `
* E: Q% j% @0 j; W. }6 G: Y" V# ^&shy;&shy;&shy;;, Y0 N- [! W* ?+ c7 h7 Y
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
" F; x& H9 l1 }  L# l            {* `; f; ^- k  c- [( k) X; p" }
                numw[j - 1] = j;
( Q% j( O+ S9 j; Z, q            }* V: z* K; _( ^6 @9 m; }! R
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!+ j/ i7 h* u+ z8 Y
            while (d != m - 1)
% c. R3 n2 f/ |            {
! i( o" P, Y+ Y9 C                if (i == m && d != m - 1). L& D* |4 {  G+ f6 c
                {
3 ]: r" s% ~, t* d" e: Y8 b                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
, \) a7 v1 e, h0 H" _( n" i                    continue;8 c! y& v! e9 L7 m( s6 M! f2 j% @
                }' |0 L* p9 t$ h2 W: R
                else
$ K! ^+ I( S* P: Y# ^7 G# B                {
0 [4 G! A# K( n, J" R7 |$ w                    if (numw[i] != 0)' K# O4 c1 k1 H% C# e  g5 b
                    {' D1 `6 q$ z' ^
                        i++;4 L9 a) p  u: U4 V
                        k++;; j+ b0 a5 a# H& l; ^
                        if (k == n)- t6 F) ^1 O- f. V$ X1 M1 C$ T9 l8 G
                        {4 |" W, g" a  A& {* g
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了- ~) W; N: s' ~8 y5 C
                            k = 0;
& G- L, Q1 n: ^, T! \1 W" u              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1; c% |. M4 y% ^" X
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
- |9 n7 q3 R* h4 u8 v& U( i                        }
; ]1 G$ `4 w- i5 \" j$ U) l1 E                        else//输出暂时还没有改变数组元素的值) e) d* Z9 ]% b  R* @
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, }0 W, d1 R3 z. o4 i                    }6 u1 w2 ~5 z$ G( D$ v3 p
                    else; P/ X3 K3 f5 A4 r
                        i++;//数组元素为0,直接跳过,不计数。。。
0 P) R+ k1 A( q                }
6 i* R. Y) ?4 [3 x& W; L : P% D  N# W% [* W
8 @5 n: J6 c* ?" j
            }//结束while循环
' D- h2 R) l2 d- c8 H            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
7 h! ]. j5 c% X' J/ Z           $ z4 Y" ]* j2 t  w) A
                if (numw[i] != 0)
$ }* @" U3 R# p. \/ A3 n                    Console.WriteLine(numw[i]);( r( }2 E$ S7 t
           
3 s) n8 p/ H& Y0 w8 v& N3 @            Console.ReadLine();, L9 l: t& a' `
        }6 j2 W5 d# |9 M1 u" d5 x
    }
6 S8 X/ W" E) Q+ W  b}
+ W9 f7 L9 x, \  E1 l# G" i, d
小甲鱼最新课程 -> 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-24 11:37

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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