鱼C论坛

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

猴子问题

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

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

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

x
大家好!2 s1 G7 v& H( ], Q$ ^& Y6 f2 D
这几天我在忙着编一个问题,我用了一种方法编出来!9 x+ @8 G' f8 @/ A+ q+ s
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
4 l9 \$ i) q. {& R1 T注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 m4 f- p% H3 z$ \, d4 w6 u. q- P6 k$ g- r0 Q  K
/ ~) R' e, U' c
                            题目
7 f: Z0 j1 P6 C& a3 h" |6 L( \山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
, ^/ M% y9 D. _4 V  }6 N第一种方法:利用循环链表$ _& O$ E5 {1 f1 N: F& S
#include<stdio.h>6 X, u5 e1 J+ T2 l. h* i
#include<malloc.h>' h* ?( I: d; D" r. e! V# _
#define M 8            //共有8只猴子, ?# r8 g/ T6 O6 Y# X2 ]0 p& E; D
#define N 3            //数到3只时退出第三只
/ i9 C8 C- |: L% v* h# K7 atypedef struct monkey1 x6 R! v% Z( [: V( z
{int number;
$ j$ \. ?( r- P+ R$ w* nint flag;
3 Q* M' }7 s4 r4 V$ Ustruct monkey* next;$ I3 I3 k9 R; A2 V( {
}MONKEY;
7 z9 t0 {# c' e9 d  Amain()
1 L7 ~* M( h0 P4 T) ~6 F& t4 A: C{ MONKEY *head=NULL,*p,*s;
" _! \& F9 c0 R& u0 ?  int i,sum=0,count=0;1 F& ^: M# P% \4 i6 z) `
  clrscr();              //清屏4 d- t  b  R7 J' X$ y
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
/ {/ a9 o4 `6 y$ P' v8 V  p->number=1;p->flag=1;& w& A+ R3 b/ h8 I
  p->next=head;
" X. a5 X' m. `' i/ T  head=p;$ t) }9 U4 }+ t; c7 G- p
  for(i=2;i<=M;i++)
: X0 {  D3 W* O0 {) `    { s=(MONKEY *)malloc(sizeof(MONKEY));
( k+ M: w9 F+ X, Y     s->number=i;s->flag=1;
- f/ o" j7 ^* |$ h     s->next=head;! x- e- Z6 T9 B
     p->next=s;p=p->next;
* h' e: G3 V+ l- j  q1 C( ~1 \    }
8 {$ S& ^3 @1 _7 \3 m+ b3 I    p=head;
; e! [  v. P  k5 Z  @8 P  V& J3 d   for(;;)
; t$ Q( d( f5 E5 i# l5 C    {if(p->flag==1)
4 C8 `( t% U' x' e' d       count++;
' e+ V3 R$ @) J& k0 g6 g     if(count==N)8 F+ g0 L$ P. C6 v
        {p->flag=0;
% B! f1 o( U4 k, @6 D5 M) h% y, P         count=0;
7 w/ @8 c3 M- Y         sum++;}
) X# [# x% U' o/ q* n     if(sum==M-1)2 H- }7 ~( g9 q! ^4 @4 I' h  ^
        break;# a" W) q: v$ C3 Q8 |! e! n8 T
     p=p->next;
% j7 W/ v. v- H/ }    }2 S1 n, ^3 S" {" N
    p=# T/ q2 s5 G* s) _: m8 h
    head;: H3 Q& }  a6 N8 O' P
    for(i=1;i<=M;i++)" S5 w( ?, O0 I
    { if(p->flag==1)- j$ o) C' x( ]4 W. z4 B5 q( z8 Z3 R
        printf("\t%d",p->number);
& z4 o8 Y$ E+ ^7 @      p=p->next;' }4 e9 W6 x# o# g8 |+ J
    }0 Y  Y; Y+ \) h; p: j$ A' t
/ Q4 W( h) K. ], X- Y
9 P' L+ Y, G( G0 e' L/ ]

& K; q+ X- o3 c, d. v$ }- m, l0 c0 |}
3 W% n3 L9 x+ Y6 s7 F- a7 ~
第二种方法:数组2 p' ]  p6 H1 q6 J$ Q
#include<stdio.h>  d1 [! e; b4 Q; L& C
#define M 8
  t2 r! y& I4 K6 L/ ustruct monkey
