鱼C论坛

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

猴子问题

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

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

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

x
大家好!: n, e' J8 j4 y0 q
这几天我在忙着编一个问题,我用了一种方法编出来!
  q4 K+ ?# d- {+ Y/ c9 ^, O但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!# h: B" i! ~$ J/ G  N$ F
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
& ^) Y6 F" i$ l3 L
) `: b: c8 p0 d3 T: x8 A
0 a: S- R- V! o: Y# \$ U* w; W2 k5 J
                            题目
& J+ ]" M( S; l  a* V. S山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。5 H" j* n- ^; n2 Z  Y9 f) ]9 V
第一种方法:利用循环链表& _0 ?( g  P, E, D+ p
#include<stdio.h>
5 P# e+ O4 k$ c/ x/ J2 w#include<malloc.h>  f1 H+ p% P' t+ ?0 c& E" i0 K$ {
#define M 8            //共有8只猴子
3 S* D2 J2 @2 E; ]% b#define N 3            //数到3只时退出第三只
9 C6 `) ?) k  [typedef struct monkey- o4 c* {; [3 h4 ?# m
{int number;; t" Z% j' b  l8 d0 m, I: U
int flag;
$ X3 T2 j! z, N$ L4 t0 Q. B4 qstruct monkey* next;6 D8 W. L* C6 {
}MONKEY;1 q, h7 ]! M8 ^$ E
main()
7 m' k, q* R! }7 H{ MONKEY *head=NULL,*p,*s;
: S& }! ~- n# V1 r, g, A3 A  int i,sum=0,count=0;* F/ \+ @8 n& k
  clrscr();              //清屏0 I! f& }5 b0 K9 l
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
9 T6 g4 k7 W) w) \: R# ^& O% M0 B  p->number=1;p->flag=1;
. c; z. t) C% r( {8 o. `  p->next=head;. e8 d6 i( i. P# Q
  head=p;5 \% g5 \4 q. a) p
  for(i=2;i<=M;i++)4 ~1 X4 E% M) g( g6 u; N3 n
    { s=(MONKEY *)malloc(sizeof(MONKEY));
& T4 Y/ g) ^% J6 `     s->number=i;s->flag=1;
5 o% m2 i0 P4 h     s->next=head;4 n1 J- m. X  R( [3 s
     p->next=s;p=p->next;
4 X4 \) G/ w3 [% ?    }" M' X- ]- N! W" ~
    p=head;
* F; a5 U  W& \( i   for(;;)/ L5 {5 |4 p. K9 n. t( [
    {if(p->flag==1)1 x# U$ X" `* R
       count++;
" [  I# s3 N6 w2 z     if(count==N)# l  B. {/ n6 e! ?; \% l
        {p->flag=0;/ n% r8 x1 Y& a* L1 \
         count=0;0 [' f4 R6 Y( Z* z
         sum++;}8 g' c% M$ k# x5 y! L/ F/ E
     if(sum==M-1)" h9 i9 L. }6 E# q1 A" p) }
        break;" t/ U; d# C7 ]( I0 D, P
     p=p->next;
8 T, N4 \' E- o' l0 l8 E    }
( m! ]! @- V* q- _    p=, c) R. S, @: o7 i
    head;* X9 f, [& s0 O# I( l
    for(i=1;i<=M;i++)+ R% G% k- K: f7 u9 g
    { if(p->flag==1)$ s( z2 d* x! u: r2 s( W$ }! K
        printf("\t%d",p->number);, L+ B; C% B& u. F' |
      p=p->next;" f4 t2 d' i# R; c( G; N
    }
% B1 c  O3 y7 h  y* T; T
" }4 O4 T/ Q0 j% `- q( _% e8 n" b) \
* Q) V- C4 u& v0 ?% A* f% w
  o2 r) H2 ]; V8 p& ~: I}

9 z$ F$ m, I) \+ A' s/ c3 T第二种方法:数组) b; |1 p/ s! e% V4 R
#include<stdio.h>/ z. L% n! w3 R0 _) I  M
#define M 8+ z" e; m5 @3 o! l
struct monkey
. d. i* j$ x3 [6 ~4 q3 v{int number;, H5 _* n. f9 {
int nextp;
' {4 x/ V3 c( i$ U  ?}link[M+1];
; b; p  G7 v  R- ?4 g/ q( P* c* ?( L4 I2 L
void main()7 @5 v" e! K- g  R. v' t. Q; r
{int i,count,h;
- L" h% d2 J6 B$ k. B/ i$ Yfor(i=1;i<=M;i++)/ R- Z0 S: k) `: o( z3 q. R& S( L0 o
{  if(i==M)- w/ h% i0 d- _9 N
   link[i].nextp=1;
# W; B- A- o6 s+ N7 h5 O; G   else! c6 j, n5 ~7 C0 _# y
   link[i].nextp=i+1;  Z. |  F1 k6 h6 U( U
  link[i].number=i;6 W! P9 ~* Z% D8 I
}. M" z  {9 |- R: m/ k  Q( w, H
printf("\n");- T* {8 e* J; ]
count=0;' i$ @; ~" J+ r4 e( `) J
h=M;
+ K9 ?, v5 z/ W7 _1 Eprintf("依次退出的猴子: \n");
. V0 i" A5 H/ V: P* B$ C0 lwhile(count<M-1)
- O1 t4 N$ c9 h{i=0;7 d7 U* s, b* D0 U7 m
while(i!=3)
3 M* f* E- j5 ~  J- h{ h=link[h].nextp;
$ B; X! a# _8 P: i& _4 @" Z   if(link[h].number)
8 |. ?( N) ^& e9 O( D* k: A$ {     i++;}* n) O8 c) C, x6 Y; B

6 W% Q; u$ @+ G0 vprintf("%4d",link[h].number);, }2 q' e0 d6 S  M" }2 s# S
link[h].number=0;
" X6 C6 \  O5 {+ a9 m3 X* Gcount++;
% x! F4 K3 X* h" Z. a$ c7 v4 i. o}
+ b% T! m3 a; d# ^; V6 Z
! X7 Q& u% s/ I1 D7 t1 pprintf("\n大王是:");* ~  `) I" `# Y6 n
  for(i=1;i<=M;i++)- ]9 j# G# k7 \. G) e' h
  if(link[i].number)
9 A% A' v3 F5 b/ k4 G" [# N1 Q- @    printf("%3d\n",link[i].number);
( r1 u7 p9 Q: I- y' E% S3 a/ n( y

( J- c- M  G& m6 m8 W* h}

; E  K  L- Q2 S) w第三种是普通方法for循环
' F6 K" P! O9 j; e
#include<stdio.h>
) d, O: `9 ?$ R2 e  nvoid main()
' }: `! R2 o& _, P' [{ int i,k,m,n,num[50],q,*p;0 I$ S7 C. f! R+ G! R* Q* ?/ m& B6 u' A
    clrscr();$ w, C( W* Y. ?; ]! J! t' T3 V
   printf("input number of person: n=");( S( r7 h- ^2 N% y6 n7 K
    scanf("%d",&n);
, N3 x% N6 N4 C" ^, i) f' {printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
, u9 t: I. L$ r; |* f    scanf("%d",&q);
  W, Z# C6 H. ^- h# B3 _' y   p=num;
, R9 B4 L7 r3 y  for(i=0;i<n;i++)
7 D% m3 b+ s& n. W! I+ W8 U  E    *(p+i)=i+1;/ t" ]9 [1 D% A8 n, c: A, o" P, M
   i=0;/ s. g; Z7 h/ I' f7 a
   k=0;
7 H9 u  S: \: E6 E   m=0;
' X8 g* I2 r5 I* u# F6 K  while(m<n-1)
: T* C! t! J$ L' \, F   {if(*(p+i)!=0) k++;
/ Y+ n4 Z% _* v. J     if(k==q)" y( M/ b6 ?" |2 D8 g+ S' S: t* _
      { *(p+i)=0;
! j4 a8 V, S  g4 \3 ~: |- V        k=0;3 F- D" ^& N- M+ Y* F
        m++;, n4 U" m6 P9 M$ {9 C$ l1 Y4 k! y6 y
      }2 m5 Z4 k  ~$ W2 e
    i++;  Q$ \2 }& p0 o, {0 q# V  H  w! ?9 H
    if(i==n)i=0;. N# }: i% b" Z# @( C
   }
$ k) d" F6 I9 l$ N7 c4 v( c' {+ J  while(*p==0)p++;
. j1 g$ x+ k2 ?5 p0 m. E& x; t    printf("The last one is NO:%d\n",*p);2 f! Q& D+ d. ~; X  r. _3 G8 w
     getch();
  T* a- D% [8 g9 Y) |
) N) P' J9 x# a( _8 c- S}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;" J; i% N$ E* i$ R; x
namespace 又费马达又费电
7 N( o" ]; A4 I1 K) K3 ?' x0 j3 `{
) V( b' Y* p0 S2 i) b/ I    class Program
2 g( [  I/ i# H+ i, ^2 r    {
- H; v+ Y; ?% X2 x5 B4 T        static void Main(string[] args)
5 ?% g  @& u  d& Y5 V- I$ }) i8 l! Y2 w        {
9 S! \2 I: d! ^            int m, n;
1 Q- U5 M6 X" C+ n: Q) l& H5 j            Console.WriteLine("请输入数组长度");
( U; s8 G% {6 f. S% H  f) P            m = int.Parse(Console.ReadLine());//m为数组的大小' ^' n9 [+ o2 O+ A% S! {' U
            Console.WriteLine("请输入要截取数字的大小");
: H5 u& l* b* c1 f3 ^- D            n = int.Parse(Console.ReadLine());  n1 z4 \  M6 y3 L
            int [] numw=new int
  e/ M4 d5 F8 Q( D
0 c" `1 L+ L, r7 a* x&shy;&shy;&shy;;& W. h/ h/ Z& \1 d- P6 G
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数3 z' ^; \4 C, F, W3 t3 B
            {
! \& D, P! d9 Z+ V4 J+ [                numw[j - 1] = j;4 Y3 q0 E: j, S' N3 C% J. D
            }
9 b% e4 r; s& b! B9 }, R- B( ]            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!& D' ^9 I' b; ?/ M& k
            while (d != m - 1)
# h# d. m3 O4 z8 `; h            {) W' U' v& k- A+ k
                if (i == m && d != m - 1): i4 H9 S2 i$ a1 H& K" |
                {" j9 d# ^* |/ R/ k
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!7 R" K: b$ m& h! `) V8 A  U
                    continue;
: u- ]9 J" T- ?  l                }
4 e' a7 j2 Z$ t4 H! d                else, `: b. @' [/ j8 Z; A( X
                {4 F: |; T, w) b4 k3 F( q* _4 O
                    if (numw[i] != 0)0 b- m: N) ]" C8 Z% E
                    {
" }' x( D& T; s+ `  J) `/ S                        i++;$ L; v% C: |: B0 [7 R
                        k++;- V8 x  S0 Z& y* I- }8 G
                        if (k == n)
& Q% V: ^% e5 n1 a4 p                        {
4 G, M" w, J& s% K5 \                            numw[i - 1] = 0;//把在n位置数组元素的值改变了) D4 v. e5 n6 I5 {* h" P
                            k = 0;7 |8 D( P) A( K: Y# @
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
# v1 t, S+ Y) C0 A4 l                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 `( B1 F( }: K, @) S1 @( S9 o, a                        }
  ^7 R2 c/ x& W+ Q- \0 _; _                        else//输出暂时还没有改变数组元素的值
: q" ^  s) d9 V) L; G0 i; f                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);- G3 `( C3 O% Y3 T6 g, Y; }! Y
                    }
3 U; O' c$ ]) F  {5 g% u; `9 M                    else5 @" a; h6 A1 m3 J
                        i++;//数组元素为0,直接跳过,不计数。。。
3 V8 |5 a1 H# g4 \. x7 r, }                }
* a# h! t( O1 A8 V9 u% x2 b% _! w $ A) b# }4 x( ^

8 _7 W: |# W. Y7 T, O* F& w* S            }//结束while循环
  \' A* P  \' ^            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
7 T6 @2 g: |6 Z. S1 \/ f1 X           
/ j3 e/ j' _7 @7 O5 I. L$ t                if (numw[i] != 0)
+ a- b0 V: t% \: _, z                    Console.WriteLine(numw[i]);
/ G. X8 Q; q  m( f8 K* I( O4 q+ G             |8 L" O. O3 @7 C3 i& Z6 q2 i
            Console.ReadLine();
1 X7 H7 }, P4 n: ]/ N2 f        }
. Z/ T* a. m1 X" R9 \6 H( c    }
  W  x; `9 E) ^0 n}
: n$ i  j( K2 s6 G
小甲鱼最新课程 -> 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-28 02:23

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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