鱼C论坛

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

猴子问题

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

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

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

x
大家好!/ E- E3 t  W  P/ [' v  g
这几天我在忙着编一个问题,我用了一种方法编出来!& i: Q! d# H6 B& w: U5 z
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!8 m, k) J( T" c% S- n# o
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 o3 g$ G. G" s+ O6 H. Y1 X+ \+ X( R8 E& D3 p

+ U+ `" f& Y8 m% T: G2 i
                            题目' y' Z: t1 R. X( a0 B. Q, V, {
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。' G3 a' ]6 `, c& x% q0 Z  W
第一种方法:利用循环链表
* C! k! o' L. f( @9 e#include<stdio.h>
* K# a" t- K6 I+ R- c#include<malloc.h>. L; S) z; \$ E) y3 [" M
#define M 8            //共有8只猴子4 O5 h! d1 K5 F4 X( _
#define N 3            //数到3只时退出第三只
3 b7 m! L/ H" Itypedef struct monkey
0 i0 z% O1 X# t  E0 Y{int number;$ G2 @; k0 |. u0 t/ {
int flag;
+ E5 x2 u. g, \- |& l, [1 v1 N# xstruct monkey* next;. ~  m' i6 L! ~- k7 u1 I
}MONKEY;/ ?2 q5 e0 a1 f+ q; K
main()6 U5 I8 z+ V# t5 x$ ]% K$ B
{ MONKEY *head=NULL,*p,*s;; I+ L* ^& A  c
  int i,sum=0,count=0;9 y# U4 n. R+ [9 U. L) Y
  clrscr();              //清屏
" D) i2 _& G$ z3 F& }  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
; i0 S& O4 j  O9 z; `; X! v  p->number=1;p->flag=1;1 C$ h6 H2 J* p7 d7 r) v; h" E& i
  p->next=head;: T" p. [4 g. H6 [" ^, h& B! ^1 X- B
  head=p;- w( |6 r, R; t/ @. P+ h  W
  for(i=2;i<=M;i++)! Q  A7 }' X3 L# U1 n6 r" P
    { s=(MONKEY *)malloc(sizeof(MONKEY));* w; {9 r& m3 H" T* u
     s->number=i;s->flag=1;+ O# ~; y2 `3 v: ~
     s->next=head;2 e' B+ C+ {" V+ f1 n
     p->next=s;p=p->next;
: ^$ |6 P. t! u4 w    }
, }2 S2 e! |. `7 L    p=head;3 R$ E) d' y4 A: b) d) h0 u3 ^! R
   for(;;)0 z' n7 h/ @: Y' }  a
    {if(p->flag==1)) m3 I2 g+ r8 `5 O
       count++;% q; {) \- L3 n6 Z
     if(count==N)
  ?: e1 E  D* H& P) D5 k& E        {p->flag=0;
% `* K9 {% o' [$ z5 w         count=0;
3 @' s# O# S+ p: s; Q         sum++;}
+ y" i. e+ A, h7 O" Z     if(sum==M-1)
- ]0 V7 w! P! |* o6 |        break;+ H+ ~" M$ B$ a5 o. C7 f4 C' j
     p=p->next;
; W+ K+ }1 L/ {$ {    }
2 y. b* F7 D* x" F! Q% A" A    p=3 s7 Q1 K5 j* n6 g
    head;
( [: K* A# n2 b! d    for(i=1;i<=M;i++)
+ n. {5 i5 N9 C# @  e4 f" m  M    { if(p->flag==1)9 c. G' V! n" y3 i( M9 ]
        printf("\t%d",p->number);  t6 b. T1 B; U) G
      p=p->next;
1 H/ T' w  ]* ?* `, ?    }: y1 s* Y, V  y' Z$ m6 e- a3 R

7 P0 \( A4 h) x' p  V* i+ O2 u& D7 R1 T/ b7 ^/ K; k  [