! n" A# E/ u2 L# w- i* s3 M; {- J{int number;
7 Q0 N/ t) I/ f3 g6 x5 z4 b/ v0 jint nextp;
# }# P( o. s* x, V4 v( X3 c/ v}link[M+1];
- G* c( \$ I( P6 e" L; S) o* ?4 c- g  [1 W0 D, `; g8 L) k
void main()
" ]$ j  k5 a" C$ g% _/ K{int i,count,h;
4 @* e+ U- p8 n+ y6 efor(i=1;i<=M;i++); v- N+ a/ x: Z; _: l
{  if(i==M)
- f# X7 s/ ]8 k) f4 a   link[i].nextp=1;
' u. I/ @- @: Q, p! x1 s   else9 x4 L7 q8 {% Y# H
   link[i].nextp=i+1;
) W$ o3 [: S. w5 O& ?) k3 L$ I% g  link[i].number=i;# A5 c! R# `2 h
}% O- j! t3 O2 @1 |9 P
printf("\n");0 n) `6 s3 R6 s7 w$ ?! b. F
count=0;
# R  y; I& |4 Eh=M;
. S* R3 Q3 r2 aprintf("依次退出的猴子: \n");
7 Q% p4 H& c( [. F  x  ^& iwhile(count<M-1)/ _  }9 n* W+ u5 j# `
{i=0;
1 r3 a- _8 W1 A: c: Jwhile(i!=3)
$ ^- M' D, B# q4 W' A& Q{ h=link[h].nextp;. _4 E6 d; c$ s
   if(link[h].number)
5 i5 S0 a) v+ t0 d& h2 R     i++;}
; i7 m) @$ j2 o, e  y7 D" v( |5 m
printf("%4d",link[h].number);
; {9 F: A3 b3 {link[h].number=0;
9 Q3 w  D0 G2 K7 |9 rcount++;
: q" X8 v3 Z+ t9 @}; L% _9 s6 z- G4 l: s
/ S8 |; l) _. [' C% `8 s4 v
printf("\n大王是:");
- n# |4 |  w7 S' n0 |, w- |  for(i=1;i<=M;i++)
" k9 z, g3 h! p& T) _& y7 w3 p  if(link[i].number)
2 ?% p) R. q2 z8 b  u    printf("%3d\n",link[i].number);
9 V- ^* s/ T/ b6 X# h$ X
9 z' m% Z2 r* G0 u# J0 J1 L& ^  m$ O) x0 o
}

