鱼C论坛

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

猴子问题

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

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

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

x
大家好!
' x/ v9 @' ^, \6 p( t. Z这几天我在忙着编一个问题,我用了一种方法编出来!) Q5 ^' S9 u1 a" x. s7 ~) M8 e
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
# e. l/ p) q- u% ]( C0 p, }' Y- }0 q注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 9 \, S& d- B+ j1 i
2 n" |8 r8 Y% `% }- n2 K

8 @1 ~7 o- a7 p  f3 `) u  i
                            题目
  h( f& r1 B' b山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。+ _2 p" N( `3 x; U+ m+ e7 Q, n3 G% g
第一种方法:利用循环链表! I' N  S  L8 M
#include<stdio.h>
0 L8 C- L% W: m) ?/ c#include<malloc.h>  A2 M) t3 C$ t) W5 a" X
#define M 8            //共有8只猴子! e' k% u6 h$ x. v5 Z( v( b0 j
#define N 3            //数到3只时退出第三只1 @; g0 [. A5 @( j% B5 p- B0 a
typedef struct monkey# Z3 H8 V( \: C6 t9 E  Z& s
{int number;0 K" r: G& [: ?" W# P$ j- v, L
int flag;) `0 M& e/ Q, h) a! R  t- P
struct monkey* next;
  N3 L! b" F9 X" h) \}MONKEY;
, h" K" J* a; y' _main()
* V2 ^6 T5 C- r% w7 [- R{ MONKEY *head=NULL,*p,*s;
# h" l4 a/ U: \  int i,sum=0,count=0;
8 G6 C: G0 r, f  clrscr();              //清屏
! F3 j: \. o& l* k" Z  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存0 t. \9 ~6 {, D( m9 |8 L
  p->number=1;p->flag=1;
* c- y6 q8 Z" Q2 U  ?6 m" i9 @  p->next=head;
0 A5 F0 w* U% j! t  head=p;
/ _/ k* W! A0 C' G  for(i=2;i<=M;i++)$ U5 i& n1 ~7 r0 F
    { s=(MONKEY *)malloc(sizeof(MONKEY));
/ x. d2 `+ Y* O: d; o8 d     s->number=i;s->flag=1;
# ]$ J$ Z- ]* U' Z" ^     s->next=head;( r; T& y; \# V) o* f- S/ f1 q/ |. j% i  P
     p->next=s;p=p->next;
* Y+ c/ ]% a8 F. M% n    }
0 Z% D# r; ^! Y' t4 M" J    p=head;
4 v2 ?6 l$ `( q: _% H   for(;;). S) \5 B! T0 S7 v
    {if(p->flag==1)
' j5 [% j; {8 {- j# m7 a  i       count++;
5 _, X" ]9 q8 |4 [     if(count==N)
1 ?- |) ~* @8 J) o4 `/ M        {p->flag=0;
3 N* E& a* Y6 ?$ d         count=0;: Y% ^" F* K+ ^" a' M
         sum++;}: N6 L. h4 c2 p3 D4 ?$ ~
     if(sum==M-1)
  b6 w2 w' D' _% a5 n- g1 U        break;
