鱼C论坛

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

猴子问题

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

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

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

x
大家好!& h: l1 _4 U: @5 f' R
这几天我在忙着编一个问题,我用了一种方法编出来!
% ^2 Q$ D/ P: J3 w: i但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, p, E7 x* M* }/ o! x) P5 V
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 9 E' I' E4 u6 d' _' s  Y/ K: }

9 V+ q. `* _% K# }  j$ U$ C9 s% C$ l1 `' ?- @( [* u$ ]
                            题目
) c/ g1 M1 i& M5 I2 W% c  a' i1 y山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
# b  Z8 q$ X( v+ l3 D第一种方法:利用循环链表% b7 i( I  o1 p' c
#include<stdio.h>* U1 ?( n* R  z9 B% e% u
#include<malloc.h>( ]1 f: A& f' _# E) B
#define M 8            //共有8只猴子
2 \3 I- e& ~3 I7 v. ]1 ]#define N 3            //数到3只时退出第三只9 x/ N3 o4 G4 F
typedef struct monkey- g9 W/ i% |1 \% t9 O0 p( F8 O2 w: e
{int number;! z# ^# k" N: f  |. h) f1 {
int flag;4 U+ q: F& b4 {- R
struct monkey* next;! c  A  h2 K8 Y7 J; G( u/ T
}MONKEY;7 r! t" Q7 I. V/ Y. U
main()
  |7 }' z, u+ G0 W- q# }1 o{ MONKEY *head=NULL,*p,*s;
. Q% ^+ ?) H2 O0 `6 d3 ?) G) |  int i,sum=0,count=0;+ Z* [) x4 t3 ?$ H7 U( {' z
  clrscr();              //清屏
+ L& O0 S$ v$ v8 e  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
: f8 S( t7 s) p* L, Y7 S1 `  p->number=1;p->flag=1;  @4 e. K* @% D$ L- e+ m) U
  p->next=head;# E' [: g$ m  c( e. o  r
  head=p;
