鱼C论坛

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

猴子问题

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

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

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

x
大家好!
, e& M; \3 Q$ u$ v; z这几天我在忙着编一个问题,我用了一种方法编出来!& _3 M; E3 Z+ [0 z- R
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
$ I" y4 k( m: j5 E9 n注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 % c0 Y) c; K- X" @# ]6 U, b- s
, v9 H7 X, G5 ~/ h
) O. C1 V$ M4 h9 a
                            题目6 @. y' c; ?* `% S) k* X2 x1 m  v
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
, E8 D& [$ u. q3 ?2 H) Y第一种方法:利用循环链表- u1 L* I3 a* H
#include<stdio.h>; l) K' B; g# M/ K" B
#include<malloc.h>
+ x5 S3 G, {- b9 N" v" c6 o- K. v#define M 8            //共有8只猴子
) q7 A: {- v" E7 L# W# @) J# v; M#define N 3            //数到3只时退出第三只
  y+ _# |8 Z/ V0 j  O6 e0 ]typedef struct monkey/ E' W1 ~3 K, q- w- n/ `/ \9 A
{int number;
8 R, X' {: |! e9 mint flag;
& Y" t# A# I6 s! e$ ]. Tstruct monkey* next;* m, ]* x8 ?$ u0 H+ I
}MONKEY;/ I% M5 u) G# F( a' A( z2 V7 T
main()
7 F  y$ t- s+ |$ x8 d{ MONKEY *head=NULL,*p,*s;
& z2 {1 F9 M2 {1 J  int i,sum=0,count=0;
7 l- A% E- @9 y. P% M  clrscr();              //清屏
# ?- {% n6 u3 j- W$ t/ \  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
! D4 q. E1 H# O5 {; ]  n) I! a3 k  p->number=1;p->flag=1;
7 Q7 L3 F. M3 h& V& v# e  p->next=head;
" `$ w% o- g' v9 a  head=p;
8 F$ ^  @8 z$ \; r4 K) G$ e; i3 V. {  for(i=2;i<=M;i++)8 x" t8 @8 [4 p( O- h% h8 a
    { s=(MONKEY *)malloc(sizeof(MONKEY));
* M0 Y( C9 S0 ]2 ]7 m6 M) n     s->number=i;s->flag=1;1 S6 f$ m9 ~7 p' ], w
     s->next=head;# `) a  l% j  ?5 L% [6 v
     p->next=s;p=p->next;( u' |$ r7 k' K, r% o( P4 {
    }4 I/ m4 A. z; L- a
    p=head;
. r! i3 Y6 M  n) R' N   for(;;)
. R& b3 c5 l# M, D* ^    {if(p->flag==1)
+ t+ ?" l' p9 i  e$ m2 w2 ~       count++;
6 _# u( `4 x' M3 q8 U6 b5 I8 D     if(count==N)
  ?, m: O& C: _        {p->flag=0;
- \9 _6 y/ k6 w         count=0;
8 O* d1 }( a& V5 f  i; j% p         sum++;}
1 P6 p4 N" M0 P( y4 P) q) H     if(sum==M-1)
* i  M5 z2 G, R6 r        break;
6 l+ G( @' {7 O$ l6 F4 x     p=p->next;
# l! P3 R+ Z8 J* N  X/ B2 \6 H    }- D: R: n; f& R7 F3 _! l3 K
    p=
4 N$ Q8 u8 w, p2 M/ x2 L" m    head;+ Q9 Z: ]( }' V
    for(i=1;i<=M;i++)$ F7 ~- _2 y3 U3 n
    { if(p->flag==1)6 d) L8 J5 _* \' l% h( G
        printf("\t%d",p->number);2 T7 v/ \" @, T7 J' h
      p=p->next;5 V- \5 y- i6 `/ s) }- Z" u
    }) N- m9 m7 W( {' Y

7 q  ]  s) m* _$ \- v7 X: t: P; ~3 l/ T" O& U

& I' M+ E' `( i1 J/ r* d+ |0 g}

& x9 k- X# [7 [6 ^2 e. [第二种方法:数组
# U  J  F+ m" M7 r) p! I( L#include<stdio.h>) X) p1 v7 ?% [
#define M 85 f0 h+ h" @: E% \6 {/ B/ ]/ s
struct monkey
+ [+ i* f9 q$ }- |* r{int number;
" h7 R8 s) ]# O4 F. ?+ l4 a; L# [int nextp;
$ Z) @" C% ?" c}link[M+1];
+ Z- m) p2 i" E: F" j+ C( D& \; J& w
5 b! x8 d: @1 i& z" b# r: i& U# |void main()2 {/ K. d+ }; H4 |( c) x9 I* H2 b: P
{int i,count,h;$ H) c4 i8 g- V+ z9 w8 K9 ]& I" K
for(i=1;i<=M;i++)+ g  ]. U  p. K
{  if(i==M)
. a9 M4 U9 q  i6 Q2 [   link[i].nextp=1;4 O" s8 V: v- }1 ?3 E5 E5 s6 N
   else7 |0 R& O2 a4 n0 w4 L' L
   link[i].nextp=i+1;9 @, n0 Q" x" \0 @/ W& y+ l
  link[i].number=i;( F1 _5 s0 w0 d3 L+ `3 d4 \; J$ ^
}
. D4 D  s" b7 G  ]% {printf("\n");
# d( M6 b5 Q; y$ e. J1 c. qcount=0;* d5 k/ W7 }# y+ u7 L! O2 H
h=M;; {  d/ ~/ r2 C/ k" H
printf("依次退出的猴子: \n");
0 I' b0 l0 [) R: r, Z) N  o& w- dwhile(count<M-1)2 o5 |  q# l+ m& l& z* I
{i=0;
, i5 F; k$ z0 {* j4 Pwhile(i!=3)
0 Y  C( s; r. x! k2 }- D1 g2 b{ h=link[h].nextp;% U( C/ \$ j( ~0 k6 j5 s
   if(link[h].number)+ i& a8 F& R1 i# V! c
     i++;}; B' ~+ `4 R$ @5 l1 Z

  C! F. c  g; v# fprintf("%4d",link[h].number);- |# N' D- r6 k( a- {* y
link[h].number=0;
8 l) N9 T3 k2 l; [1 bcount++;
% T; [) T/ r% _  n' Y1 Z}
! N6 c8 {" m0 P4 G
3 Y) ]2 g) i. C! Qprintf("\n大王是:");- s+ m1 u6 j& }! I
  for(i=1;i<=M;i++)
$ ]' {, t2 _4 M: C* s1 k1 j9 c7 {- a! o  if(link[i].number)
4 u2 I( Z1 E2 }8 ~    printf("%3d\n",link[i].number);* J4 b! V4 ?" U5 ^: t2 \

