鱼C论坛

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

猴子问题

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

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

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

x
大家好!
( ?6 U4 y! B" F2 p" V4 m1 K0 r9 N这几天我在忙着编一个问题,我用了一种方法编出来!
  ~& Z0 z" ]* [. p# v7 p但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!& Q6 L& S+ T, b- h& d  S1 C& G+ J) ~& O
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
" D+ L5 Q# l' j: z) e
" @+ t8 K4 n" F0 f2 r2 L; V0 C9 j* v7 S0 M! h0 g" A& c7 x
                            题目
; h) n3 b8 J7 y3 ^- I& y# `山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。. j# [: D% E4 f! y
第一种方法:利用循环链表) K) S4 J" l: o* K9 S
#include<stdio.h>) I  c* @7 X. ~' S& p
#include<malloc.h># [* L( D& O2 P% m/ l8 T8 s
#define M 8            //共有8只猴子2 M" |  ?& q5 ~
#define N 3            //数到3只时退出第三只- U7 x0 T% S5 g) R
typedef struct monkey
! N2 [4 }$ |# U; R{int number;
4 X; {' A$ N4 z' g# s1 G! x6 gint flag;! b1 O+ w7 I% Z% p$ i
struct monkey* next;; M2 p$ k0 w$ g& H8 o
}MONKEY;
& v2 F) o. f' T; U+ d! emain()8 _6 R& D$ N7 V
{ MONKEY *head=NULL,*p,*s;) z! t& ^2 b1 R- b% h# p/ ^# P6 ~
  int i,sum=0,count=0;
! W7 ~, z. ~% p! T1 M  clrscr();              //清屏: L5 R7 k% s+ y4 |, W
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存, @+ U: T# L# s5 m4 C% I
  p->number=1;p->flag=1;2 X4 a/ }' v; {3 ?5 `# T
  p->next=head;
" Q& D3 e( c3 S- d  head=p;4 l1 Y0 `+ x* @2 X0 X
  for(i=2;i<=M;i++)
8 m4 y$ M7 }7 s) y6 j8 J, p    { s=(MONKEY *)malloc(sizeof(MONKEY));
9 S  G0 r. m7 u( |+ ^6 o, j7 ]     s->number=i;s->flag=1;
- _) e: Q8 m, H) S( T     s->next=head;/ V, s. ~' p' Q- x6 ?  ~
     p->next=s;p=p->next;5 c! f& k+ i" D( E  a  S3 R& s3 W" h
    }- Z" h8 [4 T; J9 D7 S
    p=head;' S1 T3 ~. P" `, ^1 [' J: k
   for(;;)
- g0 R* _0 a2 x6 S, K    {if(p->flag==1)
/ i, }' y- Z* _! }; n       count++;+ {' _* W$ a( [: |4 a' z2 b
     if(count==N)# R$ B# n. O# F; V- v3 ?7 ?; j
        {p->flag=0;
+ I4 s1 @7 N# K: T7 u' e! m* |         count=0;
- Z2 e+ Y- v, Z) z7 O4 W         sum++;}
+ u9 P( _4 x+ P     if(sum==M-1); ]7 f7 Y1 T5 n7 O* \
        break;$ Y2 W0 e1 Z5 O, C/ _6 r" T( D
     p=p->next;
7 V+ z: R5 l5 Y+ _) s4 |    }
# E6 a% U7 [% s$ S    p=- _$ h9 b0 O0 o) m7 W
    head;
0 r+ `" J) j/ o* m4 |1 I    for(i=1;i<=M;i++)
0 A8 z" v) c# J% u    { if(p->flag==1)/ \, l( p. J+ n4 c; a3 t* X& p
        printf("\t%d",p->number);& R& Q9 v" ?5 d! V
      p=p->next;! N0 r+ A3 q4 L5 p
    }
2 R, c( u; ?: U$ J. Y0 O' t! v- h6 [( R# A
: @7 S2 J) `# V9 G6 ?/ ]. m) h
9 D6 S7 |6 E2 k" F8 `9 U
}

