鱼C论坛

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

猴子问题

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

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

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

x
大家好!
" F( T8 c6 E! Q; v8 {6 ^1 s, q这几天我在忙着编一个问题,我用了一种方法编出来!
& d" M9 y+ t' O: f8 m# j" d1 d# D但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!5 f$ I4 I; b0 ~; b$ ^: G
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 # N+ d3 m/ g" `' [1 _5 b

$ u7 G7 g# D' K9 M6 A
) V! H! r, n4 |( X, {
                            题目
1 D) B: z5 l& j( `山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
, Z1 z+ F5 `. F第一种方法:利用循环链表, Z: n4 B6 _6 Z2 R
#include<stdio.h>
0 r% ]8 W' J5 V8 H% _/ i8 u#include<malloc.h>
7 R* c+ g* V9 R' b: j0 G#define M 8            //共有8只猴子
7 A  m. x; }) K3 l% |' f, L#define N 3            //数到3只时退出第三只
+ U0 s2 x" t7 Ctypedef struct monkey
' B+ @* f  u1 e) K  P; |% K: [& q{int number;* J( d; o5 B% B; ^# X) @8 P
int flag;9 {) P* {) `1 ?1 t% }  m! f6 e
struct monkey* next;# M, J/ J/ U9 p0 q" r
}MONKEY;
0 n8 a- w' o' ~2 l# nmain(); A) N( c4 n' c- _" x- i
{ MONKEY *head=NULL,*p,*s;' ^0 D% b( K) S6 e
  int i,sum=0,count=0;
) B( {* [% m6 J9 u! w! M" b  clrscr();              //清屏9 q; U( r$ D4 X+ B& X
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存) K. X: y; M& W$ ^$ W
  p->number=1;p->flag=1;8 j$ O; b& r7 J' ?" D6 D; C
  p->next=head;
6 T9 ?  a, W9 `. W- Z( j9 ~  head=p;
! e; u7 k! V3 H/ Q' L7 ^  for(i=2;i<=M;i++)% k- V- Z7 s8 o: L0 I
    { s=(MONKEY *)malloc(sizeof(MONKEY));8 f% z: t* D5 W" R4 f
     s->number=i;s->flag=1;
: p* h5 a) G  E     s->next=head;) Q+ W( D1 j, }" v0 \' V! M
     p->next=s;p=p->next;4 i6 t8 d5 s9 n! |  ?2 r2 [/ I5 l& L
    }
" ^, T3 f% ]+ D/ J* U    p=head;( c( F. y! G) b" z
   for(;;)3 n0 Z/ q- U7 ]8 D4 S% E: K/ {
    {if(p->flag==1)
7 e8 h6 i) M1 r8 I0 r       count++;  n/ b, w/ o& P5 W( Y4 l7 `9 M7 |
     if(count==N)/ M$ M# W7 h& t
        {p->flag=0;
  D- o$ e# g7 }5 u! M         count=0;
( x8 D: `$ E3 G9 {/ Y) n, N         sum++;}8 l, {4 N% y6 h! u
     if(sum==M-1). H% L# ]( v/ v
        break;
5 F4 |# ^0 D* s' x5 l     p=p->next;
$ @# B) E8 ^" E) n' L- S; S. v2 X% a1 D    }, |' f  I. U/ \: y
    p=
" U+ u) s8 M0 N) r3 {* F    head;
* u" Y1 W+ ^/ y/ Z% o' z7 T    for(i=1;i<=M;i++)
% v. c' L6 m4 K* t5 j5 q2 H, n    { if(p->flag==1)/ f" {1 I) }4 E) k: x
        printf("\t%d",p->number);
) K' y% R4 I. _: r1 f1 X3 Y      p=p->next;
) [, \! A6 n) E5 j* g- G    }
' p6 w! H& @5 M- f1 K* Z7 W
  T7 N9 y9 h$ j' u
2 j2 K2 E7 O( e/ W; h% s
9 i' K# X. m5 w: `) B. W, p5 S}
5 O1 F3 w' G9 n" A$ V/ U2 N5 r
第二种方法:数组* K. g( A1 f* J% |3 O) {( ?
#include<stdio.h>% I6 S+ O# |4 s+ t) V$ Q0 w
#define M 8
; j& [) }% E4 pstruct monkey
. A" ^2 ?' j3 M" ~! G3 a% q{int number;- L9 ?7 A' y+ F5 t
int nextp;
! h: \0 F0 j5 i/ m}link[M+1];) K. u0 \7 _( S7 a! ]

  j. z9 I. N0 E2 ]; lvoid main()
