鱼C论坛

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

猴子问题

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

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

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

x
大家好!& b% _6 n+ w) X# ^; I
这几天我在忙着编一个问题,我用了一种方法编出来!, [1 B% g# B' B1 i# K
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!+ `3 w/ o4 }1 M' n* h* }4 |
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ; q2 A) q( m3 J$ N6 d
0 [4 V4 V- I2 ~0 Q! ~9 U: D4 i
9 d9 R& u: P( X& B" W1 o
                            题目8 O" D1 u2 ?) Y. l; N
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
, O8 y$ |( z+ i" B$ z9 J' ?第一种方法:利用循环链表
" M" p; N0 f4 s$ m. `#include<stdio.h>' m8 R. I% B; O5 ^0 g+ |! B6 }/ a
#include<malloc.h>9 k$ r, d& y" f' ~& ?, E2 [
#define M 8            //共有8只猴子
/ J9 G) d" \1 j#define N 3            //数到3只时退出第三只
) C, d, t* l0 H4 u$ btypedef struct monkey
! g1 L" o) f# ^8 ^4 i6 w{int number;
7 r  @2 C' s' k1 d* P) I* w: k7 Qint flag;
/ r6 G  P0 t  K/ X9 d$ l, pstruct monkey* next;
3 _" h3 U& B( Q$ T" F}MONKEY;0 f8 O$ F( g! A6 a0 e% V
main()! s1 Z; O+ N5 I2 [) y
{ MONKEY *head=NULL,*p,*s;# [! w0 J# w8 v: }" b
  int i,sum=0,count=0;* _( b* D- }1 F7 w0 S! J& E
  clrscr();              //清屏0 H; Z. Q% e9 u0 P& h8 z2 G  D; [
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存7 c# ?& E8 C) l+ b% n
  p->number=1;p->flag=1;
/ V4 S% I1 C1 C  p->next=head;
: G  p  L$ ^. Q" p% S7 r: E  head=p;. E9 Z( x. c- V& W
  for(i=2;i<=M;i++)
, j+ }! Y5 @8 i    { s=(MONKEY *)malloc(sizeof(MONKEY));4 ]; ^% t7 N6 D& @9 w8 j
     s->number=i;s->flag=1;
4 p$ X: W. g/ d& p     s->next=head;
' @) y" b) c6 l& h9 _0 F     p->next=s;p=p->next;
' |2 j+ k; C& W; n  s, E    }
) P1 q0 e' e2 `  o' T. y- K' c    p=head;
5 F* `* E. {4 C6 q4 I   for(;;)
; B- r0 H! X- F7 D; z, D    {if(p->flag==1)/ m% N# l4 O' m) @
       count++;/ F7 ~  S, Y# ]
     if(count==N)
( y  _9 t" h. x( b9 C: Q5 M( k: h7 @        {p->flag=0;* `) I0 @- f0 g0 J+ O( F# ^
         count=0;
7 ~4 p6 u. e4 \' @' _         sum++;}& `  x' x, V7 J; [- ]
     if(sum==M-1)! m* m: D1 Y1 H& T1 ]
        break;
4 g- O, [8 n- L0 U     p=p->next;
) O& x  J& x2 N4 w( m    }9 O5 k* f6 s# ?) G, K# V
    p=4 P% `4 k& r6 K& O8 O
    head;
7 }; g4 M1 ^4 R$ v    for(i=1;i<=M;i++)
+ `8 y2 T) C1 |2 k    { if(p->flag==1)) B) d! P( t/ j# F* D; n4 S
        printf("\t%d",p->number);7 `, u, x9 A& Y# \9 |  W/ ?9 W
      p=p->next;
$ S! j/ a+ P& O2 V. Q    }# m+ e( e! j+ ?

8 l& v: k! R5 O$ \0 m3 M: X8 s2 X& s, M, |