, r+ x5 [# q$ k; R2 A  for(i=2;i<=M;i++)
+ T- P4 x4 g- x5 V    { s=(MONKEY *)malloc(sizeof(MONKEY));  a6 \; p1 |* X8 ]
     s->number=i;s->flag=1;. |3 ~7 \$ x- z$ P/ h: i8 t$ x+ X
     s->next=head;
# c+ R7 ?7 V, J! F     p->next=s;p=p->next;
- u3 v3 N, k+ {0 ]  l2 {/ F3 L6 e    }4 Y, f/ q/ C8 B' s1 i& `% C
    p=head;8 x8 M4 T, b$ N1 y1 K
   for(;;)
9 Y6 L" |; `' j' g+ Z5 B    {if(p->flag==1)
; \! R* {8 B$ ~) c       count++;
% G# V) C, k  t. b9 L7 D     if(count==N)0 R) e* G1 E$ S( l. n/ u* Z
        {p->flag=0;/ v! O& {2 v4 p0 U8 E8 y
         count=0;& k( n$ _- ^6 ~9 {! G
         sum++;}
% n; |- Z; R9 S! M4 ]     if(sum==M-1)
4 U( }  w; h8 R0 M" s        break;/ J, M$ J$ E3 c/ ]
     p=p->next;, w2 u" }. }, [: n
    }- Q9 r) u* I; Z8 A7 A! k7 \% d
    p=
/ f, \+ l6 U9 K: B( b# {    head;1 |( o: |8 f# s& n
    for(i=1;i<=M;i++)
0 n% S6 x( @# G+ D3 |- r    { if(p->flag==1)" z5 x" V+ w0 z5 P$ ?  [4 _) }
        printf("\t%d",p->number);# f- {/ {& p+ }6 o+ A3 \( x: x
      p=p->next;- d3 x0 o/ C+ d, n& W
    }4 v1 M' e) R$ z8 M

  A' y0 w9 b& x
9 A& K* |) x0 |% ?
" H7 d" f, B2 n  a6 W0 m' [" W}
( f9 |/ Y( K- U' d( t) ?7 N- O
第二种方法:数组
9 f/ Z' D% k6 x0 w1 O+ l" J% C#include<stdio.h>
9 m6 C6 |3 z( H- z/ ]/ }#define M 8( \2 R6 j& U5 n8 ]
struct monkey
- m+ R) l* S* x1 \3 c. H& W{int number;6 Q$ P; A) d4 v# ]
int nextp;, k* q6 x' i0 D& q  M/ n% R
}link[M+1];
, `; p" Y7 u, k+ T* E6 V" y. l
3 M6 d$ ?5 M# h, kvoid main(): i9 l  H6 g  F! J1 M4 G
{int i,count,h;* t6 A# w( i5 R, ]
for(i=1;i<=M;i++)* x( `! H$ T+ y& ~/ I3 k+ F
{  if(i==M), t3 {; V. J) U6 g4 C+ Q& ~( j  C
   link[i].nextp=1;
& _2 h& L9 Z" ]" N   else$ c5 p+ {2 L3 j9 H
   link[i].nextp=i+1;# [$ U- G& O( l& ?+ `, k0 Q
  link[i].number=i;* V* h/ U# W' ]& W8 _! {
}$ O, [; H5 e5 W4 V- j5 e
printf("\n");& J1 d! Z. E! u* y3 J- i8 X
count=0;
: o  E) B7 y* a! W; t* oh=M;! I- i6 K8 u5 y: l) v+ ?& C; E
printf("依次退出的猴子: \n");+ j6 g, N7 ], U2 ^, c. j8 M. `. N7 H8 \
while(count<M-1)
5 E2 n7 n) ?, ]# X{i=0;
2 _" \' T/ A. @( c/ mwhile(i!=3)4 x7 T/ ?2 c5 ^1 G
{ h=link[h].nextp;
- C5 m* }2 a+ A6 G$ n+ C3 y# h   if(link[h].number)
% X# c. K- t+ q% I+ Z     i++;}
% u: y6 b* X2 c$ g
2 p- h* E  k; p6 _. v" G1 [( n& x0 _printf("%4d",link[h].number);. g8 u0 f# w' U( Z4 p- R: S. s2 L
link[h].number=0;; V1 g/ i1 b; ~2 R' T
count++;
7 v7 z9 K* M- ~' I5 P}" J8 ^' H; u, P# ~" M7 [2 y
! i3 O' w8 T! W
printf("\n大王是:");
; }2 ~3 G* X# {- I3 R  for(i=1;i<=M;i++)8 j; \+ B; E5 W# |+ B$ y2 n1 {
  if(link[i].number)
7 U6 t, Z1 A' b, l0 [    printf("%3d\n",link[i].number);
% w2 J! h6 Q6 B0 e8 l. H
, x8 N7 ?% P% J3 Z6 C9 a# h8 D* ]* A  T
}

1 _5 N5 o/ o. l第三种是普通方法for循环
2 J) t- R2 U, }
#include<stdio.h>
' M' {( ~) o* t) Gvoid main()8 o" t+ e2 z  t
{ int i,k,m,n,num[50],q,*p;
/ X) _2 \' l- A  M    clrscr();( |' S: v/ y4 X' G! A
   printf("input number of person: n=");
6 c6 }. x1 ]" l  ?    scanf("%d",&n);9 ^  I7 u$ l; }. u
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 t2 {$ d% I$ E5 `3 G' H5 R) y1 E    scanf("%d",&q);
' I8 D$ `" [9 ]- A' t- ?   p=num;, ?1 B- N3 i1 H  N; ^; u
  for(i=0;i<n;i++)
