鱼C论坛

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

猴子问题

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

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

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

x
大家好!
% |6 B7 }% _9 t+ X- j/ C这几天我在忙着编一个问题,我用了一种方法编出来!
& i( c8 I; _  n& `1 Y0 u0 H但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!; i5 b8 @. \& V6 h: W
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
' d. J7 n9 O, {0 k4 ~) [+ U/ ^" a" O( ^0 Q( u3 T( N3 z
. h% @2 ]8 K% P3 j1 C
                            题目
  m) i1 [  e% W山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。6 `3 u7 Y# Y( x% b1 M! m
第一种方法:利用循环链表: u" \3 W2 E: ?( [' U
#include<stdio.h>4 e8 b# ^9 q& c/ Q5 {2 h/ s; r
#include<malloc.h>
' G! t% n! g( M0 c#define M 8            //共有8只猴子3 s) B. R, i/ `( }$ R) P/ D' ]
#define N 3            //数到3只时退出第三只
: `' ~! ^9 _7 t$ ?typedef struct monkey
+ ~& s. K5 E8 R: S# a% ~' ~0 Q{int number;
- O2 c4 w+ l- h7 y( S: Fint flag;
, w. t, ]. c1 w) C$ D' Xstruct monkey* next;
3 n" I3 h# @2 I4 X8 u" B6 o! M& t}MONKEY;# Y2 c- O/ e7 x4 p" o) o, O8 [7 ~
main()
! c- R& n0 K* @* }: ?{ MONKEY *head=NULL,*p,*s;
0 q) S- d2 @: N1 b6 e  int i,sum=0,count=0;
  F3 L9 Q9 w( k- t& o+ F: H# O$ w( W& t  clrscr();              //清屏: ?6 D8 e: _3 H; `8 t5 b; ]# `% ~
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
& G- o0 d. y$ w1 H  p->number=1;p->flag=1;1 X+ G( _* b0 F  c+ a
  p->next=head;+ [9 K4 k- e9 K- b/ ~/ Q# `( k
  head=p;7 s( e& y) X" @, Z9 a
  for(i=2;i<=M;i++)9 w" G, i/ u9 ]8 N: u2 P& Q: Y% g
    { s=(MONKEY *)malloc(sizeof(MONKEY));
( l5 n8 @6 U* O6 x4 K0 P1 Z     s->number=i;s->flag=1;
  b2 G$ s/ l7 f( c& X. i     s->next=head;  R3 H" O" F% a2 L9 p2 A
     p->next=s;p=p->next;
9 `+ e( N- i2 @2 p, Z: d; a: l2 H    }3 X) y' d+ ~& ~% l8 N3 j
    p=head;( L2 T0 ~3 U7 Z3 ^. Q9 s. s0 A3 I+ w
   for(;;)) N# V9 d0 t- U4 h6 t, o
    {if(p->flag==1)
2 p) R& Y9 B( d2 A* K( I       count++;8 a  f% r& D) V8 V* Z: N) _  ^$ ?
     if(count==N)
# B' t* z* N  @        {p->flag=0;' V, o: l% m( ~- T' g( q+ v5 o3 x
         count=0;& D, C* |' s: X' i* ?! R0 A$ @$ B! d" r
         sum++;}" E1 r* r9 R( l
     if(sum==M-1)
& y8 y" G* M) K: K0 L        break;: |1 }& Q5 O/ X7 }2 |( c- b
     p=p->next;7 \0 H1 N8 z, }- o, {* n' X7 f
    }! L$ v5 W$ o, S$ B( M
    p=
7 I1 y% ]) Z6 B4 W8 {: d9 Q    head;
5 z0 c) R) ]- d8 W! Q% U    for(i=1;i<=M;i++): p1 X$ L. Z, t: ]* d
    { if(p->flag==1)6 \$ Z6 Y7 [. c. H" }5 R
        printf("\t%d",p->number);
' t  J- H& t. Y: e. D  N* \4 C* u      p=p->next;
! I7 u. Z9 L; L& T6 ?  T# |    }6 r0 E6 e3 R& u. Q4 N. F

( I2 {! t4 j- _; O9 ]
. X1 {. e- s9 M2 F: F: h- T' L- [$ `6 _
}
% |' Q# ~9 g" o* X/ B4 [( O/ P. }
第二种方法:数组8 I6 M. }- R8 s' m
#include<stdio.h>
- ~" b' s* H' H+ l' ~#define M 8
6 p8 `- F/ x) C# |struct monkey  F$ N3 {( a& p: {' {
{int number;
# Q0 ~. _, E' O& e( C& aint nextp;6 F( V+ {0 |* P+ N% M
}link[M+1];
. @2 k, J- S/ H. o7 A9 p, B. D* l/ U; W1 p% p' F7 @' r
void main()) V9 Q; ], N9 l2 b/ z! l) s! L) ~9 a
{int i,count,h;
$ l$ z" V8 E( Y! Q) Qfor(i=1;i<=M;i++)0 y6 s" M8 _0 B! m( v; e  B
{  if(i==M)
. Z- [+ m, Q5 u6 V5 m" u' A+ F: W   link[i].nextp=1;6 o+ k4 [! N/ i" W! `9 l# }
   else' w. |. v* I+ y0 K; Z1 Z* ]3 j
   link[i].nextp=i+1;
3 j! f' g7 g6 |" X0 {. C: ^  link[i].number=i;
% N# K4 ^" m5 [! r2 s" G, _( G# x6 i}
: ]. Z4 c9 F. Y& Fprintf("\n");
4 U% x$ _9 `/ z/ l, u# dcount=0;0 x$ y4 G3 l# S! A
h=M;9 [' @1 V" i: j* M+ O- G! h
printf("依次退出的猴子: \n");( |% Y3 ]9 K4 S/ A' y) E3 V
while(count<M-1)7 j$ p5 e0 K: a
{i=0;. o$ Z0 v4 c, ]3 A* @8 B
while(i!=3)+ W: }7 a6 f3 I9 [
{ h=link[h].nextp;7 V4 W' ]' |& P
   if(link[h].number)
8 y* X' g: H% L$ i! V     i++;}
8 D, w$ t+ m& w  r  R. L$ b, z$ q* V% @9 z
printf("%4d",link[h].number);
7 V+ V# M$ n$ K( `link[h].number=0;
/ }5 I) `) d) q( qcount++;
7 K1 b, C3 \4 U- ^  t- c}
: H0 [2 Y# ~; H8 ]0 V
+ ]" X; `* A5 {% f; }printf("\n大王是:");
' |4 T( Y8 `% Y  for(i=1;i<=M;i++)
! Y8 b+ U( n. N' b9 B/ X) u9 P  if(link[i].number). S/ }9 k9 U3 `! `3 P  D4 `
    printf("%3d\n",link[i].number);
' n( |2 E3 g" l) V) l+ n% Z' k# D- v4 e2 f2 s/ L

5 ]  @) m$ z2 v6 f& T}

