鱼C论坛

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

猴子问题

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

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

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

x
大家好!  e0 \: w. E! F# S$ A; w: z
这几天我在忙着编一个问题,我用了一种方法编出来!2 U/ M$ u; u3 ]
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ g2 i7 Q7 t* I. h7 }" p
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
! L) v' m0 O' a" J% P
, K* F; i2 b  ^
. P6 V% C8 C( c" @$ n
                            题目
9 U" W* h. L% Q/ d山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
8 V4 w9 t! m' j" ?/ A9 R第一种方法:利用循环链表  S6 |6 y+ e# |& e7 D5 F
#include<stdio.h>
) c: W7 i# U1 t+ g& v3 S#include<malloc.h>
5 E, @, M1 f& |2 J3 M: }1 R% B#define M 8            //共有8只猴子9 k/ T; z1 B. c0 T3 B% ]9 D
#define N 3            //数到3只时退出第三只
% c$ Y3 j  r0 G) ]* m0 ~9 D0 v1 M/ ]typedef struct monkey
+ r4 l; p1 B: M6 j$ Z6 h{int number;1 T& |1 c. @% H! R. C
int flag;9 `5 }# _0 M5 f
struct monkey* next;6 J4 X/ _6 N" Y  l& n
}MONKEY;1 e7 Z0 h- T4 l! R* T, `
main()
6 j3 A  k6 R  a& W$ B2 v5 z{ MONKEY *head=NULL,*p,*s;
8 F: I8 d, ]# ]' V" l  int i,sum=0,count=0;
- y  d, Y  }0 O  clrscr();              //清屏
  q9 N2 W" s3 |  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存2 x2 p, r$ x) T* l
  p->number=1;p->flag=1;
