鱼C论坛

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

猴子问题

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

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

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

x
大家好!
( I+ W( n/ x$ d5 h# k这几天我在忙着编一个问题,我用了一种方法编出来!3 d- s4 ~8 |/ E, R% s# G" z( z
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!+ u$ v& ^% R" I& B
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ( @/ O" @9 _1 _! V
/ o' r; r. n- k8 S7 D7 ^

4 m+ ?* {8 \# d/ S5 [2 o
                            题目
) ^+ Z- \3 I5 e4 o4 X) y7 Z山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。/ E0 f) `2 M  C* [: b/ T
第一种方法:利用循环链表
/ k( N5 U' Y1 {' t- }& w#include<stdio.h>
3 C. e6 G4 I; }: _! L#include<malloc.h>
, [  E, Y* R4 J3 {( n5 U6 @#define M 8            //共有8只猴子: f8 K( P, s" p1 K4 _, N, Q
#define N 3            //数到3只时退出第三只/ X& z2 D$ U3 Y4 N) a. l
typedef struct monkey/ b/ W/ g/ Q) A, r! _) {% D
{int number;
) N- m: w& B! dint flag;0 I# G  `  S  A3 S' E# r0 O
struct monkey* next;) D7 N! d  Y4 I, @
}MONKEY;
1 R0 L( E  _9 @, m( Xmain()
5 r( s& A8 |/ T+ q0 @{ MONKEY *head=NULL,*p,*s;6 c) @% B& n/ ^( I4 F* b
  int i,sum=0,count=0;
$ Q3 m+ |/ G+ m9 ]$ w  |4 {  clrscr();              //清屏! B3 C2 b0 o) {
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
" Z! k& W- ?9 m+ O  p->number=1;p->flag=1;
8 w- h# |" W4 u; l4 U. X  p->next=head;# q0 \4 j4 t- s9 j7 @
  head=p;6 H1 H; r, g4 o0 v
  for(i=2;i<=M;i++)% [& s6 G; W7 @+ Q$ k
    { s=(MONKEY *)malloc(sizeof(MONKEY));
$ L! p( p( R8 k2 q' H8 h9 Q. |     s->number=i;s->flag=1;
: u+ [) f3 i+ v8 s( J% e3 _, K     s->next=head;4 D/ g" v6 S& s
     p->next=s;p=p->next;
" [" j- M: x- [; |4 @% \    }* |) l$ P- k- y
    p=head;
; p4 V# y2 |; E% C8 T0 w) O- R" C$ a   for(;;)
( L; g7 K1 \- j% z3 A$ ?    {if(p->flag==1)
/ S* U" d2 x$ V/ [: ?( p' u       count++;. \  s$ ~+ N4 c/ \
     if(count==N)
) X3 f% E! P7 r+ E: T$ z" ^$ i        {p->flag=0;9 A( Y: ?( X4 x$ i* L
         count=0;
- q7 J3 ]/ ]* i. ^         sum++;}1 [* w2 ]" {8 T3 P& r' K1 {0 ]
     if(sum==M-1)
5 l+ d9 J" |8 d        break;
0 I: V. v' n& w     p=p->next;
4 ^3 V5 {9 y( \% M. J4 i. D    }
' q3 l  O. |; n: o, `    p=1 L* M1 M1 \6 b0 ~+ K* @; ?
    head;
" Y0 ^% [! [1 ~( ?# n    for(i=1;i<=M;i++)
% q+ U4 l8 @4 d& V) v    { if(p->flag==1)) M1 X0 a( n. o0 W
        printf("\t%d",p->number);
) y: j2 G3 P, s) z      p=p->next;5 y0 [5 u+ c) g' V4 V& {( j0 l0 g
    }* I; U/ n% l' F: |

' Z  o# C" t7 J1 M4 n+ R: X& M/ p: X, @/ s3 k9 W9 u- c

, U6 z) _- t% `3 G' f}
  `& j/ e1 M$ n2 }' ~$ W& S4 m* I. q
第二种方法:数组; t8 N) L, C( @+ n
#include<stdio.h>' Y) A$ x9 u! i' z: r
#define M 83 U# d, m( E- F# m6 x1 Y" h" v
struct monkey
5 W3 w- U  z' U7 H& r) v6 k{int number;3 C, h; Y5 N! C( D; t
int nextp;
& S: T) `& [2 T! W& G}link[M+1];: N$ ~  i0 |  f
3 B" V: v/ N( f! Q$ w
void main()
0 t; J/ X- d9 B! F7 v{int i,count,h;
9 \7 m+ G% t& ^for(i=1;i<=M;i++)7 s3 ~0 I0 y3 W- o% y
{  if(i==M)# E/ {: c  R- q% G
   link[i].nextp=1;0 u/ J0 Z+ x* q% e
   else
# z- p3 l# U8 E8 ]% v   link[i].nextp=i+1;- s; C, B2 X1 ^$ J8 e7 m% Y% f
  link[i].number=i;
6 }$ i. [% Z" b, \6 Z+ A) }7 y: X}
+ N& r! Q5 Q+ {& Z  mprintf("\n");
) c3 E: p! h% e3 ncount=0;. _- o9 w- _4 P0 D" V/ B, ?* b
h=M;
/ e! Z% i7 {3 g. e% |9 b+ a; ]printf("依次退出的猴子: \n");) L8 g9 ?- ~) k$ T- K
while(count<M-1)" t+ f' S! _! q
{i=0;
4 J, R$ B8 ]: G' P# h. X- [while(i!=3)8 @+ ?. O! Q( B# m
{ h=link[h].nextp;
8 {- \3 T  H' g* i$ X6 b9 Q- l% e$ }   if(link[h].number)
0 w. q, j. q8 f- k, X     i++;}: J, Q  V, {( X( `; c! [  @

; c3 Z6 r" l. z, k: xprintf("%4d",link[h].number);
/ q* n  K! A3 Z9 {  U# Blink[h].number=0;$ z' L* P4 X! T# O& B+ Q
count++;9 C, }; c" j% ]  o% @
}
. S2 y/ u( O& _0 U" H5 c
1 p/ A; o1 P9 xprintf("\n大王是:");
) O! f* D( z$ V, t/ L2 c  for(i=1;i<=M;i++)
% }  R; l5 n( V7 M  if(link[i].number). l4 I9 K# E; ^5 \5 c
    printf("%3d\n",link[i].number);6 x3 o# s1 t8 H$ m, J

6 z  W. f& U( u# @' m/ R; T4 K) J( e) q) W
}

2 w( ^0 ~% E0 d" p$ z第三种是普通方法for循环
. U9 M5 s  U, T8 Q* u- ~
#include<stdio.h>
8 C% D0 C0 R/ t) C6 t( lvoid main()' q) |0 a1 j' ~  f8 G
{ int i,k,m,n,num[50],q,*p;9 @9 J. _3 i: w/ [. S
    clrscr();
( L0 g' A( f& j, L( q0 u   printf("input number of person: n=");
0 |3 _5 j2 H& r; j  g    scanf("%d",&n);
  r3 S4 e" M% R# y# Vprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只7 x, m. b9 |  z* L4 k1 K
    scanf("%d",&q);
1 f6 p+ W! x9 y) J1 A! T/ f( y   p=num;
& e# M$ j3 w2 N  for(i=0;i<n;i++). E5 ~+ i+ `% ^/ s/ M
    *(p+i)=i+1;
6 ~6 y- S7 }5 O. {+ ^5 ?$ e   i=0;
. B1 F/ i# _( Y, X4 y7 y/ R   k=0;
, ]! L2 A& [6 N   m=0;6 U( L# b1 g$ T) h% _0 K- z( }
  while(m<n-1)$ D1 K" g0 ?. S; n: A4 r( t
   {if(*(p+i)!=0) k++;
/ B# B' \  |5 Q     if(k==q)
: ^) @7 z# r# O, E1 s      { *(p+i)=0;
! W4 }$ ]3 ?, u        k=0;
& c4 n0 C8 [- v# ~8 }9 c1 t5 Y; Q0 z        m++;
/ {5 U" S# j" a! a* I! m  j& d      }! `8 I/ z; O0 Z" k. Z$ k, x' [
    i++;
( S& a& o( E# N4 V    if(i==n)i=0;
& W/ M) E1 w! A0 F: _8 {$ _% M   }' {5 j9 g1 _( e: F% c# t* p
  while(*p==0)p++;
" w8 B2 l& X" O/ \. i    printf("The last one is NO:%d\n",*p);$ R' b$ u! d# a
     getch();2 V( g6 h4 U6 k) T0 M
0 }. B/ z& Y/ [7 B( @3 Q; e
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
, m+ P8 U. a' H  p) t9 |& bnamespace 又费马达又费电
( ?" W# b! k3 V* k; z+ W{
- ?3 b8 E9 X. G3 ]2 d" a, {. ?" S* V    class Program- r- l& p4 r3 u$ _
    {
( i9 c6 X. |) g7 f        static void Main(string[] args)$ b% x. G/ }& i1 i$ N
        {* z3 }2 [" c6 x# T- U0 Y) d
            int m, n;
( v& I+ }9 o, Z0 C9 l            Console.WriteLine("请输入数组长度");& H  c7 m* E6 s" _, V9 r; `
            m = int.Parse(Console.ReadLine());//m为数组的大小
# a6 p& i3 d% I            Console.WriteLine("请输入要截取数字的大小");) \7 o! O* e. ]# C  q9 g$ ?
            n = int.Parse(Console.ReadLine());* M! E/ S  l( R& [: g8 f
            int [] numw=new int
( L" q9 i  K6 y- W" ?. ?  r9 C# i
$ Y: L3 R$ P/ U* V+ M6 T2 ]&shy;&shy;&shy;;
+ Q! F& k* h/ Y8 n            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
- v, r: G. A7 N& g            {
$ E) p0 t& E( Z$ y! Q                numw[j - 1] = j;
# j5 G! N+ \% [5 I            }
, R/ f3 @1 L7 B2 k            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
! }! V  s' Q8 v4 z) `            while (d != m - 1)
- @' _& g1 z3 c3 z            {
/ ^4 E9 K7 J. U- z                if (i == m && d != m - 1)1 o( i* Y: X* Q" n: Y1 c* u
                {
% H/ K0 B. {, d( w) v7 E5 u                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!- m+ G7 x: P$ A. J
                    continue;  p; u2 o1 i' N. r2 F2 z
                }/ y/ z" W$ z' t
                else
  E$ H7 r/ z1 t; m# `1 ]                {* Q- G$ f( n. Y1 d* }" e
                    if (numw[i] != 0)" V/ N; V0 V+ H2 c
                    {' d* L# ~; d  d) o3 u9 i  ?- I
                        i++;
* s8 a) t) ^3 I- v                        k++;
5 |4 \) @1 K5 m                        if (k == n)
8 M, G% F$ ]% z8 _1 N8 Q                        {! A: @1 w, K+ r% n
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
* q2 E/ z8 d, L/ y5 s! p" D, R) D0 P                            k = 0;
; U& K* }  j$ c) F( i              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小13 c' l1 d6 _1 g4 E
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: \) n3 Q5 h' m) A, L5 d1 ?
                        }" e! n$ M; S) J
                        else//输出暂时还没有改变数组元素的值
2 Y: r" L3 F! R5 g$ }8 d; l4 I                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, D! Q* p. n! l+ V- L. V7 u/ O                    }
3 i1 d5 G9 c6 {) t0 ~$ C/ ]                    else
  X# X' N% S. k) s  o7 j                        i++;//数组元素为0,直接跳过,不计数。。。
8 b6 Y: f; S% W' o8 n7 k) e: `) n! |                }) V' _" G! X" s+ O3 a

# S" X# Z: b# O9 _+ A/ n4 D* g. ?
2 E$ U4 N8 q+ Q% c  }5 U            }//结束while循环# t, z) x/ D4 T
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
1 \- A7 F- O- I/ E# N  V" X           % o$ w5 t3 \5 d# z# l, T7 y% m" D
                if (numw[i] != 0)
# v- x, |7 ?0 ]3 ?5 r, `                    Console.WriteLine(numw[i]);
1 i: T: ]& O( `* j2 _0 k0 R1 V3 m           / p" ]8 d! l) I) D5 Z0 X
            Console.ReadLine();
- @5 O. B" u2 r% J        }
, ?. _" j, R7 E- D! n+ Z( ]    }
( X  U- \$ \/ {}1 j3 ?; W- R& d0 x; `8 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-17 04:50

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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