鱼C论坛

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

猴子问题

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

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

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

x
大家好!, E$ d- ]: _! G2 d; ^
这几天我在忙着编一个问题,我用了一种方法编出来!
, m0 s! h5 U$ D, y但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
# j0 i+ f; J; R; F( [, {注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 & d: h% E7 q: B* p' T. v$ U& o% ?

9 x7 [' x$ w) X5 u1 S& p; g  e) H/ x  G+ t/ U; @: F4 ~
                            题目
' S) Z$ e, F: [4 Z7 t; v# P山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
0 T0 C. w. R- l+ V+ P1 W; y第一种方法:利用循环链表% S" K8 t+ Z+ G$ ]/ _: e, ?
#include<stdio.h>
4 j' Y, J6 k0 ~- ]7 B; @% G#include<malloc.h>
5 i& \; I$ U& `; R3 q: Q' |0 `. a6 E#define M 8            //共有8只猴子
, ]; ]* G: Z; s0 D3 B, C$ p5 q#define N 3            //数到3只时退出第三只
) V* X. A& H! g$ x5 Htypedef struct monkey6 i0 G- Z2 y1 Y  u$ F
{int number;
: K: z+ d- p7 L: k) K7 Sint flag;
4 C/ ]6 C4 O% ]* ]struct monkey* next;7 k6 e4 P8 Z8 _
}MONKEY;
1 x8 ~6 K9 D5 D) ~main()5 p& G) e, _8 G5 R, R9 p7 [
{ MONKEY *head=NULL,*p,*s;
( p) I& U0 t' }& y) G0 s+ G  int i,sum=0,count=0;# X3 B2 P6 J  _( B7 l
  clrscr();              //清屏
* }. U) n) n; K. m( f+ y7 b4 i  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存# X2 e8 i5 z4 y4 o% s
  p->number=1;p->flag=1;
! L, |4 q0 \. x3 y9 f) L6 u  p->next=head;
0 C. |. A( \+ [  head=p;) |' H0 z( f" s1 ~, v$ u
  for(i=2;i<=M;i++)- p* _2 A& r8 S5 \, f
    { s=(MONKEY *)malloc(sizeof(MONKEY));" S; ^  n( a; `1 Z9 }
     s->number=i;s->flag=1;
9 f+ n8 J; |' I* C7 j     s->next=head;8 l8 M1 H% l8 t3 q
     p->next=s;p=p->next;: \% A/ h2 |, D  u" c5 O4 }
    }
- V2 c" Q$ q) W    p=head;
" n  p% l1 a7 i   for(;;)
; G2 j! b6 o9 U4 n4 F3 j    {if(p->flag==1)
- l, S& J6 X$ e. @+ f8 J       count++;$ R2 s- [3 C) L" N
     if(count==N)! o3 L6 A+ M5 v( P! C: C
        {p->flag=0;
9 B) J% H' {/ Y6 L! Q         count=0;6 S4 \' W9 Q$ o! L# ^# Z/ Y0 W
         sum++;}3 B0 r: F6 i! f4 k, q4 H+ Q, ], o
     if(sum==M-1)
* n" p) `! e% E8 u& x        break;8 f* F  f- G& `! R  b1 y
     p=p->next;& w, [8 U3 o  A1 N& C
    }6 t# S5 r* D* A# C7 i
    p=
6 t) Y- b/ c0 X8 c' n    head;3 y, c2 Z4 z! T, Z+ y) F7 l! d
    for(i=1;i<=M;i++)( g2 T  [, z9 L7 {& L0 g
    { if(p->flag==1)
* {0 d3 \2 u+ l4 w        printf("\t%d",p->number);
8 B$ K) W; ^2 K8 t1 f! ]8 L1 P      p=p->next;  i0 l. O! P$ c7 S! X
    }% G! p; S. a; D: U! v
. z6 z3 c( v; A% C, o/ u9 |

" B5 I2 E6 ~- M; W% |& w+ S" p- w  D+ u- i1 y" @0 u: C
}

' ~! C9 |4 t, @( o' `& _$ \第二种方法:数组
1 m+ ?7 Q4 q0 c7 F#include<stdio.h>6 t7 R9 y- z0 E
#define M 8
8 o9 ^. L3 O0 f5 V6 U, Sstruct monkey, q- M" S, S2 f9 B- I1 z
{int number;
+ R, M1 n- w/ |4 ]8 s& l6 d: @int nextp;
( U( V% n5 ]* |+ T8 R6 o}link[M+1];
4 e! K7 R2 {, p( i1 D& I1 Q$ ~( v, R3 m( e& }
void main()% A/ A1 V# t* D, x
{int i,count,h;
! M4 ~8 H+ t5 ?for(i=1;i<=M;i++)
6 S* Y' |( P! y4 C, Q{  if(i==M)
8 q! Y' X7 A. h   link[i].nextp=1;# Z9 M3 a' l4 t+ e/ Z$ W
   else
8 V7 Y' v) S# U0 O0 k   link[i].nextp=i+1;, d1 F4 Y. a9 d1 Z. `# l. _' ?+ ^
  link[i].number=i;
& g# r' Z+ o  s* k- o}
( p$ h& J( C7 M0 V( f) [$ `: Sprintf("\n");
# ~8 n4 M' u, J4 h2 {count=0;4 J$ k/ |+ S& \5 n& P1 v4 G) H: e. t
h=M;
2 g0 b  R( d% B1 A! l: X, X3 |printf("依次退出的猴子: \n");
8 I9 T( ]) Z% _! y$ X3 Hwhile(count<M-1)7 [0 P9 q& X8 ~; ^
{i=0;
8 n0 Q; ^) j1 S( k6 c; jwhile(i!=3)/ B7 M6 \9 y$ u, \$ }9 [* t0 a
{ h=link[h].nextp;
; }& d: M7 h3 l; q* W! W   if(link[h].number)
+ T' n; V/ J, U! c8 U     i++;}+ o9 \5 E4 Z9 {

4 B, N5 N* n7 z  E& {! Oprintf("%4d",link[h].number);
# a9 ?% y& m1 b9 q4 ~6 x$ h. ]: Clink[h].number=0;
3 W2 _0 D$ n! |' U* }. Jcount++;' v" q" u3 W6 s. C4 P3 D. X
}  f4 A1 C0 ~! v9 y  |5 V) U- x' D
- ]* Z: B& b' \; [% d' q
printf("\n大王是:");
; ~  e& }: |% I  K* x) k# c- `: Y  for(i=1;i<=M;i++)
# E6 I6 p  R" f3 ]4 y4 s  if(link[i].number)4 j% p  A# i6 C7 L& C/ p! X8 [
    printf("%3d\n",link[i].number);: k- W1 x/ M. U) g- c
- O4 T; m" v6 y4 D# c

+ |# _6 e# D% Q, ?5 o1 N. K}

/ G  O1 F* p+ ^4 ?第三种是普通方法for循环
) u7 C6 j; _( ]
#include<stdio.h>
& u9 L8 Z" \- y  H6 f6 L3 X' Fvoid main()8 d" m6 V- x2 k2 z: v
{ int i,k,m,n,num[50],q,*p;) b" T' K+ m/ [' h
    clrscr();1 C7 \+ v7 [) ]7 z+ E9 A
   printf("input number of person: n=");
3 y. x5 ^6 l0 }    scanf("%d",&n);8 F- ^7 \( e+ q7 T2 F. X
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 ?4 B4 w5 |- W  A/ k    scanf("%d",&q);% z: f. T# A) A  C) o
   p=num;
, Y' c9 p$ U& \9 F1 U  for(i=0;i<n;i++)# @6 A1 L6 m& F+ Z
    *(p+i)=i+1;
0 g3 O# S2 H8 W2 g1 f/ O1 L5 x( k   i=0;
9 D/ h, k! S% q6 K9 m   k=0;# s+ J  |  F9 J% |$ U
   m=0;
+ B; x5 [  n& Y: N$ V, M; y9 ?9 G; i  while(m<n-1)* P) {8 K8 k  V9 Q! m, n# }, r
   {if(*(p+i)!=0) k++;( x% b# s- v5 e
     if(k==q)5 B; i0 U' U' ?0 p' F' ~$ K7 K
      { *(p+i)=0;* C' {0 ^) ^: ?
        k=0;7 p5 D: W' V; k/ n9 }
        m++;
6 k2 r" s. D5 ?- T$ o      }
  E- `7 J) |8 u7 O8 E8 |    i++;
+ L/ r  \4 n1 f8 D, {    if(i==n)i=0;
$ f% G' H! h) ?/ U; n   }4 H& s; D3 e& R5 }' o3 E- D6 j4 R4 _
  while(*p==0)p++;
; {0 q9 A3 U& B    printf("The last one is NO:%d\n",*p);: I, H0 u3 B4 b* v/ t% m
     getch();" t: p! N# s  P
5 x/ `+ @+ ^0 x8 h
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
; a7 H2 c0 }5 Y0 v# b6 z: b/ Mnamespace 又费马达又费电
. ~- S- n! X# I  @3 O{- e  y3 W  M- h; @* o/ }: y
    class Program
, Y* d+ `. L: l& r( p7 _    {8 l. M/ [* t2 N9 a
        static void Main(string[] args)$ z# `- D! P3 K& g' g
        {  q& d& W1 }! O8 T
            int m, n;7 H5 m% p& }; {# Y6 u& `& T, J
            Console.WriteLine("请输入数组长度");
6 V. o0 t. K6 x8 A            m = int.Parse(Console.ReadLine());//m为数组的大小( [( j& o  [! }' @' Q1 z
            Console.WriteLine("请输入要截取数字的大小");0 k7 z  ]9 W3 r, N2 S
            n = int.Parse(Console.ReadLine());2 a7 `% [5 K  Z) N8 d
            int [] numw=new int- r$ E; s" v! @/ G+ b
. n2 E8 ^8 T! d) Q+ f. _/ B
&shy;&shy;&shy;;6 E0 y: T" X1 ^% ], l
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
  Q8 W! y7 [( U% o2 |" m" Y+ g+ m            {
) Z& ]* f9 c# l9 F+ ?) p) u                numw[j - 1] = j;
# ]  T6 F# x) u            }
9 Z, ~/ j( b. @. q            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
. T0 g) ~6 N1 B5 [" I            while (d != m - 1)
* i7 S9 p! P/ V% v6 u/ e# _7 f            {
* j  S# s& f) x* o                if (i == m && d != m - 1)% g0 Y6 }6 a% t9 v3 a0 X2 n; c
                {$ F/ b4 y8 A) c9 D0 h0 Y
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
, ]+ w4 C( o, Q+ {" {7 S+ f+ k                    continue;
( N3 x3 v, w3 i. P" W, _: k                }+ G3 ~- Y3 m$ P$ _# ]- u
                else
+ \2 ]' q7 C% Q/ v1 J( s7 L                {
- S+ k1 R8 G2 `/ G7 {" P% V                    if (numw[i] != 0)
4 v+ F, Z/ N: V7 B  X2 u. E% ^) i                    {
" A" s% G# I% r/ R  H                        i++;
6 G" M! S, X! `5 U                        k++;
# F- Z+ O& b$ S2 U0 d6 }6 j                        if (k == n)
7 P& H# w9 l1 |) t                        {
1 {, A. p! ?0 V1 G* g2 R5 p                            numw[i - 1] = 0;//把在n位置数组元素的值改变了- E3 R. [, f- k+ _/ ]+ f" Y) Z
                            k = 0;: Z: i, L4 M  W" V3 D* v5 ]8 z& ~8 z" U
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
. ?/ b  ?. T3 H- `* b* ~                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
7 ~  J; U, D% _) U: u# a) G! Z                        }, P; q# D: d4 N. _
                        else//输出暂时还没有改变数组元素的值' j9 L8 Q% [0 V. W3 R9 f8 N. @1 |
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
7 m; w0 h: o- o" L9 L                    }' ~9 ~, }6 R3 |
                    else
+ s2 A) h; B. X: ~: X                        i++;//数组元素为0,直接跳过,不计数。。。
0 p5 l$ Q( P8 w% z, h                }
" a, u9 p/ `5 k1 U0 M
8 E2 i6 c' X; {5 |1 B% x. F! C$ P1 f* A9 t
            }//结束while循环
& n. ?) ^1 w5 ]5 f, H% o            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
% C& u% g5 W2 R1 {; a% Q           
- o5 r, n  S! V3 Z                if (numw[i] != 0)
& v# a. Z, }! @5 o$ k                    Console.WriteLine(numw[i]);
- x. Y/ x/ T# e           
4 C$ E4 Q/ d9 D            Console.ReadLine();* P2 R% ?2 W0 P4 u0 k+ r
        }( X; {/ P# i5 l
    }
" |* T* [' N$ V5 P. _4 ?9 V. j}; S8 |' S: d; ~
小甲鱼最新课程 -> 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-7-19 07:44

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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