鱼C论坛

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

猴子问题

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

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

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

x
大家好!# i& \3 h5 F. t" P" I7 L) r
这几天我在忙着编一个问题,我用了一种方法编出来!  E- y( N' |! t( v& }
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!& I2 t3 {) w  p% |  {. v
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
% u" u9 g% a* B5 t
% |9 L7 }2 D5 t3 D, Y; M  u: D2 ^) N
                            题目  ^9 E: |/ s) P% y% R5 @
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。" W4 ~& R# a9 X" G# O' l2 v; H# R
第一种方法:利用循环链表% Q8 s- C/ J+ p8 D0 m7 ?
#include<stdio.h>
3 D2 d( S- o+ Y1 B  z- p' D#include<malloc.h>
7 Q+ E. j1 u2 }! Y9 ?% d( x#define M 8            //共有8只猴子2 y: g; W: s2 B3 ?" g# k; B7 d
#define N 3            //数到3只时退出第三只
+ P8 Y- M+ o# C% E& ntypedef struct monkey
' b& {4 X) O9 [2 I( H' L{int number;
# A9 D' Q: h2 pint flag;
/ k: Y( i, W$ _6 s% w- Tstruct monkey* next;
" v, {4 _, K1 Z$ u( G' d}MONKEY;0 D: I+ u% j7 L  B
main()
" T$ q$ r" G: [$ M0 _{ MONKEY *head=NULL,*p,*s;/ j, d9 r$ s! \
  int i,sum=0,count=0;9 K3 m. ~! r0 A8 B. ]
  clrscr();              //清屏
+ N6 b. e; U* m$ M( S6 c3 l9 ~  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
. n7 s& t4 ~# M/ k  p->number=1;p->flag=1;0 _8 u8 j) I! x( o
  p->next=head;
  p& a' R1 A2 I1 g( X# s  head=p;
5 _* }2 S8 X" c( Q, x' M  B  for(i=2;i<=M;i++)
5 D( d4 r1 d$ w+ t    { s=(MONKEY *)malloc(sizeof(MONKEY));# J6 d& w1 v, D. B
     s->number=i;s->flag=1;% [& _9 o  t5 i: V8 Q" z0 a# n
     s->next=head;
. N7 E/ R2 n' U     p->next=s;p=p->next;
/ B/ N2 j" {0 H* F/ X+ I4 }  T    }, R3 \4 z& m' N" }: S0 N
    p=head;! `( E& b& l' T  \
   for(;;)( v, _7 Y# w# `  f
    {if(p->flag==1): \7 |6 E2 V" v/ Q4 t
       count++;
9 f) y9 @4 @! b! V+ a' A" d& r; s     if(count==N)/ C- |6 z7 I* d. ^/ |
        {p->flag=0;
8 ]3 z% b3 p9 x' R         count=0;
: m! S. j% |/ E" T# j& s         sum++;}
/ k6 _. \$ J7 W4 M) t     if(sum==M-1)# z9 u/ S* x' x' T
        break;  i3 A5 k. {5 c% n
     p=p->next;* O  x/ R+ t" x3 ~. ?1 R9 |) i/ J
    }4 h4 f) @& I8 e/ V% G% |2 b# j
    p=
: r* F4 o0 J' ~    head;
( [3 G; Y: p. _# P    for(i=1;i<=M;i++)
& {; _* f, t+ o9 \' @1 Z) n  `( u    { if(p->flag==1)3 m4 G3 h* C* f  W- }( U# o
        printf("\t%d",p->number);0 |+ c- h; v0 P" N" c
      p=p->next;
$ K6 P9 {9 B" }; T% w6 n    }, }2 `$ z5 a6 ?) f0 T; N; |3 I/ x0 d. z

9 o7 A& Y, s5 z
3 Q; G- b: X! u2 `/ A) d3 B- X  [7 E0 @) z: Q/ Y2 R
}
$ W# L4 l1 H! T7 t. r  p
第二种方法:数组
* J8 D" n4 w/ E( D/ _' D" @, p#include<stdio.h>
( J# r1 t& v" g4 E# E+ ~#define M 8
( A/ L5 c8 ^5 \" {- K# P% _struct monkey
6 K4 l/ n$ X1 t& L5 s1 R{int number;% w( L  l- K, k
int nextp;( y8 r# P6 K+ }$ L2 `
}link[M+1];( A( Y, f/ J2 O* g2 B3 ?& L5 ^
# L: F! ]7 h' r; i( y
void main()
( w& \6 ~' Z% H& f{int i,count,h;
, @( [" x' S% ?for(i=1;i<=M;i++)
* ~" h; d7 u# q& T$ b1 c{  if(i==M)
' K' L5 D/ E* K* g* J& Y   link[i].nextp=1;* H4 P% J4 U* G5 ~/ H0 C9 C
   else
  S3 Z/ c- f; ^( v. J/ z# V! E! _' N  Y   link[i].nextp=i+1;
: b' {( u3 L: s2 G  u8 H+ S  link[i].number=i;
- L# J" _& }# _4 {% X6 ^, B}
1 Z7 t( Q4 W' Dprintf("\n");
! V* I6 i) s' f4 w( P4 V2 w& f( Ccount=0;9 U4 ]/ l4 L% p5 n- Z8 C# q
h=M;
3 X/ [& T/ t, a  oprintf("依次退出的猴子: \n");
& h- m7 d! L9 ?; P* w( \5 A% Awhile(count<M-1)
& p  `( v4 R: g' O8 t* I7 f{i=0;
7 A4 w+ q# f+ z5 c" `6 jwhile(i!=3)' s4 l! G- c! T9 W6 f2 X
{ h=link[h].nextp;
# @  U# L# h1 u1 N' g5 @6 t   if(link[h].number)/ g8 N. d+ v- y
     i++;}
+ f* R' Q* V2 \8 Z2 x: P
% E% [) V: B4 [  q, N3 g, u5 Mprintf("%4d",link[h].number);
# G6 D6 W6 g1 [4 s1 d6 K. \link[h].number=0;5 h3 _8 f- @6 D0 s: ^. t
count++;
; F( H( H& {- }}+ I) T7 o% I6 q

" s$ w) p9 x2 {" m% gprintf("\n大王是:");
7 H; B0 S% ]& ]4 w; ]4 A: L  for(i=1;i<=M;i++)
1 T" R: l9 ~" u" V- A  if(link[i].number)" T0 e5 V2 I$ N# ?2 p5 l# C( x) Z' J
    printf("%3d\n",link[i].number);, l. y( p' ~/ S; j

; D4 R) L2 u' z3 t% R
, r  I. |$ T* P0 X9 G* m' @( w}

" j3 T# ^8 C. k4 p0 b, J0 U- k第三种是普通方法for循环
8 U% J9 {3 z+ A
#include<stdio.h>6 P7 w  a2 A' v2 o6 \( ]# P
void main()
! Z; |. Y$ Z' i{ int i,k,m,n,num[50],q,*p;
! O. J1 ~! f- x! h    clrscr();
+ N, U; j( M) m7 S3 F- q. E$ N   printf("input number of person: n=");2 P1 G8 X0 @2 N6 r- G6 r
    scanf("%d",&n);* ^# r% [4 ^# O7 [( Y
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
, P4 O6 F* }7 Z3 N' b    scanf("%d",&q);
: R! X% O/ i( w; e   p=num;
5 \& j1 F- M' p' M# j4 v, B2 t  for(i=0;i<n;i++); F, \( \8 m, O2 c
    *(p+i)=i+1;% [1 V  A, n9 `1 i
   i=0;
4 g4 ~& b# B) Z& w# {   k=0;
' [3 }' _& ]7 Z/ I% x/ j# [+ h8 |   m=0;' `+ g0 M0 {  A5 d& j
  while(m<n-1)
; U6 _1 q! Y- M) N8 v" t   {if(*(p+i)!=0) k++;
$ _9 I: T; ^% B3 G     if(k==q)! C7 ^- M# M7 G! a
      { *(p+i)=0;
+ D% B( i3 H" V2 G( m        k=0;' w# U: [. D) z9 j1 `
        m++;
) w! ]- ]5 J1 ^( g5 [' D+ m      }9 z8 o2 C0 Z. r, H" h1 s/ J  g
    i++;' r* N% J3 s, e7 }8 D
    if(i==n)i=0;
8 ^; n6 k0 v) R$ e   }
; o. R8 {* a; X* N  while(*p==0)p++;- ~- ?, v9 c+ M4 a6 E6 Z
    printf("The last one is NO:%d\n",*p);, {7 V. B2 T! ^' ]) m1 i& R( E
     getch();
9 s" Q2 @6 s" S- Z/ m1 }3 h, B7 k! P, s# N4 A: O
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
- X: J( \4 {$ N! B, m# N$ [7 Dnamespace 又费马达又费电) W& ~5 K4 _& j; g9 Q
{
9 @8 B/ x5 j% {    class Program4 Y" y7 u" m, i) R& f
    {" h) f0 I. ^  o7 A  H- D
        static void Main(string[] args)
. q) a: v6 W  Z. h        {' b2 A5 J$ x" }5 Q6 e) x
            int m, n;. ]* t! b2 j# ^" f
            Console.WriteLine("请输入数组长度");
% R+ k0 x. Y2 {! j  ?% B3 O            m = int.Parse(Console.ReadLine());//m为数组的大小
, D2 x; H0 ^- U! x$ C            Console.WriteLine("请输入要截取数字的大小");) e7 B( g. K1 ~( [$ w0 g( h
            n = int.Parse(Console.ReadLine());
2 f2 x( ]6 A6 u( u8 d0 P            int [] numw=new int
& A7 o' g7 @. g+ q
- k7 Z4 i/ |2 |&shy;&shy;&shy;;6 t0 f# N3 k0 j
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
* O: T" u  i# i& R            {7 F6 W& y  r8 ~' w$ r. z: n: `
                numw[j - 1] = j;
: E5 ~- T& z% o" a. g            }2 g+ d3 E# I7 O# f/ t9 ]
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
$ Y$ [  x% `' h2 L6 ^: j/ G2 z            while (d != m - 1)
6 V/ e, x& C, A- ^( B* C: {            {
) J% }0 l, W* _- i/ _& D                if (i == m && d != m - 1)
0 e! |8 `  e: k                {
- C' W7 g& E' B- f7 y( O                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!  R$ {0 G) m7 L
                    continue;% `) C* R  W: C4 T7 [: y4 O/ S
                }* H, [3 k+ u/ k4 ]9 a
                else! |) |& n$ b/ }3 J9 h
                {
$ }5 }0 K9 A. M$ ^                    if (numw[i] != 0)9 g* }( ^4 o7 I3 p1 z
                    {8 C9 K* ~/ B+ o$ T8 F
                        i++;0 U( S% o. L" d, T+ }$ i
                        k++;
- a% U7 T% X7 K                        if (k == n)+ E0 Y' ^* m0 m& Z
                        {
0 c) b9 L2 Q! b6 t                            numw[i - 1] = 0;//把在n位置数组元素的值改变了. t2 P+ v6 y7 V9 o
                            k = 0;
" H+ T7 I9 q& p              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1' o2 N# d7 T, ~* _2 w9 P/ i
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
5 @  Z$ `0 G- L# Y& o9 P7 ?                        }
0 l8 P3 J6 n7 T! c' z                        else//输出暂时还没有改变数组元素的值. ]8 z; S! u9 B. `, G$ X# H
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
0 y# ~9 C* r5 y# {                    }( W! }' |9 H( l; m7 g& T# ?, g" X
                    else. Q" ?- p1 d) z
                        i++;//数组元素为0,直接跳过,不计数。。。1 j* Z/ D  g4 F0 k% O  S8 O
                }; K/ `7 I) z3 |, x9 Y7 b/ V
  N& l" U, U  W
- z3 Z# \7 N7 z. p7 O
            }//结束while循环6 @1 F2 D" z9 q. o  t) W* v; {
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦9 P' J8 c$ r1 D( H4 C
           
! ]- Q' {$ t( V) e6 z                if (numw[i] != 0)) Z+ d, g# f8 b& h
                    Console.WriteLine(numw[i]);4 x# Y: H: o6 \; l+ \/ g5 [
           7 G$ W9 F1 t1 M4 E5 b
            Console.ReadLine();$ f7 n; L2 Q% X' O
        }) r* X. L) O7 B2 m1 P
    }# N. M& q( e% ]& q# g! i1 X8 t
}( x" Z2 `; U$ `
小甲鱼最新课程 -> 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-4-20 19:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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