鱼C论坛

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

猴子问题

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

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

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

x
大家好!9 {: P1 M5 ^8 y0 n
这几天我在忙着编一个问题,我用了一种方法编出来!
. p6 @& Z0 j% O, K" y! j5 a7 j+ c但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!  }! x9 O/ Q' d# x2 C
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
  }7 A; T1 O8 T5 B) ^+ T, A7 \' z, T" d% C( F
3 a" m( u* ]# N2 b: _9 a! ?
                            题目% E) Y7 C; Q" Z
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
+ Q; s, T# ^( Z6 ^! R第一种方法:利用循环链表, M( z0 f1 V, [4 `5 {  D4 @; K& r0 W  m
#include<stdio.h>7 o, L0 @  ^; \' q) r0 Z
#include<malloc.h>
/ G/ ]4 ]# l- V0 Z2 s#define M 8            //共有8只猴子+ N# D. \* e2 n/ f8 D" C
#define N 3            //数到3只时退出第三只2 k. ]& G0 c) E) v, Z
typedef struct monkey
1 B7 @) x6 J" D# N' o{int number;) w8 l5 _: s% C1 i( z  I: [& ~6 i
int flag;
( W1 [: K5 Z5 p- Mstruct monkey* next;7 @5 T8 q  h7 J2 v7 }
}MONKEY;. P+ k' m9 J9 M% Z" T
main()3 i* {6 H; U+ A) k4 Y- W0 j0 h, E
{ MONKEY *head=NULL,*p,*s;* V& @2 N1 j, @# U) b
  int i,sum=0,count=0;- s+ S# i6 d- R! G
  clrscr();              //清屏
. A' v) s; L- c0 J  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存5 ?& }9 d& Z% A+ |: E
  p->number=1;p->flag=1;
1 l6 Z" {+ X0 W" s  p->next=head;
& A; |! D8 D* g: y! V5 v2 w  head=p;
) P! L  j2 A  h+ L1 R  for(i=2;i<=M;i++)( E$ Z( A, z- D+ y! e. y
    { s=(MONKEY *)malloc(sizeof(MONKEY));% x8 p1 {9 r, ^
     s->number=i;s->flag=1;
# h, y+ L$ C& C2 i( O0 d3 V) ]     s->next=head;
% ^8 `; T2 X; W: W0 g1 T. U     p->next=s;p=p->next;* e4 \" L' D( O/ W
    }* D$ j6 D7 g) Z) D
    p=head;
' M; W- \0 f) I" h- N; P   for(;;)
3 N+ W, v9 ]" d0 k" h; A* ]6 M& ]    {if(p->flag==1)
4 a) q; b+ p9 g3 C1 V       count++;
8 N8 }! H  P3 U8 |     if(count==N)
" W& {  F2 e. V, q; L0 P$ @        {p->flag=0;3 f+ n. r# o# R7 [0 p
         count=0;
1 y, R$ h& |& o+ w# ~; B* F         sum++;}
$ g' L6 ]4 P& L( r; [     if(sum==M-1)
4 r" \* A& F; i" J1 D; d( S        break;/ C; `" E! I/ y" l( u% y  G1 Z2 Q+ V
     p=p->next;, ^  e. b* d8 m* j5 T' T4 R% b) m' K
    }
: _0 y3 M; ~* D# R+ Z, K    p=
( I/ J2 _. x2 N0 x0 R    head;6 @1 o( b3 Q: j( U  q+ Q, D
    for(i=1;i<=M;i++); ]7 `; h; a+ {! E$ Q
    { if(p->flag==1)8 j/ |3 R0 Y, `- r: ~
        printf("\t%d",p->number);
1 Z+ {6 O7 f1 R- k5 i3 i. o5 O: ~      p=p->next;
3 x5 l4 f$ l9 w" I$ N    }/ u4 b6 h6 n3 N' @1 I  }
; h( S* B! E7 }3 S# _: G9 N) E  y
8 A, h2 H9 i6 G& o

  @  H; c, P4 G" w$ ^}

* v6 v& ~0 o. j' X, r第二种方法:数组
. D/ `1 Z9 z2 J6 m#include<stdio.h>
' t: ~$ N; u( B1 X#define M 8
2 v& j' n0 m$ Y4 d/ \+ n: |# {struct monkey' |+ P$ Y# s$ p  \, l' e
{int number;0 L: R* y/ r& L. M! ^# P
int nextp;8 Q- I- ]. b2 f
}link[M+1];! J. n0 i2 R0 r

" s7 T8 W4 ?/ D( xvoid main()
; h. V  j9 V& R! r' c) T# k2 K{int i,count,h;
0 l' c8 w: v, w7 J" Cfor(i=1;i<=M;i++)
& v$ b8 }4 |2 O{  if(i==M)
- H1 {$ e; F: F   link[i].nextp=1;' D7 N$ m3 Y; H6 {! O* X. I; V
   else
! d/ y- d4 y4 j. c. }) @/ t+ w   link[i].nextp=i+1;
" g& w* N9 R1 K8 P( n  link[i].number=i;
% ]& ?/ [5 R( J7 I  Q) P/ ]; p}6 x6 V5 x' I" S! e9 s9 u# _
printf("\n");
, Q. A. i9 I# T5 n2 ^count=0;
3 o+ y5 q! G; t  b) Z' o- N. ih=M;
: r: w- y! N2 m6 jprintf("依次退出的猴子: \n");
2 F2 v5 i9 k1 n2 h" Lwhile(count<M-1)
  s$ v6 {6 O& U, F& D" |9 Q3 y{i=0;7 m! [9 E, r- P/ R( G0 V
while(i!=3)5 n4 J: K# Y) {/ u- C7 ^/ m9 E
{ h=link[h].nextp;
" i1 q8 b4 r" C8 j2 i- ], j2 V   if(link[h].number)5 j! ?0 l/ X( r- K- a+ @8 X4 K6 v
     i++;}
% j; E" J* Q& `: o7 D
4 A8 o3 _5 N: U+ Y- _, K: K1 `+ \printf("%4d",link[h].number);
. G8 Y8 P' s* |! N6 f' a/ Plink[h].number=0;& g* z* g3 Q2 j% f
count++;
4 s2 ?6 h% Z6 h}; K( N! d% ?9 H% X$ B, c2 V. a5 y
7 [! o! h3 c0 Y
printf("\n大王是:");
9 o2 k& d+ E+ E5 O% b7 A! C( l, H  for(i=1;i<=M;i++); E8 H  Y0 ^& a4 g. I
  if(link[i].number)
9 t# {" [6 Q6 C- T; z7 [    printf("%3d\n",link[i].number);* n7 P* ^: [1 H# o  F+ n

7 r  {( M0 ?9 n
2 c7 X+ u# M5 P+ Q  u}

0 W7 c1 M$ b; o第三种是普通方法for循环
0 w& V; L2 S8 e. U5 Y5 S& V7 i" `+ @( b
#include<stdio.h>  i1 [6 W% S+ J. Z8 W6 I% X4 m
void main()
6 R6 \  o  ?# o7 ?% x3 u{ int i,k,m,n,num[50],q,*p;2 \$ \, {4 H% L4 D
    clrscr();& D, q# s- {* x: Y
   printf("input number of person: n=");, X/ B4 m( v  O$ R: |8 A1 S+ t
    scanf("%d",&n);
7 G3 \8 U3 I/ Z! A4 {2 J4 _8 t4 Kprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只; g, h3 E* I2 u8 L: K3 [9 j
    scanf("%d",&q);/ X5 Y+ I6 e, ]
   p=num;- m1 e7 E$ p6 R9 \. y! a0 H
  for(i=0;i<n;i++)
& _% {# W% m- O0 X1 |8 ^8 n    *(p+i)=i+1;
: s  S6 h0 n0 g7 W: e- N! q   i=0;
2 d3 {5 @) h# J: M   k=0;' d3 X, q: b7 ^/ b
   m=0;
& b# ^5 Y3 ?) [! W1 o) Q  Q3 j9 o+ F  while(m<n-1)
1 Y  m! [2 k, k6 L+ a$ D) V   {if(*(p+i)!=0) k++;! {$ P2 O) n1 D( Z3 S
     if(k==q)( N* g. Z. j  n4 o% ?1 V6 j) V% c$ @- t
      { *(p+i)=0;
' R* W8 J; C5 l: u        k=0;
- F  N4 d$ I: Z/ b3 n- R0 _/ d5 u        m++;
' V$ z( h& }6 O( W# O      }
  x6 {# s9 X! r% Y5 p0 p# o" O' J    i++;
% }. k% h. a+ O9 G' V) q    if(i==n)i=0;  L$ m2 }3 v* U, s
   }0 g/ q4 z: ^1 w8 a7 C6 ], v  J: G
  while(*p==0)p++;# q# W) S3 @, x$ a
    printf("The last one is NO:%d\n",*p);/ f6 ]* E* ^, g& v3 ?# k
     getch();! t) t* {0 g8 p  V$ {$ S

& y+ I* I4 D# a1 G}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
, k' y: [! h$ S+ |7 ^namespace 又费马达又费电+ q: v1 B6 b+ T1 a( [
{
; g5 j. P) n: k3 N$ d: ~    class Program
, {! D4 d8 w! f, o6 t    {9 V3 d: m! A8 g
        static void Main(string[] args)
8 }& b, E# `% w# `" z) z        {" K0 Z9 H1 ]9 J9 F
            int m, n;
. X* r" v! y  ^. l& g( b* L            Console.WriteLine("请输入数组长度");& r% t0 L1 F: W( |/ h3 [
            m = int.Parse(Console.ReadLine());//m为数组的大小
" B! F" ^- i8 G            Console.WriteLine("请输入要截取数字的大小");
6 N# E# x% n6 `3 @; e7 \/ }8 l! p+ F            n = int.Parse(Console.ReadLine());
8 ~) n, J8 d+ g  B3 a5 L            int [] numw=new int/ P" U' ^* P8 R

% D% H# D' x+ y1 t&shy;&shy;&shy;;
5 k) y* [' [+ n2 z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
2 ~. X  ^- g/ e6 f: p            {
$ }' x. q- `$ k$ ^# v                numw[j - 1] = j;
' e! A. m- O: r: m; i7 |            }7 y: s- L& w2 o
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
; H( V1 _- K6 I            while (d != m - 1): M3 M) V  K! b, s: s1 H* r
            {
! G4 s0 x( u; d7 M/ J                if (i == m && d != m - 1)0 i5 T0 I) y; g6 O
                {6 ]2 {4 l- z' U7 N% S1 s; e
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
+ P- A2 D  I: t9 c                    continue;
! g9 y: f1 |% Q" _  G& b0 x                }
9 B: Z9 E/ ?- s& t1 Q                else
- M. I. G/ c8 y  a) _$ @- |1 y! |0 u                {8 k* U, @' u! |0 p" e1 I
                    if (numw[i] != 0)& D9 u. V6 ^/ Z+ d9 L: h7 g9 ^
                    {9 I/ O9 h  [+ B5 a; i1 n: v5 N" h
                        i++;5 I$ _1 I4 I  l
                        k++;
( R0 A& V6 K) I3 t  f                        if (k == n)5 x1 |6 n5 t, k: f
                        {$ K6 X: X/ k3 N- M; ?6 b$ u
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了8 }8 r7 x, ~. O' r# k
                            k = 0;
. D, \& r* r" m6 v              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
# ^: q. z2 A1 q' C$ k! M' n/ g                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
% W) T" a6 ^" y/ N                        }
' o, u( D! V; L2 {                        else//输出暂时还没有改变数组元素的值
& _" c5 _1 l6 s6 C5 u* N- k                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 g0 R$ ~9 Q2 z- M, ~6 l, N
                    }
) v% E+ H9 |8 Y2 d3 V8 x5 f2 |                    else
! @, I: Y  Z3 a                        i++;//数组元素为0,直接跳过,不计数。。。5 O6 l; S: e1 D, S/ J
                }
3 B! a; g- a% `! l& T! Y
; A* K$ `0 v+ A0 S0 y1 R6 `0 {1 z" @$ m% o1 Y) n
            }//结束while循环
& d4 Z' V8 j  m# E( _            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
2 g7 n  a+ l% R: S: T, Y           5 Y& |1 D5 C! a4 l% g
                if (numw[i] != 0)
  ]* b0 {# Z  K, m                    Console.WriteLine(numw[i]);
1 X! L; f& Z. {2 X* a           
, s" |7 L+ z1 k1 L8 s& _8 B            Console.ReadLine();; Z, n9 }2 Z0 @  U" X
        }9 A( c' S0 \- H. {5 `. L& a
    }" g6 S8 q- e6 f7 z4 P  Q  q
}+ I4 y7 m0 j" z) _8 J8 o
小甲鱼最新课程 -> 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-4-22 22:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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