鱼C论坛

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

猴子问题

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

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

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

x
大家好!
# S6 p' R# ?% Y1 Q+ T: w1 l  r这几天我在忙着编一个问题,我用了一种方法编出来!
' P. }% L8 I# L# Y但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
' s: d( T. w- }  K" G注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 + M) T: j( ^$ M
* E  k" G: [* k+ ^# w
( w1 A! M' M% \7 t% ~6 b7 U* s
                            题目
+ a% e* k$ r( v" l# S山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
3 j0 J4 r1 }. ]3 H第一种方法:利用循环链表
. L' }* N; s* c4 I0 i$ x  d9 L1 o' u#include<stdio.h>& D( Z( m% M, f: l* z, f
#include<malloc.h>$ l7 T, a4 u8 o6 T
#define M 8            //共有8只猴子9 t3 T, L& Z' F$ O
#define N 3            //数到3只时退出第三只
( t' U1 Y  A# G$ a1 m+ itypedef struct monkey) N; e/ J/ @  @8 }
{int number;( C( R( {- H3 M( l/ c- d
int flag;
5 J* A( H* N' \5 Wstruct monkey* next;# y5 y' V0 z4 A
}MONKEY;
3 G1 g9 l& z0 H% ?; S4 r! f- zmain()& L  S" T+ d- r  p  x
{ MONKEY *head=NULL,*p,*s;
$ e  S# u. a) E+ r0 ]9 [  int i,sum=0,count=0;8 @  h# g3 d! S% Y+ J1 H' k
  clrscr();              //清屏
7 r% U' I4 W6 ]6 _. Q# i* {6 u  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
) U5 t8 L1 W# c. ?/ }, W  P0 X% k( t  p->number=1;p->flag=1;
+ C9 `- F" C$ S4 {/ i; C  x$ H  p->next=head;
; z) i1 X; `$ H$ w4 Z  head=p;
0 i" G: h, Y+ \6 R( ]  for(i=2;i<=M;i++)
% x6 {" f$ u1 ~3 J    { s=(MONKEY *)malloc(sizeof(MONKEY));
1 E: |- _& q0 i4 `# _1 y     s->number=i;s->flag=1;( F( P7 a# S7 G& c
     s->next=head;: w" T  H$ g8 R! l8 C2 k
     p->next=s;p=p->next;+ {9 F& D9 l  e1 D
    }
! M" a. ?8 Q0 h, T2 m5 M6 f  J% ~    p=head;
! \0 w/ E8 D5 p3 o) Y+ F   for(;;)( a% }+ P0 ~$ M2 \9 T
    {if(p->flag==1): `. Z5 A' m! A
       count++;3 P; K# y6 i5 m% t! |7 R7 ~5 e; a
     if(count==N)
+ |( a7 p* D# E- H* w        {p->flag=0;
' k* [" }' l  J! J         count=0;" i8 H8 B2 p1 @. \
         sum++;}
% R; m1 n0 w9 U     if(sum==M-1)
- `/ r3 d( S% o! z, S% y$ v        break;
, ]" F/ t; O  _& z1 o$ z2 J3 w8 l     p=p->next;
4 J0 o3 ~% {& Z$ Y' w6 T    }+ e! `% M4 j2 s& ^& d
    p=
- U2 F  x2 L" ^' _0 H/ i" t    head;: |6 b! c: x, K, @  m* t
    for(i=1;i<=M;i++)
0 ]! o& n" B* S/ Q6 I    { if(p->flag==1)
2 a# A4 f, v1 N/ D        printf("\t%d",p->number);
6 k; t8 b7 K: A4 M- e9 o, x      p=p->next;5 B4 R7 \, ^1 L! l* I8 C
    }
0 v  z  [+ X: n+ _' `4 y
8 m5 e; P; r3 A5 P7 N1 P' o" o9 R' f4 e; b
8 d; I5 V# k2 _3 G! b
}

" ]/ P2 E9 k5 f# ]7 _8 f- Y5 ~- _第二种方法:数组
" r* h9 |+ ]# `( z4 B) {+ x#include<stdio.h>
) T0 C; t2 Y+ e#define M 8. N. M9 _, {2 h0 g% B& ]' Q
struct monkey
# Q# S# b6 l- o6 D{int number;3 ^" O. I* y# {8 `6 E
int nextp;
- I" B: o% N+ w2 r4 `}link[M+1];; y. _5 g* g  z/ {& f
$ a& T1 h  f1 O' e# E6 ?" Z
void main()
+ V% ^1 f. U; k1 Y' W# G: S+ Y% o! {{int i,count,h;
+ `& \/ i+ w* e# ~: G7 wfor(i=1;i<=M;i++)+ A5 k1 Q1 p3 t/ G- e, D
{  if(i==M)
; G) S' h0 i4 h  b6 W   link[i].nextp=1;# y2 m$ a. U6 [% r# `" T' D
   else- i: H8 z4 d0 ?
   link[i].nextp=i+1;
' p; @3 J2 M" e; ]' v  link[i].number=i;; K, j+ X2 k( V( ]& P0 ?" t
}" I% r1 b$ B' Q& A0 @7 ~
printf("\n");
( R8 \! B) K. p- M; R* m% O0 Kcount=0;, r3 }2 b" U4 v! j
h=M;3 b, @! l/ j0 @- O- w; ]3 D
printf("依次退出的猴子: \n");1 h9 ^$ T4 U: m, ^! Y+ r
while(count<M-1)+ _0 T, A8 ?0 a( k5 G+ i
{i=0;3 a) H# G  y6 r
while(i!=3)" S; T+ c9 Q5 N
{ h=link[h].nextp;
! Q( @0 E. V7 R$ H8 j9 f4 ^% O   if(link[h].number)
3 E5 _- k9 ?5 u: ?( M6 W/ d, c     i++;}
7 |" @3 j! @( x+ e, z) g  F7 ^! x4 Q
printf("%4d",link[h].number);
- b1 w: u( [! w6 ^. w% elink[h].number=0;) J0 e' w; w- V8 z
count++;
8 J2 w' y- q6 M7 `5 K% _: r}4 p2 ?* T* F9 }  X$ O# O
: Y) P5 i. P( [& I
printf("\n大王是:");$ u# K8 m9 N$ A1 N( a& D( q" ^
  for(i=1;i<=M;i++)
* H5 Y% @5 f' L) ^* }, U) k  if(link[i].number)+ I0 z+ M" Q! N% I- f9 ~# L
    printf("%3d\n",link[i].number);
: n1 H+ }3 `* P9 M3 r3 a4 ?5 Q& s) O

) r2 q2 X( G* H# o! ^9 V3 [}

+ p8 L9 w- `  Z; z4 _. o" c第三种是普通方法for循环
2 B+ U. \  h. Z
#include<stdio.h>6 \' A$ d* ], z5 ?, q
void main()
& }5 I- K7 C/ {7 u7 B{ int i,k,m,n,num[50],q,*p;
9 ^  L. E/ }! m* N/ o  l    clrscr();( w# x  F7 b! v9 `0 K
   printf("input number of person: n=");
! I2 ^$ b' {. ~0 I3 V' h    scanf("%d",&n);% T6 g9 J" M2 {$ c. |( s
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
" V. O+ B: x  W. N4 Y$ Y1 Q    scanf("%d",&q);
8 E/ u2 A  o& B3 J2 G   p=num;2 e% d4 X& p& K( Q4 ~) ^$ K2 R) S
  for(i=0;i<n;i++)6 S. J5 b7 R3 i
    *(p+i)=i+1;1 _& g& C9 V3 t3 A! n
   i=0;
: t* `# J, y. P" I. E6 }2 {) r1 ~* W   k=0;
5 l1 G2 B% c7 V! I   m=0;# [4 E; [4 _$ h9 l+ [; E
  while(m<n-1)
, ^6 I, t& C% x! j0 y4 x# E   {if(*(p+i)!=0) k++;1 a7 M0 M& e* g$ ~, l
     if(k==q)
5 S$ O8 ]: V" y$ m4 A+ \% f      { *(p+i)=0;
9 U/ H- D" a2 @9 \# w" F1 {$ @' Q        k=0;
, k8 t0 {' Q+ d        m++;9 Q3 g% v; {. q. B# G4 q
      }
2 ^5 }; v' K+ `( s; T! b2 f# g    i++;, s9 q* K4 t! y$ l
    if(i==n)i=0;& D3 O& X. c& o: {# g) C  J! O
   }
) x+ n- y  i. ]/ G& O8 j( B+ ?  while(*p==0)p++;
, f& F. h- E3 v4 n% ?0 }3 G    printf("The last one is NO:%d\n",*p);
/ w( Z( ]  ^# K! W% M     getch();
- V1 D7 g9 |( H# A% t" o1 P6 Q$ I3 N7 l9 D  d, J3 w
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;% ^, C7 t) V+ e' B2 m, b
namespace 又费马达又费电
# I' n" Q5 I9 X, }. ?% W$ |{" \! R- I7 F6 x6 {. a! g' a* a
    class Program
% J$ W* [2 t% }0 N0 M# V    {
8 U7 r: k. F% N, J6 ~( S3 o+ }, b2 G        static void Main(string[] args)
  F2 _& J4 O. J% w( x" n        {
7 @' @. K7 T# H' c+ i7 r7 w            int m, n;
9 X+ k6 B) q8 v0 K; T* a            Console.WriteLine("请输入数组长度");
+ G; Q) [/ g& z" g5 w8 L            m = int.Parse(Console.ReadLine());//m为数组的大小6 I2 V' Q5 f) Y" v$ \/ m. O
            Console.WriteLine("请输入要截取数字的大小");/ ^- W! Q" e6 {! ]' ]# D; D' {/ e
            n = int.Parse(Console.ReadLine());
; q0 r/ r8 P/ Y3 R& i, s6 ^0 ~0 j            int [] numw=new int
0 t1 v1 R' Z# U( W5 i- ?2 }. Y- u
/ C" \# H; n/ S&shy;&shy;&shy;;
# E, G: J3 o+ {: Q7 D" a3 {            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数. ]4 t" C) z5 K* G, m+ S+ E5 Q7 ?0 S
            {
8 I5 N1 K4 F) k6 K( C. ~                numw[j - 1] = j;
9 k6 x! J5 e) ^+ T. ~            }. L0 K* }* q# e6 Z/ O! ]: Z
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
  f1 _  b7 l0 x$ G9 H            while (d != m - 1): S2 c8 O% h; d, S6 O
            {
; w( U! L! p9 i                if (i == m && d != m - 1)8 V; r- o# \; D5 a- A) \
                {
- |7 S( O; Y7 _1 }' j                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
  Y8 f/ h) q: q) H, D, ^9 Y% Y/ i/ E+ M                    continue;
5 f$ M- e8 z) P4 ^                }* J6 c2 ]9 ?9 F! }7 z3 R- @
                else
( d4 k8 L3 J9 l, t                {
9 K8 q1 B. b+ `1 V  i6 u( s5 H* \7 a& R                    if (numw[i] != 0)
4 f; a! `5 H. X                    {
! o. q8 a: b2 o, p& y" o; V% b                        i++;
0 M9 n# P0 T9 d4 n% S                        k++;8 n" e3 b9 M* Y8 H
                        if (k == n)# r& H. s' }& z6 v- V
                        {
. a+ {  m2 ]; h2 R5 X                            numw[i - 1] = 0;//把在n位置数组元素的值改变了# v5 `& Z- O. i* H+ ?; `- Z& N$ {8 F: H
                            k = 0;" g: U! R6 O* r! R* b& R- U
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小17 ?6 b' r6 S5 d6 s4 O' s$ U
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
/ O; Q) P! {+ d: q, E1 [                        }
9 ~! h2 {7 |0 ?& v                        else//输出暂时还没有改变数组元素的值/ B0 d, H, j& l
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);- E- A7 X& u# r% l' ?7 s3 q+ V2 x( h5 `
                    }
. C0 H7 h, k- b0 K* \5 t0 W% f1 g                    else' d3 o1 u! A- V- Z1 ?6 j
                        i++;//数组元素为0,直接跳过,不计数。。。
0 l) w0 I  o6 R5 a                }
3 a2 x8 H  P( {  e7 V+ L4 W 9 l2 G1 l% \* ~8 A) a0 c
) v7 |& R* f& W3 A3 ?; [7 M: V8 U
            }//结束while循环
8 c( c; Y, ?4 L% T            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦% k0 {7 S6 B$ G
           
# b; r( I$ c5 w7 B9 y, g8 f                if (numw[i] != 0)" {4 C: `$ Y9 k) z7 u; S
                    Console.WriteLine(numw[i]);
& J* c3 w# T8 T           
) _( b5 g5 c- @! z            Console.ReadLine();2 |2 ~# i* c4 u7 e+ t: m
        }, g9 V/ W  r2 y+ F- O  A
    }
% }5 p  u5 ?/ d1 F7 B}
$ c) G6 z, q4 N2 i- W8 ?
小甲鱼最新课程 -> 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-14 12:22

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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