鱼C论坛

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

猴子问题

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

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

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

x
大家好!& k6 B# x+ L  f4 z' l9 Y
这几天我在忙着编一个问题,我用了一种方法编出来!
5 C7 Y* M4 Z6 _6 T但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!4 x& S3 f0 n8 y! z% s
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 & R6 L! R4 e8 C. C/ g

3 W- ^, g/ F6 E+ H; P% t" o; X; c9 H  y% S3 P2 O! y
                            题目9 ]' j0 l5 p: x" L' S
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。( s! O+ d7 f- w" q  Q. Z- K$ F
第一种方法:利用循环链表4 G% ]: V( c/ q- N: z  C
#include<stdio.h>
. i0 [  N9 O0 f1 k# Q# }0 ]#include<malloc.h>2 d/ R/ w: w( j1 e& Q$ `5 W
#define M 8            //共有8只猴子
9 ?/ |; q5 E* Y1 R#define N 3            //数到3只时退出第三只, n* C  `0 ^2 P0 o4 o- j$ T: x
typedef struct monkey1 q+ h; }( k0 W! K2 n
{int number;# U) P8 j# W, s! J" d. }" `1 T
int flag;2 Z% a2 Q6 x' ?: I6 G( Q
struct monkey* next;
3 e" C/ N* T. K3 d( E}MONKEY;; B: D  P+ z( O( M2 s( ?$ N5 y/ w
main(); y2 q' g. T( Z( {, M# y/ w
{ MONKEY *head=NULL,*p,*s;2 N& S0 n  x# R0 K. A
  int i,sum=0,count=0;. s$ l7 z1 ]: @: b8 `; _
  clrscr();              //清屏! l* n2 I% F$ F  W
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
# z- d5 c, x( k  p->number=1;p->flag=1;" v/ t; f$ w2 y+ v# s+ T
  p->next=head;
) Y. ]8 P' {) l% o8 Q9 _7 W  head=p;4 }* i3 p5 [8 f) H. z: }
  for(i=2;i<=M;i++)
8 \1 F" r: W- f9 T    { s=(MONKEY *)malloc(sizeof(MONKEY));
6 D; b& D' }- j5 a# m( Z# k     s->number=i;s->flag=1;4 z5 ~9 q# a  E4 {) }+ \- C" P
     s->next=head;
( ~4 K: a# Z( P7 k, v- c6 g- z6 ]     p->next=s;p=p->next;9 W9 t4 v9 V5 ~0 T; a
    }6 m6 K( V& C( g* K
    p=head;
+ L5 y9 D% h3 l   for(;;)9 h( B1 B5 @& Q5 i) h) Q- `0 s
    {if(p->flag==1)
/ M) E3 h& y8 M3 v3 I       count++;% w1 C+ d9 i3 i" T" a- t, o  J$ Y) |7 w
     if(count==N)
1 O9 ]  ~$ \' |1 y: Q- R, a  ]0 c        {p->flag=0;0 w3 H( O) {4 w$ a
         count=0;
% M: [. F- x: ?( z, E. E1 ^         sum++;}
- y4 d$ }3 s; I; H5 @* g     if(sum==M-1)
& A. M) B% B7 n% S        break;
1 H/ R* l+ F' g- _; ]% v, J     p=p->next;- T' M: q* |6 Z% T3 A; }$ P
    }