0 E9 |) x4 v: s, G; d6 J  p->next=head;
0 {: q' r/ G. {" i' g  head=p;8 m, C" S) y" s4 f" h# ?  x
  for(i=2;i<=M;i++)/ B( ]9 V& ^, ?( ~' r: |6 t
    { s=(MONKEY *)malloc(sizeof(MONKEY));
6 L. J, }* Q" b! v     s->number=i;s->flag=1;
! u% R! c" F4 A$ e2 t' d     s->next=head;! O: I; {9 h* Y3 t0 F+ k2 G# D
     p->next=s;p=p->next;
4 P" N6 J; ^5 m4 K- f6 r( N    }
' G" y5 T: r9 u- S$ P; z    p=head;# W1 s7 y  e; O# [* `7 s
   for(;;)
0 B4 A, `6 i; i3 E    {if(p->flag==1)7 S/ i( E! r3 j/ f
       count++;
1 |* u+ J$ k% O% l, G' _* u5 f" g0 P     if(count==N)9 E) p- S/ I1 m$ {& e$ s& w
        {p->flag=0;9 O( T7 ~4 u) C$ ]
         count=0;
' z; }" n. N3 ^" ^1 @! S         sum++;}
  X2 m/ E" R. v+ ?6 F4 ?5 L     if(sum==M-1)
4 W9 L1 C1 w/ k2 [+ D* W* C' N' j" M        break;
) {2 ~0 U/ a3 S" l" u1 A9 G     p=p->next;) J; d4 e& q1 M, @
    }7 H& M" U5 p( s- O6 n  C5 q: {$ w
    p=7 n0 J7 u  A* V3 f4 k
    head;6 l( C. @5 `1 V
    for(i=1;i<=M;i++)4 `) q9 |2 F) d$ j. s) M2 i- N9 f2 O
    { if(p->flag==1)
: c, K% S) B' V1 B        printf("\t%d",p->number);
( m1 V: p, R+ V0 h$ I# l      p=p->next;
7 e# Y  {" {% b% h' Q    }
$ ~4 w+ P  ]# N% \
0 a; N% `8 s/ e$ p8 n! b
& u  Y1 {2 y% ?1 B0 c, b1 F5 q4 n% ~: T4 x& S) R- R2 X
}

. P" ~( z9 o% f1 z5 E第二种方法:数组
7 ?% c5 L9 m3 r* b. |* ^% V#include<stdio.h>
, Q* \6 s2 c1 ~& O#define M 8
& \) X+ T; ^) M+ p3 B3 B' M4 estruct monkey! {$ R) L8 D/ N0 W  N) m5 c! a* i
{int number;
" P: ~* G9 I; f  B  t1 W3 O( Iint nextp;
5 e7 i: p5 t- [% f) ?$ c}link[M+1];% {3 f" J% [1 z5 F5 i

( T2 O7 h2 }$ @$ B; p8 w2 Bvoid main()9 p# D6 }/ n; z3 E# q4 k
{int i,count,h;
; Z/ C* y0 F9 V6 E# L) i! _for(i=1;i<=M;i++)
, Y8 k9 J; h/ B; z- N{  if(i==M)
0 l; Y* Z4 J) y8 D" g, `   link[i].nextp=1;- x/ s$ t" `$ ]% h
   else9 q. g" e3 F: p& E% g$ p
   link[i].nextp=i+1;* }, R, s6 G* B  J& S- I0 @
  link[i].number=i;
) J, ~  s0 N1 a8 {}
# g# l* y6 {! u/ @: K' ]printf("\n");2 b* z4 g5 ]" |8 x
count=0;+ N8 B1 a9 ]5 n$ a; ~
h=M;8 f/ |6 ]9 d9 M) ]
printf("依次退出的猴子: \n");$ f9 {  B( `6 L: }, N
while(count<M-1)
+ K; |6 i+ C% J, A" v5 M{i=0;* W  z% o0 G  F) ?$ C% c) A
while(i!=3)' l# E+ C; p! B* t
{ h=link[h].nextp;
' i  q& l' W3 U# a! D, b8 Y5 J   if(link[h].number)% h- x6 @, T: f# B: m& o4 v( G$ z
     i++;}6 G- h, Y2 S# z3 H

9 N( h) U- a: f+ h) _5 \printf("%4d",link[h].number);* N! s( k. y& c  V
link[h].number=0;8 e8 L5 V5 ?3 G% u$ b! Y; p
count++;
7 m! f2 e  {5 B3 G; H  {}8 M% R0 Q* A$ Q  q! n
4 I& l! ~' [+ N5 i$ w; O5 z
printf("\n大王是:");# ]' g) d" G2 B# t( S' ?* v
  for(i=1;i<=M;i++)+ _1 e7 E4 x7 W: L" u8 h8 A  Z1 c+ D* b
  if(link[i].number)7 e! _3 d' e7 V# g& \2 I/ ^- S/ K
    printf("%3d\n",link[i].number);
) P  _, O& B9 i$ @  c* b/ I
- y0 H( i; i" u$ k, [
  w# A, D$ z# o# b4 [3 @}
, i% M' |8 I' T
第三种是普通方法for循环

6 u- M% S. W: b#include<stdio.h>
& ^6 O) T1 N. G9 ^. L/ A9 j' n! h; yvoid main()5 K( d7 ^  V9 ]2 t3 m8 B6 k9 n3 C* m
{ int i,k,m,n,num[50],q,*p;. f, P+ \- J. Z
    clrscr();' \$ v2 t( `2 ]
   printf("input number of person: n=");* o& o2 f: P: i  s, Y
    scanf("%d",&n);
7 N. m% L7 {- a5 sprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
: n- O% J6 K( `& A    scanf("%d",&q);2 }* H# |- S7 ~4 X+ u, f9 f1 O
   p=num;7 B, @4 i) o+ E  ~
  for(i=0;i<n;i++)
/ U% p0 J! Z! I9 T6 o    *(p+i)=i+1;) P: l( R  Y4 e7 x
   i=0;
4 i& ]/ H1 ]" B   k=0;
8 ^, ^8 g7 t  q% q+ N( \8 S   m=0;
$ b( |! A. R6 T  while(m<n-1)
- m, k, O9 [4 u8 U8 H" Y   {if(*(p+i)!=0) k++;
, J/ i! ?% _1 C2 u& E' P     if(k==q)( ~: k2 C4 o) [2 `( D) ?5 q6 b' [
      { *(p+i)=0;
' |, T$ p  w3 {: j1 e        k=0;' R3 Z0 @& b# O( L
        m++;+ e, O; k9 M7 O2 b, I' _) H
      }' _9 u: f: {# e
    i++;# R2 O1 I* v" \$ d8 Q9 I( Z
    if(i==n)i=0;7 r' c3 u) j/ n" X( p: q; D, |+ q
   }% I" ]( B2 \0 H0 D* E5 r
  while(*p==0)p++;# N( V* G# P1 Q, x2 U6 N6 [! {
    printf("The last one is NO:%d\n",*p);( q1 O& z9 W7 D6 y' p& R+ G* ?
     getch();
; N- z# {! D& h7 a% Y; K6 H, y
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;, _  ^6 x, _1 U( o
namespace 又费马达又费电0 S' u: h7 c, z' @" A/ z- P+ B
{* {9 d9 Y: ^) Z5 P
    class Program9 @6 a1 @" @* M; |6 b4 @8 D2 T3 e
    {
2 n* ?( h8 G) B4 \* H2 \        static void Main(string[] args)
' r, }! ]# [' b0 p3 d4 H" u+ U        {  O, a+ ~  Z% V9 C/ A
            int m, n;
0 c& t7 k) s: ^9 T            Console.WriteLine("请输入数组长度");% A7 Y0 j2 F+ H6 c$ D. k; n( j4 e
            m = int.Parse(Console.ReadLine());//m为数组的大小
5 j/ I+ O+ Z: g$ x, y; ?            Console.WriteLine("请输入要截取数字的大小");
4 i5 O  G7 R# I1 \3 @  y" J            n = int.Parse(Console.ReadLine());
3 z7 o# a$ v& V$ I' T            int [] numw=new int
7 R0 U' t3 K6 O0 E( L0 E8 n3 r
8 y$ I5 P. H/ f- S0 N0 E&shy;&shy;&shy;;- l1 _" l6 i/ \, Y# v0 [* b( D/ P6 m
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
6 m* ^' ~0 Q7 X" A            {
/ c' u0 ~: V4 L                numw[j - 1] = j;& c' ?4 G! P1 V% u/ [
            }1 O9 u" Z, ]' r6 ^. ?% ^8 W
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!, m% q( C- s$ |8 v
            while (d != m - 1)  A3 P8 ^- W% U2 {- W
            {
8 X" K$ n. v; z, [6 a% W0 u                if (i == m && d != m - 1)
  ^1 L* D8 N( c# a3 z; o( r                {
7 \# H/ _; C4 N9 [% Q# g- p                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!  s+ h' H& X5 r$ U9 X
                    continue;0 A2 v% ]) J1 W% X! H
                }. N, i% n; o! Z2 s1 A, f1 }
                else; _# F- i% j" K  ^  r( ?
                {
( N" I8 w* v) q                    if (numw[i] != 0)
0 J1 b% {. E( l/ y                    {: S3 P5 L0 ~( _$ @$ s
                        i++;
4 q$ d/ g4 s7 k2 R                        k++;
+ W* b5 B0 {/ f1 x' w/ w                        if (k == n)
& H* W( e9 z7 N% I                        {7 O! d8 N" a; [. ~4 |& d' j3 J
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了. y9 A' {3 e5 a( g" E0 L
                            k = 0;
: ^% q- S6 k! C- a% \              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小18 H6 {9 _2 s2 Q  q- K- |
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);, E- A( z5 V! E6 u
                        }- q; [5 S' y8 F
                        else//输出暂时还没有改变数组元素的值1 S, O  }; [/ P& g
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
6 k0 l6 t: B/ H' [# N                    }
- O  v% H% f' }/ M  b                    else
5 L) E* i7 |% y" m                        i++;//数组元素为0,直接跳过,不计数。。。2 O, X1 D$ v  N/ b- B- V
                }& P( ?' \+ t- e( p

+ D+ I, [/ l- k& t9 U  [+ o
2 B! q$ l! a2 n$ u8 `5 N. H" D            }//结束while循环
( \+ p1 I1 F0 w' V# D. ~) H! Z            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
4 F. g0 g2 x, s! C# c  N           5 T7 l; U7 r* w2 f
                if (numw[i] != 0)/ c* E7 O/ _' z
                    Console.WriteLine(numw[i]);
% ?2 O, o6 }; z  E6 K& a4 R/ ?           ( q* }( o/ M1 `1 p
            Console.ReadLine();6 w# x9 h4 i: ]$ [5 u3 a$ K7 m
        }# U  W! ?6 \2 x  O+ g/ l4 g1 P& j3 T
    }
* h! }5 u4 c* U# Q( X& [}
& R2 E4 |- M7 m; E/ L. d7 O8 Z- S( Z& 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, 2025-10-14 13:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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