鱼C论坛

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

猴子问题

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

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

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

x
大家好!
2 J& `  e, K9 Q1 c, b2 {这几天我在忙着编一个问题,我用了一种方法编出来!- w# a9 o6 f. K3 H7 a$ m2 w( ~" C
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!4 F' o! G# }; H2 @- B
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
* Q" L+ Q9 j* r
4 l- I, r) c" d  M9 [4 q* s, e8 v6 N# U6 Z% p7 s# V9 c
                            题目
# i% s; ~8 k7 W9 A! ^% H: x( U山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
1 }8 H1 d' q4 o# T5 ^6 \: F+ {第一种方法:利用循环链表! `; F2 r! \! i1 t! ?
#include<stdio.h>
+ l" _4 X. J) H! p#include<malloc.h>7 j7 {! u2 o2 G
#define M 8            //共有8只猴子
% k: a4 M* F( A7 M#define N 3            //数到3只时退出第三只
" e! ?: w  o% S" W2 h0 Q4 Ftypedef struct monkey. C/ \' u/ j5 Y5 I- c# g" M9 @
{int number;
; H& G$ J0 h( S6 }, k9 @& Vint flag;
" G0 ~1 S. _' t. X1 J* l' @struct monkey* next;
* R$ M1 s  e, w. D5 e0 D}MONKEY;
# V- z; A/ k' p' Q) D4 ymain()" l3 w3 k! X( U# o. _
{ MONKEY *head=NULL,*p,*s;2 d; c: H- H3 h4 x" O8 d: S
  int i,sum=0,count=0;" {! F. J: V$ l; q3 w
  clrscr();              //清屏7 c" U2 I. L; ~  H% }
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
6 s0 G. A  Q* f  l8 n' V9 ]( {  p->number=1;p->flag=1;6 d# s1 M0 P/ L' ~2 B
  p->next=head;
2 U( t. e6 R0 Z6 s  head=p;& \, @0 A7 e+ W; p3 i& a) M
  for(i=2;i<=M;i++): R/ j; t* C+ d) K  ]; j! t  w
    { s=(MONKEY *)malloc(sizeof(MONKEY));
7 ]0 P$ k7 E4 U# F& |$ t7 K     s->number=i;s->flag=1;
$ U7 S. ^% [! }& @% @     s->next=head;
2 `9 S% t2 e5 d, V     p->next=s;p=p->next;
' V. _% ]9 g" ^& u0 X* b5 K    }2 f8 Q* e# s5 N9 V# S/ N
    p=head;& p$ t( _" D2 w& ]1 I
   for(;;)
* w( y9 P9 M; f4 q4 G0 e    {if(p->flag==1)1 P' ^7 [3 V/ P% B( V% z5 z/ S
       count++;
, `5 d; D& [- e9 R     if(count==N)
8 |; R$ c  N: l5 s! I        {p->flag=0;; b1 k1 _4 r" Y2 ^. `
         count=0;2 j9 a  u  N2 }- n
         sum++;}
1 e+ N* j+ o6 H% O# z9 X  ]     if(sum==M-1)7 P5 @9 q# T6 v6 h; h6 I
        break;) l" h  {5 [& A: g* [; f
     p=p->next;
