鱼C论坛

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

猴子问题

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

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

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

x
大家好!
5 o( E* X& @: o9 L: {这几天我在忙着编一个问题,我用了一种方法编出来!/ A8 |# @- I- k0 {
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
- F- x5 f# Z: N& m  f5 P* \注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
" Q( [$ k% B' S3 X5 K' v; s9 M
$ b- u, X: K0 _0 S
" S/ Y. b' E/ |
                            题目
5 m  |0 X, s' j  Y山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
7 y9 Q" E3 Q& ~第一种方法:利用循环链表4 d* H2 e2 U* R+ f: N
#include<stdio.h>2 c9 ~9 |' U6 x! m6 U
#include<malloc.h>, Y% b, H& ^, z
#define M 8            //共有8只猴子
- Q- R5 ?% h/ c7 o  v1 B1 ^$ S8 S# s#define N 3            //数到3只时退出第三只
& G4 F  y3 E- b, Ktypedef struct monkey( b( R; k( q* X6 P5 Z( q2 S, t
{int number;0 J2 t$ n( ?8 q& \0 K% J
int flag;  O. ^$ s; [0 u! E9 h( Y7 {
struct monkey* next;- V: o& q* B- T9 H1 R
}MONKEY;
8 f7 s( ~7 _, e" @main()# n7 X8 L5 U2 a6 a
{ MONKEY *head=NULL,*p,*s;! A+ u' k! S0 x1 O
  int i,sum=0,count=0;! M8 R- {1 H) ^  A& d& V/ w
  clrscr();              //清屏$ O" x8 q, G9 v2 d0 |/ K
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存( @& P4 o: }8 x9 o
  p->number=1;p->flag=1;4 j3 I' k4 ], W8 ~
  p->next=head;
! W. @" U$ W0 R" h  head=p;: Y, l4 j: w7 I4 R8 n, f8 U. u4 x3 I
  for(i=2;i<=M;i++): Y# h' }: P7 j! z: M! ^
    { s=(MONKEY *)malloc(sizeof(MONKEY));. d6 ?/ O5 I; c% d2 N9 h
     s->number=i;s->flag=1;( [% i7 e& h$ l! {* V
     s->next=head;
( [3 ^1 m1 G$ b! P& A' ~     p->next=s;p=p->next;
8 y, i5 [' Z6 O' t( u& \- R    }
, S. ~$ z% ~- U9 I0 J    p=head;* ]; f9 H5 X4 O: k1 Y5 s" s9 V
   for(;;)
5 ]/ ~' r1 l5 e  l    {if(p->flag==1)
. D  I& E( x1 M2 @1 O! l: M       count++;
: r5 l1 A1 a) e! i1 n     if(count==N)) k7 r2 ^/ M/ D" B0 l! i
        {p->flag=0;3 S" n( L" ?7 e
         count=0;
/ N7 p- G: [! q7 @         sum++;}
! M: N, P/ A# E# q     if(sum==M-1)& m( J; B/ F3 d; @% V$ e
        break;
4 [8 P, A0 v1 D3 v$ U     p=p->next;( q9 T6 L' K' Q- }8 ?2 X; B
    }
( _1 v0 m" }! L) |9 o8 {" I5 L    p=
$ }9 R8 h" R0 p* l" s    head;
  S$ f3 U& m* a  F: O6 q9 q    for(i=1;i<=M;i++)6 b: B" F# n3 E6 Y) D' G4 \
    { if(p->flag==1)
# ^' Y' g- M' s7 t5 i, o" M" z        printf("\t%d",p->number);
5 O2 L6 Q: K! `/ N) D5 |      p=p->next;
/ `. R; l, }, U/ |( _  R1 M    }+ X9 n5 ^6 B4 @. U

  |& c8 m3 F% s5 h6 a9 ~/ Y# A
  U3 w: u) [" q0 R
) h* P1 d3 @; |1 ]7 W* l1 S}
  S2 ?( r7 u: M, T
第二种方法:数组
- G: W) ~. H# g1 ~6 c1 H#include<stdio.h>
, v* l3 h( i9 d6 R5 y& P#define M 8
/ M( E8 H( s# a' n( L8 n6 Fstruct monkey/ l7 a0 _( h( x% [/ L
{int number;
  Y% q" _% e$ b$ @int nextp;
6 ^( S- b: P- g) S# B3 r8 _) k}link[M+1];
, E' D" R9 k* D2 ?+ |$ {0 K7 \/ F. f/ D& S: {$ C
void main()
' d3 M1 v# v0 j# M{int i,count,h;" t5 e. l& A" b
for(i=1;i<=M;i++)
, i+ S( z2 E$ a" Y0 C0 l" N  v4 h; H{  if(i==M)
& a% G; m  ^& U   link[i].nextp=1;
0 U8 i7 n& r' n. ^& q   else" q+ S& ?3 h' K" J6 q3 S: d
   link[i].nextp=i+1;5 z8 T, V0 d& x# K9 x
  link[i].number=i;
: ]/ _& Z) K; ]}2 I5 _: A4 f7 I( c/ q- V+ Q! i
printf("\n");
4 p$ A6 I$ j5 O! e% Jcount=0;% z* e$ b% p" u( o+ d, X
h=M;
1 r( ^4 R8 h6 ^; b  lprintf("依次退出的猴子: \n");
3 v3 f2 c( i! g) H( Iwhile(count<M-1)7 L5 }( W8 r6 ^; [
{i=0;. F1 F$ V) z( @, D
while(i!=3)5 B. }" F  W( `4 x
{ h=link[h].nextp;
- N6 ?0 h$ X7 d: a" }8 m  T   if(link[h].number)$ P; @1 C* O& l8 g5 S$ D
     i++;}! U& j5 f. x7 w6 A( W( `
9 H% ]( w+ I( S5 }- v9 I' Z$ b* O
printf("%4d",link[h].number);! Y, x7 i8 z8 u0 C: u9 A8 B* P; A8 B# U
link[h].number=0;
- h$ `4 J$ |( r4 j/ @% V/ qcount++;' K; E0 v; p; w9 z9 p% R
}
9 @1 U$ s# |7 d8 W' m
# k- h% K" [. ^2 a: [/ z) F' Nprintf("\n大王是:");& V, b( \  H. v
  for(i=1;i<=M;i++)2 Y: C7 M" S4 B) ]% I# p9 S$ g4 Z8 n
  if(link[i].number)
! C- V$ W1 C% _( N# o8 ]2 `    printf("%3d\n",link[i].number);2 X! a" h4 z6 H6 f6 c0 T0 q8 k
3 z  \& r( ?7 T4 ?. X. j" [; q: z( @- P: v

/ w" t: M( ^& W! X, Q4 H: [}

; `: w& W( P. Y$ N' Z/ P第三种是普通方法for循环
) z+ d) u  V- E- T% b- y
#include<stdio.h>
* t6 U, ]: L: x3 \/ g1 |* K! ?! Fvoid main()
2 k9 d4 T$ x# e! X6 H; k/ g3 W3 W{ int i,k,m,n,num[50],q,*p;" A( n0 X3 p; N) `$ o
    clrscr();. l. T( r$ C$ R7 ~# u7 E" j7 k4 x: D
   printf("input number of person: n=");
8 U4 d% N! O7 ]! {! E, Q5 I# |    scanf("%d",&n);9 ^. W- |2 L8 v+ c
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
! M- a, i$ ~) k2 G    scanf("%d",&q);
! E+ g+ I4 D, s  i5 A   p=num;$ I: |. ~( h& t+ G5 f, D
  for(i=0;i<n;i++)" q% m* @: N8 n. c9 o! i2 f
    *(p+i)=i+1;) F, t4 e: G% B. G1 U6 s0 I. h
   i=0;
  X- z% F$ P' E. E! }   k=0;3 r1 F% d" {" E5 a# [
   m=0;
6 W; a' U( [& g& Y2 Q  while(m<n-1)2 q- P) h, @0 t5 g7 b
   {if(*(p+i)!=0) k++;& _$ `+ G% p, @+ m2 z% j: i
     if(k==q)
5 C! S' n* C( J! D. u      { *(p+i)=0;8 q! V- f# R1 y+ t
        k=0;
$ a# w9 G0 W7 e) N' K        m++;
0 [2 ~  @" ]9 B) L# F      }1 g/ C$ I# s4 t3 R. d
    i++;
8 r8 _  [) B( E. \# Y    if(i==n)i=0;9 ^# ^$ J7 S7 a& R) b8 W7 u$ q
   }
2 K. v7 W/ n* @( L1 I* H7 i  while(*p==0)p++;
, w, ^! J1 i4 m% I2 d! P    printf("The last one is NO:%d\n",*p);1 T1 e% @: }3 O" d# l! G
     getch();
0 n' _/ r, ~' q  u" O' A- h
; v4 i, A# `! @1 z}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
8 d: k/ a9 z! Y  i7 J6 P7 ^namespace 又费马达又费电
- h8 S) n8 u) x+ k: j{
3 T% }* }$ Q9 P9 {6 k& X7 r    class Program
$ i9 A% F4 @% h9 J    {4 R( I8 q- M, R9 \  b9 m/ f8 [
        static void Main(string[] args)3 d1 b1 m( r, H8 x
        {7 k/ n" z2 i# ]: d% @! U
            int m, n;$ R& r# N( D: a9 A& @
            Console.WriteLine("请输入数组长度");% E5 e, s9 F& N; v8 i) p
            m = int.Parse(Console.ReadLine());//m为数组的大小
/ S5 r, Q  T2 d& F            Console.WriteLine("请输入要截取数字的大小");$ u) m+ ?' N' U! X  |# I+ w0 H
            n = int.Parse(Console.ReadLine());
7 \" w' O  J) B+ r$ ?; d            int [] numw=new int( a+ A; A" U( |  j/ q6 h9 Y
) G4 _2 B4 K- j0 u" t
&shy;&shy;&shy;;5 L) r1 g# {2 z5 O
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
. m! A. C5 i6 S8 K% ~# o            {! L% m: X6 ~6 }$ E: E
                numw[j - 1] = j;
$ d" G9 h8 B+ Z! Z2 X6 |! P            }, S( v4 R' S+ @9 W
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
" ?$ D$ q7 x. H- @9 g% @5 I            while (d != m - 1)! v+ `( p1 ?8 i8 i) H: `5 X( P7 ^
            {
; v: G3 I8 o, @% b7 X: ?                if (i == m && d != m - 1)6 N4 A7 M2 e2 Y" c
                {6 S" s* O$ x! @' \8 p) |; s% y
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!, {- s6 s) S% q! ~0 n
                    continue;
$ w/ }( Z$ V  B. {! c% d                }5 D. K7 a9 r. e6 _! a
                else
# Y4 Y" E5 h" F/ A; s- {                {
2 A2 u- T  W; P$ G7 l; X( u+ z8 K/ ^                    if (numw[i] != 0)# c% p  p3 o+ W! _( n" i. Q0 Z2 w
                    {
) O6 B& D2 h: _; c6 B: O2 d                        i++;
8 {& f1 B+ H, i# b7 V                        k++;
  C/ \; B4 D, q                        if (k == n)  T+ h1 @5 _! V5 X
                        {. j& ]( D2 @% x. I, \0 _' \
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了$ R) }; Q4 Q, I* |, e# g& O
                            k = 0;) G, t$ T  L0 K" Q0 f
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1" b* @  Q) H1 u) i1 D
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);9 J7 L& Q3 T! s3 ?3 J
                        }
$ F3 Q6 d% Q# B( y* G& T                        else//输出暂时还没有改变数组元素的值* ~0 G9 Q1 x+ c* P; o6 K6 \
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);3 G4 h  Z/ e7 l) f* b# @3 n; i
                    }
) |( o; L1 d2 q                    else$ T% a/ J! K! N" H" s. a# y
                        i++;//数组元素为0,直接跳过,不计数。。。
" O: @' j' d( O3 u) E: Y                }
$ f9 i* O) `+ f0 w! x . `: [7 I( r0 `+ g( c& @
0 T9 N' j. v/ s4 v9 a( a: E* f: r
            }//结束while循环
( g, o. q* ^  p* f4 e$ B, Z            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦5 v8 b( P8 P/ _; _  m6 a
           
  s8 ^. K* y. T. N  [                if (numw[i] != 0)
6 [. B4 e; u% o+ `                    Console.WriteLine(numw[i]);
9 c) i, \& f% ]8 L9 n           " ~& K1 [  A2 p+ \2 z0 g3 l
            Console.ReadLine();
  E+ z* j3 d8 y2 @        }
+ w6 j  y5 s2 O6 |& r$ j2 N    }! {' A8 y& q, E0 |7 h  E: H0 C4 w
}
% L) H& g" q2 u5 z  U/ S, p, C9 A
小甲鱼最新课程 -> 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-2-7 10:49

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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