/ Q; z# \" Z: X0 `! H% u; X    p=
) n- ~: n7 J" d' h6 I* ?1 w6 z- q    head;. K. \1 l+ J, q" s3 e- `7 |
    for(i=1;i<=M;i++)
2 d+ ?, \6 B( a. ]' n    { if(p->flag==1)4 {& }3 E" l' h' L$ d. J; G2 c
        printf("\t%d",p->number);
; j( L' M0 j  F. \      p=p->next;
% D' r+ C; s) H' x0 v    }
: ]2 N6 ]% B5 b2 t+ q5 x/ a" X! ~- z; x

- y+ S; V- G& {3 U5 t$ ^/ O4 b/ F) b* N# S+ o+ ~
}

- m9 y5 b% U& g) ^8 @1 {4 \- Q第二种方法:数组
5 s1 F  {% I" b: K#include<stdio.h>
- d* ~2 E5 A8 S% q#define M 8
: u9 o. v9 _0 M$ U- jstruct monkey' T6 E% s4 P8 a6 G
{int number;
- \+ v* I+ p6 P* bint nextp;
0 q& F/ S3 r7 g2 ]" s. _8 E}link[M+1];+ f4 V, E0 X: y2 p
# O4 y. B; d+ v0 s  C) e! @& M
void main()
/ P/ }% H+ K% Z9 h+ W' x" n{int i,count,h;
+ r. s% t, a- n# ]! Bfor(i=1;i<=M;i++)
+ `) A4 d% Y6 R4 [( p3 r5 {2 a$ b{  if(i==M)& k& x- \7 w4 @, k
   link[i].nextp=1;
4 [- i/ Y/ u1 s" V* y' ?' w6 r   else
' a, _* ?$ G7 q2 J8 X   link[i].nextp=i+1;$ B6 D( O$ b  v9 z& `* j
  link[i].number=i;
4 ~; T6 i; n$ A: h$ ], x}/ _, J6 N7 B% a+ z! }
printf("\n");
/ B7 V. c0 B( r$ gcount=0;0 k- B: a( a) U7 v" z* }1 n" p
h=M;/ B3 U$ o2 N2 s
printf("依次退出的猴子: \n");& [7 E" |8 X3 a' p# N9 Y
while(count<M-1)8 u1 ~. u3 u0 l# M: t& b. j2 I
{i=0;
7 `; e- S* v- Z, h7 @7 Dwhile(i!=3)5 @* ^9 G$ j5 o
{ h=link[h].nextp;
! {5 k6 d& W( K7 a* c' g# m   if(link[h].number)+ U+ B% d- G7 Q' H. ?: N
     i++;}
" {! b5 p8 G* j5 n* k
) f+ ~1 Y/ U+ k% p" L7 Xprintf("%4d",link[h].number);
" Z7 M! C. _! B  plink[h].number=0;3 }/ ?; u* t5 w; k! a0 L
count++;+ H$ N4 C* Q6 b% T8 O& ]
}
: I8 N2 H8 o1 J2 _7 F- f1 F! @- Q. X8 |- O
printf("\n大王是:");  U* s+ R& V7 h$ c/ A& V' Q! W/ c3 a
  for(i=1;i<=M;i++)
9 E9 N4 e( Q* p, g2 W8 l  if(link[i].number)2 Q( b; b. k9 r
    printf("%3d\n",link[i].number);1 p. Y: p  ]$ {$ V

& w7 }1 U$ Z; I5 S" D; |9 s
" y8 i4 r$ D  [1 M( ]7 _3 o' G$ v}

  n" P+ |) i4 z: k; _$ f' D* z第三种是普通方法for循环

! F8 b1 H+ ]# k/ G/ X% R( f#include<stdio.h>
' Y* B- X$ u- ?1 V  R- d. k/ D& jvoid main(); P  W7 n8 U( ]
{ int i,k,m,n,num[50],q,*p;
7 \, d) O# N7 {1 s0 b2 E    clrscr();
5 u6 V9 ?& y$ [: P) f( F' U+ D   printf("input number of person: n=");* p1 j0 @$ Y6 Z! b4 B1 v* `
    scanf("%d",&n);+ H0 K3 ?' w* r% s
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
6 X& C2 v% ~. }, T    scanf("%d",&q);$ ?* Y$ Z# h! j8 c3 [! Z2 u$ R( ^
   p=num;9 q! e: C8 t4 t( u
  for(i=0;i<n;i++)
! R* S" W/ I6 B+ G# l    *(p+i)=i+1;+ {4 \9 W9 U) U+ r. P9 |1 y6 h
   i=0;
% U4 @6 e. u- y0 F2 ~   k=0;
0 u  L9 Z# V, }: D! F+ O- k   m=0;
3 |7 E7 }" B0 u$ G9 V( H  while(m<n-1)
; }+ R2 J6 D, o7 B   {if(*(p+i)!=0) k++;
$ f1 j7 |7 x" k9 x; M     if(k==q)) ?" E% M( ~2 D1 d0 w4 w
      { *(p+i)=0;
7 K7 E1 V2 C# D4 C. f( C# ~        k=0;1 ?3 z6 s2 R/ x/ N/ U
        m++;4 d) A7 ~' A/ O8 \
      }" ?8 H$ G, r' F( E$ [! [. _
    i++;+ C; z( K6 G$ e. [0 ^  x! I
    if(i==n)i=0;
7 }8 X. b6 {  H4 [( K   }
/ Z  b5 O( M+ J9 |. R3 Q6 ?& E  while(*p==0)p++;
# ]- y( a" d" q& w& B2 S* ?    printf("The last one is NO:%d\n",*p);
+ {0 w8 h! ?' |$ y$ c" u3 W7 C. X     getch();
: F- p3 _! J% e0 C  R: `! x" b6 R& x" p; a7 h1 J
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;* b6 O3 q6 M3 H+ E8 b6 T8 A2 B. ]
namespace 又费马达又费电; G' \4 S$ ~, a0 Y
{: h2 o: c4 J* S, p
    class Program- B" q2 P! ]3 N6 c, Q$ C
    {3 h% H# x4 J/ q4 O& G- ?# C% x# E
        static void Main(string[] args)% v; G# X; h  X
        {  W& x' @9 `/ S% U( J, L
            int m, n;* H9 D9 [, S3 h' ?9 l
            Console.WriteLine("请输入数组长度");
' p/ A- [# `) Q; W' m            m = int.Parse(Console.ReadLine());//m为数组的大小% B3 o" H8 ~& s1 q: c9 W
            Console.WriteLine("请输入要截取数字的大小");
1 O" W) c( X- ]4 i3 u4 k            n = int.Parse(Console.ReadLine());. u+ g3 h& i5 x; t) I
            int [] numw=new int
6 j# ~1 M# b$ E& M3 l! o. \0 Q5 j3 [8 p
2 T2 b- x, N! q! o5 K: R. v&shy;&shy;&shy;;
8 d2 J! k8 Q% P6 ~6 ^            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
3 e% m* S$ p3 M% q1 ^            {) A4 J9 T( Q! n6 w; n: A3 c+ Y
                numw[j - 1] = j;
1 O% y/ |. }% y- x) }5 J            }2 ]& K' D% c' F2 b4 }5 A* y' l
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
. a4 g" }; K6 ]  R6 j( C# s" U            while (d != m - 1)1 ^, w/ v- a8 P" b. }) H5 i
            {8 g- ]' L0 ]" f7 B
                if (i == m && d != m - 1)6 b8 Z( z( k& s: _! i: l
                {
5 I/ @0 f% t$ [8 a4 X/ d                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!. w! }3 u0 z. m0 [
                    continue;
; E8 H  L+ G" t; s$ s                }/ t' v, L, w. d: I& W5 ~! v$ b# k
                else
  m) y5 f5 [0 c+ B: c' ?% [& ^                {
# p; m3 j, z4 Z3 n- m; J% v& [                    if (numw[i] != 0)
: h) E/ Y8 v0 ]+ a+ ]; Q                    {
# o  [4 D1 J! i0 D! _' w& w( @                        i++;; I3 K, V, w, q1 s9 w
                        k++;
7 Z; B' `0 J5 A* G8 g+ @( o- B                        if (k == n)* E: ~0 R; P+ O: d' {
                        {
7 _4 Z7 b$ U% c* O/ X1 a& `; ^" \0 W                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
* F9 W; B4 m8 a- `( B( ?9 b% \- d                            k = 0;$ I% r/ S1 e- ?: W) }
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
% f/ m% `3 D) Q" {0 Z6 _% W                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
5 x  @8 N* W4 k' B/ P                        }3 i0 _8 q& j1 r! {8 u" ?; Y
                        else//输出暂时还没有改变数组元素的值
8 A6 y- ~- r3 N4 I" B8 p. A                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
6 F" L$ Z* G& D) v                    }
# _0 G+ L% _4 P4 c                    else3 {7 n. q4 u' L: i5 M
                        i++;//数组元素为0,直接跳过,不计数。。。
5 L. x/ d4 E% y+ r1 m0 m/ b                }( m% {# L3 E( c: W  [. V$ b

" B# s8 x8 ]$ ^" T- u8 Z: Z0 `* M
1 d6 m2 [- K1 Q9 E' s3 ?. C            }//结束while循环
& ]: |7 F& L3 H7 Q6 Z8 G6 g            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
* e6 \# w! ?# g, B$ n2 R- _           
5 ?5 o( ?9 g' x, L/ f6 _                if (numw[i] != 0)
( q5 ^+ u& g7 a- v                    Console.WriteLine(numw[i]);
- ?) Q: _* c. m/ U2 F$ F           ! O" ?% ^% m% G* e
            Console.ReadLine();
: [( k6 g7 P5 G  r        }+ H- j5 c% N* y; D3 B3 ?  z0 p
    }
% d, w* }4 J! a}8 |2 R5 k% u- y  k" G# r7 A
小甲鱼最新课程 -> 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-1 05:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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