鱼C论坛

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

猴子问题

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

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

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

x
大家好!
8 {7 j. O  d+ b7 V; Z# a1 H这几天我在忙着编一个问题,我用了一种方法编出来!
9 d$ C2 E) R& R但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
7 j, ]2 r) `$ o5 u+ b注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 4 R0 ~# D1 Y- l- @
& {' H. f1 }5 K0 u8 x6 s+ |

! a# ?; k1 q3 v8 v0 ?: O$ K( J! @3 ?
                            题目5 _* S. c; C1 j$ i  w
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
9 D+ i) x+ |: ^" X第一种方法:利用循环链表
( }! ~9 j- E& L, c0 k5 P9 I#include<stdio.h>5 t$ W% a8 e; B, e+ H3 S# k
#include<malloc.h>
: v3 z5 W( E4 G$ {; ^& x( E#define M 8            //共有8只猴子
4 h$ @0 e+ m: D6 r1 _! ^8 L; K1 r#define N 3            //数到3只时退出第三只
. \0 P5 L/ d; j/ Xtypedef struct monkey
* B: N  P6 D% g# D{int number;+ a- p# Q+ X) Z) B$ p* D( x1 I( r
int flag;; Y0 i% P  N# {! ?6 ~# g* g# Z
struct monkey* next;
1 v" g) A4 x1 z1 z/ t}MONKEY;
( n. s( ~  i2 ymain()  Y' M( O9 a/ v9 {4 `, M
{ MONKEY *head=NULL,*p,*s;$ I* B6 n) m5 i
  int i,sum=0,count=0;
) K: b; j6 T0 F5 ?( n  clrscr();              //清屏& f! \8 P- l" c) M( g- {! q
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存6 X1 D: M- {- f" ^
  p->number=1;p->flag=1;' _6 Y6 m+ x) ~3 B: t
  p->next=head;
: S) [) M2 n2 `9 K) d  head=p;
+ ^7 t6 V/ P4 u  for(i=2;i<=M;i++)
& K2 |8 @0 B  x$ M% Q7 N    { s=(MONKEY *)malloc(sizeof(MONKEY));- ~0 i6 \! q" O) c6 @4 x8 `# p" ^
     s->number=i;s->flag=1;
6 `6 Q5 G* h7 X& X     s->next=head;
# V: w+ U4 T; o+ B4 v+ y     p->next=s;p=p->next;  V$ J. m( ~& D5 ]' h, V- R" Z. D% z
    }
, D! Q# D3 ^' f% w7 r  [    p=head;
. B# I5 t9 q! `$ u/ N) e& {* e   for(;;)
0 R* a( r4 A, N! H/ q. J    {if(p->flag==1)
# G7 u  }4 Q" P       count++;
  e+ y' T# e* U) K- D, O: U  B     if(count==N)0 c; p. I# ~3 f- x6 l
        {p->flag=0;- a' i  d  J4 P& U$ L
         count=0;
4 p1 `$ y( q3 Y( @  d         sum++;}
9 R, o) l$ ]5 N, ^4 |) F, D; h     if(sum==M-1)
' O, n- q; k3 p7 j6 V        break;  P; m$ P5 y/ j5 v
     p=p->next;: d7 ]% w  l3 e1 A" |1 j
    }
( f( ]& Q( o! g% G1 V, g- k    p=
1 ]7 U$ S3 m, A: |0 U1 f, B    head;5 Q3 g* H  L0 f2 E4 o4 d& T/ F
    for(i=1;i<=M;i++)' m6 L) J- R: x4 S0 J6 t8 L
    { if(p->flag==1)6 I  y7 }; @6 C& I, I7 g
        printf("\t%d",p->number);
1 M/ `9 v5 C& ~; v% f      p=p->next;) C7 b* N2 k6 d3 V
    }+ M# N- E% ?' N* a% F1 C
* _/ a( Q$ b' L: [/ u0 [( B
& \8 s! R, M! p# F
$ w1 ~, t; x1 Y  W6 @, |* Y
}
5 a, U: ~0 e0 s2 ~5 k+ C
第二种方法:数组
3 o1 k# w3 f! D; Y  Z#include<stdio.h>6 F) q: N' B, R4 ?/ Q- k
#define M 8. G- ~) ~! d/ q5 P
struct monkey
+ w9 ]* v" ^+ X: w0 r3 @2 o{int number;. `- S5 N5 u' G# k: u  l- Z6 E
int nextp;# F1 H4 w$ O7 M0 _4 M. }
}link[M+1];
0 @1 o5 A6 q7 D' H3 u4 N& C7 p5 B8 o2 {# C( i
void main()6 p, W- h% v; b, m7 `! J+ q6 ?
{int i,count,h;2 Q* @6 ]4 g- A( Q3 ]
for(i=1;i<=M;i++)
! L! A8 N+ j" ?7 Y9 r{  if(i==M)
5 j. d6 U' B4 b0 p0 }/ e   link[i].nextp=1;) B, l2 G! R/ f, J+ r
   else
0 F. V7 Q$ T2 k3 ]! h- u( j   link[i].nextp=i+1;
( f% s' z* @0 E9 k& @. g  link[i].number=i;
  @1 I. A6 J9 Z% Z! u8 t) }9 V}
. _7 k5 e$ J/ @4 Uprintf("\n");/ k2 _6 D- k4 ~2 o/ g# D4 u# ?1 y
count=0;, [# d; F1 d3 j  l5 ^
h=M;! E9 Q) \; p6 l7 z- d, O
printf("依次退出的猴子: \n");
, A; j  w  L% K# H. D% Nwhile(count<M-1)
% V6 I/ D' Q7 E{i=0;7 A9 [6 c5 p% T
while(i!=3)) y- y9 V0 Q$ g8 P  d' T/ T0 X; @
{ h=link[h].nextp;
" |/ @9 S$ ]8 p# Q3 Q  y* @& j   if(link[h].number)# U' f* j/ A, u" N/ q1 U
     i++;}
- J2 ~0 n/ p# ?1 F. d& r
, f% V( Y# R' o+ N+ z, ~printf("%4d",link[h].number);# [) a5 x9 {9 y0 X6 S
link[h].number=0;$ Y  Z5 ]$ R% M: N' v# X$ a5 J! N
count++;- l0 b; W6 o3 H$ J: y
}
% V, d) D. @' b) u' B9 P% q( a' N3 ~& n
printf("\n大王是:");
# I# b! t3 p/ t' r% k3 E. B  for(i=1;i<=M;i++)
7 H& ]9 _: T6 O1 G' V  if(link[i].number)/ ]. H5 ]. O+ h2 v
    printf("%3d\n",link[i].number);
4 E* ]" t3 q( @  j( _1 {  d% t7 g7 X4 x

- n! [# [$ W4 C6 c  J}

" Q# u% Y& R+ I2 F第三种是普通方法for循环

6 L: V3 F$ r3 n' Y#include<stdio.h>
7 t: r  d% @' Kvoid main()+ C% v3 e6 J4 u9 m, s
{ int i,k,m,n,num[50],q,*p;4 F0 a& `, w3 z0 T# Y
    clrscr();