% x4 _+ S$ t( E( n5 [+ H) ?$ |# g' O{int i,count,h;8 X! V( g1 p2 M9 D: o
for(i=1;i<=M;i++)+ j" t9 V' e9 x( t) }( ~( O
{  if(i==M)
( b+ K0 f+ s1 q8 z   link[i].nextp=1;+ y* L- T$ a, Y- H8 a  M* P4 s  v
   else
0 x% x+ C5 a, L! K- j* ~   link[i].nextp=i+1;
# f/ W- a* u! G. C. u  link[i].number=i;
$ j0 P( W8 D  N, H9 c2 d}8 e1 u* J7 _% X1 c' [: S
printf("\n");
* L  j% i. t4 A6 T- x9 I. @count=0;
4 e# o  a, I+ X8 U) E( V, v+ P6 xh=M;. [: N. V# P6 h. a; W
printf("依次退出的猴子: \n");6 c+ u. V6 S4 T) d
while(count<M-1)/ W  x" O7 Q! `" K1 {$ h5 c
{i=0;9 z+ L6 |% `" A7 p: i% u
while(i!=3)
  F3 s+ l8 i! E* c, ?$ h{ h=link[h].nextp;
* d6 Q1 a4 B2 _" I( u# \7 Z" W  X( o! L   if(link[h].number)
) f  J/ O* }( D: j! t     i++;}* X& D3 A7 v8 D* c
, ~/ }0 p- A3 I3 B- `3 H' s
printf("%4d",link[h].number);
# M" L1 t2 V& d2 Z( W6 d- xlink[h].number=0;
: s/ \5 I; T3 t+ T7 Z; tcount++;
8 H% R) r0 r1 f2 h; `* K' K$ u1 Q}
, Y, I+ U$ o( r* _- o0 S
: L6 Y8 |  i: u3 }4 d! mprintf("\n大王是:");& e5 C2 m  O) k: `' w
  for(i=1;i<=M;i++)9 ~( d$ U0 l2 A3 T2 v
  if(link[i].number)% ?# E$ l9 B+ U- I5 `
    printf("%3d\n",link[i].number);
" T  ~" C$ B: r! p/ j. e, ~; K, O
" @. p3 k$ A& K: u0 z# Q! T
}
( o. C: [4 `( V0 N5 l9 y& F
第三种是普通方法for循环
/ o8 A- Q6 Z2 Z3 F
#include<stdio.h>
+ O( d& F1 e% ]4 t( k- p0 _void main()
7 J1 X8 r6 d) f# v% }/ y{ int i,k,m,n,num[50],q,*p;' }8 q9 ?8 A1 z" e& h
    clrscr();
9 J/ L4 {6 I) w' I7 l! u; ^- U   printf("input number of person: n=");6 k$ k1 L: V! c" w' o! f  s: M
    scanf("%d",&n);. m- A4 H% X" u. }2 c+ f+ G
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只5 U+ L0 [/ L) k) s7 J" Y/ R. a  W
    scanf("%d",&q);8 s% U4 P2 u* |2 m! @" U
   p=num;4 Z3 k$ x& Z& M* m
  for(i=0;i<n;i++)& H* K, {) Z9 S0 [
    *(p+i)=i+1;6 w" }% X, @1 M
   i=0;9 M, |) A+ E* n0 @
   k=0;& }/ }0 E0 ]5 b2 [% z2 A6 ]* }
   m=0;. T& l0 J6 G- C) l6 F1 s
  while(m<n-1)% L, v% f" ^  A  [, a
   {if(*(p+i)!=0) k++;6 t& _3 V/ b  X
     if(k==q)) W" J8 _. S; {! `; w
      { *(p+i)=0;
& B+ F0 J# j& K9 Q3 y& x2 E/ `        k=0;
- x9 p; ]3 `4 p! H" t/ m* A9 u. p        m++;/ h3 j1 ~! h5 J  s3 E0 Q6 }
      }: X2 S. e( ^& P% _1 R
    i++;
: Z3 v; G) u* r0 Q! U( d7 G    if(i==n)i=0;: R9 x. e4 w, N2 d6 |8 r
   }% B8 q4 ~/ `4 `7 C% S+ w
  while(*p==0)p++;
7 r4 R/ m  i7 v5 z! t    printf("The last one is NO:%d\n",*p);$ X* g6 z0 J( \+ l7 r: I
     getch();
1 b/ x2 |1 w# x% s
. b/ u9 d& t( K$ u}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;+ K( J' Q3 I/ b1 w
namespace 又费马达又费电
3 C, E, t) S- _# @5 p{" z8 O9 H8 f3 W# A# @# {
    class Program1 i. `/ M$ E: h' c: G7 K  `2 t
    {
- K+ S  p4 f! ?( B6 {& i        static void Main(string[] args)9 Z$ q! V  D: `2 d
        {
' e$ D0 r% x4 B" v& F* T5 |            int m, n;$ L  [! x1 E) o
            Console.WriteLine("请输入数组长度");
- m$ ?& E, b$ g! _: W  J6 d2 B            m = int.Parse(Console.ReadLine());//m为数组的大小
4 K+ H! m* b& \            Console.WriteLine("请输入要截取数字的大小");  ^* X1 o$ N7 Y
            n = int.Parse(Console.ReadLine());2 `/ J! Q) p. l8 }: \7 F
            int [] numw=new int* z# C: c% {  r4 C& \
: y% \8 d* C6 Y) n+ D4 G" `
&shy;&shy;&shy;;4 i# O7 M+ M) Y0 c; _
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数9 l1 M8 ^/ G- y: C+ S" N( f3 Y
            {
$ u, _1 @) z$ o. j" N8 ]                numw[j - 1] = j;8 ]. i0 P+ A! q/ h! {; m+ f5 v
            }- w9 Y* A4 ~' O6 x( p, M
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!3 h3 k9 s6 \; N8 m5 c1 J9 s
            while (d != m - 1)
" ?( }. r3 ?% W3 c" d# Q+ N            {
6 k0 b. v% M1 \' U  t$ }                if (i == m && d != m - 1)
- K& R3 v; k. H9 w8 p5 p& G& B                {
: K$ Z  L# |5 P  \$ I& q: D                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!! x- n0 W: U* e7 i, \) d+ M
                    continue;
% T. N+ e! u" {* `4 A                }3 J6 Q! m" S  a4 i3 q$ ?
                else
% d; r( n- G' a( S3 P                {, ^# H* S8 f  |# @5 s1 S
                    if (numw[i] != 0)5 \- o2 \9 f( p3 L. ^
                    {
- A- I& v- U. N& ?" {$ a                        i++;
2 Q" A$ ?2 K; ^; X5 x/ y+ W' |0 H                        k++;
/ |. G2 t# p9 r' K6 ?3 L/ X* P                        if (k == n)
. o9 T" Q) N- p9 v) n" [) ?" w                        {) j' ?, B. I* J6 h3 S" }
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
/ M' R5 e- S  o8 p- y2 _) R4 ?                            k = 0;% }0 D# Z0 m( m
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
2 b" Z( w) K: y0 q7 i                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);& z, z0 R  t8 r1 x" |) m* n
                        }
2 |8 o/ k2 B% A/ D  b5 S) f) m5 W1 S                        else//输出暂时还没有改变数组元素的值* i! s; n6 C2 N- X2 J2 |9 k5 y; Q
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
) _" U9 ~& e" J$ v: }( m                    }
2 V' ~) W, Q! ~+ [, _' p                    else
7 z, {' n# L& _7 e1 W                        i++;//数组元素为0,直接跳过,不计数。。。5 p# p( w0 [+ A
                }
9 G; I; I% {; V3 c9 @2 w5 n5 ] - {: D- D0 s; k6 I& B
8 F% `; \$ O' f: `6 W5 f0 N
            }//结束while循环
" Y0 M+ W5 ^( o  U            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦8 S9 x9 y( [8 p9 R6 f6 Q
           ; p8 s% o& e! z& I" m7 Y9 B& G
                if (numw[i] != 0)
6 W) i+ G# K; H1 `; U2 c- T% ~                    Console.WriteLine(numw[i]);
# v# A- R) ^0 D$ T' \0 Y/ Z5 M: Y+ Q             z% t1 \* v3 x( U2 s
            Console.ReadLine();; a6 l; u( a8 ^) g: }3 L  r( w
        }2 m4 f" o* y+ V  l. \% \7 u, a
    }
, s. |0 O6 Q9 ~9 o$ v  [6 h}4 r0 x* y$ y" K$ a* F
小甲鱼最新课程 -> 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-19 04:17

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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