鱼C论坛

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

猴子问题

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

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

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

x
大家好!# o# X. a1 k: t' f
这几天我在忙着编一个问题,我用了一种方法编出来!. x/ x$ Y  |: \5 k
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!5 k3 I3 P; s8 N' i
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 . l: ^9 a0 e. W
" e" Y; C/ ]2 ]& U8 a
1 h8 `8 L% M+ E
                            题目" p+ ~/ B# t: P9 ~+ Y
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。, J  r1 p1 a2 v& s( B6 l, ~
第一种方法:利用循环链表% y( o. U! _( I& M, u
#include<stdio.h>
3 l, Z1 @/ o8 ?/ b  {#include<malloc.h>
: B( b  t( v& A#define M 8            //共有8只猴子
* I& P6 i( u( {) N#define N 3            //数到3只时退出第三只
% r( k8 E0 _  q! \typedef struct monkey
# G; s! L0 C7 s7 C/ Y) s/ k{int number;& K* b9 e2 I7 ^5 H) C+ r. ^5 b
int flag;
. N% b+ h, o: @% v' Z$ [struct monkey* next;  ]) P0 V; [) ~; t- x
}MONKEY;; Z6 n' Y8 {) A( X# a
main()# s" q, e5 S# C- z
{ MONKEY *head=NULL,*p,*s;
, g: c  V- M) O  int i,sum=0,count=0;4 w3 `2 X+ x/ F6 }' {( o
  clrscr();              //清屏( R1 N( ~) m5 }8 w% O% V
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存* }7 K1 Y- [5 Q; a2 C# P* R
  p->number=1;p->flag=1;
" Y9 a3 p" L) U; W, [, R+ q6 N  p->next=head;
& m% {/ G1 Q6 {$ _+ _  head=p;
- A1 _6 p. u& {0 T) U& S! n- o. @  for(i=2;i<=M;i++)
7 j8 n1 m4 a& r- U# V5 R    { s=(MONKEY *)malloc(sizeof(MONKEY));/ w# ?, s5 \; Z. e0 h
     s->number=i;s->flag=1;
2 I* D( b8 s2 t6 D8 x: s     s->next=head;3 X) V7 M9 J' d* Y1 o& r8 C# N
     p->next=s;p=p->next;
' |( q3 Z/ G- M9 A* y7 t    }
0 c! f$ N/ M! Q# o; @' A4 I2 M; ^    p=head;" l0 \1 f% u6 w' v2 P0 O" B* f
   for(;;)8 a! E. y. V+ G+ q
    {if(p->flag==1)
" ^; \# ]6 F0 c' P       count++;( n% G/ [( v$ q4 G
     if(count==N)- v5 I) |% s% }* H
        {p->flag=0;7 P  P4 c! {4 j) i
         count=0;
3 b4 C0 E, m: n0 G. Y3 S         sum++;}
4 k; E1 e9 q5 X6 b" T     if(sum==M-1)
$ F. b. n. F* ]- x2 J7 `- v        break;7 v0 C% R- D$ R9 c- e
     p=p->next;+ d. S( T( G( {% c4 u1 A! _
    }0 H+ z3 O' h7 i- ?# A
    p=
. K& z4 ~3 T9 L& }    head;
' q* P' o% G! o9 O3 ~    for(i=1;i<=M;i++)( U1 E6 ?2 V4 i' k! R, n
    { if(p->flag==1)* p* M, N4 G" q+ t
        printf("\t%d",p->number);
: s3 R& l$ ?( f$ ?1 q& t1 t4 O      p=p->next;
& f, {# d) F6 }3 H" V    }9 U+ }* R6 r2 W) r! P) F2 f& M
! a4 P% Z7 X( }: a  y; {" _
8 v( s: k+ r% c5 W& {

( Z* I7 ^0 R0 ]  w! C; r}
; e0 q$ d8 g+ V4 }
第二种方法:数组6 ]" t/ v1 z8 x8 u$ f
#include<stdio.h>8 x+ M, a- [4 v0 S) Y/ g
#define M 8
9 o* f& i* t: d4 d# `! k! d' pstruct monkey
* q: d+ n! J* W: l. z% \9 z{int number;" T1 c0 e: Y; G+ G
int nextp;" y* y0 o9 Q2 t9 t6 V8 r
}link[M+1];
  m' p* I6 D2 [; y/ n6 _0 A& b. u2 |
void main(): s( s7 z% L! E) e! n( E6 Z
{int i,count,h;
6 S9 J/ A0 F( `. O6 ifor(i=1;i<=M;i++)
2 Q  W* W3 s/ U* S& q' o{  if(i==M)6 x$ W- k5 u: V; a) u0 E5 b; V& Z" W
   link[i].nextp=1;% U$ J, b+ X  X0 D, Q7 D
   else! _: v4 o9 Q1 d0 n9 \! j
   link[i].nextp=i+1;
; U( m$ V  r" Y$ I' w  link[i].number=i;7 N  G/ @) z. A
}% Z: f: K7 s  ^
printf("\n");
$ D7 S' b; e4 L& k) c2 b7 ?count=0;
) {: b; p- q, E, B2 H8 S, P5 L2 k: gh=M;7 i: w6 v; D5 P& ?) r$ X9 k
printf("依次退出的猴子: \n");
9 y5 K! f# k8 J7 J' v7 ]7 `/ Gwhile(count<M-1)2 P  I: F5 q( c1 X! f7 J7 ~
{i=0;
6 z8 x/ y8 r: r8 [, `while(i!=3)8 ]" F4 p5 j  d. ?# K7 P
{ h=link[h].nextp;
/ ^; B- l: [) P9 \# }. q5 U" x  {   if(link[h].number)1 K) q% e/ o, ?6 A( M5 i5 C+ W
     i++;}4 k3 y( |: j3 t' P# f6 V7 `7 m& c5 E
( R9 D: F2 B' I3 c+ \0 [) ?
printf("%4d",link[h].number);% R$ _5 r6 z  h
link[h].number=0;# R+ J: k# j1 ?! L/ s4 t$ }6 w
count++;% u+ F1 J" _6 x+ V+ T3 t4 U
}% }( m1 _+ [! m$ ~9 L
( c7 C; p! \: U( W
printf("\n大王是:");
' q6 u2 ~" h. U# Q4 W) x; G2 H  for(i=1;i<=M;i++)
5 ~+ F  J- L+ j5 {  R: K( x  if(link[i].number)
1 A. b, k* g+ y1 L2 D3 ]' S2 A    printf("%3d\n",link[i].number);" }4 }- S* u5 ~$ m4 B. u

6 s1 V& g  j0 v  x/ Q* V+ K/ S0 y  {6 i: ?% h$ _
}
  G1 r1 q& X$ c
第三种是普通方法for循环

+ A5 d( r! I4 o! P& ^* ~3 M#include<stdio.h>
5 o5 A0 r/ M. j# @) ivoid main()$ x+ i: K2 U; Y: s: _, p6 }. B4 O
{ int i,k,m,n,num[50],q,*p;
$ I" y; A0 m  B    clrscr();! x7 V; D) L/ x  r
   printf("input number of person: n=");
- t6 u; z* v/ P  y' e    scanf("%d",&n);
- f+ G, b' e" P, O$ y* L" xprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 U5 X- |/ |( r" e) W    scanf("%d",&q);
$ ?. b0 {: A  f+ y   p=num;' ?3 i  |0 R, R# @" R/ s" E5 d8 Y- q
  for(i=0;i<n;i++)+ o( S. q: W1 j& i0 S/ H
    *(p+i)=i+1;3 z( e! n/ v0 {) Y* _
   i=0;
' x) [3 d8 R3 {! ^7 z8 \   k=0;5 m/ D9 ^, `& o% W( Q' `
   m=0;
. ?) d1 e( l; |# O! e2 }  while(m<n-1)
& x' W2 O. K+ o3 u) y% S   {if(*(p+i)!=0) k++;
  F4 k" U. L: q' B$ i% `! D     if(k==q)
* d) \6 U+ {4 c4 m- D8 v      { *(p+i)=0;
1 ], y7 ^- t3 t        k=0;
6 X! E9 R/ w; q        m++;
' i, t2 O% A) z      }, W6 k8 a5 d, y+ ], D
    i++;
& |( S/ C8 R* `& L3 y1 b    if(i==n)i=0;
0 z/ S. a5 q0 T   }
+ t* h( e6 `* ]5 ~7 v6 m1 q' |/ q  while(*p==0)p++;9 ^0 U$ t8 N4 C: K
    printf("The last one is NO:%d\n",*p);( F# P6 L" L8 n4 @6 ^
     getch();
2 F, t3 Q5 t" w4 |# v! e7 g: C5 T; }, k' b' ]5 Y$ D
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
' Z5 k( i; t7 u: ~3 l' Ynamespace 又费马达又费电/ h8 X: J- @8 E% l; z1 }8 Y
{- }( B. _! x  x5 j- ]. z. m
    class Program
: P5 U) i& F( o* |. Q/ p    {& A. H" j6 W' v4 @- b% W5 @5 \' j5 v
        static void Main(string[] args)1 q8 ^8 J  j' d  \8 q' u* m& }& K" u/ D
        {6 m$ k/ U( D& r* C  B) D
            int m, n;+ M$ C+ M% l" z" @4 A/ I" \# J
            Console.WriteLine("请输入数组长度");
5 M& A: X7 Z) P! e            m = int.Parse(Console.ReadLine());//m为数组的大小% z" v% q8 x# }
            Console.WriteLine("请输入要截取数字的大小");/ z: C1 @6 S! x2 E( S9 {
            n = int.Parse(Console.ReadLine());/ E4 z# A# A8 q
            int [] numw=new int
0 l) s2 L+ E# E5 l1 ^; S; H" {9 K1 H0 I# a
&shy;&shy;&shy;;
2 t  c1 E$ w; h8 p8 |1 j) {            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
  v% Y3 Q$ U$ t0 g" _9 i            {0 |5 w6 y- i2 }# u- y8 F
                numw[j - 1] = j;5 E$ a% d' h  u; N7 B' h' n
            }7 a3 |) m2 z, y# J
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!3 p4 n3 B' N" W% y& h9 n# J4 O* j! j
            while (d != m - 1)
: s1 m" Y! H5 S/ T5 y            {4 z* \) l" q9 R' D/ R6 e4 ?
                if (i == m && d != m - 1)
) o3 D6 X, J9 [) l- N( s                {6 B$ _- y# b9 B% ]0 q. ^/ c
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!0 R/ n2 o/ C: a% X2 M6 H6 v
                    continue;
8 Z. _4 t: u. T) G( l) v6 p                }
% U. |8 x* A/ M; `                else7 J1 Q2 K' g' M7 ?0 Q
                {3 w$ D/ Q4 C4 n0 J) M. f* X. r
                    if (numw[i] != 0)  Q; }  D0 ~9 @/ o" U
                    {
" f# w6 n0 ~3 i& e# n. W, ~* q1 ^                        i++;
- C8 G% Y- [. r! i4 d' `6 q                        k++;
) ~% r/ k, X. l; y- E$ |& G* ^                        if (k == n)) y( X7 F+ r  g/ I
                        {
+ n, l4 T. z# R+ y                            numw[i - 1] = 0;//把在n位置数组元素的值改变了! r; D/ q) ~5 ?# ?/ W
                            k = 0;
" Z+ }+ T! }+ V0 X              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
- Z; M3 d( J5 H( f                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
! t, J7 p3 {# c( H9 I                        }0 y& f% Y; D6 d0 M8 g- j0 D) p/ u
                        else//输出暂时还没有改变数组元素的值* g, [( b  W) o/ }. X
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
' d( m8 ?+ ?4 `, I6 K$ c                    }6 u5 w" P. c" v, B( R, Y
                    else
2 H3 f- r8 `# |4 W                        i++;//数组元素为0,直接跳过,不计数。。。2 @/ C+ }- K  G, k
                }' x- j9 M3 O4 s5 i4 G

% d; T$ x2 [' }7 S3 U* s5 I1 G3 y1 S0 |, f
            }//结束while循环- D+ x) u& k6 {( w
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
- M7 ~+ h$ F+ @) N  d8 x. u. m2 e           
' D. ?# t: _1 V* `# R                if (numw[i] != 0)  Z) f# I2 ]3 Z, [& y
                    Console.WriteLine(numw[i]);
2 H9 r0 A: y2 a/ K; t           
& E9 Z& h: p3 {2 i# A, f* K9 C& A            Console.ReadLine();
1 C0 r1 O( z( R; @! K5 N        }
4 F: [3 c3 c) b' x3 A    }& s8 F1 J7 f" G1 b( U; }
}2 z& V/ W6 y9 _- \8 \
小甲鱼最新课程 -> 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-6-22 09:13

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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