鱼C论坛

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

猴子问题

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

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

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

x
大家好!( l6 K7 n4 G, e( r
这几天我在忙着编一个问题,我用了一种方法编出来!7 b) D( N3 S- X8 o
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
3 r& z+ X" U1 w- d3 t( n注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 $ v+ Y/ Y9 _9 f& Z$ T4 `/ S
! n  j. ?( E4 z8 W5 g" O

9 u3 B* e) e7 t/ a( H# Z3 ?. z
                            题目5 L9 f, k8 O9 ?4 c( I- ~! O) t) Y
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
8 f* M* y+ H" Z3 O* o2 i第一种方法:利用循环链表  |7 g2 ~2 K# s9 n) l% l
#include<stdio.h>
# V* c. p4 n& h  w3 J#include<malloc.h>
, H: S' G' k  _, z#define M 8            //共有8只猴子( e  v* O$ f; z) g+ y+ k$ ]
#define N 3            //数到3只时退出第三只
9 C$ T+ ?: Y0 N1 w5 p0 x+ Ktypedef struct monkey7 J4 e0 \' c5 g8 `, R
{int number;- Z# z) S: K* L
int flag;
2 I! B1 g2 K7 l- U. z5 Tstruct monkey* next;
5 v4 {0 f5 x( b7 g7 E. V* l}MONKEY;
* Y) _7 y1 U" h# \main(), T# r8 y$ ^* V% d1 U* e( y: I5 y
{ MONKEY *head=NULL,*p,*s;- z; Y2 l1 D8 D8 K" F
  int i,sum=0,count=0;: i& u5 P; Z- @& _6 m
  clrscr();              //清屏
: F& k: E# m7 v8 ?* d1 Q6 J4 U- w5 _- ~" w  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存1 [: d( L/ h- M' \+ }
  p->number=1;p->flag=1;1 G( z, |  o/ u" w6 x0 E0 k( J
  p->next=head;
4 F7 s( d  a6 H  head=p;1 ?- Q! B1 @$ K1 o( A4 m
  for(i=2;i<=M;i++). p! k$ ]# Q* X1 Z
    { s=(MONKEY *)malloc(sizeof(MONKEY));( z8 D- D" n' O! R" v' w& n
     s->number=i;s->flag=1;
; P* \( a$ z9 ?1 e     s->next=head;
% U) Q# F  t" D+ d% l     p->next=s;p=p->next;
4 i0 G' n/ h0 t8 e" O    }( E/ v  b0 ?5 \4 O! y5 _! L, x. [
    p=head;
) \& _$ \+ R4 X6 S) M7 G/ [, b$ I   for(;;)4 X8 g* W8 v9 n8 ^- C  x
    {if(p->flag==1)
  p: l7 _) C% c+ c# |" j. B       count++;5 V- K# A  P8 E. k/ }0 e5 n* z
     if(count==N)/ Z5 l0 Z+ _& t- ]2 o5 @1 A
        {p->flag=0;
: Z) o  x0 n) E$ K         count=0;, E. m7 F0 l) v" ^  Z; T3 s
         sum++;}, E. z* o& x; @8 i" J1 N6 p
     if(sum==M-1)
/ |- G% A; q6 E3 a! a6 K        break;* h* T) ^0 G) a8 W2 o
     p=p->next;
& V! r4 x! h: @& ]" O    }3 J1 E! f/ l6 r7 \! }: i$ I5 U  y
    p=
( L7 _) Z, P; p& @" r    head;7 I5 P/ ?) T/ [
    for(i=1;i<=M;i++)
