鱼C论坛

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

猴子问题

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

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

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

x
大家好!
5 p- q7 y* l8 J4 O' f* d8 r  r这几天我在忙着编一个问题,我用了一种方法编出来!* Y  ?% f0 K! q! J2 H; [
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
8 q. u/ v+ n; ^2 M( S; q5 I: f5 E, W注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 6 C- |' W8 ]' c6 Q

0 r: U! x% ~& t7 K5 w
% Z/ W: v/ n. z3 A, D% R
                            题目8 g5 K2 D1 G3 _
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。! d! f% F, N: P$ b0 ]: L
第一种方法:利用循环链表
: @( y2 G$ F6 L5 _#include<stdio.h>, K7 k. H/ I$ f$ J% p
#include<malloc.h>
6 O' Z% [* ?- b#define M 8            //共有8只猴子9 n4 ~; I& Y- G  w0 z6 H6 W. a
#define N 3            //数到3只时退出第三只$ N2 M% j' V5 V$ G) D0 g
typedef struct monkey
+ C' n9 C! z+ x* x  [9 Q{int number;
& V7 h' O- y" @. _- xint flag;$ E# H& c, ^* h
struct monkey* next;
$ v* w6 |; v% H+ }* b: W}MONKEY;0 y- @5 Q! w; I/ W, a
main()
6 I. h2 X, ]  g{ MONKEY *head=NULL,*p,*s;+ O0 d1 L- \, ?: S8 B5 C/ \' m
  int i,sum=0,count=0;
, A$ r0 w( c% `; d1 u8 l  clrscr();              //清屏/ d) x4 X( ?. r8 M  ], j
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
! P+ H# s$ e- I+ h( g) J6 t& ~& c  p->number=1;p->flag=1;8 N0 n2 I2 K6 p7 J/ L
  p->next=head;
; U, H2 T& X& u5 o5 ^" J: D4 i/ D  head=p;
, H) H9 S  D9 w( m, n# e- J  for(i=2;i<=M;i++)! p$ v' S$ }: \1 n" x% ]) d
    { s=(MONKEY *)malloc(sizeof(MONKEY));, n6 \4 e( ~+ Q6 \$ m
     s->number=i;s->flag=1;) {! K8 T: l3 Y& j$ a# T
     s->next=head;- Q0 N: o* {, U+ d! [, t
     p->next=s;p=p->next;
7 N5 |) O2 x/ U" X& y    }
1 f8 U8 M9 E' y; I# Q2 x    p=head;
6 ~, b4 H* w9 h, x+ o   for(;;)
/ H# F" l# L) s: D$ |: N  U: M' I    {if(p->flag==1)
: r4 c2 g1 o& ^5 j9 F# v       count++;
" I- g7 U- G1 V     if(count==N)
7 g& J! m5 p* d4 n/ _& \. r  b9 n        {p->flag=0;) _$ `, T, m* c
         count=0;6 k9 ^* D4 J" o: d' m  }
         sum++;}
0 l" n+ Q9 d- V6 k7 A* U( a. z5 F     if(sum==M-1)
3 r1 z- a) \; @7 w0 |! \* ?! s        break;
- ~+ N5 R% h6 |. A( Z$ C     p=p->next;
2 w+ A( x  X: x+ B4 c+ h    }
' E2 O  f4 D$ [! K' W0 `    p=. k5 v+ K( w* n: x
    head;
! U& N. M  A  W$ k    for(i=1;i<=M;i++)" B: y+ M' ]; U1 K# d- a
    { if(p->flag==1)4 W: @& P0 ^9 U. k
        printf("\t%d",p->number);
8 p9 J' @( M8 V0 ^# e; i( P      p=p->next;; {" R2 |4 {4 F6 x; I4 q* J0 j6 ?& C
    }
$ ~- d; |" o9 r1 I' `8 o
8 i9 ]" o! g+ U, B$ I. Q& r3 |0 r5 S* e5 W: ]3 w6 m: X5 c  s- r
% {9 U! n- v3 N" B
}
( r' b6 ]  m: h% b6 ~- j
第二种方法:数组2 A( e  K/ N. a  O8 Z5 X
#include<stdio.h>
/ _$ F6 O2 O3 R! K( Q#define M 8
2 m" J: s. s( d  D. r& a" Nstruct monkey
, B3 i+ l4 N4 j5 ]3 ]8 V{int number;* A; [0 z/ i+ \1 Q! n
int nextp;
& ]3 Q# V! H1 i6 S' B: K}link[M+1];3 h! R; _' [% \9 V

  W- T8 J# m* L! J+ N) {6 w$ ?void main()1 A7 l8 x$ F( v7 i
{int i,count,h;
* j0 K# t% j+ q0 ]( yfor(i=1;i<=M;i++)9 G3 Y) ]) H5 h. E- {  M
{  if(i==M)
; I/ |+ p& s1 h0 T   link[i].nextp=1;
& p! {4 m- U0 z9 M6 s4 x3 y   else; x5 [1 L' y  l- {
   link[i].nextp=i+1;* a- X+ g8 Y8 U4 F9 r
  link[i].number=i;+ i+ {3 d( P4 z  Z+ }
}
  z: w" K+ @) M5 s, ^+ `% T/ hprintf("\n");
( R* I' f- c9 {) |0 Bcount=0;. b, D2 r- V1 d9 y# m9 L* [
h=M;8 Y. @1 v7 m/ w, K6 ^( G
printf("依次退出的猴子: \n");
; `& s% m$ I% ~9 S! j7 @while(count<M-1)6 P( K: s* ~; o
{i=0;+ A& Q0 n) j$ Z9 W- G: Y5 l% e
while(i!=3)
; u1 r9 |8 ^0 ?/ U; v& X7 o& |: [{ h=link[h].nextp;
6 Y! o( J8 L/ @8 r/ K# D2 a   if(link[h].number)0 _3 l4 h& r( Z, h4 @
     i++;}
5 W4 U# l5 F; V
9 n1 ~+ v; p+ J. t, mprintf("%4d",link[h].number);
7 {; D! I/ M9 l& Xlink[h].number=0;) V/ t( j5 @2 {7 O7 x  e
count++;# c+ x( b& ^' I+ O" o" s& T2 Z. d
}; V& D8 D6 \3 v( o5 B

3 D/ z2 ~# K1 i' kprintf("\n大王是:");
% ?0 s' M/ J6 z/ p2 J0 m- N  for(i=1;i<=M;i++)1 y7 T5 D$ O+ R
  if(link[i].number)0 C% j  D- ^1 }) A1 s$ s( q  f
    printf("%3d\n",link[i].number);
- c5 |# d5 K# H7 E4 \
2 P# R. u0 u1 }9 \8 w/ w% t" Y0 J! c
}
- ~' U! [% N) {8 x0 Z
第三种是普通方法for循环
: A8 e, N9 ~! v7 W" _+ i* S
#include<stdio.h>
) @  a/ Z; d1 t# j, m) h' bvoid main()
3 H' ?# {  I" @, z{ int i,k,m,n,num[50],q,*p;
" d) |5 f: w" @    clrscr();8 [8 a" X7 _6 w+ i* x7 Q3 |
   printf("input number of person: n=");
. q. E2 A: q6 U' z+ z, G( t    scanf("%d",&n);% L* p  B8 V3 A' \4 }# f
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只4 o3 P0 Y# ^; m) t" A1 J
    scanf("%d",&q);
* F$ F5 L' X/ a* Y  ]   p=num;( l8 j8 D+ N& o  z4 B
  for(i=0;i<n;i++)
, ]( V/ l: W3 N/ L    *(p+i)=i+1;% k! D. s6 N& k, M" H3 d, N9 P9 `
   i=0;# ~! L2 D- X4 y" m/ x$ v1 g
   k=0;
  U6 D$ B3 z+ v( ?8 V   m=0;: D4 K" p3 g- I' e& v
  while(m<n-1)  O2 h4 R2 b) t
   {if(*(p+i)!=0) k++;
3 a; C2 I2 U" i. ?4 R7 z4 K     if(k==q)
4 p# V5 y3 @; S" h) k      { *(p+i)=0;
# j/ j* P- w: ^, y4 \        k=0;
* O: ~% n/ P' o$ _2 l/ y7 }        m++;
# P; O3 z; O" f+ r# ^      }
$ ^) t2 |. B; z' p! W& |    i++;0 ~+ R: L) G3 Y: m5 Y
    if(i==n)i=0;6 d& X; K6 G* _% r
   }
% S* g9 n0 {* C& g; n" U  while(*p==0)p++;) O/ v0 c. J0 |) m7 N" _, r
    printf("The last one is NO:%d\n",*p);! \3 a, t* U) e" ]5 S) A
     getch();4 p7 c; Q. d9 F* s9 \6 r8 |

. W4 B2 v* Y- A4 D$ J}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
4 z" P0 p4 {7 q* W" C' E# k+ l4 |namespace 又费马达又费电' O& _2 C) g  |7 L! R, }" P$ r
{+ t8 }9 Z2 C3 Q
    class Program. e. W+ c8 \1 k8 z! g# ^
    {
4 ?' [" A4 [3 X        static void Main(string[] args)% t8 m6 O3 i' l( o6 _7 |) w. }
        {8 m7 \/ {) r2 s- f+ j
            int m, n;. S! m, X9 u$ i! R  X" s3 b& m5 A
            Console.WriteLine("请输入数组长度");7 \, d2 \! [4 M* e- ^/ j3 v( k
            m = int.Parse(Console.ReadLine());//m为数组的大小
7 P8 e0 x# q: A  O" F2 A            Console.WriteLine("请输入要截取数字的大小");
7 R, p" w& K7 b2 D; D3 `$ h            n = int.Parse(Console.ReadLine());
0 p% J; ~8 `# ^  ~; ?) B            int [] numw=new int! }$ C, r2 C. |+ o- p  O$ A: |% m% ^
. }' {7 k3 v# f7 ]7 P6 G6 @
&shy;&shy;&shy;;! o1 n3 a- F# ?: B! m
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数- k& K9 g% g: N/ @0 q
            {
, n! s& W7 ?- T                numw[j - 1] = j;
( C! V8 Y- y/ [# [1 O3 e            }
# z: k& |) {: X4 D            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!8 a, a# V% Z' o4 B1 O
            while (d != m - 1)% @" h, ?9 a* l% q+ a! ~4 U
            {
# m/ s5 S( b0 F1 x/ D                if (i == m && d != m - 1)+ ^  Z5 W- F2 S' q+ a. J% G
                {
1 F+ }' K5 g8 u# _                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
9 H9 z! L. F4 Z5 x$ q0 q                    continue;
4 e; ]2 |+ q) N                }; ^1 q% ^- ~. g, i
                else
" H6 Q+ o& I) k, H$ b% F                {
6 e0 i7 r+ s, P! l                    if (numw[i] != 0)
1 Z/ p1 o% @  R; h1 W, G                    {
' L6 @6 v% |: e  V, b; Y                        i++;
0 ~- U! r9 H- O1 S, L0 l5 i                        k++;
0 F$ |+ c- B1 t7 ^                        if (k == n)
6 T2 \' U3 Z: ~4 G$ z7 V                        {9 s3 c' T+ L, t7 u. M: P9 s
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
! b" F9 L  Q" h( Q: l  g5 h                            k = 0;
, T% _" q" x. C$ ?              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小16 ?: _1 z, H4 a+ u: z+ N  O
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
! {/ S+ x; J* r/ G/ {# M4 Q                        }
* J+ R# ?. C) n, }; X                        else//输出暂时还没有改变数组元素的值8 n; g* C% |& r. A9 S0 z
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);2 Q* C9 x. D' u9 m8 U, [9 I2 v
                    }
0 x& `& O- j  ]; c- M& [) a6 @                    else3 Y, [2 g: J: s1 o
                        i++;//数组元素为0,直接跳过,不计数。。。
6 r# s5 ~$ I6 q7 f9 Q! g0 J                }
5 k8 G" v, w3 W5 v* b( a5 Y$ H 8 n# _9 ^1 A3 g8 y5 G, S  K

+ d2 g: i; h4 W: C+ Q$ B% J1 n            }//结束while循环
: x- d! b5 V; p7 m5 _$ J            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦% Q4 f- r1 v9 r) `4 b8 y" J
           
( l5 B$ B& _! Q5 F                if (numw[i] != 0)& q) `" L( M: ~. w: p4 m7 t& R
                    Console.WriteLine(numw[i]);/ G; P5 X7 T+ V: }/ z
             U6 R" d- w8 m3 ^
            Console.ReadLine();3 U; P0 ~0 l, ~. c8 Q6 o% z
        }
+ ^/ t8 v7 s& W& p$ \) K5 v    }
7 \: j+ z, K4 T' p9 L7 T, W}1 t7 [; k4 V2 ~* X9 c
小甲鱼最新课程 -> 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-3-10 00:35

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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