鱼C论坛

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

猴子问题

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

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

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

x
大家好!) ^4 B) d; b& ]- p$ s& L' G
这几天我在忙着编一个问题,我用了一种方法编出来!6 m" x$ ]. j, v/ u5 _. H; @# J
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
) E, a; W6 @$ L$ F8 c. s注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
/ A. }4 t. g9 e
) Q8 K2 Q) y- S) Y6 |- j* R$ d1 T$ i; r0 A
                            题目5 M, @+ H5 G- V( W/ S
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。; ^$ m+ r5 N% V2 Q. y( K. n
第一种方法:利用循环链表5 C" h$ ?- N5 t' A1 o
#include<stdio.h>" Q7 n9 c% q/ @( _) \
#include<malloc.h>4 X! a! H0 x- R) M# }
#define M 8            //共有8只猴子1 L9 E  ~# F. N5 B/ V
#define N 3            //数到3只时退出第三只: Y7 H/ k) R* n, L$ v
typedef struct monkey& w7 o, }$ w+ H. G* V* @; M% L! q
{int number;
7 k' H5 z5 N& B$ [, D- j8 Uint flag;
! G6 |/ n$ v6 w, u9 V* C" xstruct monkey* next;
, D$ X* L- t  ]6 O% \" o& l1 ]}MONKEY;/ {) D' U; p5 H1 g
main()
& X( R- U+ ?) I" S0 \, a  u{ MONKEY *head=NULL,*p,*s;
; R, T3 {! t9 G! @  int i,sum=0,count=0;, {8 m& F  X. t' N! |+ X
  clrscr();              //清屏
4 O. M6 ?  v6 A: i  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
; Y) I- Q- N. d  p->number=1;p->flag=1;
# E* [* s* U& G4 P5 r9 e  p->next=head;
/ ]6 S8 i* W$ t9 F  head=p;* e. ~2 o4 Z3 \- Y. l7 u0 Q" e; ]
  for(i=2;i<=M;i++)5 }( G7 S, w& h" O4 L
    { s=(MONKEY *)malloc(sizeof(MONKEY));
0 E  u, ?0 s( B& I$ C  U     s->number=i;s->flag=1;
2 n5 k9 N5 N- X  j8 N     s->next=head;7 E" f: A" l! v9 c+ N6 o: h8 g
     p->next=s;p=p->next;5 E( \7 b) K3 [$ @' x
    }
4 \, i$ j5 F0 {# K  `; V    p=head;& R1 Z1 [/ n' Y' d, w; c9 |, e$ {: d
   for(;;)5 P5 N% V+ T! Z! k2 u
    {if(p->flag==1)$ r- F; M: I( e' v8 v
       count++;
5 k3 {4 K3 e8 i# I; q+ }! F     if(count==N)
, [; w# e$ A( {8 J& N0 K) z        {p->flag=0;  V. ^9 n6 T( F$ y  g# L& G6 F# o
         count=0;
- c6 j1 b. a5 O! z* `$ L5 Z         sum++;}
+ {' Y3 W/ f' f3 a8 m1 o5 i; w* y  ?     if(sum==M-1)
2 r, @1 U7 a* Y3 F) z$ l9 s" E! K        break;
; R, x3 F1 Y. I$ S     p=p->next;
0 T) Z& r/ L6 M    }
! e& I1 X* c4 I/ V    p=
' s& E: q& h6 ]2 p; p1 h1 D6 G0 U' e    head;
, ^9 H& `' ^" j3 {* P& A! f/ A    for(i=1;i<=M;i++)+ @4 }- C, z" j6 V0 F
    { if(p->flag==1)- K2 p7 R; p6 N. g
        printf("\t%d",p->number);
! s% h# L# @2 f0 b      p=p->next;
: n! i% \) L# ^) @( b  v% q1 ?% V    }3 ]9 x- B# B  o& C
, s* X$ P2 U! B. @! |2 I* D' D

" l# Z2 W! d7 g- A
1 Z/ |; d7 A4 X- s2 @: o}

) C9 Z' y% }# X# r0 H" ?第二种方法:数组3 F' x8 d3 X8 [: K
#include<stdio.h>
- p7 [2 I+ Q! b; |1 F  o0 `#define M 8# R- C) G' D3 u# p5 t
struct monkey
5 ]/ r# W0 F7 Y+ D: J: r& _{int number;
) V% L( G& `" c/ C3 h0 vint nextp;+ c" C# g( B1 z2 g) k; j- t
}link[M+1];
; m9 s9 }" ~! Y% m3 Q" P1 F! q6 |7 i
void main()/ P, d& h  t2 W
{int i,count,h;$ l& v: T0 H3 P0 ?
for(i=1;i<=M;i++)
- D  i; o5 @' W9 A% L{  if(i==M)
* h9 r3 n0 F$ w   link[i].nextp=1;
- O! V  G3 U# s& t- ]; a* N   else: K" q& [) u( B& y& e
   link[i].nextp=i+1;
# w2 }( q# G( P9 n- Q6 y9 |  link[i].number=i;
9 r, l, P& ?5 p" Z7 L& g8 i3 x}1 E( u6 S# H! w+ U- |, C3 y7 n8 ~
printf("\n");% O0 e" n% |7 ?4 N4 R
count=0;. n3 |+ v1 r- \' i& I
h=M;+ x0 v! p6 f2 y' U; S+ K
printf("依次退出的猴子: \n");- J5 |3 O8 ^0 G
while(count<M-1)
) I' U! X  o5 O7 O- d* u0 `9 b0 e{i=0;
& ?1 S3 Z+ s* G) N, @( Zwhile(i!=3)) S7 H8 m' o! q1 m8 X8 ~0 }
{ h=link[h].nextp;  S1 E" F( `' B
   if(link[h].number)
5 d: V: E$ {+ U. C4 I1 O     i++;}2 a, q0 R. N  e# i# a

, T6 T& ?' l( [2 yprintf("%4d",link[h].number);
) h; C/ p2 r7 g8 zlink[h].number=0;
3 \2 X, z; o% L' Ycount++;
2 u9 Y1 W5 Y& a. O# P9 E9 l}( H0 _  b; m# P, w; I2 W
+ m1 J6 S9 ^5 ?' H% _% ?
printf("\n大王是:");# e6 A4 ?9 T8 N3 ^5 h
  for(i=1;i<=M;i++)
! w2 H  I1 M) _8 j  if(link[i].number)
- G! e, a5 W5 Y  }. ^, h    printf("%3d\n",link[i].number);
. p& S% q8 S; q" o2 v$ J# B/ H1 S" U7 ?* b8 i5 G: s: T* O

; n- r5 ]; f5 Y5 U2 c; U}
% B* C0 G; T6 X' S$ P. A/ T2 L( M
第三种是普通方法for循环

: R9 g5 n" k2 a+ O0 b1 M#include<stdio.h>% j6 F3 Y1 C/ w, [, ~2 {
void main()3 N4 }' J; D" o  {2 m0 ^
{ int i,k,m,n,num[50],q,*p;8 c( y$ U; K1 ?& O5 W$ W  X4 S
    clrscr();
# A! A2 q7 {5 z& J! A2 [   printf("input number of person: n=");8 m; f( ~# `6 q5 |6 h- N1 w
    scanf("%d",&n);. g) Q2 D% v+ M/ a" \, c
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只: P, Q4 J3 b6 q% n, ?
    scanf("%d",&q);
& w( \% _0 p& Q& O   p=num;
0 S( A% e& i( @0 K, A  for(i=0;i<n;i++)
0 T& z0 A8 K4 J: g$ w% w    *(p+i)=i+1;
5 c# P+ J' p1 [  @( {# u* L% n$ X   i=0;  ~2 B$ D! B3 G
   k=0;
' _4 D" m0 g% G) j" s7 |0 e   m=0;
4 \- T5 {& j+ i; `+ {  while(m<n-1)
5 `, m- v9 _- H6 v1 x   {if(*(p+i)!=0) k++;
5 c( A. S7 y5 F2 s% O- ~7 [     if(k==q)) z5 C( V! h  |4 i
      { *(p+i)=0;
# W' y( N. P; k" B9 n        k=0;
' l3 k3 i& p' J( i        m++;% M' b, N/ ~, I. E3 T7 g* |
      }
* v4 f* p" [/ I$ q6 W7 e  m    i++;
) k. Z$ q, Q+ _    if(i==n)i=0;
; }5 f9 h" o9 E1 [1 Z+ \   }
: T! j# G& A1 M$ n6 |: N' T  while(*p==0)p++;8 P$ |0 L4 H4 E2 ~- g
    printf("The last one is NO:%d\n",*p);
! P* P4 _, i% _& b6 s     getch();% J' |" R% }8 [" e' d
1 _7 r0 Y8 a! M+ J
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
( Y8 T/ R# l  I+ vnamespace 又费马达又费电# K3 `2 }$ A% Y; n6 Q" O9 T
{
, I. V6 U5 L- w2 z* c( ~' M$ }8 X    class Program( N3 ?9 e( y# H
    {+ k4 j$ X' [! V" Q4 P0 A- N
        static void Main(string[] args)  ]2 S% }; l* }' I4 e7 ?4 Y2 x
        {# p$ D, f5 N. L
            int m, n;
1 y; k: ?" h4 F- n8 Q& e            Console.WriteLine("请输入数组长度");
, w- n0 o% T0 Z            m = int.Parse(Console.ReadLine());//m为数组的大小4 z" I( ^  e8 Z5 w4 ]( [
            Console.WriteLine("请输入要截取数字的大小");7 r& K4 z- p5 u5 R
            n = int.Parse(Console.ReadLine());. ?+ [  H# F/ v% e/ ^: u1 }6 I
            int [] numw=new int5 g$ B% @$ b: ~0 S
  z- [( w" i* y9 t3 T0 e  A
&shy;&shy;&shy;;7 V1 X) I# x; P1 ~. N4 g. y
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数4 P6 S% m7 Z2 b: Y$ Q$ f& P: h
            {6 W6 w8 I) N2 G% f- c- j8 T/ e
                numw[j - 1] = j;2 H) r7 V) P, L$ d  w( p" M2 n. N
            }
3 F! {! [8 R  `% g! l# u# V            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
+ k" K  s! A; S, G            while (d != m - 1)
* M$ h& Y' R& n3 e            {" Q" A; e5 j3 O3 A$ A6 Z
                if (i == m && d != m - 1)6 Z& \. b; ?6 u  Q5 C, w. D
                {
# y! q7 _5 S0 h! w/ i+ c" Q1 P2 T, C                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!6 X/ ?0 i' u- @. X- ~9 }2 E
                    continue;- i, Z6 f3 s, T2 h
                }  E  R% S# G3 k! ~. g: y2 [
                else
/ V' l" m! U0 Z0 g: _1 j                {! O& ^2 y# l5 _% x" m0 I, h0 s
                    if (numw[i] != 0)
1 q0 S& ?9 P$ Y4 z. ?: \  K; H: n                    {
. _: H; C  B  X7 o                        i++;, Z- Q' p2 H2 D; O' T* A
                        k++;0 l0 f1 _; Q9 A- M5 L
                        if (k == n)
; E: K$ R) F5 i- P3 `, f; n8 |                        {3 e& T7 a6 c2 q3 }
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
: b% a4 ^5 d, W9 z; ~; j9 P) g1 d                            k = 0;. i+ M* v+ ?9 b9 R  k
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1. a( g& s; V0 h+ d2 t( L' }4 R7 g
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);( c6 X0 l& l6 n" ?$ a7 x$ G
                        }! J5 X5 L: [" f$ L3 l7 D
                        else//输出暂时还没有改变数组元素的值
( g' S. V. m( E# v7 ?# U                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);/ C( T# ^- D1 q
                    }  M! c& D% h: B; a, N; v8 A
                    else# I) a6 m- |% L8 Q  a) S- P- n
                        i++;//数组元素为0,直接跳过,不计数。。。9 O2 f6 L* c  Z/ F( `
                }
  K' `- k  H" I5 o& }. W
1 E# Q5 \+ z7 g, X# X: t; n- B8 \8 ^: @5 w# Y6 q. w
            }//结束while循环
& W9 b- ?" d7 N3 P, y! N- a            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦2 W/ u# g+ T  @: O# @
           : F) @; p0 Y  K6 D( w9 Y2 D
                if (numw[i] != 0)
" r9 _; ^& t/ J; M$ Q8 ]: O. p6 q+ D                    Console.WriteLine(numw[i]);
$ `, _8 x/ {4 X: ]) y: [) d           6 n4 r, `8 |2 [2 I. K& u
            Console.ReadLine();
0 S6 F3 p$ a; n        }
# a% }( A2 o9 H6 [+ r9 C8 G* r7 b) R! |    }
) W) c& u7 _* Q/ F) V}* _$ b1 Y! b% [% O+ r  N2 O1 f
小甲鱼最新课程 -> 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-25 12:49

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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