鱼C论坛

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

猴子问题

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

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

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

x
大家好!2 p, v+ i% ~+ _" I+ H
这几天我在忙着编一个问题,我用了一种方法编出来!
2 @5 B8 F0 a2 ^但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
& s$ G: N, @6 ~; |* w注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ' f  S" `6 w/ \+ M% `  ]
- T1 _6 V8 N0 F5 S4 y& E& [
% h* T+ {6 M1 v/ r
                            题目
0 [$ M# y. m. I山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。- _  n0 h0 m8 V0 V
第一种方法:利用循环链表
1 }( {! e0 R% U8 M5 Y8 p, L, A#include<stdio.h>
) ]3 \4 {8 @5 r$ ]0 ~#include<malloc.h>
% s; }- X0 O0 n# C; F7 M  u#define M 8            //共有8只猴子
- Z6 E, g" d% s. o) Z#define N 3            //数到3只时退出第三只
- @3 S  u: {1 D% k: J9 O; atypedef struct monkey4 ]3 x( u9 N; w  f/ x6 g
{int number;$ A% ]" s& f6 r1 F. p6 n: M
int flag;
/ J4 q  M* {/ Hstruct monkey* next;$ G( O0 F4 r1 i) n
}MONKEY;
; |& o9 u) K7 \$ Smain()! w. G6 @% S, ]) v4 y
{ MONKEY *head=NULL,*p,*s;
, Z1 b/ w- l! ]* h  int i,sum=0,count=0;2 m* S/ i. `! ]0 H5 O# `, Q1 [- G
  clrscr();              //清屏
1 A" r' @1 i( G# [  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
% i0 n2 M' e6 ]3 g6 m$ f% Q/ Q/ X% g  p->number=1;p->flag=1;2 ^1 _% u1 ]; G0 q, W; T6 ~8 r
  p->next=head;
! u% c$ }( `+ p& J- J  head=p;; ?8 d9 M0 E; c% c2 ?6 w
  for(i=2;i<=M;i++)
, G/ ~6 e) B9 n( v4 g% V    { s=(MONKEY *)malloc(sizeof(MONKEY));
5 r  X% f& W' Y: K% i3 L/ g     s->number=i;s->flag=1;
$ i$ Z6 ]9 F3 X- E     s->next=head;
: N  X8 N/ r- y6 [* Y# d4 A     p->next=s;p=p->next;
9 v$ v8 O  N, A. ~7 Z3 y    }
% t9 f4 R1 ]& l( ^/ F    p=head;2 t; e! P- K2 \3 A
   for(;;)5 w' f, l% \  q" d2 K
    {if(p->flag==1)
  T, R, p) H* \$ [7 J       count++;
" c$ k5 P  y1 q1 `5 x5 I- [     if(count==N)0 w- E, r& O: \( X; V
        {p->flag=0;, ?0 E2 f+ C; `0 x  @
         count=0;
. L& f. \: J1 D3 [* I         sum++;}
5 u! D4 U" c6 W. q  H  j  Q     if(sum==M-1)
8 m1 C. g% T  y5 t/ \0 a  a        break;' W% Y5 i2 V6 u; [4 ^, N8 W
     p=p->next;+ ?5 u+ C/ S6 }3 p% ?
    }! J8 V; Q9 S& A, a6 L3 X# F
    p=
$ S. a! Z! l' f  k    head;) C- R& s* [2 g0 x
    for(i=1;i<=M;i++)
: e( T& d: i1 P4 Q, @: S    { if(p->flag==1)
$ I: T. a( P" B4 d! i+ |        printf("\t%d",p->number);7 @% e: m$ c4 i; M' k" V3 U
      p=p->next;3 N, g$ n5 ^' S7 e$ \- G
    }
, t. t' t) j8 x( p" v2 }0 H7 W% q6 G2 ?

8 z( Z+ E, G0 e
5 C" y  X/ B: a7 w9 S4 T  ]}
. M( s3 J) J9 I7 Z! j
第二种方法:数组* B  G2 Y4 |: Z% \
#include<stdio.h>
3 \# _. |) G4 o0 D6 y3 G#define M 8
1 w0 S, {+ l' j" j9 w( gstruct monkey' }; A7 Y. V" `: Y
{int number;& c3 l7 q; o. S( M$ j3 L
int nextp;
( {% m- ?8 G0 B" S}link[M+1];
: A% d. m) |* Q2 i7 j! {
; B, N! W' x9 s, nvoid main()
8 T7 u3 U+ k3 _7 [- s- I{int i,count,h;
; `0 _: y& z/ C% c3 Hfor(i=1;i<=M;i++)
2 Z2 ?; u9 S* I& s/ `1 L{  if(i==M)
" h9 d3 R4 L. t7 U: R; z8 q* P   link[i].nextp=1;. h$ Y- T( V6 e2 o
   else" ~! F. p( g& E2 D4 U. s0 G
   link[i].nextp=i+1;
. }" ~$ R, Q4 l# n  R, ]  link[i].number=i;  ?6 i* F" }+ g
}: S  v! w/ ]4 @+ J- H" ~* z
printf("\n");" V" o* j8 f1 M
count=0;0 U/ u! u8 V. _- X3 U& J
h=M;
' ~  D1 v1 H1 m2 ]$ t3 aprintf("依次退出的猴子: \n");
0 S5 e0 J  r: j9 D: R* Qwhile(count<M-1)
: \3 V/ u- d6 Y2 r- v! m) H{i=0;
; |4 y( t6 N) lwhile(i!=3)
& f: j- H2 O: g{ h=link[h].nextp;( Q7 g* P: y, Q/ G
   if(link[h].number)& @0 e$ Y! f; A
     i++;}3 n, }+ K5 |5 r
6 j; R8 L2 D6 v+ x2 e( T7 `
printf("%4d",link[h].number);& ?; l/ z, u, K* o0 D
link[h].number=0;! Y, ]# K3 \6 ?; G) j( n
count++;
( ?8 y4 ?! Z' M}  L* ]5 {- H( G* G% o# Q
& B8 Z8 M! c+ F$ ]" l, Z* M  I
printf("\n大王是:");
) V1 L( D! Y0 `1 F  for(i=1;i<=M;i++)
8 i2 u4 q- }, v3 A* o/ g  if(link[i].number)
4 i# K+ v: a0 ^" D$ ?1 R    printf("%3d\n",link[i].number);
. R! d$ H1 o; h) K' F; }& o$ y/ Y! N7 G

4 w5 Q9 c. Z$ E! B$ X* o7 A, D}
% |. f' {  M, I
第三种是普通方法for循环
1 m5 ~& c0 @  l: M
#include<stdio.h>
1 _+ m% ]/ K. W# Y4 cvoid main()+ l' x$ f2 P0 w/ V
{ int i,k,m,n,num[50],q,*p;8 |5 ]% o! \2 [# U- n# E% N6 @
    clrscr();; Q# t& X* R! b0 O4 X4 N# q5 P0 ~
   printf("input number of person: n=");  K) z, t) k  a* S, V8 |
    scanf("%d",&n);1 Y7 |' K4 p: G$ Q
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只! }7 ^5 N4 ?0 [; v& y9 Q% X6 z, l
    scanf("%d",&q);
, i/ i, D+ V! U. M   p=num;. H" r7 H7 s% v  z! h: l' ~
  for(i=0;i<n;i++)
/ m' f! L% T# x2 {& D    *(p+i)=i+1;7 a" k5 [6 m- `( x, o1 U6 T
   i=0;
$ u4 g7 D+ Z, y5 I   k=0;, b  ?9 F2 x6 h9 B
   m=0;! J0 z7 o- a6 t( n& H
  while(m<n-1)% r! W) W+ O! o7 A  M
   {if(*(p+i)!=0) k++;
- O; J8 [; u2 ^$ }. Q# v     if(k==q)
+ [; F; q; c1 v# a# G      { *(p+i)=0;$ I, U9 N# L$ ~0 ^/ {" U
        k=0;
% g# o3 b# A) z/ X7 Y        m++;
( A) R( \! n/ i+ ~/ B2 Y' e& f      }
/ R8 [( W5 F! o+ R) b    i++;
' b" e% o0 {! T* o2 K0 O% @- \- B$ y    if(i==n)i=0;
/ {7 A+ s. N. _! G" b% B   }+ a6 J" c& C! d: |, }
  while(*p==0)p++;
. V3 k% a  {' C) T    printf("The last one is NO:%d\n",*p);6 s& p  m) v& ~2 P6 ^. L  o5 i: Z
     getch();
$ T! U( T+ U7 M& N( f* \& N
1 N3 p* `/ u* Z( I* }3 Y' o9 U}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;7 o4 g( Z% G0 n5 f
namespace 又费马达又费电
6 F7 @3 Y( N# V4 v# C{
; \! l3 U/ P* u% A( O" n( @    class Program" f5 ~- `  c& ?) ?  a
    {* G1 `! c* ^' l
        static void Main(string[] args)
4 K! ~- }  @/ l4 V        {: {, w) S& B/ O( f% t
            int m, n;! f& O$ m( }2 m6 h
            Console.WriteLine("请输入数组长度");
" l5 V' a7 f6 J% U            m = int.Parse(Console.ReadLine());//m为数组的大小; c+ `3 N+ i0 E) W! c& h
            Console.WriteLine("请输入要截取数字的大小");
, J3 N/ @4 L( n' Z6 L8 s  V% o$ {            n = int.Parse(Console.ReadLine());
1 ?8 J# ^; _- X            int [] numw=new int
( f& {6 G+ c) i' p  m2 V2 p: u/ g: F9 ^7 q! s
&shy;&shy;&shy;;% T9 T3 u; r- x- d( X* h# J! X
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
+ w" O3 D, A" A            {/ q  Z( m5 G1 m5 k8 z2 E
                numw[j - 1] = j;
  j; H3 T2 D2 e: r6 O5 g4 ^* @6 J            }
/ l8 M6 K* ]2 F4 Y( _* p. P            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!3 q) l* w$ k: X3 G
            while (d != m - 1)
# o. A9 c* x0 D0 T% D1 x9 f2 ?            {
0 M2 H/ A9 r2 v3 V                if (i == m && d != m - 1)
" P% e% t' [4 i% M. l5 t                {
( w. ~/ N! x* _7 c$ M9 g+ y                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!& L. ~+ ^5 b0 w; v! j' l* [
                    continue;  J' n4 x( O2 Q, X2 |4 D; e
                }
% f' ?6 {! v  b5 d                else) i9 K1 i6 N6 q. O' a: [6 u
                {
8 ?+ j) A9 i6 f( ?# f9 |3 y                    if (numw[i] != 0)
! N' G' O3 C+ w                    {, ]* k, G7 P8 a- o  c
                        i++;! S- s+ H$ F8 o2 ?- a( [
                        k++;
2 K0 j0 }% a. c9 g                        if (k == n); g: q" F; l3 \& L7 E1 G/ {
                        {
$ d/ d* h7 c1 [2 R1 s                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
- l! h4 y# L& Z                            k = 0;
- \# z1 V, E- W+ D! Q              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1- R* n. E5 E6 T( H. c* L- d
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);4 \) e. `, G" ?4 |0 N" J
                        }
( M7 q( @; w! g8 I' ]                        else//输出暂时还没有改变数组元素的值& c; g  K1 D( \8 n' H5 a2 x0 D5 |& H
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);; d: X! R% v- e9 r
                    }+ U( v/ \' M9 B
                    else" l4 w+ E5 V( ]3 m/ n3 k! I
                        i++;//数组元素为0,直接跳过,不计数。。。7 B4 s+ ]$ i% D
                }, q2 H$ n5 E/ ~" H! p- ]1 P
* N; @2 A; k1 W( N( y7 Z% ~
& y4 B) h: J, x
            }//结束while循环
$ T5 ]# U! J  J' [2 l            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦+ r$ H) `3 R0 q
           
( x0 {* W' j# a0 b5 c4 k                if (numw[i] != 0)0 b: G( B7 J* k# S* n+ ]& u- z' K) z
                    Console.WriteLine(numw[i]);
  K4 X( Q: R( [8 C: x# R' A" Z           9 C. n9 G. ]$ T7 u4 L( ]
            Console.ReadLine();
2 |7 D+ d# L* ]* s        }, ]6 [1 ]8 y9 {4 F2 X1 ^: @# Q
    }
( k1 ^3 P7 q( ]9 u8 r8 a}0 [5 V# l: X  T+ W  T2 U6 q$ H
小甲鱼最新课程 -> 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-7-20 22:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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