& k4 Z" @5 i' D6 _}
1 V, e* i' L* J: b
第二种方法:数组
9 {$ f7 R: A! V5 u: l, H#include<stdio.h>9 |  J* t2 w. E  {  N7 e
#define M 8% z6 @* B0 ?, `* d) {
struct monkey
2 @7 S1 m. ^7 b- N; S5 W{int number;
% a& g( ^/ h" w( L+ Pint nextp;  K0 g* f/ T, I- ?: G* Z% J
}link[M+1];9 d+ J, Q6 X% C* @! U* y
. d4 d- C2 V) B. z0 _3 |: @1 N
void main()
  H" o4 b5 V1 B: ^! H{int i,count,h;
# h0 P( J9 w' R$ yfor(i=1;i<=M;i++)
. {' x$ `8 h0 ~) M9 `- e8 o7 l{  if(i==M). n: \& e8 z' n$ f- A
   link[i].nextp=1;: O3 Q$ T6 ~7 w7 h+ f
   else3 a5 p+ a/ [' S+ ~
   link[i].nextp=i+1;8 n$ r- f$ u% P
  link[i].number=i;; A9 T7 h- Q. q3 B; K
}
. I% K6 ^4 }! S' X+ X) R' nprintf("\n");) j- I6 w( Z+ F( u; A0 W
count=0;( s, y, H2 l8 W% W( D+ o
h=M;
5 X% U3 J$ B8 _7 ^printf("依次退出的猴子: \n");' Y1 d7 n2 v' y
while(count<M-1)
/ ^& y7 q$ c9 S- O2 D{i=0;
6 Q' ^6 _2 B( iwhile(i!=3)
- b3 ?1 {9 Z! z7 h# Q1 @( R{ h=link[h].nextp;
- S4 X7 Z1 u# Y9 r9 _   if(link[h].number)8 j( R; G) ?. ?. k# m% x
     i++;}
% H# S  ?3 p; \) b. K- ~& a( V* d6 o5 Z! N( M6 F
printf("%4d",link[h].number);% e0 L' K& U; A; W5 `/ u
link[h].number=0;
5 d& w# |& B3 f: Icount++;
* N6 }$ d* K6 P9 }* w}3 _- Y9 ~+ D+ H# s  ^' a

# p4 W2 g$ o' z$ x0 I9 I7 V! `4 Jprintf("\n大王是:");
! v7 i& ~, h" b  for(i=1;i<=M;i++)
) @- k, y1 X' j/ k; R  if(link[i].number)
/ Z1 l/ J! {: {    printf("%3d\n",link[i].number);
3 l* b* `5 }: ~' a4 \" I$ e, }, Z9 j( P  ]" O7 R* u
) Y3 L, ^. Y* k: ^
}
+ [: m. H1 x2 Y/ L
第三种是普通方法for循环
: p2 p* E6 ^+ A( k9 |. ]& x
#include<stdio.h>  c6 c/ D( F! x) z" a
void main()
+ W7 n' i5 D/ S! m0 `{ int i,k,m,n,num[50],q,*p;
: I* @. I. U7 J  ?8 e+ X! G    clrscr();3 i/ r5 L% p' [" l7 w6 Q4 L
   printf("input number of person: n=");5 A1 W0 ?8 I+ U! Q8 }% R
    scanf("%d",&n);
  r1 B+ i% \( r. T+ F$ J7 tprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只: D9 k9 n6 k0 D$ k8 r) v9 Y7 ]; x% B
    scanf("%d",&q);
+ L. h! P6 D, L6 _+ \' r1 X. W   p=num;
1 X9 Q1 m+ g" N% z+ \- \  for(i=0;i<n;i++)  D* B9 `/ U( X3 s( N
    *(p+i)=i+1;" M5 V& f7 y! \
   i=0;) B: n/ u0 J) m& q, l$ k
   k=0;
# m9 h$ H5 E4 n  T! F8 C: p   m=0;: j8 D" U* ^7 o/ d! K
  while(m<n-1)7 G7 l/ `  f1 f8 ~
   {if(*(p+i)!=0) k++;
* y" A5 `: o4 I4 s3 F% y& C     if(k==q)
+ H, r( Y8 h0 I0 e( w4 r- U6 R& z      { *(p+i)=0;
3 t* C. i$ Z0 j        k=0;
$ {3 ]) R+ ]1 K- J* L9 t8 p( @        m++;
* Z# |4 A/ f6 L) I1 K: |      }% ^# L: F: e; r8 n6 |
    i++;
5 @% \/ ?- j' n& M* |  v& j) V6 d8 e. [    if(i==n)i=0;% Y; ]1 ?0 p2 H0 c. k. I
   }! v! R8 X9 h0 F, R  t
  while(*p==0)p++;
8 l: n' Z+ ~7 ~! [! `3 _    printf("The last one is NO:%d\n",*p);
2 i3 {* J' T3 Q! R- h  D3 s     getch();2 W% }0 D  d* u  ]2 c

; Z6 F. o, ?( S4 s6 p' Q* k}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
4 p  m5 B( D) U# mnamespace 又费马达又费电/ j3 X0 k: W! [
{
. a& F& \1 |8 D: J* u    class Program3 c* N. H, ^# }, I
    {
, U- r" H4 p/ v: V; \9 c$ C; ]        static void Main(string[] args)- f% }4 l. J. n0 ?3 m
        {
: O# [" N! c+ L. k. t: ~% Z* t            int m, n;
, T( p0 X+ i8 q6 _! z' q            Console.WriteLine("请输入数组长度");
# q; |9 i' I0 B6 f) l            m = int.Parse(Console.ReadLine());//m为数组的大小. N/ ^+ x, j9 [! y5 A
            Console.WriteLine("请输入要截取数字的大小");
, ~( T% a! J' m" d  n5 L+ R            n = int.Parse(Console.ReadLine());
6 Z- A. f: x" w9 I            int [] numw=new int
* k3 a4 G$ E* X) M4 q. {) b
7 j' Z+ l6 E, t) W& R+ y) m* H&shy;&shy;&shy;;
. r2 t1 R) P7 }& }6 m2 B, L* I            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
- |/ _, s1 O4 N            {7 U% h7 p* [, ?, X$ h: Q# r" F' t
                numw[j - 1] = j;
7 X' L0 ~& K! ]. A            }
; \9 _" `- f' F2 h% I' ?( ~            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
% _6 U+ L. l3 m* D% [( B5 k            while (d != m - 1)
9 Z6 J9 s. c: e& `+ }3 T            {
4 C) C' t/ M8 v' ]3 ]0 ]' s( f3 B. L                if (i == m && d != m - 1)
- W3 w$ T: A4 ^; o0 `. v                {
/ J0 y3 y. o: Q+ \, k" H5 T                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
- E+ V( T4 H: E/ B2 P                    continue;
# B: h5 c% T' {1 c0 v# z0 K  N                }: V' a; K! A: O5 n( e
                else8 e. I; s/ @0 O' D
                {
+ W1 ]/ I+ c2 d9 r                    if (numw[i] != 0)) Q% o  H9 b6 }" {
                    {
$ [1 ^+ O* n1 A: E: h2 O, g, V3 d                        i++;; n$ r2 v  G* z& A4 E) U2 r
                        k++;' W! y8 L4 x7 R$ z  X  J
                        if (k == n)
/ Q: T4 V  ~2 T$ z7 j# W                        {
/ e$ Z$ P+ }7 j+ r                            numw[i - 1] = 0;//把在n位置数组元素的值改变了1 r' B" a" r9 `% p/ n
                            k = 0;' N3 {7 c& D2 M6 R2 Z+ r$ w, t7 V2 X
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小14 R: A1 d8 W( t4 w
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);& r+ o* s/ ?& J$ @  _; Z
                        }
8 V% T" {/ `) N+ [, e4 ^                        else//输出暂时还没有改变数组元素的值
4 o" r3 B( o$ G8 ^# K0 [                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
/ P" ]- ]& m/ p3 h+ |$ C' R                    }& M& Y! x( C4 a4 ^- Y4 Z
                    else
7 Z1 m) _4 }( x6 u. W# b. ^$ g2 N                        i++;//数组元素为0,直接跳过,不计数。。。, ]2 T3 R7 X9 G6 T# O  C# i! N
                }
/ K& O0 \& {# _4 s6 \9 l+ |
' k7 u6 p) F. W% j, }* f0 ]  S  t& A4 d" _
            }//结束while循环
+ B$ j/ [" h* T; H            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
" i* c; P* y" c- r           
. d8 `& x# q. g( i  D/ F+ W5 x! P! x                if (numw[i] != 0)
  ?) j$ l& M6 K; o7 N1 _                    Console.WriteLine(numw[i]);
  {' Q( U- v5 b8 c6 ~/ z) f4 N           6 v8 T! Z; y" M0 [9 I5 o% N7 R* f
            Console.ReadLine();: V9 o! [2 {" T$ p3 h- t
        }
& u% d, I; F& y) x    }
' o0 V, S6 h- o' x  {}
- R( m' G# B! e
小甲鱼最新课程 -> 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-21 20:50

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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