% Y" {. E% I' r7 G4 j, j5 `0 B' N& r    { if(p->flag==1)
. v  E2 f8 I. g4 Y0 c: F        printf("\t%d",p->number);$ m7 y7 E6 `7 V% e, _- ~; g
      p=p->next;
3 S7 R) _3 l  d- b    }) x6 T. X3 e" K4 s. N( g( l

/ G: j% {' C. Z5 q* \" U+ E) W5 I1 z2 W4 H! N* C, G( I0 c" q

  {/ k& h7 J$ D" W}

9 j' M& g5 a9 G, q8 k( ]2 \% F第二种方法:数组7 q$ ~0 o/ Y7 i& Q
#include<stdio.h>
: S0 E9 Z  \, O/ @; y: R#define M 8
( U* c  {3 N1 @. i% R9 A5 Pstruct monkey
6 k* l! Q" T' ^& p8 ]8 Y: I/ I- V/ Z{int number;
0 ]  Q: k) E/ Y8 W$ Nint nextp;
. o  J& G9 b! ?! {& `2 e}link[M+1];
% w7 V5 g: q' b  E/ }. u4 }; ^3 q. f( `
void main()
7 l4 L: _1 `4 \{int i,count,h;. o$ ^: P+ C) A+ C
for(i=1;i<=M;i++)' u8 e6 k0 ^& P- f; |) @
{  if(i==M)
1 a+ Y' W; T8 X0 d8 a- e   link[i].nextp=1;: h$ ^0 G$ p$ C$ u
   else
  k9 q3 w; W6 C* k   link[i].nextp=i+1;
) U3 T2 {( a$ D7 ~$ z  link[i].number=i;
/ C" h  T+ [7 `4 X. R8 ~0 P}
' d# U3 o' a9 {# C1 eprintf("\n");0 u- n4 {! r' G; g! u. _9 O. D
count=0;1 f6 I( x' |% u- o6 k! V- A. c
h=M;2 y+ l. c" }0 R1 S: H
printf("依次退出的猴子: \n");
/ L# E# ]* Z. N9 L9 Zwhile(count<M-1)
/ ~- k% B' [' w6 V# h& r# y: M{i=0;
3 E2 k3 ^2 X& e% p6 s+ A) kwhile(i!=3)
8 o  r$ K! w% @1 o; G6 I3 k{ h=link[h].nextp;! @8 c2 y* z" N2 w2 M
   if(link[h].number)# Z$ N: a" X* T$ K% q. ?2 m
     i++;}
& P: |) U- g& n& U
( c  P, t$ E) E; [) B' u% |printf("%4d",link[h].number);
1 C1 J2 r% C" T0 K8 O7 Blink[h].number=0;
' I) a4 S5 h% A" T; ^: a% w0 X/ vcount++;
* W1 r; E5 p* W' n}4 N! m* s+ y$ m5 ?

& P2 [; P+ N# d( R. dprintf("\n大王是:");
( l. B% h1 ~' b3 m) K  for(i=1;i<=M;i++)$ r6 T8 U  W5 q. X
  if(link[i].number)' D4 E! {! y9 p
    printf("%3d\n",link[i].number);
7 L6 b) V/ @7 [8 N4 }( r# G( E' T( G7 w
, x' ~9 P4 s' I3 F, G1 o
}
4 ]# A6 q1 ?7 g" l, K% {+ @
第三种是普通方法for循环

  i# t) T0 A; B" N#include<stdio.h>
