鱼C论坛

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

猴子问题

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

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

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

x
大家好!
5 r. C1 g! d# |8 z0 L& z! N这几天我在忙着编一个问题,我用了一种方法编出来!
$ {* G: E/ Q! Y( r: D/ u4 t但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
+ m5 X) B$ b  e6 a3 a( ?- O- Z) \9 h注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
  ^* y1 k+ }, A7 T+ c8 |1 q/ O$ `9 E! C9 E+ S0 O/ a2 r* ~1 ?
9 \6 U1 M# ?$ b# x6 v8 c
                            题目4 T+ L9 U2 f$ T3 K( t- B8 V
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
$ v7 {+ ^$ M& S# g7 a第一种方法:利用循环链表
4 V/ E( m1 w, C. d$ M3 n. J) C- W$ ^* q#include<stdio.h>3 [! \0 u4 Q# a1 g; `' }) D4 |* l
#include<malloc.h>
  W2 k4 J/ G, i, F+ @4 x' C: R& l( T#define M 8            //共有8只猴子3 z7 ~$ B3 S5 N- S/ h, ^/ F9 |
#define N 3            //数到3只时退出第三只
) @+ n  z, U7 k. q' |' P) Rtypedef struct monkey
; Z: u7 ]& x3 X8 L. h2 ~8 f{int number;
* i: O) R& R5 e- _! G' `3 Rint flag;3 @! f+ `* K5 T0 E2 S) V
struct monkey* next;
, l6 J9 }7 M3 |% R' G5 w9 q7 @}MONKEY;
* a' `0 ]' Z$ g& u5 C6 i. Imain()
! U5 e$ a6 P7 f: p! B, {{ MONKEY *head=NULL,*p,*s;! V+ b! Y9 m" {( Z
  int i,sum=0,count=0;
3 n9 }! V! m+ g  clrscr();              //清屏5 I' N, }7 [5 k
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存! O, d# c7 z$ l9 [
  p->number=1;p->flag=1;
7 Q0 d. s7 q6 x8 V+ U  p->next=head;
2 X, ?- s* M# n% @% t- K  head=p;- c+ ?% U) C6 c1 u
  for(i=2;i<=M;i++)
3 u% `6 u, X, d* H    { s=(MONKEY *)malloc(sizeof(MONKEY));
8 @9 m7 o9 N$ U& ?5 X$ _     s->number=i;s->flag=1;
: K; f9 q( S# i     s->next=head;, n, u% M; R5 R, b1 R# _- x+ F
     p->next=s;p=p->next;
( M- C" _, i1 e    }' X- a: }7 ^' ^' a/ v6 k
    p=head;
2 C5 I" t" u7 g) ~9 Q9 Y   for(;;)
; ?" F* _$ v( ]4 m- d    {if(p->flag==1); ]0 m1 `7 ?# q; Y$ g" w
       count++;
5 \7 C/ c$ {' P; L) N. e     if(count==N)
8 [+ J: n& c3 _/ _6 L4 e' E: j        {p->flag=0;' y& z+ S; p; Y3 V9 O1 L
         count=0;+ }1 w3 i+ [3 T
         sum++;}1 Q9 B3 p% F7 ?$ @$ s
     if(sum==M-1)
" a) x5 h- H* _# t' c( n        break;
5 v4 ~% g# @; j0 p$ ?; Q     p=p->next;
8 J7 r- Y  h  t    }
+ {7 r- Z$ ^3 r" o% C7 n    p=+ c  e$ x( c5 p' q8 }" g/ f, l
    head;
8 a  }/ {$ ]% q  `    for(i=1;i<=M;i++)
+ M" a( o  B/ _3 V    { if(p->flag==1)
2 G3 p, w2 D+ @& S8 K        printf("\t%d",p->number);
- u5 {4 M. O, Y: M" _- y      p=p->next;8 H% j3 r6 M, l" n, I' o
    }
0 z) c2 c0 B$ j( B& J
+ N2 [/ r5 t  W+ k# G( f8 w
$ Y$ u% K7 Y5 }% u0 K  R. K
7 H3 Z% l0 K: D}
" L( u- x/ k0 H# P7 r
第二种方法:数组
# {  P& L# h6 C# n/ z6 f5 o( T8 I#include<stdio.h>
: ~) M( [& C( i( f' `+ f! S#define M 8* `* Q2 ~; k. s
struct monkey6 W9 V. }; G& |2 ^/ |: }
{int number;
* n- R% R4 }) ^3 s  A0 [: Yint nextp;4 l0 g3 b0 F4 a. \
}link[M+1];
' j4 w9 _  P1 Z/ b; _- t, \: f* O9 P9 S- n! q6 W$ j5 p# n0 [( N
void main()& W& m6 U6 _) [! _$ ~' K# b" Z
{int i,count,h;
/ D# X0 c9 \8 J# m+ Nfor(i=1;i<=M;i++)
( k) z! M% ^- t/ h{  if(i==M)0 k+ X" A- f9 Z. \0 b
   link[i].nextp=1;
4 k) F" N% l; i& T2 Y) l0 J+ G) v   else" p7 V( Q: S4 e, i; A1 k  J
   link[i].nextp=i+1;7 M2 V- L# A4 ~  A1 D; |! G3 C- L
  link[i].number=i;5 {# z# }. i& ~9 x  |
}1 w& X1 Q( N$ |) S! k% N0 ]
printf("\n");# @- P9 T6 w" j, c
count=0;
8 Z; W$ v1 o1 k% y) Kh=M;
2 c0 L4 M  K# ]% Eprintf("依次退出的猴子: \n");9 `6 ^. c3 v' v8 [* ?
while(count<M-1)
) L3 e: V: }2 `1 Z+ T5 Y2 \4 W{i=0;
  p4 Z/ @: x! Bwhile(i!=3)
. p! `) C/ v; p# S7 g{ h=link[h].nextp;
. C9 _. F# p1 L& H5 y6 N0 d" ?   if(link[h].number)
8 s2 ~5 F0 ?( k* l' b& ^     i++;}
) h# ?& u) c0 `' R" t0 w; x& M
printf("%4d",link[h].number);8 l; f7 @3 y+ }9 F1 j4 K8 `" N
link[h].number=0;/ [& V  `7 C, }3 f& s& P6 s+ S
count++;
1 p+ h1 _% n9 F6 X}
: g" I! H1 r) p- {( r" m& h' R
# \. O4 \$ x/ m5 {/ ]( Kprintf("\n大王是:");: \% j5 E% m) s7 S4 g! N
  for(i=1;i<=M;i++)