1 z0 T9 Q* {" |6 f# \+ h     p=p->next;& i2 I3 @- m$ A" {0 g7 x3 P
    }
- [" C3 C5 \6 q    p=
2 ~3 {+ e( T( B. k! }& A3 ]) K; @    head;: _  T- N$ i' Q' |1 e* x5 j
    for(i=1;i<=M;i++)
6 P, Y3 I* O( `1 n( _7 q    { if(p->flag==1)8 ^" z: p2 H3 V7 t
        printf("\t%d",p->number);( D2 w9 R" j/ c7 i- W; m7 p# m4 x
      p=p->next;
" M! c' ]- ~; @. {, K0 {7 V$ K    }
+ V) k6 I8 j% }" K1 D, W2 N6 r9 g  R) \* n9 t6 O

4 J" _: n, v- f' G$ U8 f' e3 F* @7 ~5 l2 o2 A
}

( |0 c7 e! B! ?4 V* ~( }% ?第二种方法:数组0 W2 L. F  ~- d9 L" X* I
#include<stdio.h>' D) k& E# V& e4 {
#define M 87 }' x2 y# w8 b9 N& z$ o
struct monkey
  z7 G; M5 I; z; ^* M- S{int number;8 q. N2 w# Y" q6 d( |
int nextp;
4 k+ k. _8 F6 Y3 j7 ~6 D  H( W9 D}link[M+1];/ X0 n- ]. C& z) |. R2 ^2 Y( f
3 ?7 w; y; R! N/ V1 D& \2 I+ {
void main()0 m6 L" n% `) ^& x
{int i,count,h;
, l" e- Q) F4 e" Afor(i=1;i<=M;i++)) m2 |8 n0 @; }4 U* w" n
{  if(i==M)
' j& k6 T5 c, A* A1 H   link[i].nextp=1;
/ o8 u0 b2 x. t, p4 g   else1 `/ a( S9 n0 \* l; A1 h
   link[i].nextp=i+1;
! m& x& f' g2 Y; r& K  R  j  link[i].number=i;
% f9 R2 z4 ]2 |- F}$ @" m, T6 x) }. s& y
printf("\n");8 I. k+ \& B: \! V" H- `" K
count=0;9 {) F0 I7 t$ ]* |8 q6 }
h=M;
2 i) q- h. H3 W6 c* z6 Z: Y/ Aprintf("依次退出的猴子: \n");
7 a7 @# \/ M# Ewhile(count<M-1)& _  }. {- u/ w' y7 h5 p
{i=0;" c% E4 C3 _# N
while(i!=3)
) K- S& Q) R# M: z* O* e{ h=link[h].nextp;
% v) r1 |/ o" N( t' K) L1 v( I   if(link[h].number)+ G( p* o/ |- B8 ]! J# D  k
     i++;}: j# S8 S" K) A  _) I

, P( h% l8 w) Y9 ?0 o) Eprintf("%4d",link[h].number);
8 r. d1 ?6 L/ |5 P+ e- `' nlink[h].number=0;; ^6 ^5 b# k; @) D# M+ ^" ]
count++;
8 z: |9 q- ]. b; q}) d. v4 Z9 ^3 i" m2 M$ n, ]5 S
8 F2 R& {" S. G
printf("\n大王是:");
" u) {! \) c  s( a( v3 B6 M/ D0 W$ V8 e  for(i=1;i<=M;i++)9 K1 `' C5 O! o' a
  if(link[i].number)
2 w2 Z3 i6 m4 o, [& x9 P    printf("%3d\n",link[i].number);
' A" G0 s2 T) R
& ]+ v) [* @" M* ~; \6 k( l. V7 b  l; Z. F$ q& f# z1 J3 s$ L
}
( Y" `9 W7 x+ c) W8 Q1 ]0 |
第三种是普通方法for循环
" [9 Z2 X4 q7 h! U  z; h
#include<stdio.h>
+ j$ X7 G" C4 g+ z7 Evoid main()8 _% c; i; I: s' v1 m6 v6 E
{ int i,k,m,n,num[50],q,*p;0 ]& o! l3 D: W  k; V
    clrscr();
! [5 \& Z) X0 P3 }   printf("input number of person: n=");
( V- F, y9 d- ^4 e! D2 N    scanf("%d",&n);
) G& n1 O) j/ p& Z& Sprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只& l9 Z3 ^% ^2 V3 X0 H9 ?* q& T
    scanf("%d",&q);* Z0 e: z: M: |. p2 k) y2 i
   p=num;
