鱼C论坛

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

猴子问题

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

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

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

x
大家好!
: M3 b- w7 c  l( ^5 t5 Q. l这几天我在忙着编一个问题,我用了一种方法编出来!
3 B  \7 y, D6 e; t" a3 z& ^) ~但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
/ o$ C0 e, _4 O5 V3 Q注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
  I; p. c9 p0 U7 J4 E% H% ]; U1 q- S: U; X

) S8 J5 C$ ^4 s) h3 L$ S3 z
                            题目$ b* U7 Q( I4 a1 w' g
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
6 |( H2 R0 V& p第一种方法:利用循环链表
+ k" j# Q& E" A. h0 p+ C& a#include<stdio.h>
- s1 B" N7 e* n+ p6 Y- K#include<malloc.h>
+ S% z3 }& D- c* t; n% \& x7 {$ |+ \#define M 8            //共有8只猴子
& p! w4 W( Z% y! c- U. m8 U#define N 3            //数到3只时退出第三只# Z6 x  x, ^1 D
typedef struct monkey) a% O7 g6 _2 w- k/ Q
{int number;1 j- n$ y0 y  i8 @% W  \: Y
int flag;
8 S: K7 b' j& l( w" H6 I; J) E% I6 H8 @struct monkey* next;
1 L2 E9 h' M! A3 O$ S}MONKEY;
, a6 h' K" I/ }: u9 i  Y# Wmain()
; [/ N- r# x+ M- A+ Q{ MONKEY *head=NULL,*p,*s;
. h2 M; `1 P( ~+ n3 J  int i,sum=0,count=0;
1 L4 ^/ C8 t2 _; v. `* m  clrscr();              //清屏/ _! M! N  V  U$ S& g
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存% p: k. m4 v) ^- {
  p->number=1;p->flag=1;$ I! k& [( k2 o! F7 v* y) o
  p->next=head;, M5 b  z3 e0 E8 Y. y. T
  head=p;
" x, c0 \3 O* E  for(i=2;i<=M;i++)
% M: U: }- {  W7 S5 T% m    { s=(MONKEY *)malloc(sizeof(MONKEY));
3 l0 f+ e/ b* t, `5 Q9 k# v/ O- D9 P     s->number=i;s->flag=1;) B0 }5 k8 G1 G  p- [* k
     s->next=head;
0 A  d' t3 ?+ N- [, T/ ~8 ~+ M     p->next=s;p=p->next;
& F' A# |, ^8 M- F8 T- Y    }
. t7 g  z( K0 \# z. u- F    p=head;
1 ^0 u  o. S* E9 G   for(;;)
. _6 A" k8 S% p    {if(p->flag==1)
* O7 L; a0 K6 Q! f. i       count++;6 N! Z3 t2 S" K# d+ t
     if(count==N)
, i5 Z6 l- ^9 c        {p->flag=0;) E. |! j4 B/ c- ]
         count=0;
, }3 n! x$ \, x+ t         sum++;}& J( g. ?. y& a7 b: Q
     if(sum==M-1)# r. B6 Q; T' j; l( v2 }
        break;6 d* Q9 v, Z' X! f& a
     p=p->next;
& K" n& P# T$ x! @    }% ^* R3 D  ~4 p4 G
    p=" c$ s' j  E: L9 N& C1 v7 b" D
    head;. s0 L9 g( C' x4 f
    for(i=1;i<=M;i++)
) ?# o0 Q% P# u. _* q9 O    { if(p->flag==1); I) n3 b7 A% I' P5 ?8 L6 S
        printf("\t%d",p->number);
# O+ [8 B+ _1 a& @; E( ~1 |      p=p->next;+ @( L" j3 H4 M+ J" M  {% B+ B
    }
, U, n9 `1 P6 U, k7 {  t; X3 P+ T  J7 j" [6 n% T" b
; `4 h% O6 H" h& C
6 ]6 m% K$ F# u* E& m8 w: W
}

1 @4 }+ a8 B( S5 O第二种方法:数组# H/ A" O' \7 j1 g7 J9 M
#include<stdio.h>
3 Q8 W5 x. W9 |" e, {#define M 84 \# i/ x# n$ }5 G! Y  p" w
struct monkey" v) Y( j$ V: J1 ^. u
{int number;1 O( C4 s; `$ {0 e! B  G
int nextp;/ i+ k/ [) V# `6 n
}link[M+1];& S# T8 f5 I2 ?1 j; w2 R  A
1 ]' u# b' ^+ K$ ^8 D
void main()4 J( ~% ~( d) t5 m0 ]3 N
{int i,count,h;- U: U7 [! L! J) a, u
for(i=1;i<=M;i++)) C, j, ?6 L4 M4 ?# S
{  if(i==M), ^' y1 j; ]/ S' C
   link[i].nextp=1;
5 X# t8 }6 ~( z) x+ ~; g   else
2 ?  E; p. T$ c, l! @# {   link[i].nextp=i+1;
6 X/ F8 S0 B) B- {  link[i].number=i;
! j" [5 T! v$ z}
/ B: E6 j; @2 K3 {$ {1 wprintf("\n");6 Q+ U% Q5 h8 q' j& }
count=0;
. e9 ~4 F) L2 l/ D6 qh=M;# \5 O9 x" B' n! \2 Q
printf("依次退出的猴子: \n");9 A# q  s( u+ s. m# `+ a
while(count<M-1)
) M6 j8 Z" _9 B2 [- C2 [; P{i=0;: i2 I, W+ `: D$ M
while(i!=3)
4 ~/ o8 a+ p  [{ h=link[h].nextp;
) Z! `" n- N4 J4 p- w! Q2 q- [  [   if(link[h].number)
$ C1 H7 n6 O# o! ]0 \3 [: x8 G     i++;}
7 N: f  N4 p2 W( d) w. h& s, c) `5 g, S+ v1 x) R5 u
printf("%4d",link[h].number);
- H4 [" Y, ]) L, S+ D6 n. k/ X4 Blink[h].number=0;
" _$ G+ F' G1 Jcount++;  H. x$ U! {5 K' f! R" G
}1 a, S! w' h- @$ b# S3 }

( \6 O  ^5 D" J0 B. |) I$ G+ [printf("\n大王是:");- t: [, d; F& c5 `. y% f
  for(i=1;i<=M;i++)
  m* T( K) v4 j  if(link[i].number)/ N. n( Q4 |% r. e2 g3 w) q
    printf("%3d\n",link[i].number);0 v. b: R* r, Z1 ^. l6 j
- d" ?# h7 A1 q( n
7 @3 V  X0 o+ Z+ j( m8 z9 R
}

+ D$ p  b  Y" G; O% \  P2 [7 r; P第三种是普通方法for循环
3 S2 v% k7 q8 I7 x" }
#include<stdio.h>
8 b) M0 E; J6 y; }) o/ V- ovoid main()
. m. Y. y; s! W5 n# R. ?& N& }{ int i,k,m,n,num[50],q,*p;5 Y0 K& X, m! f
    clrscr();
( P+ y& K% g: \" y   printf("input number of person: n=");8 {) d/ ^1 Q, _6 T7 R! F2 U7 U) u
    scanf("%d",&n);. j5 w: t; e; ]7 |, M& l3 ^6 S0 y
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只2 C5 ]$ O& x0 a3 f( O. J8 w
    scanf("%d",&q);
+ E7 L5 T  ^7 M4 f1 D! }, i  Y3 s   p=num;$ r& d8 G) U" _1 A: Q
  for(i=0;i<n;i++)& S5 W/ i2 K$ l$ ?
    *(p+i)=i+1;
5 s4 N# z  K& ~! j3 m5 ~9 p   i=0;. S$ v$ g7 D% L. F4 T
   k=0;( h/ k9 x' s! h) w) R
   m=0;
, b& c) Z0 V6 B* O5 e4 l( ?  while(m<n-1)7 C) U- Y4 l5 S, F/ G, d
   {if(*(p+i)!=0) k++;
' i" K- \% T6 ?% i; T     if(k==q)2 Z, Z. S! P1 x3 X0 `
      { *(p+i)=0;
0 d+ l  n" `5 {/ @+ L+ W# b        k=0;1 O( R/ B; [. d  L
        m++;/ q. W2 V) v: q6 K0 [
      }" q/ p. u! i, I0 e% D- E  s; L
    i++;3 u& N4 Q1 @  M1 N: v: S
    if(i==n)i=0;
8 F3 e  H2 t& B# a   }
* i, x! g' F" A9 }7 z8 L* g6 N  while(*p==0)p++;
( c2 ?5 P( u# H) c8 s# O8 |    printf("The last one is NO:%d\n",*p);
5 S3 m/ @8 r% f, A3 @: O     getch();
$ w' L. g6 L' j/ A. P) O0 P
2 H- u( `$ ^# o6 n}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
' O4 j  A) T/ ~/ Xnamespace 又费马达又费电
/ f6 {8 r% ?! Y$ e$ Z, T4 T# z{6 n/ C/ q: z8 e3 @8 j; X2 ^
    class Program
$ k2 H* L8 J' A1 e1 G* p3 _    {, U( Q/ ~+ z' v4 K
        static void Main(string[] args)
6 [0 B, m0 g1 c        {' \+ Y8 a3 t9 T) U* E
            int m, n;3 I) g5 L4 B! A9 e3 R2 b
            Console.WriteLine("请输入数组长度");
% b! N8 s! O, f4 K/ j            m = int.Parse(Console.ReadLine());//m为数组的大小
: T# [+ v' r1 n/ b3 I9 D            Console.WriteLine("请输入要截取数字的大小");
$ c# x& M" ?8 y1 m$ g: ]            n = int.Parse(Console.ReadLine());- s/ g3 d0 D7 a$ b; c
            int [] numw=new int* @; v& S6 m, u
! t4 P$ D9 @( |$ F% f( R
&shy;&shy;&shy;;
) D2 h. |8 M6 R! @) R) [            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数* E0 }) a! `$ `8 q. l  z
            {+ A9 b8 K4 g  u$ r) N) f" r/ n2 N/ R! V
                numw[j - 1] = j;  p# @2 s/ i% e4 W8 o6 I
            }
2 M- e1 t$ f; ^9 {* S5 s            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
* \0 z6 g) u) X; |: q9 T  y            while (d != m - 1)8 E: Q9 B; |- @6 m
            {- D. u  r1 r1 O& t8 j- z" z+ V
                if (i == m && d != m - 1)5 i- H4 a& h; x& l$ {  D
                {
& n% _6 G- L% A5 m) s: u( {                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
0 i" o! x; a4 K" G" X0 a                    continue;5 D; t2 b  R1 J- T  ^5 R
                }
* J& B" s7 L4 z- G! [# V8 }                else. _$ Y) `3 I3 C: B% M& n. ?: d) R
                {5 U& S2 L- f( o% U4 B+ k. ]) t
                    if (numw[i] != 0)
; F& I# N0 G! ]3 j                    {8 _; M  d( L4 L4 N
                        i++;
3 F# b7 y; B' e  v& P                        k++;4 d- G, E/ M" g) J9 h/ {& m3 M! c
                        if (k == n)
, E- |: E/ o$ \) m6 P                        {
( \6 @0 \, W2 C' `0 T5 A* s                            numw[i - 1] = 0;//把在n位置数组元素的值改变了* W! k- U% U2 G
                            k = 0;
, D* i" a8 r) j0 }% r              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小13 h) Q' Z7 J* Y) X# I1 z  S
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);& ^# ?  X( C* z0 V  ~" ?/ X' L
                        }$ S3 B7 M6 f' n& A7 ^
                        else//输出暂时还没有改变数组元素的值
, K9 g& ]; a' \0 j* V: `' \                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);' r0 q- P8 [7 s  l/ H% \
                    }, d; d  ]( `, D) }5 @
                    else! I1 _. D) Q: Z
                        i++;//数组元素为0,直接跳过,不计数。。。
- x. ?3 o% ~$ Z) \/ b, L3 `' g/ S                }
. W0 j3 D% ~2 R - D3 O  w4 i* T4 H8 s6 P
9 F* i6 g, [5 v& P  l
            }//结束while循环: @; t% i/ P6 w
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦& Y- {( n2 \# T6 d
           4 E# y  l  j  o9 O: K$ e9 }
                if (numw[i] != 0); a: @" Y! h* q9 p! r" Z" V' A. B+ u
                    Console.WriteLine(numw[i]);. v, ?9 M& _" b- d) [
           
- \4 \+ {7 E6 Y9 H            Console.ReadLine();
8 B. q$ G+ B, [7 ]: y" |+ t0 t        }2 q& @6 _& ]7 a8 |( o
    }
/ b( u0 i( C9 p. x' W. D4 z}
5 X% ?& _$ Y; q( s. R
小甲鱼最新课程 -> 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-6 00:02

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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