' D$ d7 T8 V9 w/ y0 s/ m  if(link[i].number)3 ?0 R2 G* d# R% Q
    printf("%3d\n",link[i].number);
6 R4 f; q% q$ g! c; f  g, [/ o; {* I/ h) e: i- C" r% X
0 b1 e2 P/ g# o. i% \( W( O
}
" g+ s& P1 A* G4 G8 y" t8 Q
第三种是普通方法for循环

* t! b/ J/ J' W2 [4 z1 f. G#include<stdio.h>2 J, y& j3 H9 C. R
void main()- p  L/ `: }* R2 h2 p
{ int i,k,m,n,num[50],q,*p;$ Z- Z5 T) [1 I
    clrscr();
: N. S+ M: J" Y) y; [9 |8 C   printf("input number of person: n=");
: o( n% z; Z' G6 [6 {7 ~    scanf("%d",&n);) G/ U; ]& h: f/ e
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只/ r, q/ E; L8 a) c6 E
    scanf("%d",&q);( A# w" Y" ]) n! b
   p=num;$ _7 ?9 P& t- `1 d  t# _
  for(i=0;i<n;i++)
/ M: d# R# E" j% O# b: \+ Z' @    *(p+i)=i+1;7 Q2 \3 C" a' s& V1 }
   i=0;3 p& L" J& H' m. Z2 ~! J
   k=0;* G) M& T3 i; [  q9 t( f  |4 I
   m=0;
. O& I  s0 ]! {3 l; Q- U  while(m<n-1)
- T# X4 l1 q+ V# r& y. p2 j5 ?   {if(*(p+i)!=0) k++;! ^5 h1 i- _( d; w' w! k0 L
     if(k==q)' i- u% t0 v( p9 T9 K1 F
      { *(p+i)=0;( ^- c; _1 X8 R
        k=0;8 N  d5 v7 I4 m: c8 Q
        m++;
' ]0 a* i& Y3 V& G      }
0 ^6 g) `: p9 S$ _5 f  ?* M    i++;7 L- F2 W' G# P5 _. P) \
    if(i==n)i=0;: t. g0 C$ `8 a; U0 g2 g' A
   }  X/ k! x/ x) W. u& Q
  while(*p==0)p++;1 q2 g0 [% E& e7 T" M
    printf("The last one is NO:%d\n",*p);& k2 x# s0 D/ e" F; M3 _" ]; C
     getch();
5 m! j9 \  R4 v: n/ g
6 Z* }& L$ V6 a' I}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;+ Y4 u: b) X# M
namespace 又费马达又费电
. W6 D0 ]+ d& w, v! f{
# i/ L0 u9 {/ T/ k' P( r4 ~    class Program9 V) G, N& u+ I! B/ J; L  A
    {% U9 y, j4 H4 h% Q6 f
        static void Main(string[] args)
+ d" R+ L) h  C$ F$ M# A! d6 `: C        {
" t6 g( l9 h4 W. x; p5 c# i            int m, n;) D0 F( V- g2 z% m, B# ?
            Console.WriteLine("请输入数组长度");
3 e8 F+ G8 p5 o; ]. ~' b. h2 t# f; ]4 T            m = int.Parse(Console.ReadLine());//m为数组的大小
2 i( h) c5 e6 A" o: z6 b            Console.WriteLine("请输入要截取数字的大小");
& z4 [3 {  |7 b1 s6 t0 b; M            n = int.Parse(Console.ReadLine());- ?: a& Y* S7 F9 K# ]$ z. u
            int [] numw=new int
- \$ z- l: i$ |, J8 s0 i. n9 P# E  l1 Z# g: R% W' o
&shy;&shy;&shy;;# K2 [/ k, \& ]# Y9 F+ V( s
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数& k2 S+ d3 Y$ @# P  R& s) d. v
            {2 Y. v# Q( r2 L/ @( u  j" v. Y
                numw[j - 1] = j;  H0 t5 b) U9 }' o
            }( W8 k0 g1 F3 K, w2 k/ _
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
- f1 x$ L6 X8 q1 E+ T            while (d != m - 1)
# S+ v! \  V+ O+ a8 M$ j            {
, C0 ]* o' Y8 `7 w; k9 f) {, W                if (i == m && d != m - 1)2 h2 ~! @9 x8 e" i- M
                {* J2 R, ~- w  A$ L. p  |
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
. t% O. B1 p' e) }; W  _) i8 E& ~                    continue;
2 h2 i  O: ^' _' W; W8 H                }
0 o+ J+ e$ c3 f! q  A                else; T" X3 C9 r  f
                {
4 |5 w+ f& b/ q, i0 P  V- t# [* Z2 x                    if (numw[i] != 0)
( j6 s) Q8 m! O                    {
# ~2 ]* {$ e, R4 I# H# L                        i++;9 `/ p: ~- \; e8 {5 K" s6 t4 Q$ J; W
                        k++;2 x9 E& h6 a1 v! f) Z% |
                        if (k == n)- X5 n* M! X" Z8 C
                        {
4 T' X' A5 h+ ^/ I! y+ @                            numw[i - 1] = 0;//把在n位置数组元素的值改变了: i7 w" Y5 ]  u; x! @
                            k = 0;
$ M& Z9 c! E# E# a' L; J; X  x              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1) f. T* ?9 e/ c4 m, _" B
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);5 ~4 }! p% H# y9 X) }0 ^
                        }: C; ]' I9 ]% C0 T2 S
                        else//输出暂时还没有改变数组元素的值1 M' D9 o: n4 V8 [( S3 o! o- A( l
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);' J; z- |0 {* F; X! J+ u- p1 j
                    }& u* S8 W- E' B& N* K
                    else
  N3 g  B5 R. I* p                        i++;//数组元素为0,直接跳过,不计数。。。
. t2 F, x& e" Q3 J                }! a- u1 }: d3 Z; j9 [) ~

- M2 R7 w5 v, R1 ^
/ l. f" l9 j: p3 r" l; q5 u            }//结束while循环
; X2 X0 e  `' }$ O+ G- x            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦- O  F; V% `8 w" ?( C/ G9 h* g! A
           . k& X5 v) U: ~
                if (numw[i] != 0)- G8 Z& ^( S  r; b  Z8 @0 A' S: x
                    Console.WriteLine(numw[i]);
7 `+ L* o3 g4 I           
7 l& H0 ~" h& B& d            Console.ReadLine();5 r9 z# H  M5 u
        }$ @( l6 R: J; H# L" ?0 T. ?$ P7 M
    }. Y1 z$ r- \9 R/ `' r" g
}
2 F+ I  Q4 H. g  R, k) L
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-2-19 05:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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