, |% J0 y* X5 `' s9 c0 @void main()* T  C3 z. L1 I
{ int i,k,m,n,num[50],q,*p;
, `% ^. |! J* S- j/ T0 T* z    clrscr();% |/ p- r7 m$ `9 h: N
   printf("input number of person: n=");
! Z4 K5 w: d$ i2 B$ C; W- M. P: N    scanf("%d",&n);' H2 A! w) ~- u
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只  \( M' y, D7 E6 k. m* z
    scanf("%d",&q);
$ w8 ~+ o* a# {- P   p=num;
7 r+ X7 c9 Z8 J# S  for(i=0;i<n;i++)+ E& C# e+ X+ u0 V/ P6 P  \/ v
    *(p+i)=i+1;
; _* H4 h$ r4 U' f   i=0;
  j: A. \  ]0 b/ r   k=0;' f2 A- W0 z- s+ o. j- q8 T# t9 p
   m=0;- I; D0 G5 T8 B7 Z
  while(m<n-1)
8 P+ l8 Q4 E- |9 M2 z$ r3 q   {if(*(p+i)!=0) k++;
: }  d/ k* I( U0 y4 y) F) P6 a     if(k==q)
: g- w0 K$ C  {+ u5 z" p0 j      { *(p+i)=0;3 G% b2 P' w9 @# f) D
        k=0;
/ d# y* q, F; j. t  v        m++;
; \! a7 C" x! X      }" @" ]7 r# p( {- j: }8 L
    i++;
: S0 x, B3 u2 C% u; v    if(i==n)i=0;
) Y4 x6 h% T4 Q" F) N/ `   }' ?$ D/ m& S) C
  while(*p==0)p++;7 x/ v/ {8 U1 g, o4 {* v1 V% {$ D* M
    printf("The last one is NO:%d\n",*p);: O# z1 O, U* f9 W) ^
     getch();! v1 H  a2 W! |% e7 Y4 _

" a1 t8 C' q; D0 G5 ~}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
+ h9 ~4 j' G+ ]5 @) [namespace 又费马达又费电
) |) ]$ J7 v  b) o% i{$ Q* R% f4 o8 L$ L$ X5 _% i
    class Program% ^% h' S2 x- K" e" P0 I) f
    {  O% [  q, `# b- K7 d
        static void Main(string[] args)
/ H) ^: Q; x* y* F5 [' H! [        {
' @. I2 n! y; I; Y8 Z" u3 b            int m, n;
% H, e/ `* w8 I- R            Console.WriteLine("请输入数组长度");
8 ^* G6 r" x, W* I* G6 x; k            m = int.Parse(Console.ReadLine());//m为数组的大小
% ~, p  L4 S8 a& o            Console.WriteLine("请输入要截取数字的大小");1 w# h, I9 k% S0 `
            n = int.Parse(Console.ReadLine());
* K8 M) B( D/ w  P3 O) m            int [] numw=new int
/ c! r: n6 h& w( _, m0 a. \+ E- I
! J& I( h6 U* ?' d" d9 r( H&shy;&shy;&shy;;
! A1 u( P; S/ r9 _            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
$ r4 Y5 p; h3 O- ]* J1 @( I            {
( U/ e7 U) d( x# w; ^/ H3 p8 ]) H( z8 Q                numw[j - 1] = j;5 {, d: [+ k; C+ q. t# o2 W
            }' S. {1 L; x4 V* h# t" B
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
# ^7 U  ^" {* y+ O            while (d != m - 1)6 J3 q) G+ `8 w/ `9 V
            {, V6 x2 `5 r  O! `
                if (i == m && d != m - 1)5 K/ E! s2 X3 e- {
                {. T; O8 j' o3 z5 ~
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
3 m/ W2 M6 a' N' \, L7 M                    continue;. ?( d% R8 V7 V2 D
                }! S2 n4 P' O3 u+ M
                else9 n8 l9 H/ h" ^
                {% p' D( L( e7 z3 T
                    if (numw[i] != 0)
# \$ C& ^6 N" \6 U                    {) c* h5 k' p$ Y; K% H  [! C
                        i++;/ K& V1 T5 W- T' B
                        k++;, e* c& ^  A3 O; P
                        if (k == n)
0 a' L' e2 x' o                        {
, p: B8 w" _% D                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
( |! l/ m7 I8 X+ Q                            k = 0;- m$ u- B1 Q3 j
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
& C6 U$ L* ?# u( m. s+ n                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: O7 l* _. j3 p. N1 M5 a2 z
                        }
: z2 C7 `4 e! c6 y                        else//输出暂时还没有改变数组元素的值
  d) N  U& c& V  x. z                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);' V2 q& h3 j  a% Y6 O+ m0 k+ K: t
                    }
8 C6 m  b$ w. G. ^$ I) P                    else
& E6 F% }" c/ Q8 X& r                        i++;//数组元素为0,直接跳过,不计数。。。, I9 X$ X' y6 E  s5 D$ T
                }% i( O/ d$ f% Q/ I1 o2 h% J5 [
1 D0 U# W8 p  J# V  H/ A
1 E3 {8 m6 t; w2 O6 n  C8 D
            }//结束while循环
" h3 ]* i; ^; U3 m, h  X7 f            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
: {3 J: ?% d  K5 Q5 g5 x2 k1 v) Y           7 K) f& a7 O. _9 n; B% ?+ L3 B6 T. H
                if (numw[i] != 0)
4 w4 y( i2 F, o' ~/ v2 H9 o                    Console.WriteLine(numw[i]);
3 R7 }& x- W: L" c           
6 p7 G, @% |/ j            Console.ReadLine();
+ Y0 ^. F  ?& ]9 A5 w$ p& a        }
; A4 N* w6 z. x9 W' M0 j+ B    }) p! a8 S& u% Y  ]* U8 u9 C
}
. d. r7 T8 f6 t1 y
小甲鱼最新课程 -> 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-1-19 11:40

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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