8 u4 h5 d) f( G4 I第二种方法:数组
3 S* }* M+ [: T$ [* j+ X& u#include<stdio.h>
) F, [1 {) }# v% e1 ]#define M 8
' b  g; T' z; U  bstruct monkey* P$ }! m( ]9 n; T6 P1 x9 d
{int number;
& }" C; U# T2 sint nextp;
7 R8 |8 f7 j! H# m}link[M+1];
( l; z, \+ [* r) |( o0 ]( g2 R/ q& J% P- j; E, @5 \
void main()
6 h" ]" R1 h6 V$ X- z{int i,count,h;1 Y, W- C1 U: C$ A' l0 y' b" T
for(i=1;i<=M;i++)
+ k2 m+ z. U2 t1 F7 v7 k{  if(i==M)
) `, s" s- C& x3 P! ~8 R   link[i].nextp=1;; X$ a$ J3 z* `/ |; u2 i
   else7 V: k8 Q+ Z! o% c) O0 N
   link[i].nextp=i+1;9 p* G* I4 g: X- f% @
  link[i].number=i;
( N& t' m7 M4 y" \" h, L7 I  h}" j# a# ~+ l3 h2 }& S/ A
printf("\n");
5 G, B$ y8 }7 J1 i' ncount=0;5 S' {/ d' `8 b+ P! {( V; a) t8 R
h=M;; U' D* ~( x; W& m
printf("依次退出的猴子: \n");
7 G( Q2 S, w( B" {7 c( P7 R( vwhile(count<M-1). d8 b  z2 g" @3 Z* c+ W. Q  T
{i=0;9 \% A5 c# Z! s2 v1 p
while(i!=3)5 R& i9 D$ O  F. A9 X8 J! b. j0 Z9 ?
{ h=link[h].nextp;
5 [1 V6 i, L* I0 X) C   if(link[h].number)
% x- \6 @5 [/ a  V9 R% Y     i++;}
! j8 x2 q# a$ F$ V) g  {" ~
1 I& N: |, i, c" b( u6 [printf("%4d",link[h].number);
% b) f/ x. W3 |: F5 alink[h].number=0;3 M8 b' a" Q# k
count++;1 ?" Z6 J7 Z+ `4 p- m; x
}
2 o- K: t" O  H3 {0 Q% o
7 V3 r1 E+ y& ^printf("\n大王是:");
0 G# c& U7 o$ C  for(i=1;i<=M;i++)7 e) j" ]# N1 q5 ?7 f
  if(link[i].number)
. X6 O- v! D. u% Z& F    printf("%3d\n",link[i].number);4 J% F2 `4 W1 B0 o9 M$ Q5 b

' K! e. L# e( w* {2 o6 U0 \6 a# N$ e# g. a8 ~
}
5 e$ c/ f3 O  }" A. `
第三种是普通方法for循环
1 Q  ~' t" h$ i1 ^
#include<stdio.h>
; p& \$ L) D# D2 c0 bvoid main()
1 `9 _+ q: [8 M/ j4 N6 |/ T, k{ int i,k,m,n,num[50],q,*p;# @: }3 e. ]+ j* Y5 U, [
    clrscr();* W' |8 t# v+ }/ c3 i
   printf("input number of person: n=");. J" Q2 Z  t) F, ^! e
    scanf("%d",&n);# F+ L! M$ `8 M, O  b
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
& n' H3 ?7 u; D: u, M* O' [% O9 o. f    scanf("%d",&q);
0 x# |+ [4 L$ y, H& l7 Q   p=num;
# f. e& s. H0 |9 p. Q2 s" \  for(i=0;i<n;i++)
  b: n9 `) x0 E7 o$ p    *(p+i)=i+1;# [1 C+ y& L+ O6 L
   i=0;+ g8 u- ~' o! K' @9 {7 u& ?
   k=0;5 `1 D% J% H4 G) d! S
   m=0;) N. k1 K0 j) i
  while(m<n-1)5 H, Z* r6 }- q2 ^
   {if(*(p+i)!=0) k++;
$ V  v9 C( I8 _% `$ n5 h     if(k==q), O+ H: ?! U- A5 Z4 h( ]0 ]
      { *(p+i)=0;
5 P  a. C' l. w4 {        k=0;
7 p% S% P# ^, B2 A        m++;: S" i1 U2 E2 i5 `4 J
      }9 k! W& A+ R3 u4 Z8 v) p" t: w( f
    i++;. Z* [/ l' v, d9 M. w
    if(i==n)i=0;
. S1 D: E; J, u' E, @   }) W. h: G1 X+ {4 p" r- Y* Y
  while(*p==0)p++;
9 N4 F' r4 w6 U2 A6 w    printf("The last one is NO:%d\n",*p);
  k7 [$ n: q4 Q% ^! _$ s; w     getch();
. T6 M& A" j9 D! r! E+ I% \
& L5 M+ {1 K1 w$ ]9 k& l}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
% P( R' M8 D; P. c; @namespace 又费马达又费电7 i. J& q0 f9 G8 {7 s- a
{
' R' b4 \; [5 Q( z+ w8 H: r    class Program& J$ S, j  U! e. T
    {
- b7 S% X8 D9 |        static void Main(string[] args)
3 I& w& T( |+ j" y5 ]        {
& |- r& D8 ^; L* y, N            int m, n;( _- p1 f5 D7 }  |# a
            Console.WriteLine("请输入数组长度");  }% Y! n; F! J3 L
            m = int.Parse(Console.ReadLine());//m为数组的大小; }3 o8 R) b# I6 G
            Console.WriteLine("请输入要截取数字的大小");
2 {3 N! B: _/ i5 s            n = int.Parse(Console.ReadLine());
3 E' r! Y0 y, d) Z9 }7 r5 H: P& \5 _            int [] numw=new int
3 ^( @$ n# u( @: K* H" M7 v4 o6 m& F* z4 v6 Z, i% A1 V  z0 K/ O
&shy;&shy;&shy;;; R3 H7 z8 K$ |1 T6 O8 I3 N
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
* x! E! H! G0 F            {; e1 h+ f$ M2 @. ~) c0 f
                numw[j - 1] = j;7 e. u/ C- H3 ], R0 l
            }
1 k. \, X3 ]6 q; E# m            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!: f/ |. `1 {5 f6 b
            while (d != m - 1)7 d% \2 f6 H; W- I" f. F9 p
            {9 h) Z! |$ y" A  P# z
                if (i == m && d != m - 1)
% c7 [# a6 P% D6 t# X                {
3 |2 R; v. K( ~2 o: W6 @9 p                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
* F7 {( M  ~  q4 c  ?                    continue;
7 B7 Y) h! O2 G: D& g1 r                }
% Y  O% J0 `  @- v                else" l- p; Q, d% w
                {
, l6 u% r; {* ?$ E" Y+ c2 U                    if (numw[i] != 0)
% k. {3 ^! a9 C& w1 w2 n                    {  D8 a; i4 d& b/ G& k
                        i++;- ^2 ^! s& I5 I$ O0 p4 `' O
                        k++;6 u/ ?6 x- l, W0 {
                        if (k == n)% H+ J% f* \, L$ g8 }2 p
                        {* i9 X8 r# Q) N$ U9 {3 q& }/ ^
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
! R$ N$ w6 e+ T* }. I  h2 {                            k = 0;6 D  M- `; @& D5 k% [
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
, _) a0 x( D3 o+ [% F                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 z/ R4 E5 `* |0 z; h; }" u
                        }, H" \! K6 B( @- Z& |
                        else//输出暂时还没有改变数组元素的值. v0 A- K: [7 ~: ?2 D' K
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
/ v& X; q+ \: j. [  F9 \                    }7 v; T, s3 g* O
                    else4 t/ _* s  o6 U) n4 q2 ^5 y
                        i++;//数组元素为0,直接跳过,不计数。。。. Y0 e5 \" A  S0 K6 F1 x
                }
$ K1 S* p. f) \* t) r
. H' R, O1 C* F" W! m1 N5 Y5 h3 L" f+ \8 C; f! x
            }//结束while循环% F/ b$ m& u7 P( b% z2 f6 X, j3 a4 e
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦7 P  [9 d, ~& l, F8 W5 W7 g
           3 r7 c8 ~6 ^+ O! z" F" V9 i
                if (numw[i] != 0)
9 K8 Y! ^  |- ^: U' B! V" ~& j+ ~$ Q                    Console.WriteLine(numw[i]);- G% d: a' K* W8 A/ z- L1 R# X
           . m& |0 ~4 v% z# s2 I* R( B; X
            Console.ReadLine();3 x) z, W; T$ ?7 b2 t4 v) I. ?
        }
7 g3 |- i  ^# _! n) e3 I+ L    }. @- b; d" U) y6 k, {, z
}
) ^5 v0 i7 P7 K3 ?5 Z
小甲鱼最新课程 -> 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-1-9 12:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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