' G# ?* `9 K. p   printf("input number of person: n=");
; g, R$ W( p! V3 D+ J1 x    scanf("%d",&n);
+ r9 v! B; Q. u, F: L7 Xprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只2 ~: k& E5 J; }( Y( K) |
    scanf("%d",&q);
+ \; D% ~. N) A. ]2 }   p=num;
, d4 ~' J" H* F" q5 q4 P" P  for(i=0;i<n;i++)
) c' n# t9 ^! b( ?6 q2 M    *(p+i)=i+1;( K. C1 B7 f, A, C
   i=0;6 v' b6 ]5 n4 o1 N& p. h& ^
   k=0;; w( R$ t; L2 O3 f! w
   m=0;; b$ Y! P$ ^6 v; D7 e- _9 a6 P
  while(m<n-1)
0 R. X4 @* g6 J1 M   {if(*(p+i)!=0) k++;' }9 d( P; Q+ @  P
     if(k==q)
" M9 M1 J) i" ?% g; Q+ `  n* p      { *(p+i)=0;
5 ?9 N1 V9 l! d2 h        k=0;, Z) {# s+ e' X
        m++;
, o. u' m, u) {  q6 r      }7 d5 W+ n* _' T) ]
    i++;
) j% [6 x+ r5 M* O, Z7 e    if(i==n)i=0;, Q/ V) ~( l& K* k3 a% W" p
   }6 }1 i% N  N# B& r- a
  while(*p==0)p++;# F3 h2 j- F4 m* n) J' w4 ]
    printf("The last one is NO:%d\n",*p);5 W9 s! ^2 ~" W$ d
     getch();
: c4 P8 z. c& I, v+ {' @
! \  L, C7 X& h- L0 n}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;9 L/ ?4 U$ E: I- J# O' O
namespace 又费马达又费电
4 @" w) L! D; g# s{
0 a% s" H: |" q" w    class Program- o, U. r* I- [/ ~( k. p9 J
    {; k: Y2 Z( ]' @9 o4 m2 o0 |
        static void Main(string[] args)
+ l/ P5 X' T2 ~) m        {
* {1 V: p/ }' B            int m, n;
; V3 N" A6 ]2 Y7 g            Console.WriteLine("请输入数组长度");. \+ r: f1 U! G* o7 k( h: l
            m = int.Parse(Console.ReadLine());//m为数组的大小. R' S+ v4 w0 C/ G7 f6 j* V& B
            Console.WriteLine("请输入要截取数字的大小");9 T: C. @" m/ j
            n = int.Parse(Console.ReadLine());+ T* P( `8 |7 ^4 {1 r0 M
            int [] numw=new int
: m0 K- ~" F: ^3 }  K; W8 }1 C- [( J% ^# r1 Y0 ^5 I6 m
&shy;&shy;&shy;;' n' A7 N5 T3 v6 [, U4 ?& a2 p
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数2 S9 a: ~% A5 E* o8 b8 [
            {
/ Y! a# g- P- s% {2 f0 Y                numw[j - 1] = j;1 q% r% y% g9 r+ }& k( j8 V
            }
; Y+ L8 k( ?/ m3 D  Z8 E' r$ V7 h            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
1 p) g  S# K6 m7 T* P5 z8 O# p            while (d != m - 1)
0 v0 o0 F! y+ \. Z            {
+ ?. [- n* w1 R' C                if (i == m && d != m - 1). S' T- u" K  K
                {' t) C  B2 m- v
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!3 q% n, `% O: ~+ x+ Q2 a
                    continue;5 f& v' Q7 Q* D6 A
                }0 s; w( G3 k- r2 E+ N5 p8 A
                else) U6 _6 W2 S. a/ J/ ], ?8 H! F7 k
                {6 _2 W, d# A$ u6 F8 ?
                    if (numw[i] != 0)
- g, f! h+ z% Q                    {
: Y( f" _& P' J  a0 H2 I                        i++;# o* v( g- R; j) z" T: G, M9 N
                        k++;! h4 y' H* n5 B: D( r$ W
                        if (k == n)
) F; s  e6 s' k2 ~+ S! o                        {! n6 f1 s+ V! \% \3 S! e. B
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了  Q2 o: ~: m' S; W
                            k = 0;$ _* u: O* n& R
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1- Z5 f2 B3 i* u- q0 B  K
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 j) m! e5 t0 U) p* d( O4 E
                        }0 n  o3 |/ B0 ^  J; y- G1 g2 X
                        else//输出暂时还没有改变数组元素的值
) a* V( n$ y3 K1 [0 v9 }* }                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
. V. K6 \% c2 B* I1 J& {) ]# g% `0 E                    }! r- m( n+ y3 j: N' S9 K
                    else7 q# }: u4 v4 H+ m* c* }8 J1 U
                        i++;//数组元素为0,直接跳过,不计数。。。8 k9 z* e* x- i! y" @
                }+ L% r/ h7 |2 J
( [! f! t  B, V; Z, e, s+ i9 _
7 [8 ~2 a# s8 N# j* K3 d
            }//结束while循环
4 `3 W5 J, A+ a2 D            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
8 `/ I1 U5 W$ a" q( I' E+ U           / D. @$ n# v6 j, M3 o2 ~! N
                if (numw[i] != 0)
; Y; |$ x. X" e- W6 y                    Console.WriteLine(numw[i]);  Y$ V1 D* _) ^, y
           
8 g6 o& p. w/ [            Console.ReadLine();$ V1 y) h5 z1 C% Z
        }
. h( V* {% ]; ^, h    }
/ _) y) X  S$ v6 S+ @, f}
: f. S- @, n9 i6 P0 B
小甲鱼最新课程 -> 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-1-16 20:42

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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