鱼C论坛

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

猴子问题

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

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

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

x
大家好!) _2 V0 @. R$ [( B1 b
这几天我在忙着编一个问题,我用了一种方法编出来!2 X5 w8 ~7 n: d* L% f. O
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ b1 T* y+ x! G" ]3 }/ [
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
0 D0 F+ n* K# c  G0 g9 R
2 ?0 F  O* q- A
9 n0 ~* V6 g# R3 p7 S
                            题目
; g1 D1 i/ _8 b+ Z山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。/ c* E' J% h6 R: }$ t
第一种方法:利用循环链表; G% S( |! v% B* v2 f+ c
#include<stdio.h>
. }2 v" c. x. v: p% |4 P3 O#include<malloc.h># l# b3 t) ?- L) S: U1 Q) t
#define M 8            //共有8只猴子
( C# i5 k& c2 n" R/ m#define N 3            //数到3只时退出第三只/ K# [  b2 u8 s/ `$ x
typedef struct monkey8 U' j) J3 G" M7 y* b$ E
{int number;/ }. `3 e8 C# W; h/ h$ h
int flag;
% q& i' K* [) {# q5 r6 T2 Hstruct monkey* next;
3 Y' X- y0 F$ R0 Y, n' {}MONKEY;
: U* |4 A6 q$ gmain()
# Y; d  g5 p, l! W  I{ MONKEY *head=NULL,*p,*s;
, x: C0 _, q) U4 y' o  int i,sum=0,count=0;
. J$ A4 g0 l. [1 a" L5 P  clrscr();              //清屏, W" m7 ?6 [* o/ X& L
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存$ S) ]" d7 \2 l3 e+ O
  p->number=1;p->flag=1;; q" S) t& N" d* |, H
  p->next=head;* E2 B! F+ y# s4 ~
  head=p;
9 u- k) Q" Z8 W& ?# C/ r9 a  for(i=2;i<=M;i++)1 ~" C. C, @3 g2 n, F* g6 v
    { s=(MONKEY *)malloc(sizeof(MONKEY));
7 j/ `) S( N" v     s->number=i;s->flag=1;$ x, ?1 @6 B* }& l
     s->next=head;
8 k$ N7 S! V2 a% w( E# I; g; K     p->next=s;p=p->next;
" ]. O7 l' {* q    }$ Y' `% L" S$ D
    p=head;
+ ?# c# b, R) z   for(;;)
* {+ ~  S3 l2 t5 t. Q. Z    {if(p->flag==1). Q  T# }# @2 ^* L! g: Q- P) t
       count++;0 f  T# H; X* |3 P7 |) k. c
     if(count==N)
/ x, R+ R, w4 [$ K        {p->flag=0;
! q1 Z' d( q% n! @7 t         count=0;7 d8 t3 E9 n3 }0 X: M, }
         sum++;}
8 h" w$ r% p- D4 Z, a$ [     if(sum==M-1)" i& n* f  x# a+ l! O
        break;
# N5 O( F5 Q: x. n/ L& `! f& q     p=p->next;
. i8 A1 `& I# \- X    }7 j4 d: D2 g7 `! b
    p=7 }- U' a. u' `, i
    head;
3 i7 e7 x/ C( V! {( h+ p, o! K+ h    for(i=1;i<=M;i++)
: \5 t4 t; Z' P    { if(p->flag==1)4 V' y' T! a4 u9 Q& f5 H5 S; L  T
        printf("\t%d",p->number);. ]  B, ~- H2 N# @, m7 A; ~5 x
      p=p->next;
0 Y$ q% W& w% W/ o" O" k( _    }
4 x2 P' O4 v( P; j) l( a) H
  d( d8 E# ?; P7 ^& T$ I/ O. H- }0 t
  d& L! t9 W1 U! `4 V7 i
}

6 s7 A: w+ z, M: A# S第二种方法:数组
) I) t# j+ W3 X2 |& ~, {#include<stdio.h>+ t; W8 q5 e% `  V  [
#define M 8
9 A4 S. e* T) s* B& r- C( tstruct monkey
+ S% I5 R7 ~6 W! G5 i  K1 N{int number;# }! `2 e) |  S
int nextp;7 \& c% p: [1 D9 R3 G
}link[M+1];
+ k  h3 a. `- \" S/ o+ V  Y5 w/ f* V
+ B0 K) A# y) y* yvoid main()
/ g1 A( T6 N& [3 Z{int i,count,h;
9 g) F2 d  Q+ G% lfor(i=1;i<=M;i++)) l! T% ?1 x4 F3 ]; v
{  if(i==M)3 t5 O: X% Z5 j5 Q
   link[i].nextp=1;
' i2 A, g" v& |   else# @: w) M' Q* M$ x# x: D
   link[i].nextp=i+1;
1 X8 ^; P0 D0 u  link[i].number=i;
4 N0 y# f4 ]( q1 E4 q% H}
$ _" \" k( R% dprintf("\n");8 n7 ^/ G3 c. G& y) t5 j9 l
count=0;5 Y. e# k$ @1 l  H" y
h=M;/ [# ?1 x* k8 p4 T8 [: A
printf("依次退出的猴子: \n");: w' X* h7 q1 {' Z* U
while(count<M-1)% y4 M  X6 t  B
{i=0;/ }8 D5 b# t5 n/ O) h$ N
while(i!=3)
' z3 Q2 u) h$ b  d# L{ h=link[h].nextp;
$ y6 Y  O/ G7 {7 r   if(link[h].number)% y% C3 s) t4 |* R
     i++;}
3 q: s+ s) t' v( Y. [1 U/ W# b; D* v2 A. o6 w  J
printf("%4d",link[h].number);
1 {4 T2 a7 b$ o$ \+ w; z( c/ Q7 Hlink[h].number=0;, d& Y9 n' S8 i' A$ d
count++;
9 t, ~" X9 N2 Q0 H+ t0 u}7 [: C1 P9 e! ~4 R( D

) H& Q+ q+ }- e9 ]& x- c" H8 f- tprintf("\n大王是:");5 R. `5 M8 N" H" U* v% g% c
  for(i=1;i<=M;i++)
* s' h+ }9 n7 d7 ~7 n9 K  if(link[i].number)1 O" [. C6 u; y( q( A5 p2 {
    printf("%3d\n",link[i].number);- `6 ?$ R8 W" s" @" U9 X
$ [5 \5 `8 i1 b! E; j0 w1 t8 D
& J/ y1 e6 b% e1 k  r$ x4 s
}

9 s+ _. T& C& x6 I& E- O  p第三种是普通方法for循环

7 }* L8 Q$ \, V+ |2 @1 B( C& F#include<stdio.h>1 P2 j( E: i8 l5 r9 S/ ~
void main()4 f7 s8 }5 Z! I
{ int i,k,m,n,num[50],q,*p;+ A& o) r! ~5 p) t; X, E5 r$ _
    clrscr();
. z: z6 s3 B" h  A) |   printf("input number of person: n=");( M8 g. L$ L  W- Y
    scanf("%d",&n);$ N9 z2 G& s  ?& }4 W/ L1 i# o
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
9 q7 }# r' T/ o2 W    scanf("%d",&q);
2 ]- u0 s6 ]. n0 ^* ^% f   p=num;9 n. N5 e% }+ [9 v$ g, s
  for(i=0;i<n;i++)
- V( l# ?8 x' ^    *(p+i)=i+1;/ n3 c* T2 o6 |( G( {/ l% Z
   i=0;0 W, J: K0 N5 f: N: |- X
   k=0;
* n5 M# I" `8 `4 F, W% w   m=0;
2 F/ W+ p! b8 o  while(m<n-1)9 g9 |: G# ^4 k" q6 \  a% j
   {if(*(p+i)!=0) k++;
1 G+ I* D  `% K. i$ L     if(k==q)7 ]4 D6 U. j3 F
      { *(p+i)=0;
; h2 c; D; V$ a$ T: a6 z7 U; s, Y; k        k=0;
7 {6 ?1 c/ v5 V/ p        m++;
: Y3 Z! l. ?' E; \7 p9 a  i      }5 j. ^0 L' {5 |( }$ ^/ _
    i++;
  P% Q# F, ?* S. l    if(i==n)i=0;  l* L/ [( ]; |% i' Y0 s
   }
9 _) t: r/ e, Q: j& H0 Y: S/ a  while(*p==0)p++;
8 _0 B' y8 S* H3 L, y# q    printf("The last one is NO:%d\n",*p);
% q8 J& w& b7 d6 h, E% V, U7 g1 ~     getch();+ m& C# g% `5 Y; j8 x: d; ^; t

" k6 g0 h& ~+ H8 U; d3 g6 g7 f: F}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;7 e& v1 k; O# q
namespace 又费马达又费电
3 n- I7 R/ \9 W2 ?' w/ U; I{
% g2 q8 i, e9 Z# d4 C( X- R    class Program- N- X; l8 _. Y2 o( U- u
    {3 _* [+ o  _" m0 M+ V
        static void Main(string[] args)
$ r  K1 `1 p0 W: h        {$ t0 H4 o1 H  a& b5 i+ R, r! ?
            int m, n;4 l- i5 m" k7 g" H% d( G6 a( X( U
            Console.WriteLine("请输入数组长度");+ ]5 I5 `$ R6 s2 l! U
            m = int.Parse(Console.ReadLine());//m为数组的大小2 v  c0 Z: B6 k& K% e$ r& m! u
            Console.WriteLine("请输入要截取数字的大小");
9 ~6 z" h' g' v  P            n = int.Parse(Console.ReadLine());
% X% C" C0 Z, e* q/ G5 V  f# E            int [] numw=new int
) P& Z! G0 W, O- j- h! u
9 }- X2 W& G+ v5 f; s&shy;&shy;&shy;;
  b0 O" j$ o8 G$ |1 r            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数5 ~* `. s; \) }
            {
. y# E+ ~" V0 h" Z                numw[j - 1] = j;
$ W) M: @; e" }! m# Q            }
8 s0 z$ d6 ~) u) a            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
% o, J3 }% N+ @& E9 n2 l. r0 [1 J; i1 `* V            while (d != m - 1)
# p/ v9 Y: M2 s$ j5 e& }6 ~0 `* d0 @: w            {/ [/ r/ U# v# s. o4 P
                if (i == m && d != m - 1)$ q% J. M4 Q$ A# D
                {
, w2 E- e; v5 j( g$ e6 h: Z7 r                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
( G( ]; X6 s& V, v9 S# @                    continue;
3 h( Y, T4 N, \7 L                }
9 Q7 P, j% p; V) E) o                else7 M# L5 |8 Y) o8 Z1 v  S
                {5 y+ I* h" V" d+ k; h% Z1 Q% Z
                    if (numw[i] != 0)
4 h& [8 ^2 F' b. t9 s4 S2 l, p9 ?                    {
2 A) |8 P9 |) y  n1 C% f                        i++;
9 _, d, K  b) p% ?  o8 H6 E                        k++;  A' }7 k) Z3 d! K
                        if (k == n)
8 D1 _3 J# Q, B* T/ R                        {/ A: _0 C0 G$ r% L
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了6 w& t$ ?0 N% G% }! Z( {. ]- t
                            k = 0;
* w) q5 U' J& K% p; q              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小16 c- \3 p5 a, g# u
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);3 J6 L) I$ ?( x, G  g$ X/ M
                        }* G+ P+ K% G5 M" ~. v/ B) B
                        else//输出暂时还没有改变数组元素的值
  t8 S0 c, s2 V. I                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
% J( L$ Y1 n7 E                    }
" E; c' h* ^# B7 i                    else
2 o8 t; s% p' c. e+ j                        i++;//数组元素为0,直接跳过,不计数。。。; Q$ P" @" E6 V. O/ b
                }
" C$ O3 b9 v5 T ; I' _* Q" q% R4 ]

. O1 Y" y4 ?  T3 F% J$ C  n            }//结束while循环
8 Q9 `% g. q. a& b( [: G            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦: }1 z: i" B6 U7 U! Z8 g& P$ z5 g
           
) H( R* H5 n9 T8 z                if (numw[i] != 0)+ ^* V  `/ K. E) |: z& H) |) }
                    Console.WriteLine(numw[i]);
/ R+ o& U8 W! F4 q2 ]           . d7 G6 h$ d7 ]
            Console.ReadLine();& q/ k) `% U6 {: r' X( r; ^
        }
; J4 ]( {/ w% O. I( m, L) o; S    }- i! _# w6 u0 ]+ b
}
" [  E2 S' |6 y' I8 p  B% r
小甲鱼最新课程 -> 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-20 16:35

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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