/ v$ L  D( v1 v  s+ O    *(p+i)=i+1;
0 |. \; T: [8 l   i=0;) p* y! f. f. g1 Y" m! |
   k=0;
  T$ r6 s! t" u$ b& I4 D4 ]   m=0;& Y' d# k  p5 R5 {# n2 E
  while(m<n-1)
* ^  \- R. b. x  ^" G   {if(*(p+i)!=0) k++;7 a" I. K/ q2 q& z+ b
     if(k==q)
0 [+ p' J" G  w9 q, m+ u% e0 M, ~      { *(p+i)=0;4 n5 H- C" {/ y# M; q5 O
        k=0;
+ m. }5 r3 F+ [9 U# g6 @        m++;/ Y' w& i6 S" G- y1 k2 g
      }% V+ G7 t% |8 H# T* Q& `: ^, D
    i++;
. F7 L1 P# v. O    if(i==n)i=0;
6 F  \, E, R- |) z   }
3 H0 L+ i7 T- y% N2 f* \% [8 T3 ~; E  while(*p==0)p++;
+ v2 }$ t9 p. n8 r# f) u1 N    printf("The last one is NO:%d\n",*p);
$ }' T8 q4 f7 b. d0 q% d     getch();6 C7 }( t* l9 `6 `+ v
4 K0 J* q0 X/ R3 e
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
/ i" S8 Z3 B/ k( Ynamespace 又费马达又费电- l$ m" [. @& T
{
$ M9 [% M* r; j  I6 m5 o# f" P    class Program
( M( s7 S7 |$ @    {0 B- t5 c- y. i9 A, t( i
        static void Main(string[] args)& l% A! Q. c" s
        {2 k7 W8 `, N) [* x# ?1 v
            int m, n;
/ V( g+ I* b6 f            Console.WriteLine("请输入数组长度");
+ x5 K0 `( X2 V" B) L; h9 I            m = int.Parse(Console.ReadLine());//m为数组的大小: o- `9 ^# h+ t' q+ {* q3 s+ s
            Console.WriteLine("请输入要截取数字的大小");7 `# s- E" n  [# Q2 [9 E+ d0 v' B- s% M4 Y
            n = int.Parse(Console.ReadLine());
4 r( {  t0 h7 F" [7 R' u            int [] numw=new int
9 O) H; k1 G4 M' ?$ w' e; A
/ B) c3 g2 [) X. ^6 H# t$ I7 T  M&shy;&shy;&shy;;' b; ~/ g+ t4 \- N/ r- b7 T
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
; ~+ A" }- \3 F            {
9 G/ i$ }2 A! i' A                numw[j - 1] = j;
; E) t# Z3 y. f" ]' H            }
; ~0 n  r+ S8 i+ T            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!' a  H% `# Y2 g
            while (d != m - 1)
) J9 }6 p; u) p( m! Y8 V            {
) D/ n, k% A# L: y4 C9 W5 D                if (i == m && d != m - 1)
  g: i# F1 d+ ]) o4 L' K                {  K- D/ g: [) q4 n
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
" J5 X& b) R" m. E: w                    continue;
7 n3 B! n! k; ^                }' P# U  E) R) j7 i8 m
                else
" j5 a' u3 }' M                {
+ K& X+ _' A. e& r" t  j3 l. Z                    if (numw[i] != 0)/ x* }* v$ z5 i' W. r
                    {2 r2 s$ [' X3 d7 Z
                        i++;: I- @5 f( G/ e3 n( |' S
                        k++;: |1 K; a4 b6 G1 R1 A1 I- D
                        if (k == n)# Z/ a" p# u/ |& N5 x8 X
                        {8 H- V! L/ ~& c/ p, A
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& T5 c4 A3 w8 i& ~* I8 t% |
                            k = 0;" |1 K  z9 |8 C% X& l
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1) s% e- l; g5 [" D" e' Z, v0 G
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
2 W9 k: W* s; J! Q                        }) E, }0 N/ p8 ~! Z# B- x+ K8 z
                        else//输出暂时还没有改变数组元素的值0 E1 M% ^: D! J+ t2 h0 R
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
% F1 S" i& C6 X# X" V                    }+ x* H  d: m# n& d6 M9 g
                    else
/ O, t& A/ v" B                        i++;//数组元素为0,直接跳过,不计数。。。
% ^* j$ ^: d! z                }
: m9 F$ n' i2 c/ R& }
$ M8 k5 w) U, N+ v/ r0 p4 d. P: }: T  \! N, j( _9 L" X1 I
            }//结束while循环; w$ U5 v2 J0 N7 X. h2 H
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦8 I8 Q9 R+ K9 _! E0 w! K- A
           
: m2 r# x# \! R% N7 B5 P8 X2 e                if (numw[i] != 0)1 t8 v- M; U# u/ o1 E& G, B
                    Console.WriteLine(numw[i]);
0 U  p3 V- v  W6 Q5 A& R$ b4 V. s           9 e/ X2 a8 S; X( H" B7 R
            Console.ReadLine();8 H! O+ ]' D+ J/ p
        }
" R7 V; e' \( |. ]- e9 F! M    }
) J; Y3 o( ~) H8 H/ S7 X, Z}
0 V0 p9 }6 @* z' n8 ^# }2 `, R
小甲鱼最新课程 -> 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-20 15:13

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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