鱼C论坛

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

猴子问题

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

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

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

x
大家好!
5 p: H& }1 B6 B2 l这几天我在忙着编一个问题,我用了一种方法编出来!  P1 k. Y( z2 e+ v
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ t* F& Q. o' h$ r) o
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
+ Y6 y: b+ Y( y  i  l+ |! M
; {* ^" C( m! N- ?
1 c% t; P% N, w# m% s$ n( {% D
                            题目
9 C) |8 D: D4 H( j" y山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
' k8 H! q$ D9 m; [第一种方法:利用循环链表
* _* N6 M' A6 y* h#include<stdio.h>* \0 d: V0 H9 h, ^1 H
#include<malloc.h>
7 R, b. p$ B: |: {#define M 8            //共有8只猴子0 U9 f) @! \# `) U1 f9 W0 A
#define N 3            //数到3只时退出第三只
/ @. b7 t; }# f4 ~/ E1 M$ ]4 e  Wtypedef struct monkey9 [% D4 L: v7 K3 h
{int number;& V$ k* V7 A9 f4 z4 |
int flag;+ u( k4 l8 t' z
struct monkey* next;
: u0 E) |* G& \8 t2 a}MONKEY;& g- O7 e0 J& E0 S/ O! l
main()
0 e7 x% L: K, p# K/ B{ MONKEY *head=NULL,*p,*s;
) p* ]7 @0 L: A2 Q- B7 e* g) _  int i,sum=0,count=0;
1 i* w  b; X6 I6 ]! I( Z; s% N  clrscr();              //清屏
% V* z0 u7 d9 R* E" {8 u2 R  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
7 J! K, b2 J7 c7 |0 k0 c  p->number=1;p->flag=1;. W5 w9 O- m6 E
  p->next=head;
4 B5 f, D* |% N7 H  head=p;
0 R3 [; N6 f% O5 D! \4 N  for(i=2;i<=M;i++)! G+ z! `$ F1 H6 O( k2 Z, h
    { s=(MONKEY *)malloc(sizeof(MONKEY));: D6 N1 M. I5 W) F. T& [& O2 z
     s->number=i;s->flag=1;, J2 W8 `7 c( A/ s+ Q7 v
     s->next=head;* J+ H' Q, E! A, i4 b
     p->next=s;p=p->next;
9 b) I* e1 H! g1 D! F/ Y8 r" r( `    }
7 c" }" K5 b" I0 }    p=head;6 T- H- B2 r& j" u1 ~
   for(;;)
$ _( o# F1 E0 i, X0 \    {if(p->flag==1)2 j/ V3 [) R" `
       count++;& V4 }7 N* v/ t8 Y0 r
     if(count==N)
" t4 |, a" ^8 n  B        {p->flag=0;5 f. ~$ m* q1 N# p+ n* w4 i
         count=0;# R, V$ j6 \2 {, I" b4 s
         sum++;}9 t3 m. ?" y. i5 r  @$ N' Q
     if(sum==M-1)
8 G" |. k; e1 ]( w        break;' a2 k$ s; ~& H% _& I7 ~/ @
     p=p->next;
8 q5 M1 a. N5 e. T8 b    }
/ a' }" ?" v% ~    p=
7 j8 d5 I/ ]% S: T    head;
& i9 p, u' y* `" w    for(i=1;i<=M;i++)# f* Z/ a+ T6 w" @9 ?3 u# K$ Q
    { if(p->flag==1)
4 B$ K! O( @& m# F& y  Q        printf("\t%d",p->number);  ^) n: z; e- c) t+ Y
      p=p->next;
4 L# [; f9 O4 m( |9 L: Y    }
, V1 z4 _5 V6 C+ f
. C9 d; }: X: ?3 n
# O' _  `9 Q7 M$ B9 g) t
6 `7 ~6 u, Q% d  W9 X: y' d3 Y( ~( Y}

* h" m" |) |# y/ o7 h6 {& S+ r第二种方法:数组0 [/ c* K* j1 }2 ^( T9 I' }6 o7 C6 o
#include<stdio.h>
- b& s1 x1 p' J* q2 o4 A! z#define M 8
+ q* F0 X5 _, x' L& mstruct monkey
4 X( `' s2 X& o" [{int number;
3 g2 T# ]* d# C- e( xint nextp;
3 G* i' l( w/ S+ ]! W" W2 i3 y. F}link[M+1];. R/ P0 @% x9 Z. }2 X. |- Q0 v

, {' N  t5 _; j  |$ w0 evoid main()
- m" P' V3 E7 [+ |* A3 o+ s5 N{int i,count,h;. {$ g& s; K9 o* A* E/ C
for(i=1;i<=M;i++)
: W$ i3 y) T) y8 d: o{  if(i==M)+ Z9 v/ n0 s' ^1 ?. e
   link[i].nextp=1;" t2 ]3 K" L" B2 _
   else
! O- w# F) ~; R   link[i].nextp=i+1;. o1 u2 d+ @5 |; U9 }( _3 _
  link[i].number=i;
8 a4 v) o! R- X}
3 n" H9 y, b; ~2 i2 y6 Dprintf("\n");
" X  {1 ?* y5 @0 l, }5 B2 d8 O8 a( Ocount=0;
( ~5 o6 x3 K# U, F5 L" Rh=M;, |, S1 ^2 Y6 y  H
printf("依次退出的猴子: \n");1 @* E) K8 H6 x" c5 S4 _* Q2 M3 R( P: W
while(count<M-1)1 Y6 o) p2 k* }9 [. L
{i=0;- y% q7 S: w+ p/ \8 ^% }* B
while(i!=3)- D, t2 O. B5 J9 F# D# X% Q
{ h=link[h].nextp;
, S: V( R# ^0 D1 }) \   if(link[h].number)
% X% Y- l; h4 _) n, L     i++;}" p5 g- ~. Y8 A+ q, T

+ W! ^4 K- P5 Uprintf("%4d",link[h].number);
/ c1 h  y8 I* ^link[h].number=0;
1 [' M! g/ V. ~3 {  vcount++;" |$ {; W9 n/ k3 E: _& {
}
% w! ~7 v- Z$ X9 D2 Q/ f5 ]: a% R: X, {6 N8 p
printf("\n大王是:");
% o0 N- J3 K  h4 ^) J% X  for(i=1;i<=M;i++)" K) l/ p; H& u% H* G
  if(link[i].number)3 a: {) y( ~+ Y; P& z, o& ~
    printf("%3d\n",link[i].number);" r  m. g1 M: t# ?& i

; g! j- E) i, j1 Z4 C9 a! L/ l0 ^/ g& H4 N: j; R
}
" G" Q1 r8 x$ T% d
第三种是普通方法for循环
2 A, p5 i% e, {0 v% A$ M/ U/ n- q
#include<stdio.h>
4 R" H3 B8 F& Y7 M" rvoid main()
4 l) V2 Q; V  v4 q3 ^+ R4 B{ int i,k,m,n,num[50],q,*p;8 s+ j5 L2 D- P9 o. l; }3 R
    clrscr();; C& q, w* k' P9 P3 G
   printf("input number of person: n=");4 S! k# o1 W9 h) U1 J6 H
    scanf("%d",&n);
) @, O. Q4 j, l! ~! Lprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只2 s. H9 A( `: p! P1 |* J
    scanf("%d",&q);
/ q- |4 [" J4 }. ?   p=num;' }1 e% n0 ^- W/ ^) C$ J3 t
  for(i=0;i<n;i++)+ P# R5 @) ]# |9 C1 e$ h
    *(p+i)=i+1;
1 I: U- g5 f7 m; M3 j   i=0;
- t1 f# T4 N8 F6 U# |2 i$ l   k=0;
5 j* b+ k' q& Z1 h   m=0;
6 ^7 T+ ?; B! p$ g/ l  A  while(m<n-1)
- c$ j2 t+ c' `   {if(*(p+i)!=0) k++;
6 O' u# w5 E- A: ]$ z& j; S2 s     if(k==q)
4 v; }" o1 ]: F7 ]2 [      { *(p+i)=0;
: z6 O/ \1 B* n9 R9 U# Q) p        k=0;
# L& U4 s  f! v, O5 y; n, X% J        m++;  m* U$ F. w9 Y! C
      }" u1 R$ V" W* C1 k( J# ^
    i++;( r" R, Z" Z" }# |
    if(i==n)i=0;
9 w+ m* p6 F7 M% ]6 T: g2 r  B   }
. o4 @# T* I3 s& R, x3 s  while(*p==0)p++;
# k% q" s: x* E& T5 m0 y    printf("The last one is NO:%d\n",*p);
4 ]1 q1 E! R4 \6 m5 `7 N/ H     getch();
  d5 b" m/ C# Y2 P2 Q
6 W+ o; T. L3 u; |! W}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
# \$ t3 A- d7 O) @: C' d; }namespace 又费马达又费电
8 d" F4 f7 d  u% I9 ?( M{
7 i- K+ b6 m3 `/ A6 ^3 j    class Program" B: W# w+ p- Q& ~* n, }
    {
$ j/ H1 j5 b7 }7 M$ j& i( K6 c        static void Main(string[] args)
) _+ @. D! _- h, T+ L* B3 b4 {9 B        {
$ n6 A" K/ j* J            int m, n;
* v8 O5 N3 f# s$ ]            Console.WriteLine("请输入数组长度");
1 P! ~; i2 h+ F  t9 Z            m = int.Parse(Console.ReadLine());//m为数组的大小( e. a, I& Y3 i
            Console.WriteLine("请输入要截取数字的大小");9 ]! @6 `5 R' P' A2 t" ~
            n = int.Parse(Console.ReadLine());. E. W9 Y6 v3 R) e# G% t% y
            int [] numw=new int
; Y* W/ R  o; n) u) J" N; _9 d4 _2 N6 R
&shy;&shy;&shy;;( R: m2 p6 B, Z. c
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数1 q, L+ `: w6 q+ x5 c- b7 i+ f
            {
8 ^3 g/ Y& t. u+ q                numw[j - 1] = j;
: ^0 R2 W9 W+ b4 j+ |            }
; N' m! }* W: ?3 Z9 u/ l% R! D            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!( w1 a( V8 M- [5 I1 t
            while (d != m - 1)
  ?& b0 I4 B/ |5 e3 ~7 e/ ?1 N            {
+ K! D/ m5 c  v/ c9 e                if (i == m && d != m - 1). ^: w( f! H) _! d: k0 d
                {: i. c* h9 O7 L" r
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!9 Z% V$ v8 M/ D
                    continue;% o+ e: Z  R( G+ Q; W; w. `# w
                }
! _1 D0 F8 K2 e$ x                else) U& k/ t8 z* _3 {* ~/ t, n
                {9 X7 O' Y+ ]* i: h
                    if (numw[i] != 0); h  p" E3 `) ?2 u3 T  M+ V
                    {. M7 K# O5 F3 G% S# ?
                        i++;9 k* ?9 `* _' }' c% [% P  G
                        k++;
6 i3 [9 T$ Z* S8 v, m                        if (k == n)6 K, k: \' ^+ C" w2 u4 z$ B9 q8 z
                        {
( C3 y4 J* P$ F* V0 M% q6 {/ F+ E                            numw[i - 1] = 0;//把在n位置数组元素的值改变了$ I  w5 q- G1 P. n7 _
                            k = 0;  B# u; n. q- {8 q8 p1 l
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1: A9 a/ _. ]# K9 S/ N1 U3 e. i
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
5 x! A  Z* ~) c. g/ I5 i                        }
% U' B$ U$ |( `% @' _% K# i' ^- a                        else//输出暂时还没有改变数组元素的值
. ^* V; L  Q; }8 W, I# C- Q- J                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 S! C7 s0 ^3 A4 O
                    }
. P9 {7 v" ^% n1 }$ N                    else( Z, t$ c: N2 q: A7 t3 |5 R
                        i++;//数组元素为0,直接跳过,不计数。。。
1 A% i7 W6 l! H4 U7 ]# n8 T! u6 r. S3 a- A                }6 U( k( t1 S% ]' m6 @8 y
; C- U5 T* Z  k

+ k: y$ B3 F; b. a2 ~0 d/ z4 ~            }//结束while循环, \" V7 \0 _& T  t; s6 V) y
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦/ I5 p/ }, h. O
           8 N+ Q% K9 b! z6 ^8 M
                if (numw[i] != 0)" g$ t! _, ?- z2 F
                    Console.WriteLine(numw[i]);
9 ]3 S, l9 n" I( n9 p           
/ F3 @  S/ S0 Z2 i" N( M! F5 o            Console.ReadLine();
8 e1 X! S0 [8 `        }" S  _) H9 r' ~! n0 R  _# P
    }4 b( K% [7 I0 j2 u: w
}' o2 ^+ i( ^! s! v4 L
小甲鱼最新课程 -> 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-3-16 14:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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