鱼C论坛

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

猴子问题

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

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

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

x
大家好!: F- |4 |4 F1 K
这几天我在忙着编一个问题,我用了一种方法编出来!$ S5 e! h% T% p& g
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!3 l5 I/ w4 d) D
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
$ c2 m6 e/ K- }: L5 R$ D4 ]& k  N. `1 n

! ]) |: V2 ]/ o/ ~. ]" y: Q2 o
                            题目+ l8 v+ ]' i$ ]
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。% f/ x. z- l$ n4 a  y
第一种方法:利用循环链表
$ [' C, `0 s$ m5 G1 Y#include<stdio.h>
% x! S& Y* Z7 B1 Z+ l7 Y3 c#include<malloc.h>
7 ]0 d( y  G/ q* P! r$ S#define M 8            //共有8只猴子. k# M5 z- A  x: f
#define N 3            //数到3只时退出第三只
" H" U# y0 x! p# ptypedef struct monkey
, Z( x2 Z5 E6 ]% g{int number;' ^. e& V8 B, I2 N+ {
int flag;
" }0 ]  x- a7 h; E0 @) Pstruct monkey* next;
7 i7 j$ \4 |' N: r}MONKEY;: R0 K2 V+ l9 ^2 L! _
main()
1 @' j1 f; X/ B  G0 ]{ MONKEY *head=NULL,*p,*s;
# w7 J  ~2 d% m# p4 c8 a  int i,sum=0,count=0;" V: E# G9 e: c4 L: L& `! r( D: `
  clrscr();              //清屏
& V$ K) l0 _- Y/ ?! A! p  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存' ]- Q, C" D/ n6 m6 t6 J0 }
  p->number=1;p->flag=1;
; R5 A: ]; U/ l* T$ q4 H5 o. b" V  p->next=head;
2 x1 s; b. c# ~9 Z3 v  head=p;
3 X5 |6 [2 i( ?. I1 Y2 w  for(i=2;i<=M;i++). S9 |  t; \: I7 c5 e
    { s=(MONKEY *)malloc(sizeof(MONKEY));' A: P* R, s, a, p1 X, X6 R8 j
     s->number=i;s->flag=1;3 N6 F6 R$ Z/ h4 h% |
     s->next=head;
$ ~: H) N# ?. X; H     p->next=s;p=p->next;4 b) x5 J- s; c% M( u) s2 B
    }
; q8 l$ Z$ h2 y7 B' z- v9 t( P    p=head;& ?& a  C, g% ?
   for(;;)
/ O- T! a% g' m- O; J) I    {if(p->flag==1)
4 v$ n* f. u' T9 Y8 P       count++;+ P5 s5 R. ^$ K. B2 C
     if(count==N): ^2 x# T7 M9 n5 g! O- v
        {p->flag=0;
# t6 c# m$ _) p( I# n7 w3 w- k         count=0;2 L' `" J8 |( C6 Q5 H# l6 g0 N( n, s
         sum++;}4 H3 _* L* `" \; ?; g& Y- Q1 U: q1 w: j
     if(sum==M-1)" g& C& R; b1 f; r7 c
        break;2 }" S# L# w* M- _, j% }7 T! A: r
     p=p->next;) @9 o8 N; _% G4 z8 R7 @
    }- S# ], q+ a$ t6 ]) e1 A
    p=8 T9 j( o6 ^# T6 O% K/ u" k1 F
    head;
7 ~, R* u, t* h5 z2 i    for(i=1;i<=M;i++)
. A: _& q/ K0 x5 `$ U( [    { if(p->flag==1)& b3 e5 T' b; Y7 A7 b
        printf("\t%d",p->number);
+ R' M% |6 X7 B      p=p->next;0 \- A% u1 y  M
    }% f1 ?2 Q( R& {
( D2 v6 C; Y( r+ `, w8 U

0 Q0 S; r5 X  Y* [3 l- o) p1 o, q4 s' {
}

: V8 `8 ~& K% G4 S. y. G& L4 A9 S第二种方法:数组* `  Q2 B- T. ~& ~
#include<stdio.h>
2 p  N4 S% L! U9 x8 {+ I6 [& m/ f#define M 8
) v6 q* B( o  Lstruct monkey
( D7 H0 i1 G0 `* k& f# y5 @3 `{int number;
8 `3 V& F  ]1 [7 Uint nextp;
: Z5 i  i  i$ f% S6 {}link[M+1];. ]/ `  w6 o: `6 f8 e4 ?

" Z; v3 R5 z' P6 n: O3 B' yvoid main()+ }: {3 E1 u. M3 f( r$ a
{int i,count,h;/ w3 ]: L2 W, {+ ^7 F
for(i=1;i<=M;i++)
* \2 ?. a; r, M8 F; V{  if(i==M)" T# O8 v! G6 s4 d6 J
   link[i].nextp=1;" w7 Y+ A! @  ?/ b9 ^
   else
8 a) e/ N2 q2 W% l1 t' C   link[i].nextp=i+1;" d) {5 z) I, r- o0 Z
  link[i].number=i;# A+ c. [1 p% l. j, @7 K
}9 Q2 L8 ]1 V+ F/ w+ R! Y7 o0 ?
printf("\n");! C7 x$ K* }/ [9 }7 ^4 q
count=0;
% W7 `  H; e3 o& Y+ d' @; }h=M;" ]5 H) X1 C  X" x+ o
printf("依次退出的猴子: \n");
" A5 e2 V: C! K7 Mwhile(count<M-1)' Y9 M4 j  q7 w6 l5 B. ^
{i=0;
2 l6 i! V# N! rwhile(i!=3)
3 H% ]5 T6 W" u; @( L6 c{ h=link[h].nextp;5 a" \" n3 Z4 F& c- s
   if(link[h].number)' p, {9 L, a8 }
     i++;}# R+ |6 y4 c. r
, w+ A( G2 \3 @& q
printf("%4d",link[h].number);
, \3 c" ^3 m% M! k7 f2 b/ jlink[h].number=0;9 I7 J0 {3 u$ G$ I6 U9 L; Q
count++;
) }  W- ^: R1 ]: w# {0 m: W}. q$ `! w, ?" ?; C

8 W+ _4 H' P5 D! yprintf("\n大王是:");
! k* i3 ?' \5 j" l  for(i=1;i<=M;i++)
. S0 H9 Z% t- j9 ~  if(link[i].number)( M" k5 Q- _4 \" O+ s. [: _  @
    printf("%3d\n",link[i].number);
# M' w2 I0 \& P  f
, `$ X/ U+ t# M7 W' ^3 ^
/ B! O- `' O5 `. }+ ~" W6 ?}
; c' t6 v, D; |5 X* q3 u) F
第三种是普通方法for循环
# k) n( t7 i5 H5 r5 x) L/ k
#include<stdio.h>
  K$ u( h$ Z" vvoid main()
; T- p) A% P8 N2 B8 R{ int i,k,m,n,num[50],q,*p;
+ x6 E8 \% ?9 W8 S    clrscr();
  v; ~* A1 K6 s1 ^) ^+ {+ L! {# H   printf("input number of person: n=");
+ k2 U3 }8 ^$ e! }, ^    scanf("%d",&n);
" ]( |. {, k. k7 |printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只+ X  @; I: M# b4 s
    scanf("%d",&q);
: J% L3 X7 j* r* i  ?1 ]   p=num;
7 B6 B6 M4 i, j0 I) I- i. c  for(i=0;i<n;i++)- j8 ?: r6 v+ r# N
    *(p+i)=i+1;
; @6 P! c( I+ r/ R. A1 I   i=0;( |  ~$ p5 A4 L) n; T4 ?( b7 |- j
   k=0;+ \+ |  ]3 w1 @9 H+ T
   m=0;; d% l5 V/ Q9 S2 W* s
  while(m<n-1)! ^& S" \/ B5 D
   {if(*(p+i)!=0) k++;
+ O8 q. F2 g, K3 S3 U& V     if(k==q)
5 B( G. M8 E5 l5 @9 e- y6 k      { *(p+i)=0;
7 C- b: t, H# ~, ?( F6 x' @1 a% B        k=0;
3 p2 V7 G- z& E8 B- N! N. s8 i+ {        m++;
' Z9 c$ p, d! ?# o  R2 [- l      }% S& j5 H6 t# p' T. t
    i++;" B; O2 u# Z, D3 e  ]+ k! e
    if(i==n)i=0;, ]! z1 d8 b; {) u: w; A
   }
' Q4 _0 y- q9 |0 [  E  while(*p==0)p++;/ d" M1 Q# a* s' e. m2 h2 |
    printf("The last one is NO:%d\n",*p);: g6 \" P4 M: y6 x) [- ~+ g7 L
     getch();; L# f" P' i- g9 r4 s- Y) V: y6 D
0 S3 |& E4 @) U9 E. p& ?* D
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
9 |5 c4 {5 e3 Q. N5 z+ ?/ {namespace 又费马达又费电, ^; p4 d) @  U) d( U- C; Z
{
5 R- D) `+ r" ]# r( \    class Program/ F9 G$ L: t) k5 I0 W; W: O, u% y
    {1 _0 K; q1 M9 f5 m
        static void Main(string[] args)+ ~5 @/ y* U# u0 e$ q
        {
6 S% B& Z1 F0 K* v: ~            int m, n;  T- P- ^7 A1 ~% M7 {$ v6 s
            Console.WriteLine("请输入数组长度");5 n. Z9 V: n- L2 l  H; ~9 V9 F2 K6 l
            m = int.Parse(Console.ReadLine());//m为数组的大小5 q; U2 n6 ]& w6 @
            Console.WriteLine("请输入要截取数字的大小");7 @, P4 W$ c( s# z
            n = int.Parse(Console.ReadLine());' T$ A  Y0 w$ O! ~$ u- y
            int [] numw=new int2 _0 @4 T+ H# E. C: \
) t# m9 ~. p3 m7 w
&shy;&shy;&shy;;" g" E: u4 Z+ c! u6 {+ y
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数9 H- N$ C4 i" v4 O. h& Y9 [
            {
& _% b, g0 Q+ D                numw[j - 1] = j;1 l+ F$ ~- O; Q/ X) Q; w
            }" y4 F2 h' Y# r% f) h
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
, U$ Y" X. p* ~. o            while (d != m - 1)
( `6 u( Z$ D6 O: f, M% f  f            {
- F' ^) {7 D4 q3 M- L* e' f. x                if (i == m && d != m - 1): L$ ]  P, x+ p4 M4 O
                {
! P2 n6 r! p9 x/ i                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!& u$ w5 D4 a7 ]0 d- x0 ~" H
                    continue;  `) Q1 [& \% U( o
                }
3 Y, R5 p0 p# D) Q: ?8 R1 E                else6 W' u# ?) F, m9 }3 w3 b3 w5 a, P
                {5 R# C) e* E" h1 J  G+ b$ z) h
                    if (numw[i] != 0)% e0 q. J& C2 ^' R! m: n
                    {8 E2 i2 Z/ ^+ Z6 i/ O" M
                        i++;
! H7 k1 l1 v2 }                        k++;& _1 D- T' K8 v  o& r5 X1 J
                        if (k == n)! {% K! P* d6 O8 X6 {
                        {
+ `( w' Q, g' v, S4 z% l  r                            numw[i - 1] = 0;//把在n位置数组元素的值改变了! x! K! m! }/ u" g& O& f$ H0 |, ~: w
                            k = 0;5 G3 r0 k" l; L
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
8 R5 p  y6 j6 ^                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
! k8 m- w: x% }! h- e+ F/ o$ m                        }
, `0 m  I, t9 G' ^, d: O                        else//输出暂时还没有改变数组元素的值3 U7 [& ^- H+ }$ s& ]1 W+ y0 T  O/ g
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, b: [3 `3 b' z& E$ I! \5 z                    }
( ]3 ]- ~5 \7 ]3 j/ `- g                    else
& @; E0 l7 c( E                        i++;//数组元素为0,直接跳过,不计数。。。
/ L; U7 u1 C+ ]# E, W1 w6 G                }
# ^& J; ^# A  T1 B& Y9 s ( {$ {6 j" \5 v7 @- d' |' W# _

1 M! i& K) x& e* f1 l( T3 ?/ D! ^0 O            }//结束while循环
2 l9 C2 z, `. C, y: Z            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦& r: ]$ q& y; |# T8 j+ |
           % S, r# _" J! v7 N- X/ P
                if (numw[i] != 0)! V4 E; Z6 B# {' K6 |
                    Console.WriteLine(numw[i]);/ L" p5 [' Y) f
           + u! ^, c  X) l& u0 N
            Console.ReadLine();. O# _9 u8 }, s* w/ x- P
        }2 j- d* \8 ~! b1 z/ F' Z* @$ i
    }
5 ^8 P+ h8 Q0 S}% m' `) K; U. A, b! C; v# N; d
小甲鱼最新课程 -> 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-14 02:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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