# r* ^+ ^' N+ R, \* }第三种是普通方法for循环
0 p$ \3 t- M$ X) L9 }2 t
#include<stdio.h>
( B7 X% ?/ k, |1 Q9 gvoid main()
& q. `$ }& y- B. ?& P- p; i# v{ int i,k,m,n,num[50],q,*p;* }5 c# v. M! D( @
    clrscr();
) k+ W+ B: O' L3 \, t6 z2 ^& ^   printf("input number of person: n=");
9 N7 W3 j) V# \8 x8 ~    scanf("%d",&n);- \7 N1 r" w! I  U% L5 b) a3 t
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只/ {4 s6 h7 [: O$ i0 L
    scanf("%d",&q);% s1 f2 P1 g$ o0 u
   p=num;& Y: \% G, a5 ]* q/ `( f
  for(i=0;i<n;i++)
: r6 x( q. T" B2 r& J    *(p+i)=i+1;0 z# U- w2 {/ L  K0 }# H0 H; i( o: K5 X
   i=0;
* l  K: u9 R: d1 k& I( w1 t- ^   k=0;7 p5 t+ a: d% M# N5 Z
   m=0;
* v& H2 v0 A( X% l1 ?6 b2 q2 H  while(m<n-1)
/ V% W7 L- |7 f0 a   {if(*(p+i)!=0) k++;
- t3 E% v( Y% Q0 ^! m% z+ \     if(k==q)
: c, h4 I7 a; j$ s! n      { *(p+i)=0;
- v9 Y0 n% a/ l        k=0;
6 [3 G5 L  B" f5 @9 E, C        m++;
; w$ U' S8 h. b% m; d3 K! W      }
0 b0 S5 O5 E% ~$ c3 d' @' s    i++;
+ Y6 I+ U& B/ j/ U* \    if(i==n)i=0;% G+ {! Q# P) h! ~6 k5 L
   }+ e$ y- L% w' S
  while(*p==0)p++;
* c% A' R- `8 M2 c3 l, ~0 N  p$ ?    printf("The last one is NO:%d\n",*p);
/ t; z" k; ?- u+ d     getch();$ v+ \' o# a% G

3 ]' O. t1 r* \- J# E3 K9 g}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
/ b9 Q' F6 ]7 w$ ]namespace 又费马达又费电# d1 u1 h! s7 [1 G+ c0 U# Y
{
5 `) R- a- p7 h  d    class Program
0 q8 X3 V# I1 v' b8 D$ t0 H) c    {3 m( ?5 J( f& k/ W' l
        static void Main(string[] args)- n5 s( t% k2 E' R2 s5 E
        {
. M% J; D  V& ^- t9 w- R( i* H            int m, n;  h* }3 P$ h( n* O/ C1 b5 G" n
            Console.WriteLine("请输入数组长度");
9 `+ G; s/ R2 n9 W5 i( S( M            m = int.Parse(Console.ReadLine());//m为数组的大小
0 b8 e* k' ]6 x8 e; G            Console.WriteLine("请输入要截取数字的大小");
4 [5 C  R8 ]% Q0 Q& {            n = int.Parse(Console.ReadLine());3 q& {" a2 ^7 Y: a. s  Q
            int [] numw=new int
* b5 j% Y* k. R* t& g" X
9 v8 b+ b; ]- _. R4 e, Q3 [&shy;&shy;&shy;;. {1 Q/ s/ i2 L
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数; \# i6 f# j; V& L
            {
! E# m1 a' g# D& D: }' G/ @$ E                numw[j - 1] = j;
: G# _4 b  A7 g$ C( X            }
0 H" _' E/ V# Q8 Z, e" v( x            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
& n6 C% l7 {4 g; ]5 e            while (d != m - 1)4 J" |( M  {* J) ?9 R9 J
            {
0 d3 P" k8 e4 z. c% x                if (i == m && d != m - 1)
- Y' |2 _* R/ _                {
& F3 \0 T: j+ J8 [                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!5 S- B0 I& z3 B
                    continue;9 C& T' d4 Y3 l6 Q
                }
8 U9 ^8 }  U" w; S4 h' q% u                else
: P9 w& R5 {1 i0 T                {/ ?/ T( U% w6 I& h1 u
                    if (numw[i] != 0)4 f  I9 c2 Y( ^, F/ e9 D/ }6 z
                    {( }' [9 I8 x' ~/ s1 @. W
                        i++;
( S3 U, p. _# f7 u. M+ G- ]! x8 B                        k++;7 h' q$ }( n/ Y+ Z% H  A( [
                        if (k == n)6 }2 }0 Q2 W! P4 h! A
                        {
7 @7 a; S/ {/ L3 E* k  o& G. P                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
8 E2 O$ y: Z: c* z                            k = 0;
- j+ b9 |! t* C              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
+ t1 r% |7 y" i  C                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
6 c2 ?6 m2 Q  B5 n$ X9 e                        }
  I) h2 ^8 M; X- \; x                        else//输出暂时还没有改变数组元素的值( a+ ?$ ]; u  k' I- x3 n
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);! \3 c/ e* n$ o( ]
                    }1 m  S: b7 q- U7 K' @  g* V7 F+ K
                    else. {& l* \" m) _, \# C
                        i++;//数组元素为0,直接跳过,不计数。。。
( M0 x3 x4 N6 Q' u8 Z! D                }
. l- V4 t+ l3 L- ^7 ?3 U + [* [# D1 u- ?7 C
4 H3 j# D% r% o, {9 A2 S2 H3 b3 D; J
            }//结束while循环
, n: B: o9 n, c( h; f6 H2 B4 h            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦- d$ l% P' J4 s+ `
           
+ e- y6 i# j9 s& _5 B1 S. i                if (numw[i] != 0)2 ?/ ]0 e6 y1 w$ x0 Q3 L
                    Console.WriteLine(numw[i]);
" p) f" V- R0 h+ n: j           3 L% Y; o& L. p
            Console.ReadLine();) ]  j  \" |/ C1 U: j* L/ S( X
        }
8 g3 k+ K2 i! R0 y3 k( I% p    }3 d- \& f+ U* l- o9 M7 Q
}
2 P& ?, |$ d2 z8 d" O
小甲鱼最新课程 -> 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-6-16 10:34

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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