8 p( i7 E! p- @  for(i=0;i<n;i++)7 T) e# ?% k% l7 H
    *(p+i)=i+1;8 a: K. e- n4 o9 m7 l, [  {, i8 Q
   i=0;: y. f7 S. `+ V5 [# }6 B  z
   k=0;
* {2 M; _; ^( ?1 t. K. ]& }2 P* G   m=0;
$ R# @- O0 T0 e' J  while(m<n-1)$ }4 {6 e8 ~& G
   {if(*(p+i)!=0) k++;3 s7 B3 I2 H- q5 b' q
     if(k==q)( ?7 _. c7 i# L0 I/ @" v! B2 ]
      { *(p+i)=0;1 t5 _/ k/ W, o7 r0 E" B6 [& f
        k=0;  x8 j4 i& h6 D( V8 V8 m, `. [
        m++;# m6 ^" @0 B7 c- w& A8 m5 y. J
      }& `: t% \0 t! x* I: j& P
    i++;  c- y' d& z7 F4 v
    if(i==n)i=0;; @& T9 A# h6 L2 R1 F& s
   }
+ `- J/ [/ @0 y* O; d$ B4 m  while(*p==0)p++;
+ v9 u( u& X/ v3 a, @6 D  S    printf("The last one is NO:%d\n",*p);
3 `) c* E$ T. c8 S' \     getch();( f# B7 a: m6 J4 o5 a$ ?

7 t2 d9 D5 H# ]0 J  }  Z4 n2 y}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
- r  D& \; A- V0 `0 Unamespace 又费马达又费电- C* N% N' |8 L# ~  a. ?$ w
{
. E, T: x1 i& M! A, P2 ~' h- s    class Program7 r4 S, W" U" C( A
    {% G$ g  H' o0 k% o2 A+ l6 u
        static void Main(string[] args)" R6 a1 U2 Z0 U7 Q; Y; @9 L
        {9 v  k9 A; s, \5 c4 z
            int m, n;
4 {- {9 a& z+ X) v. ?) X0 m% v            Console.WriteLine("请输入数组长度");" G6 A9 @% O; p
            m = int.Parse(Console.ReadLine());//m为数组的大小
4 C' |+ ^( P7 I: s! w& m; M- R* t, s            Console.WriteLine("请输入要截取数字的大小");. M# ?3 G7 G# D7 D
            n = int.Parse(Console.ReadLine());
( X+ \' M4 Z7 W, g/ q            int [] numw=new int+ \1 x% K3 r7 N- Z& i

( D2 w: E: z* v  ?&shy;&shy;&shy;;" C5 k  o" I8 m. `, M' U2 A
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
1 N5 S+ p- [# c2 x; h" W            {  G) }* d9 ^2 g1 n  S1 D2 j
                numw[j - 1] = j;8 P" L4 d9 @2 B4 D8 Z1 C* `
            }/ i& L% a+ }) G# ~+ g1 ^
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!; F" Q6 k* h( T' ^& a+ g$ f
            while (d != m - 1)
, J; ~3 c3 `, j            {" H8 D6 P3 b3 n0 j  i! f- J
                if (i == m && d != m - 1)
- U2 `! n( f* D, s1 u1 s                {
0 ]& d9 V! n' t8 `$ n. t: P                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
) I& k( ?  e) g& l* l1 N4 ^                    continue;2 b7 Q# r$ e2 e, f  s- R* q$ B# i# F
                }
! I9 E, U8 G# P$ N2 k- G; I4 F                else
# e" _7 J6 P! t# o2 T1 H2 O                {; W- t3 O# _+ Q% x/ T' p; {
                    if (numw[i] != 0)4 l) _; w- v, \$ C7 k
                    {
* [  O0 t0 y- }3 x4 Z                        i++;
! S1 F- ^4 i; E. L. {                        k++;, n+ u- e) m! V$ o
                        if (k == n)
( x/ n1 N6 W" K4 g# T' u. c                        {
4 R* ]" x$ H& n7 j                            numw[i - 1] = 0;//把在n位置数组元素的值改变了; n6 G: a& J9 g- O
                            k = 0;4 m1 z, S& c; u' x# @
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
9 P$ {- u" P: }6 X. F: ?2 u/ z                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);$ f0 M+ i7 {5 J5 b9 M8 \' E, [
                        }2 h( ]5 u, U" d$ ?# u  I
                        else//输出暂时还没有改变数组元素的值
( D: R0 F7 J0 d. n; z- J                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);" L% c7 \6 j. l* S# t" v* t+ U0 C
                    }5 v% I0 q" \) g" p$ E4 `! N. C
                    else
6 z# }) |, b& t8 [! J6 N- |                        i++;//数组元素为0,直接跳过,不计数。。。0 V. n, [# W+ z& B& d
                }
8 o0 r4 b  v2 _* V 3 Z, y. N0 l* A( g8 I/ l

4 x* Q. L8 k& B! W            }//结束while循环5 i" z: O' ?5 l5 r/ [# x
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦! `1 x! b9 h* E* k0 ^
           ' M8 ^! F; z8 Q" w8 n+ x
                if (numw[i] != 0)( o9 J# b* g/ E( D% O2 B
                    Console.WriteLine(numw[i]);
( ~8 ]1 v) q2 i7 T/ j$ l% D0 B           , K* F0 f+ Z# P7 C9 G
            Console.ReadLine();+ N0 i! r, Y0 u$ N6 v
        }
- E# V; u) V' q: _" f9 m    }& @/ `9 `2 k& L6 D. e" W, A( G
}! F' ?& w% L  p9 }" @
小甲鱼最新课程 -> 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-21 01:05

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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