; m$ b2 j3 |/ l  l; r}
  {* p8 l3 [3 w/ d. H4 y
第二种方法:数组. Z& G6 K) Q/ Q5 u& k5 e
#include<stdio.h>
4 r+ s/ B% p  L, t#define M 8
6 @2 H0 F& I& ?# y, J8 Q. _struct monkey4 A- G+ o, |5 ~
{int number;4 o8 a" }6 ^. D. f$ V: @0 ?
int nextp;1 r* n4 `* o# ?0 _# s7 I
}link[M+1];) P! {; Q4 J/ H- g1 C
. W, u9 K$ C; t0 [# g0 A
void main()
9 p( j8 `/ T, C. X{int i,count,h;
5 n' U+ L8 G6 K6 ]0 [) Ffor(i=1;i<=M;i++)/ c* T' Q5 N) Y2 v
{  if(i==M)
5 R, B, J8 d. T9 G; F7 g% N   link[i].nextp=1;
9 S0 B! R8 E+ H8 n* Q; E   else/ [. {3 T7 L- t  g$ f/ G
   link[i].nextp=i+1;. L! O3 J" u8 E# o7 ^
  link[i].number=i;' ?5 h8 r* q: r5 H& k
}& l( f1 a6 E, n  k9 Y0 e
printf("\n");' T0 F( N- W1 ?+ x5 }1 o: ?
count=0;4 E& d8 y# j; X* e& J
h=M;
! @1 s9 N' q% L; a# fprintf("依次退出的猴子: \n");. o1 x! o8 w$ X% X) @
while(count<M-1). H9 D+ t7 B. l
{i=0;, ^' e) [' A6 j; F+ ~' ^
while(i!=3)1 T- l( L6 U8 V! Y
{ h=link[h].nextp;3 `* u1 x1 f, N& U7 Q, o
   if(link[h].number)
8 C! A' C9 U. v- p     i++;}, K7 |" j: q# z3 [% T6 D; Q) x: q! `" G
. Y" t$ g' r" f- N. A9 X
printf("%4d",link[h].number);
7 u& w; I) L8 b7 _* Hlink[h].number=0;. H" s% F+ Z/ n8 E8 U6 ~; o
count++;# p' N+ X; b  V$ @' M# z4 ~2 W8 i
}% o% |: i- j( V8 Q- p- _8 k, {

; H: E9 a0 b. j- B+ F7 vprintf("\n大王是:");. S9 K# j# E# d" S+ T( K: Z
  for(i=1;i<=M;i++)* _9 k( j; f: E, m, `- P
  if(link[i].number)
) V: Z: Y4 B4 s9 @9 R2 n    printf("%3d\n",link[i].number);
) L' `, p% g3 f% X1 G& c4 b+ G; }8 z
& V/ s/ Y( J& E$ d# Y4 \
}

& @8 A; J5 @6 e' h2 G! {1 W# x第三种是普通方法for循环

3 L) K4 i- \8 u- z+ ~; U/ i#include<stdio.h>
8 N3 X0 I( f9 z: s$ Rvoid main()
* H6 V4 K) J' h/ v, _2 `% Z{ int i,k,m,n,num[50],q,*p;
. h* [- d* y' \$ n    clrscr();* i. g( i4 j' z8 d8 q2 e" `$ Y( ~
   printf("input number of person: n=");: L' @1 L, L: I* s+ R" N$ |/ c
    scanf("%d",&n);% S. c# v0 H" `3 f0 h; m
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只7 b2 j$ |- o' U7 n
    scanf("%d",&q);1 q, ?7 E. s) p9 G0 K
   p=num;
( E- S9 z" V2 R  for(i=0;i<n;i++)
& [- b2 e: Z7 N  Y. i3 T    *(p+i)=i+1;
9 u8 s( L* {# r2 b- [0 M   i=0;# ]  V! M8 k, Z4 k# l/ j! |
   k=0;
) S/ p, h- M) p* M6 ~; I5 F   m=0;5 Q2 L% ~/ f% ^4 v
  while(m<n-1)
& X- q: [; _3 k# t   {if(*(p+i)!=0) k++;
0 l4 b; p( Q7 {2 p- F2 T2 S     if(k==q)5 W% H) J5 K+ `7 r3 s. ]* y
      { *(p+i)=0;) [1 s  N+ ?1 G+ p3 \
        k=0;
( p+ x5 S2 Q2 q% u        m++;
. e) r+ |; Y) }$ x4 I7 @      }
5 }! J8 h# Q) k# |( G7 Q3 T    i++;
, \2 u8 p& S; ~, F    if(i==n)i=0;
9 d2 q  ~, j' [: b   }3 {* o6 i: F( _% W' s
  while(*p==0)p++;  _; y- _; f# x' Q  e
    printf("The last one is NO:%d\n",*p);2 G3 \) j9 @& Z- h
     getch();
5 q0 K, x0 E( H) S0 \" H3 R  E: [( r4 w- D7 v
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;! `4 @- W% G. K/ ~/ d
namespace 又费马达又费电: B+ H* ]; h( F$ R) a6 {4 M
{
5 a5 ^: N4 v6 Q% I. ?& C1 m    class Program4 [2 g* L8 u# ?8 b6 c) g
    {
$ h4 R+ w) P3 a        static void Main(string[] args)) T8 ?6 d2 w" R' D" M
        {
- y$ S4 ]) U9 w1 Q7 q, ?            int m, n;+ L+ T6 n: j+ F0 U8 X0 A; W
            Console.WriteLine("请输入数组长度");7 B' E  I  M2 X! H( g& _0 o' k# G
            m = int.Parse(Console.ReadLine());//m为数组的大小
1 ]/ @$ C2 M; s: k( I            Console.WriteLine("请输入要截取数字的大小");7 W& x# B  n2 `
            n = int.Parse(Console.ReadLine());
7 `& f9 D3 M! Z3 v4 i% U7 A  n3 ]            int [] numw=new int4 }0 T1 b# U+ |( p- l- @
& ]2 M( B; R7 [2 _- ~
&shy;&shy;&shy;;  `8 X1 @$ o2 D2 I7 u
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数6 ]9 d8 c% m" }( `  b: n
            {
; `  y( [4 y' W. n8 ^                numw[j - 1] = j;
" J! }; I" q4 C6 g5 \2 M- {            }
* w9 A& Q# S1 n, f- l5 |3 k            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
' K/ D: G7 i$ U  _+ z            while (d != m - 1)
7 v: _. g$ j, n4 W% m            {
5 I# L3 w% O. X, G& N* W$ T                if (i == m && d != m - 1)
2 @/ ~- p; o% M9 u! \9 X                {
" V6 F3 g3 Q; |+ Y9 O                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!) q) e2 M, {6 ~4 A) g
                    continue;% u" P9 S0 U/ O5 l
                }
2 j9 l, U$ ~) U9 a! u                else$ e& D6 q9 p: B3 b
                {
$ m, O: H' X/ s  {& t8 }                    if (numw[i] != 0); i3 s( q! c3 a" N8 K
                    {
" U! P& d+ p; G. U                        i++;
8 U/ n0 @5 v7 C: H                        k++;' E( W. W9 y8 y* \$ h
                        if (k == n)& Q0 c5 m/ w% f
                        {
% b! y5 ~1 ]% q                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
  d% T+ q* W& x3 ^) a- k                            k = 0;' K5 Z5 E( @4 t7 A+ b% A
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小12 S+ ]$ J" j1 F4 q9 Y9 R# Y* |
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
2 W2 {0 v9 c( N/ x                        }) t5 n) `/ {! J4 w
                        else//输出暂时还没有改变数组元素的值
! W/ X- G4 z! O" E9 C7 A7 I  ~# m/ @                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);- E' v5 D+ a; Q
                    }
4 c7 b% V& K4 V                    else
( {5 i" X; B' F                        i++;//数组元素为0,直接跳过,不计数。。。, F" A3 c5 E, Q$ G8 r9 n
                }
  X; ?9 K# b: I; s* `4 E% @ $ e. Y, X1 |7 F% I$ w% N
% E# _7 d! a( o% |
            }//结束while循环
* i& m2 }2 [' b( A. w1 q9 A. s            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦2 F6 `8 f* r/ R1 G, U$ B  F9 f& K
           
1 u$ G( s" o2 g3 }3 y4 o                if (numw[i] != 0)) W. {2 g, X; z- g( _1 _
                    Console.WriteLine(numw[i]);1 D' s( \$ _( c; c  v) G, ?6 X
           ' I) L1 l4 _0 C' V2 E3 Y/ n/ C# h. F1 p
            Console.ReadLine();* Z4 t( ^  t) R) z
        }
3 j$ w0 b7 I9 g' r9 |3 W, X    }
! f8 B4 t6 W. {( t1 P1 @}9 O* ^3 S- M& n2 n. p
小甲鱼最新课程 -> 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-31 18:05

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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