鱼C论坛

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

猴子问题

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

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

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

x
大家好!/ W: c; D+ B% \- c
这几天我在忙着编一个问题,我用了一种方法编出来!
$ l6 {( A) [$ y  l3 ]+ r' ~但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!; J: P/ R0 s% }4 \, X
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 * y9 ~0 Q( y: G
- J* m+ L/ b+ \7 I% v" [3 w  o
. T  Y9 \; V! ]: l) h
                            题目
6 _4 u. Q9 l1 Q5 f" g" T! y山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
3 T# o2 q6 j) u第一种方法:利用循环链表
- Z; V% \1 o* C0 m#include<stdio.h>
# V6 v4 r* U6 P& C' `3 v3 d3 Q#include<malloc.h>$ {5 c4 M1 m' v- w/ \( Z' u
#define M 8            //共有8只猴子3 O3 z8 z& u9 q; m) `
#define N 3            //数到3只时退出第三只: ^0 B. W: `# S, X. x( ~2 {% _
typedef struct monkey% I$ I% s3 ^. u
{int number;- T) y! r! V4 O' G3 @, _) v# q  g
int flag;
& K* i: x& C& h. g  \2 h7 _0 rstruct monkey* next;
& n6 V: F/ y% E, O! u/ t; M}MONKEY;
  c5 m4 r4 G, K: ~; U8 ~main()( M0 v/ v: I! ^& {
{ MONKEY *head=NULL,*p,*s;
  N) w# r0 G+ {" M* O2 o4 m  int i,sum=0,count=0;# S8 _. y( d4 d# \- o& ~# G; j  j
  clrscr();              //清屏
# X& J; o. P) `5 g% t7 v* C  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
* g$ z2 g1 A& N% g  p->number=1;p->flag=1;0 z& P4 ]9 \0 B1 e3 t; X4 P  A
  p->next=head;5 S' b5 c0 q( \( \: n. x/ @9 M
  head=p;0 H7 E$ c( B, l2 V9 r
  for(i=2;i<=M;i++)
: R  }$ e- u$ [. @. \    { s=(MONKEY *)malloc(sizeof(MONKEY));
5 D3 J8 |8 R9 c7 B; l" a     s->number=i;s->flag=1;/ \1 R3 D$ ]' f4 o8 `
     s->next=head;/ h( [8 u7 D/ u4 a/ f2 |/ b3 z% s
     p->next=s;p=p->next;' G$ B1 K. N1 H6 w/ |6 {. y
    }) C0 c; t! _4 C1 J
    p=head;) F/ z6 d: g# D3 |
   for(;;)
$ R% `$ ~' _% c5 v7 |* V    {if(p->flag==1)
" R! P5 y( B# K' t3 k       count++;
4 E; h" x6 _( J1 @     if(count==N)
' S6 D$ }2 s8 a& L5 G* p. p/ K5 c        {p->flag=0;, s$ H3 r# Q- F
         count=0;& v1 z: {8 E/ c/ x& k/ ]
         sum++;}
& o$ {7 _3 P4 M2 V# n1 H     if(sum==M-1)5 W) h7 C; F' H7 B
        break;5 A' W; ~, A- J4 ?2 l* s4 T" Z
     p=p->next;
  p& v9 u2 K/ [5 H    }
1 B, w0 x* Q' l1 L$ Z2 w    p=
  \0 I  _5 ^: s    head;
+ x  q! r" P+ l" W  q: F    for(i=1;i<=M;i++)" t" p6 B, r3 n/ G$ _6 @/ c; c
    { if(p->flag==1)
2 J2 K" w6 l' Z/ Q. E2 D        printf("\t%d",p->number);
; E. O4 h0 t, r( J* q/ f% }      p=p->next;, y' x& b& E* Q) Z# D# A
    }
# R8 \7 H" B6 y% ^" Y# {
$ [+ {5 ]+ Q$ U6 t! e6 p( E+ U, G# G# ^. R0 M9 \" L

% J) ~' G5 t: x& @: F! E}
% K- V- q6 X1 m$ |, L; g
第二种方法:数组
+ \4 P+ t8 w, b1 V5 C#include<stdio.h>
' \% U. e: _5 B( h  q9 c#define M 8& j) z3 O% I, i+ w
struct monkey
& X6 u9 |+ n9 k! i/ N+ r3 O{int number;
# q, y# j$ E2 f) E1 `7 gint nextp;
8 q3 f" ~$ H2 l; `) c}link[M+1];
* s  v: @/ R1 j2 H! X9 U, A7 V) W+ r% a, A1 o+ |4 u: ]
void main()
/ Y! h: Q( E9 t* \  B/ r{int i,count,h;9 J* N- e6 H- U2 U
for(i=1;i<=M;i++)) E0 z. r9 i/ C9 i) k
{  if(i==M)7 |" T4 w3 \( H7 s; [& A( r! s
   link[i].nextp=1;/ G. e3 X! _1 q: L) }
   else0 u1 n0 J; G! ?9 {
   link[i].nextp=i+1;3 v" O5 G; x# R' D' m
  link[i].number=i;# r$ M" I1 E8 H( }' ]! r, x4 Z
}
$ z9 N' n/ V& Nprintf("\n");+ k% E1 [8 v, ^7 l3 q' e! {& J- K
count=0;' k# w; ]3 v/ }- ]
h=M;
5 X, K; {) U; Vprintf("依次退出的猴子: \n");
$ Z- o+ g, {/ |2 y% O, fwhile(count<M-1)- ^& D7 T" ]. {# M) x8 s: i
{i=0;; K* P8 x& E7 x; f5 U# R; u
while(i!=3)
" _- M- G; H. E& K) A5 t, e# v: L{ h=link[h].nextp;
  m( u( e6 [3 Z6 F4 k. w7 Y4 v   if(link[h].number)+ R8 I3 F1 v6 }+ F: S
     i++;}
6 `; [1 U9 ]9 x. O4 M: V
, X4 M6 V; ?4 A8 Kprintf("%4d",link[h].number);
9 e$ r9 I0 I. i) W/ l& v: N- ]link[h].number=0;
5 j$ c" r6 N0 C# G0 Xcount++;
" Q9 l5 e9 v. u; ^- W' y* ^}
6 l3 ^* t3 [% l  H; q" k0 ]" p3 T5 V9 w% g4 E5 L; H" i
printf("\n大王是:");5 A3 X% d4 A' E, M
  for(i=1;i<=M;i++)
9 x0 a3 T0 C. ?9 Z+ L# q/ @  if(link[i].number)
! C2 j# v; D# m/ x& z% D) ~* b    printf("%3d\n",link[i].number);
; s- x6 @5 c- U3 I. Q8 {) ?' z
* u9 u+ i8 {7 \' l: J" p( ?( ]* g* d* V7 x3 Q
}
1 k1 s, r; {" l1 ^& \+ Y! i
第三种是普通方法for循环

( [4 t0 I; M9 B1 c0 p% t# \. F#include<stdio.h>" q- ~4 ^- s9 l: b' |4 z3 K
void main()
) P' K: a7 ?1 K# E% ?{ int i,k,m,n,num[50],q,*p;
( l8 a. i  j3 h% P7 j7 ^    clrscr();
6 n$ c0 Q' U4 p/ s, Z   printf("input number of person: n=");8 V+ w8 f: t$ S
    scanf("%d",&n);; g  G- p' K. K8 ~
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
" z0 d, P/ @9 J0 x% |    scanf("%d",&q);/ g1 k# [8 w& R: S6 Z" d
   p=num;( @, M. w+ C3 m
  for(i=0;i<n;i++)
, m- W" {1 y; o    *(p+i)=i+1;
' m2 c- r9 S3 C, l9 I3 M: }9 y   i=0;
% c3 ?& y# N9 q" o   k=0;4 C9 v! x4 v9 H- R
   m=0;
/ U1 m/ w0 G/ F( p  while(m<n-1)& N* r0 o; Y* A" Z0 @
   {if(*(p+i)!=0) k++;/ f5 V# a' V/ [* Z& l7 n
     if(k==q)
! l+ a; ^' f7 D      { *(p+i)=0;, a( F( g& ^0 a  Q& X
        k=0;% p+ s1 \8 f' z4 V- d2 }8 s
        m++;
$ q; E6 W, p  v6 d6 d' Q7 _. f7 j      }. y9 s) \: k/ h$ }
    i++;* p, c; Q0 z( a" ?: T; [$ e" d. S
    if(i==n)i=0;6 b. H" Y) e1 x1 x
   }# }8 N. W& R0 m( a
  while(*p==0)p++;
1 K) r- W/ z' X/ n! O" F; ~8 p" ~& }, d    printf("The last one is NO:%d\n",*p);
# h' I# r& q! d8 v     getch();% s. s, B4 w* b1 E& Y. H  ^! T
' Z  w* ?+ m  J" b
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;9 H: S( v0 f6 H+ {& @- Y9 V" t
namespace 又费马达又费电) @6 A) d8 {. w3 d5 U5 F: O) H
{8 s7 h0 `  M$ t. L
    class Program! `8 W0 m) {1 x* F. j2 W0 A
    {
. e( ^. y7 f4 k( ?1 @        static void Main(string[] args)
2 x! B" Q" z1 B- L/ R2 {        {
9 @8 Q" ]" H2 T0 ^; X# f            int m, n;
2 x  ^1 _5 }" V; w6 r! |& e            Console.WriteLine("请输入数组长度");
) }  B: l1 ?- M4 n3 f0 M, f# ~6 Y            m = int.Parse(Console.ReadLine());//m为数组的大小# Z7 y& N  w% E8 R
            Console.WriteLine("请输入要截取数字的大小");
- E4 g+ y* c! t: x. u# y6 L            n = int.Parse(Console.ReadLine());
7 l, g3 _* a5 S$ w4 V            int [] numw=new int' n( ~( L$ m$ ^- }8 O( `
9 n2 e5 x+ Q& t' h( ^# r. ^0 q
&shy;&shy;&shy;;
+ V, g" F. ?- I6 i" v& @: D# z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数, _! Y  r( a# Q& ~3 m
            {
- m9 Y' g* Y) J) X  ]- P& G$ o, r                numw[j - 1] = j;
4 \0 F; Z. r+ k' V            }* X4 X+ c8 Y8 B& m
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!- U) ^* O( X2 Q& N: L. V
            while (d != m - 1)4 t$ ]8 p/ N; D5 q
            {2 Y/ _4 X, t/ f4 q0 C8 I& `* F; P' K
                if (i == m && d != m - 1)
  @9 t6 w$ n. a% s8 N  C1 h                {1 g0 z4 V. n4 L- g1 l8 L+ W
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
( i. N  y, Q& k5 ^: o                    continue;+ y: Y/ ~9 Y( ?
                }
) Y! ~9 P( ^0 M! D$ v                else2 o2 p  W" d5 d- }8 U6 Z% o$ E
                {
5 Z8 C/ F" M/ o) J                    if (numw[i] != 0)
* b, G9 _- O% I+ J+ e6 r* i; ?                    {& x4 M9 Q& T& L- b' ^
                        i++;
9 f( [! Z0 v5 I$ L3 g/ l8 o                        k++;2 ^$ |0 D) b; ^- m
                        if (k == n)8 p3 N$ j: L8 O& ^7 Y
                        {
# T& |1 @7 b  u( d: D$ e+ g& ~9 ]                            numw[i - 1] = 0;//把在n位置数组元素的值改变了$ S0 t- w8 z3 V0 f  G1 J+ Q3 J+ a
                            k = 0;
" C! k6 _+ I- k3 i              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小12 H. W) W! f! `
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, M* {! U* p9 P4 I$ t                        }
2 q/ m: ^- r: ^% G                        else//输出暂时还没有改变数组元素的值7 I- }0 d% D% B
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);0 y- Y7 [# u& L
                    }
6 {, l+ m1 \; u7 G: \: g& D                    else' f. _0 D6 K7 u, w, O( Y( L; M
                        i++;//数组元素为0,直接跳过,不计数。。。7 K1 c+ N. u+ e6 m# E' \/ W
                }
- P# D: Y2 Y- e  q$ {4 Y ' h- }8 A0 @$ h2 P+ ~

3 w: k2 H9 M5 N/ c            }//结束while循环
6 t) c* G2 O: E- F( i% I" K) Y- _( ?            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦, H* n/ e! O' W4 T. Y
           
  v3 C" m* L% M8 }  O: U                if (numw[i] != 0)( j9 z% d$ b' |) N+ c& D- W& x# A
                    Console.WriteLine(numw[i]);
0 _) E/ u2 c/ E; R, z& C           
  b* d9 V* _; M  \1 z            Console.ReadLine();
! M( g) g* A& s4 N4 Q( G3 j; }$ I2 R        }8 o" Y9 Q) X" P
    }
9 c+ @5 X6 V( c4 r: n}
: R1 M$ U4 l1 R1 E
小甲鱼最新课程 -> 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-16 23:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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