0 S% j9 h0 }! y3 F5 @第三种是普通方法for循环
$ y# @. O7 Y# D; |8 h  m5 O" U- t  ^! x
#include<stdio.h>; x, {2 q+ V. I- h0 v1 M9 n2 P
void main()+ o$ K- X% Z/ {" Q7 i
{ int i,k,m,n,num[50],q,*p;) z4 }# f5 K9 [, ]4 i/ k) {& K3 G
    clrscr();5 S8 R  _2 B1 F
   printf("input number of person: n=");/ ]. q  e/ P, T  a) i: l
    scanf("%d",&n);
& B; S  b# x; q0 A+ j/ y; Sprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 i7 r0 U) k6 d$ ?' s! ^& {, N    scanf("%d",&q);
* ]& u- D/ K( E6 b6 ~6 |   p=num;
3 a  l- T7 ~+ U9 e& ~. H  for(i=0;i<n;i++)
; `) W8 U+ }% G6 v6 F- K; _  |    *(p+i)=i+1;( }$ V$ w/ |+ G0 \$ c$ q
   i=0;# z# d+ i7 u3 A3 b# e
   k=0;4 v, Q) T! I- a' K9 f+ M3 k% V# w
   m=0;$ }7 v0 s4 A- M
  while(m<n-1)
0 R6 h9 M  V9 v$ J( A8 O* O1 c; u   {if(*(p+i)!=0) k++;
! I4 @7 r& F' |3 o; ]     if(k==q)' J: R1 a# y  D: u5 W3 C, X& G; A
      { *(p+i)=0;
. i& W5 q! a$ p0 X" J5 F5 V! H; v        k=0;
4 e$ _/ M! w& w  \5 {+ |( a5 P        m++;5 I! h9 o; X0 K; d5 w
      }
# S$ t  o7 Z5 |% b8 ]3 Q    i++;7 b; V( U2 j- t* a3 p
    if(i==n)i=0;
9 M9 |* h8 s0 i* h  b   }9 [1 [9 J5 i: W; _' F
  while(*p==0)p++;7 s9 U; [, G- |
    printf("The last one is NO:%d\n",*p);
1 m. t2 q& G! h2 s     getch();( v1 S* z) \8 i$ P2 f
) N+ \% ^0 ~, X1 Q6 r6 y4 u/ ^0 |
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;. W5 Y: E( R2 v0 O2 @* [0 I) A! j
namespace 又费马达又费电
. j5 d; ?2 `; c( s' h* ~{
0 X2 I+ j6 Q" E: C    class Program
2 `2 E0 m3 v; R0 G3 C    {7 L" Y7 b3 _1 u1 p6 H# q; l+ }5 v
        static void Main(string[] args)
6 X  Y, D& u* ?3 s6 r6 a        {: H$ P' j: ?' @' z+ Z6 L1 O
            int m, n;& m; q! K) P. f) I
            Console.WriteLine("请输入数组长度");
2 ?; E9 c6 }. Z4 H$ I" p. U            m = int.Parse(Console.ReadLine());//m为数组的大小
( I! b0 b. @  N; N) @$ }+ ~            Console.WriteLine("请输入要截取数字的大小");
! P7 O" B: I- U/ A/ Z/ |7 M' e+ r            n = int.Parse(Console.ReadLine());
& d6 [1 v6 y; b# Q8 E) M            int [] numw=new int. B, g) _9 N, v: W
7 O4 [8 V" g% [5 Q: Y$ U0 a
&shy;&shy;&shy;;
4 Q4 q8 M1 ^- _! `            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数0 a2 |# B- [- a% L9 a" P
            {* f4 s; Y) f- I0 \. w* u
                numw[j - 1] = j;' _. e0 Q) w, P6 h( W
            }
5 a0 _3 p% ^! o! q' C* j            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
: E' D" F$ J/ P            while (d != m - 1)# @2 O0 k* Z& a8 T& [/ C( v
            {
* y$ H" y6 v& w4 l- S, ?( b0 k                if (i == m && d != m - 1)( z7 T: x0 Q* P$ }( T
                {
- J; u9 _: b0 y# Y3 W8 O                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
3 J' ?9 A0 ?& ]& f; y' Q                    continue;
1 G  X7 B, S. q' {                }
& w8 `6 o  L7 j                else0 X& ]. d5 Z  o3 y
                {
. G3 {: [% ~4 V                    if (numw[i] != 0)  r0 A% J1 w1 s" x/ u7 O
                    {
! K0 q$ Q. }% n+ X9 ]                        i++;
. T+ N9 w+ Q' d0 K) C) B                        k++;  p/ S  [9 Q1 u6 S
                        if (k == n)
$ a- _* T' O' V: I# [* f. _                        {1 {8 R+ z! o5 `- i% j. W& I
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了5 O6 ~. J8 K/ Q* |* v0 w) ~$ H
                            k = 0;
/ B" K; Q' `3 q, O              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1$ [3 A  q) G3 J% f; T  l
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);$ T1 h& ]4 p4 \. ]
                        }