& R+ t0 J  j' f7 H" X4 }, _; c7 |
}
4 _) }& a& q1 @" c
第三种是普通方法for循环

% V' p; X2 f6 s% M: }- x+ C: D! g#include<stdio.h>" C, _6 A5 D% ]
void main()$ a( F% t$ V4 v8 E
{ int i,k,m,n,num[50],q,*p;* K: L1 q! l( C& q
    clrscr();4 X( Q+ V& S2 M" {" ^: E: \
   printf("input number of person: n=");  y* @3 u, m" r5 O% U
    scanf("%d",&n);
3 |( y9 u9 j. X" Gprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只$ H7 o8 T; m( `/ P; Z" n& j1 ~
    scanf("%d",&q);
4 I) m9 J3 s8 o* |   p=num;
' N5 L+ G9 Q9 S  for(i=0;i<n;i++)
3 U) i% k& i7 \    *(p+i)=i+1;/ G6 l" {: G) N+ ?* Z
   i=0;
- T( e( k8 l% R( C( R   k=0;- [& p  H3 R6 ?1 Q
   m=0;
3 }) f. x5 N$ I( Y  while(m<n-1)
, W9 X$ N+ i, [' B! Z2 ~   {if(*(p+i)!=0) k++;& w' J2 g2 G5 T* U. A
     if(k==q)( u2 ?! w, h! Y* i% ]
      { *(p+i)=0;
& `0 Y; }0 B. l8 H        k=0;
; ^& I- ?3 v! \- k' q) l- u        m++;8 d; `( F( S' {0 X6 h( ~
      }
9 ^) I& Z' y# y0 [7 l    i++;
! B6 Y' T" U+ f    if(i==n)i=0;, J5 x* \8 f' p9 @$ I
   }6 v! s2 z7 K+ W( z: j3 u
  while(*p==0)p++;
1 t; Z  y9 C8 X; \% O, ]    printf("The last one is NO:%d\n",*p);
; v+ O4 J/ o1 i0 ~3 I: F     getch();0 A4 a2 v1 d& h
' \2 ^0 ]0 d' H% B! R
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
- ]5 o0 x, {% W+ C0 Z8 s8 Dnamespace 又费马达又费电; i3 q2 }3 {# r  X" K+ e
{
7 w; P5 W4 i0 S6 d: a% i9 S. D# H; D5 ?    class Program/ S) R' e) [! t! E6 o! e$ B
    {
3 y- U1 @- i0 K- w; E8 J        static void Main(string[] args); _/ V! O' D& e  l
        {8 b+ R8 `3 c, B
            int m, n;  C0 m* d. U+ b+ L0 x
            Console.WriteLine("请输入数组长度");
! D& r7 H: R; V            m = int.Parse(Console.ReadLine());//m为数组的大小
, r+ X! s* k0 o( }( G6 ?! k, b1 Q' w            Console.WriteLine("请输入要截取数字的大小");
$ S, z  Q5 m  X& \7 ]9 j% Q4 H- k            n = int.Parse(Console.ReadLine());9 H; S5 g  i9 v! S' \; @
            int [] numw=new int
& y/ g' ^9 u* t& U5 p& y/ |+ z7 j4 t9 _% q& v; m4 J
&shy;&shy;&shy;;$ F$ |  V/ \" y0 F! }2 r
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
' u: c5 a  L+ E7 Z$ U            {
6 _9 C3 S) s4 [& J" {! s% {                numw[j - 1] = j;- M1 ^. T* r: n4 Z( ]/ s
            }
8 X; n4 C7 h0 _* `# `8 F% H            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
) m& A  o; K, f: K& a$ Y" h            while (d != m - 1)
8 m. b! L$ f) l            {
2 J1 j) K" m, t5 D7 ]' P: L0 t                if (i == m && d != m - 1)9 `& ^- z$ x6 X0 N" p
                {: l) J) @8 x- D6 y$ g
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!/ e; }* A0 Z4 w. z& {
                    continue;* e8 V& u8 M& H+ J) O$ M
                }, Z  q9 p) q; v' z
                else
1 D& @! {3 M! F                {
9 b# `$ ]4 {  N  ?- O                    if (numw[i] != 0)7 R" Q) ?& ]# Y: S/ F5 \& z
                    {4 k8 W, o9 p1 s* i" \: ]7 v4 [
                        i++;5 A! V3 M$ G4 H! I* F
                        k++;
+ B) S5 |& a4 O0 Q7 I. F                        if (k == n)
. L) b8 p- k, I8 e( E( y                        {3 f1 M6 A% o9 j
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
$ ~8 s! \6 ~: z7 B                            k = 0;7 I3 {  L% b# X" N; Q
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
% ?  x& G; s5 p7 N- n# Q% |                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);- H. m. G0 k- o, I5 ?) \2 {
                        }9 ^3 n, |9 G! R/ y
                        else//输出暂时还没有改变数组元素的值
# ?, p9 A2 @' J2 N% v                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);7 N  b7 Y5 S" M3 j0 u
                    }" a2 z# ^% H! m- t
                    else/ E7 D: b  V9 j1 W
                        i++;//数组元素为0,直接跳过,不计数。。。
3 ^! L% L  p, j7 K% o& a; q                }
* G, E( u. ^" h3 ~8 U& I8 c$ |
2 @8 e8 X" x1 [: P7 ]# `% E: }3 d: ~' l; |, i
            }//结束while循环
# p7 g! V4 K; q1 c1 f: f; B            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
: e3 L) x6 h. Y           
5 O; l% d: `0 R9 i1 ?                if (numw[i] != 0)  x6 J' R# M/ `' @, g( y3 f/ S$ G
                    Console.WriteLine(numw[i]);" ?- o' a( p2 |8 w
           
1 F7 D; Y" R" y+ @; V            Console.ReadLine();
2 v$ }' q: M" t' e        }) U- a( l% S4 w" Y; P' ?
    }
6 O7 `- ~; j* V$ F6 _2 n) F/ x" q! O0 Q# w}
6 M1 E7 F' t$ x7 }# R
小甲鱼最新课程 -> 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-2 03:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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