鱼C论坛

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

猴子问题

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

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

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

x
大家好!: N$ s$ m. q: |8 n6 m
这几天我在忙着编一个问题,我用了一种方法编出来!
  k, `7 A. D$ h但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!9 s* M. }' ?+ q; F. i
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
1 H/ ~8 y" o) _" F: K7 o/ s% C* q0 {9 t! [* N2 g3 e
/ C$ l  l/ q: ?, W  K2 G
                            题目
6 |4 t2 C+ X; t: Y  b3 P- {$ P山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
& R9 h4 F  ^$ A* n. D/ V" R第一种方法:利用循环链表( k3 `( [, j/ G
#include<stdio.h>
5 I3 l1 `6 i; x  @#include<malloc.h>) v/ ^' b' r' `! _! ~2 i: t+ b
#define M 8            //共有8只猴子4 z" i1 {; j2 Y- t; |
#define N 3            //数到3只时退出第三只# \3 M( O4 |" ]+ K3 _, U5 {
typedef struct monkey9 ~9 @# Z% V7 A  l. R+ }' u8 F" y
{int number;( r2 u+ f  g0 g0 o) h
int flag;
' x% L" s/ p8 J, O+ s- Bstruct monkey* next;4 E5 L' @* v- I' B
}MONKEY;
5 N" D( {/ ?# T* Y; B$ a5 hmain()9 c! o9 N5 j! K# o9 ?
{ MONKEY *head=NULL,*p,*s;0 |* u; }5 B% k$ {: Y
  int i,sum=0,count=0;* J, y# w/ n2 ?# r) R
  clrscr();              //清屏0 _$ J5 j3 v* T" E8 Y
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存) v* p" }$ i+ E; j9 o' s4 h
  p->number=1;p->flag=1;( z; W4 a$ u3 ]+ j
  p->next=head;& w! e3 p* ^' i: V. L
  head=p;+ L4 t, [! |* c" [6 V; S8 k
  for(i=2;i<=M;i++)9 w5 n" [1 C6 d2 ~/ @7 G/ J: F
    { s=(MONKEY *)malloc(sizeof(MONKEY));
6 ^# {. ^) i- v( f$ t     s->number=i;s->flag=1;* B  ^- D& _! P  Z9 Q9 @1 D
     s->next=head;
0 P9 v( h( p' P! k3 T     p->next=s;p=p->next;
- k' n/ V4 w* \( A7 a/ x% B; z! z; O    }
# n7 b8 F1 O7 G! ?) Y    p=head;+ t$ b! [2 M, W# K7 W$ V, u5 ~* Z
   for(;;)
; w' U7 T; t! M/ r  W/ [. V    {if(p->flag==1)
" ?+ J- i& K  D! R8 ?- x# u* d/ [       count++;" L- V2 H' F% @2 Y' A( Y, j
     if(count==N)4 @2 ]! r9 U) k6 Q' F# g
        {p->flag=0;8 `) B5 G* Q1 S8 {/ t
         count=0;
! Z) L" n, e' r2 D, h9 V         sum++;}. K9 C- I; c  D9 m" o
     if(sum==M-1)
6 @! G  j  i/ B4 @# ?7 Q5 L2 L        break;# f* ~8 b. o( \7 X- c
     p=p->next;
6 w! W$ V8 i# X3 S9 N, {# Q) K    }
. V: U0 U$ l4 h1 H* K' _& k" }% C# F    p=
  X+ c$ s2 k; |    head;7 K1 k+ Q; @* K5 Y7 G* r! Y# \
    for(i=1;i<=M;i++)
6 p4 [7 t) f+ R% c4 Z    { if(p->flag==1)2 N$ X7 N& V, T  b) A  j
        printf("\t%d",p->number);" Q0 m8 |( c+ x8 F- P0 m! R
      p=p->next;
) f- m9 l# H" l  P7 E8 ~    }
3 p; V6 t% R5 ]' C$ w& |! Q
5 L" b. Y3 ]  m* N; t
5 o/ C  p) ?/ p2 ?4 |2 j) _' N( S: l9 s' Y& ~/ z
}
/ B$ a; P+ f3 W6 e4 X1 q1 M& F
第二种方法:数组( U& s0 V" J' A3 t: s
#include<stdio.h>* W1 l5 k1 |6 X, @/ ~1 v; U3 D
#define M 8/ ^7 `, f% ?4 w; W4 u" ~4 p5 G6 D
struct monkey( k) g8 w' `6 T9 }' l: n
{int number;
3 b+ D/ W  G9 \6 Sint nextp;! v$ k* H2 h/ V, `+ C6 w
}link[M+1];2 n% x, @/ V0 w, ~9 F8 s( f
8 j0 R' K$ x/ Z: u6 {
void main()# z* K7 s4 ?2 x. @; s
{int i,count,h;
: _$ Q; ^7 n4 Bfor(i=1;i<=M;i++)) q: c/ @9 U: z  }
{  if(i==M)/ I3 S) ]# A) }( h: e( `8 U; W
   link[i].nextp=1;( F) r. j2 J/ z0 H# i$ V  ]
   else8 c6 Y6 x1 O. @0 T& h6 l
   link[i].nextp=i+1;. u. {# U, C, ?' ~
  link[i].number=i;
$ }9 z4 D; k7 W+ L) D* C! D}
; A. D, C% V! g' L6 ]. Oprintf("\n");
0 Q& t# K5 w8 V' q3 z  Jcount=0;5 A% L$ I+ k: R' H2 V0 b. ]$ O4 J
h=M;
" A. h& X: _9 m4 O, vprintf("依次退出的猴子: \n");9 o# M% s8 r& w" o
while(count<M-1)
2 f/ w3 {" U1 H- r5 q7 h{i=0;" v; {9 `! k- D6 D1 y  A' ~; a( b% z
while(i!=3)/ @0 \1 S1 q' {0 w' d/ b
{ h=link[h].nextp;/ w$ |; ^5 d+ B
   if(link[h].number)
9 n4 K6 F, Q* d( Q% e% b. l! U( v     i++;}
% w. {5 b0 d4 n9 T- e8 o% _6 m% {4 N" C" }
printf("%4d",link[h].number);
# [- P" z8 ^) S) Olink[h].number=0;1 B6 I3 |+ Z- Z
count++;! k7 m7 I( _- X
}
4 q+ g9 a, @9 s5 u3 R) K& C& B$ v' a2 X, \
printf("\n大王是:");3 \. k' ]2 K3 d+ m
  for(i=1;i<=M;i++)
7 o; }+ `4 d3 }" W# X; Q  Y# F  e  if(link[i].number)
/ n6 U. o1 j% C' \2 W5 I    printf("%3d\n",link[i].number);
$ J; w0 ~4 i# K- l
- P5 l- s2 w7 _7 `7 I/ x) J2 |: o- T, g
}
: ?3 F! C5 Q0 S# [& j, H/ i
第三种是普通方法for循环

. _# D; Z+ O: w3 h5 f, ?8 \#include<stdio.h>& F! ]( Y4 F2 u& u. c( T" t8 V/ q
void main()
2 `* E% {( v' h' a7 k# T{ int i,k,m,n,num[50],q,*p;
& {1 r7 T4 n  x1 W. X    clrscr();" C' r% }4 E$ J, O" N4 O# }& F
   printf("input number of person: n=");
# j! O# [- J7 ^- i    scanf("%d",&n);* H9 h: b, l$ X2 {5 L% q
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
; ~9 |" @1 r7 S7 P9 j* p    scanf("%d",&q);6 V9 P& q# q& X! e
   p=num;
, o' G! v3 A; i% l+ |0 t  for(i=0;i<n;i++)
8 N( ~0 d* P! [6 l    *(p+i)=i+1;* C  H. @1 J- Q
   i=0;
4 i9 o) r9 {, n( V# }9 U4 t   k=0;: C6 ], Z# S/ w, R; j
   m=0;
( d" s- v7 D3 s1 A  while(m<n-1)& e: ]; t0 G) v2 n
   {if(*(p+i)!=0) k++;' n0 t* w4 Z7 Q! T9 a* a
     if(k==q)
# c4 {+ H: V* \6 M/ {# r0 v+ a      { *(p+i)=0;
% e. F$ [/ P8 Q. `6 l        k=0;
- B. V& V0 A; q        m++;# S1 l/ g; X8 l3 U* d" l
      }
' R* L* ~) P& G$ w$ Q( O4 P    i++;
  E. m" f2 ^" A' u" u  \7 V, g    if(i==n)i=0;! `0 A3 Y1 f7 l5 W- \9 ]* N% A0 s$ t
   }
  s8 I( L' j1 G* Z9 u  while(*p==0)p++;
. ^  n2 n+ W3 ?2 T+ N    printf("The last one is NO:%d\n",*p);
3 ^1 D6 k2 h  z; }9 |     getch();
- ?! G& x7 ^2 r: I
$ f- n6 E, \7 m2 e, p}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
9 y7 u% S6 Y' Unamespace 又费马达又费电
7 P# p# _" g0 y2 d3 q1 ~5 t{: P# D+ z( n4 C4 j
    class Program( f) _' k' s2 ~) y
    {
1 O4 m7 W% I/ L2 x2 f" X( T  u0 Y        static void Main(string[] args)$ W. ^2 e0 L4 q, a4 i: l& Y, C
        {- d( S+ J8 m  P4 B+ W3 s
            int m, n;* j9 Q2 b7 i% R. Q) j
            Console.WriteLine("请输入数组长度");9 W1 W6 x- k3 q3 w
            m = int.Parse(Console.ReadLine());//m为数组的大小' Z/ v3 y7 ^7 P& g  G+ c, W
            Console.WriteLine("请输入要截取数字的大小");0 f- ?  [! u; K4 ^
            n = int.Parse(Console.ReadLine());
9 O7 h! V; f6 L; n/ a! M/ w1 }+ @9 Y            int [] numw=new int
8 a/ g2 q7 Z9 e: X, T' v! M. Z1 p  ], u) Z) O: c
&shy;&shy;&shy;;
# G, B. B7 Z9 g' N3 h5 {! O            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
% ^# }+ [. z' n% j' w            {
, o( {) e8 w% i) Q4 X( D6 k: }                numw[j - 1] = j;; w1 p0 q3 a% V4 }0 C  T/ K  h
            }
  k8 p- H, ?5 c+ a: _            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!% R) f) y* ^; g4 U6 H: A
            while (d != m - 1)
! L9 z4 H# K1 a            {
6 `" g, k" B; t# ~$ y/ [: Z& x                if (i == m && d != m - 1)7 C' A% t( r, Q; P
                {
" a* y( t8 K8 X/ b4 P                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
% n( T, Q' c- c9 l2 S4 y! P5 w                    continue;3 }; g6 j. ]+ _$ k& ?) A
                }
. l) r  e6 g) u: _+ {& P# [                else
, J* ]; i& L( j                {
/ n: r% S. ?9 L7 [& d                    if (numw[i] != 0)
2 ]9 W' a1 j' R6 p; z                    {$ }# F; n6 r, @0 q# l2 O
                        i++;0 {! j. ]3 V) t! |& V
                        k++;! \/ j# O$ z. L' O9 j
                        if (k == n)) K: p. Y& ]& B6 U, @
                        {
3 H3 B; u+ H' \' s7 k! X                            numw[i - 1] = 0;//把在n位置数组元素的值改变了7 V3 L& s& o6 F. T
                            k = 0;
$ Z- ?$ _9 h7 K# e1 g: F              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1) I: ~& S; w5 Z9 Z1 {, G. H) b
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
+ A  s/ h5 J/ h0 Y                        }( K5 A$ s6 q' s9 j* k) d
                        else//输出暂时还没有改变数组元素的值% s6 Y6 ]6 |' Z( Y1 o; M9 r
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* p! ]& [8 |2 X! B8 ]
                    }
+ E" u# ]5 a# {: c( k                    else0 m' f/ R9 @$ U: i  m* e
                        i++;//数组元素为0,直接跳过,不计数。。。* \; a3 J& c5 s* G/ ?
                }
- N; e3 O; P) Y, f- G" L: u
$ x6 `! L* E9 K) y' i
: ^2 [, S2 V2 \            }//结束while循环
* ]0 x' Y5 @$ X% {9 e% B            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
5 }7 G+ G: w. v6 D1 q8 {           
) ]+ R# U0 R& q                if (numw[i] != 0)
% Y' ~1 y' X  I4 g$ h0 m9 y                    Console.WriteLine(numw[i]);
/ }* W( ]: U, V  Q6 x           
0 b; _4 i, B+ q8 _9 s5 q            Console.ReadLine();" Y7 q* W  R3 R5 J  Q1 y( i
        }4 z( K! t0 M; y! c& c) r& c1 B
    }
5 d3 e, m$ ^" J. ], k7 ]; p' a}
; V: L) \  R0 o7 a
小甲鱼最新课程 -> 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, 2025-11-9 18:24

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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