7 N  g6 G8 p4 x7 M: @                        else//输出暂时还没有改变数组元素的值& @9 }/ b& [' N* e: Z
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);7 v; Q% o% q! b; d! B
                    }
+ {( ^4 |! V; o- u0 M                    else7 c5 }5 D2 ?9 C% Y* a$ D6 q
                        i++;//数组元素为0,直接跳过,不计数。。。
( k, R! e0 L) B0 r, a. U                }8 W! r, n9 O5 y. P  B1 Z
4 s, T& F$ t1 Y  Q3 O- ], V; q* `
5 }, m6 P8 I* {. u! g+ V8 `
            }//结束while循环2 \: Y( @6 }( v6 ~4 Q7 F
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦6 r5 j* g8 t* [1 l3 A
           
4 y8 p! v1 J& A$ |                if (numw[i] != 0). @& D, F) u+ f' R
                    Console.WriteLine(numw[i]);
  L; U9 Y1 x+ y& l8 |4 @           1 U! o* z" U4 T& n( i5 ~, I
            Console.ReadLine();5 Y6 a+ m0 }: C# `, a- V% L
        }# e% z( X; j' H
    }6 ?7 Q+ F5 r' z) O9 y, {3 T& a5 g
}" k6 Z4 `/ U$ ^1 f3 T
小甲鱼最新课程 -> 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-5 22:22

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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