, }8 h* d; t# F2 Z0 o( S    }
  e9 G8 U9 s! D  }* L    p=1 g  |/ t9 P1 l! v; o
    head;8 S1 X, L; x, c9 a* }( R0 C6 o
    for(i=1;i<=M;i++)
" s& l5 B; A! T    { if(p->flag==1)& ^- `% k, i  e8 X3 l. O
        printf("\t%d",p->number);
3 }; H( I4 ^1 [$ a      p=p->next;$ `* C1 ]- w: P
    }
+ D) m- o+ H; B* p6 f
5 o* ?* j$ ]0 k  Q; d! t) ]9 V) f  W9 U9 V1 U% c

$ c% R% l7 R7 Y}
: N" o3 h/ @; t9 A* _& j
第二种方法:数组
1 b% A2 `3 u, A0 ]3 R#include<stdio.h>
6 b1 W5 g7 {: x: Y: r- j% e#define M 8
7 C2 [6 A* Z' |8 l% gstruct monkey
/ H5 s; a' J6 }{int number;- o7 A. m, g+ R$ A5 o
int nextp;
9 \, G2 d. w" ^9 i+ ^0 [" a5 D6 `}link[M+1];
! J5 X& o: t$ c4 c3 R- m! I7 u& T2 A
+ D* M3 m. }. x7 |6 ]+ z; O# }void main(): }" l# a# G- C1 U; R
{int i,count,h;
# w% Z" E2 ~( q0 wfor(i=1;i<=M;i++)
& g5 j: O0 _; i& }3 ]) `, h{  if(i==M)
  Q7 ~: @) y7 Y3 x$ v! {   link[i].nextp=1;. J6 ^0 O0 F& s; C8 L# {& Q8 U1 l" H
   else
" e5 {# t! ^# C   link[i].nextp=i+1;
  _; m" t& p8 Q  t; p1 r. x% H  L  link[i].number=i;
# q8 O) s7 b/ F% Q$ j}
/ H. ~/ A! ?) jprintf("\n");
- _; j+ o7 O9 F1 a9 U) Bcount=0;. G9 S2 W  k4 L0 _+ T
h=M;
. p: [2 E2 y6 y/ m. Cprintf("依次退出的猴子: \n");3 X) |( r9 F& ]' F0 Y
while(count<M-1)
  ^8 w2 b- a& U2 V" {7 R+ i; ]{i=0;
2 y" p7 N" u$ L# C' N, {' Pwhile(i!=3)4 x! i" f& N1 q; }$ }
{ h=link[h].nextp;
; t0 O1 u% ~& P/ u! B: A4 u   if(link[h].number)5 U7 }  I: ?8 l
     i++;}+ g# t1 R( Z) ^% d6 i
: M, l9 Z9 j" B4 C
printf("%4d",link[h].number);5 Z0 u- M' P3 s7 ?! v
link[h].number=0;
& L) f' l6 G3 ?: }count++;3 T) r3 q8 ?0 H9 K  f1 S* F
}
' d* ?' n* G  |: F* x# c
8 Q2 ^$ i/ j; B6 n, rprintf("\n大王是:");
3 S' v9 `( Z2 n; w) T: D+ K* D  for(i=1;i<=M;i++)
) Y2 X( r( Y. k$ B3 u5 ~( X3 o  if(link[i].number)0 A6 i0 D+ H; i( g4 f* D1 q1 [
    printf("%3d\n",link[i].number);: @$ \( K7 T$ l, }$ A. z4 }9 e5 ^7 `

7 h2 @/ t0 H1 z7 Y
& R6 d! O0 s( U7 {  Y$ p}
$ N  Q; ~# C1 n8 h/ h
第三种是普通方法for循环

2 @/ e- g: F8 H, Y, g0 W#include<stdio.h>8 n& v4 Z6 q; ^3 B
void main()7 x/ u! ~3 Q8 {6 y2 |  s" G
{ int i,k,m,n,num[50],q,*p;
; C2 g- ?( s( F# w5 F; K    clrscr();
$ n/ i4 ?) _  H, G# G   printf("input number of person: n=");. N# f2 \) ]: E% o0 f# Z: N
    scanf("%d",&n);$ C: F# ]8 R4 D
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只4 {7 G0 \; J* ^6 I
    scanf("%d",&q);) h3 B7 c1 V+ S  `. N5 ^% ]2 `
   p=num;/ v, Q+ o9 }+ {
  for(i=0;i<n;i++): N2 E; a( ^" P% W
    *(p+i)=i+1;
! j) n' E3 ?3 y# z- j4 f   i=0;
+ K: g' u$ X6 [3 B: A: X# H   k=0;7 ?  h9 H7 ~& r4 A0 d( M
   m=0;% o, q* Q* v5 j$ a% n, @
  while(m<n-1)$ [8 B" i7 e! f% J7 ]( q
   {if(*(p+i)!=0) k++;2 P, i" d- O9 n) c! E) {. H
     if(k==q)
$ Y- n# r/ X. T4 O      { *(p+i)=0;
4 X/ f6 u& ?' y3 X4 w9 m        k=0;# y6 b6 z* q( U! q
        m++;3 a! a4 m% W# v3 U. j
      }! s& g; c7 m- [: \' T6 x
    i++;
: F& |2 e6 X" f% W- U& O( N    if(i==n)i=0;
+ ~/ s. s4 J1 I& \% [; f   }
6 z* q5 P( x) W+ f2 X  while(*p==0)p++;
" Y+ V4 f( J( E    printf("The last one is NO:%d\n",*p);
+ h- L( V& v$ G3 \  L. `1 d     getch();
% k4 d- m; \2 {" n6 E/ k3 E4 S  \9 d! C: T5 p& F% H# r- k- Z* u
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;2 M7 M2 `/ T8 F' V# k1 E4 a
namespace 又费马达又费电: a& Q7 t6 q8 z+ G0 `* `
{
/ ?  m  b, V; G    class Program8 X- G- x0 @2 {! D  p! P
    {
8 J/ P! F1 ~$ d6 t$ q- q        static void Main(string[] args)
6 \! q, R$ P; t* ?- m* V" q2 w        {
% C4 R4 y" P5 M9 |            int m, n;. W1 s8 U: y0 s! S( c
            Console.WriteLine("请输入数组长度");
' r# A5 {9 ]# `: Z, w4 G2 s" h            m = int.Parse(Console.ReadLine());//m为数组的大小
6 j2 ?! A+ c1 X* p+ ~8 W, g            Console.WriteLine("请输入要截取数字的大小");) W3 @8 Z( z! S* f8 X& R
            n = int.Parse(Console.ReadLine());1 y0 H" r" d  F4 h  _1 h1 h: @% D' p
            int [] numw=new int
! @- @! a  C  x: j4 m. u0 F8 o% w( b- i- k1 a( R, S9 l
&shy;&shy;&shy;;
& a  R: r7 j4 z& {4 O0 w9 E6 {            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
# x9 v, R4 r) J, B  ~% c            {
) ]9 o, {/ F- t- c                numw[j - 1] = j;# g0 b7 M; I( O8 z4 X
            }
* f' G5 X; B3 t( [7 I' `$ R& Q            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!/ _) r' b: m. m8 w- E$ Z
            while (d != m - 1)
& z( o1 \( _' U7 g            {
3 n, w: c) b' M! Z' z  P                if (i == m && d != m - 1)* H$ `+ x( v* J0 Y0 z  R
                {
1 }8 |' X' T. u" P* R                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
7 _: h+ a  ~9 ]) y$ Q5 q                    continue;
4 @) P5 Q9 v8 ~5 e6 D4 H+ m                }) ?- U5 h' X. `& |
                else0 [5 G8 U6 h/ N  R. s
                {! z% }5 J# W% A: }
                    if (numw[i] != 0)7 u* _+ T( F% M3 ?% n8 j& F9 J
                    {
9 z' W" c2 d' A  y# B) Q                        i++;
; ?' `) M7 @& u' L                        k++;3 w5 N: Y5 m) S* T% [0 x
                        if (k == n)3 S2 P: q9 N2 i  q0 a4 l  I6 {2 X
                        {
8 E+ q  m4 Q9 a7 N7 N3 l                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
& l! \5 A- B. ^# y5 }! r7 o9 j                            k = 0;7 P4 x% X5 S) j( N+ C$ m
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1* x* H, P' C2 ^1 T/ h1 S
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);) D) w) X- L5 W8 \* \8 Q2 P
                        }
  Q" O+ W- t9 H) ]- W; }                        else//输出暂时还没有改变数组元素的值
- Q6 q6 H( ?' ~% ]) D                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
5 `, G* Z& G+ C7 x: _9 T, ?: _                    }
# c1 s! E! J# F9 w6 l9 }                    else
4 j$ n8 d1 I* e5 C1 l) v                        i++;//数组元素为0,直接跳过,不计数。。。7 J6 t2 I' W; X5 e) p( h& o% [
                }
& ?! y0 T8 @( T- Y8 ]8 w& v2 ^ 4 G0 W2 l9 ~# q

! r: k) d( H$ m. O# ~  X" Y            }//结束while循环
  k/ L8 t  ]3 h- M  O1 Q3 v- i2 h            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦: [% P) t; M, R8 B3 [+ A7 o# @
           
9 y0 d, Q% t% r" c3 K  h                if (numw[i] != 0)
+ m: N+ s1 C# s                    Console.WriteLine(numw[i]);
. U6 \) ~4 q7 f! f; n( T: u           
& g" S% C( t: b# c9 \8 d. `% k* i            Console.ReadLine();: a  ^/ ]' r1 h: y
        }
0 i- j6 `* n+ V& E- A& v  T    }  B2 c0 I3 [3 X& s$ c
}4 h9 S0 F& T" D$ L9 y
小甲鱼最新课程 -> 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-16 12:07

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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