鱼C论坛

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

猴子问题

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

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

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

x
大家好!
4 m3 v, @8 @* k$ ], a- J/ b; K这几天我在忙着编一个问题,我用了一种方法编出来!3 z! h5 Q0 I3 X1 }6 Z/ S% R# V
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, f: z8 q7 B# }. \
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 / @6 U# `% L3 h+ ]/ [

% w( v1 g8 y+ |& @- _$ @: J
0 j9 `0 p& g; K  M
                            题目5 D3 q' o& m. x9 f0 R$ E' P
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。/ U* C; \/ S4 c# {
第一种方法:利用循环链表
4 _& I4 N9 u/ y$ U$ k' `#include<stdio.h>0 ?2 [$ u) Z; ^; l6 s" j4 X
#include<malloc.h>/ S9 n! ]/ O. l  B! ~6 V9 {
#define M 8            //共有8只猴子  x1 q( ?6 Q, E- w& [
#define N 3            //数到3只时退出第三只
8 C6 `1 N, \- L: e0 ^/ ?4 Htypedef struct monkey
5 G; K9 h# A- M8 {7 O7 Y{int number;$ e2 b+ E" Y0 ^+ h
int flag;0 [1 z7 W$ F) ?) x
struct monkey* next;
/ b; j$ \/ T4 G, P- R/ k}MONKEY;
1 P/ e9 \) _: {  Z" ?2 Rmain()
% J8 H$ H7 j6 I; t, J! M{ MONKEY *head=NULL,*p,*s;
, t6 r9 g' m; k; i/ @  int i,sum=0,count=0;
  z1 M3 H% [: Y+ a$ j  clrscr();              //清屏
  L" n) j" l7 {6 I2 k- ]  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
- r3 B) V6 [: f8 X& M/ P" x$ x7 N9 P  p->number=1;p->flag=1;
1 F; f0 Q% y2 X1 P9 L  p->next=head;
3 ^' M' ^* {5 i' `  head=p;  T7 \7 d7 j4 B  {) p2 b: |- h
  for(i=2;i<=M;i++)1 [0 M9 p5 H* a1 }1 W. `7 ]4 U& K
    { s=(MONKEY *)malloc(sizeof(MONKEY));/ Q- s9 d4 q1 F2 p. m
     s->number=i;s->flag=1;
  g1 g: M6 {/ U: {* ~& Z$ X. z     s->next=head;
; c! s$ i! @5 O* z3 H     p->next=s;p=p->next;; ]9 ^6 l) o$ e: ~' @
    }
" o6 Y& l% T9 K6 M2 n    p=head;
3 f+ _- i8 R0 y& a   for(;;). T9 N: K# o) w" c4 G( l5 a
    {if(p->flag==1)' z$ ~1 b3 A4 e! m
       count++;
# Y  N3 y1 P, a/ }6 J$ @' ^     if(count==N)- M! D; J( p9 X( |" u
        {p->flag=0;& X& q( @: D" D! C& I( l; w( `
         count=0;" ~4 n: p, h7 @: t/ L
         sum++;}9 P) Y2 M/ n% ~2 t, c) `
     if(sum==M-1)
/ i" W* {) d3 u) h  R/ L3 m- W        break;
- }2 O+ h' ^# w0 Q     p=p->next;" E& f9 I. I9 j$ p$ ]4 e
    }
  L; z* x7 {3 G8 x0 H% Q- W    p=5 [2 }2 a+ M. o+ u! t: N2 G7 c
    head;+ o& w; B! ^, t4 `  e% F
    for(i=1;i<=M;i++)
6 `6 @8 n& f3 Q' N    { if(p->flag==1)
' S7 ]2 |& l' e# [. i        printf("\t%d",p->number);
& G: ]% K$ d' h8 g  {! m      p=p->next;
* X) D) {% w6 I5 W5 p5 o! ~    }. t4 D* |" f" D6 S/ [' \! a8 H. O
" V, G( G% F. U

4 Q! b, V9 E- a  a& Y5 t) V( T: t. f$ O3 e
}
0 N4 a6 \  A; r; c; N
第二种方法:数组; \/ G. b) t& F5 f8 L
#include<stdio.h>
( Z  O  _) a) H+ P( ]; U#define M 8
4 k; y2 g# g$ Y, Y: J9 Y4 l/ vstruct monkey, x! G" W5 l4 Y
{int number;
+ r0 K+ P  g$ W2 C! e6 e) B% lint nextp;) g8 O4 k( r9 L
}link[M+1];9 J: H$ N, h! M& k4 W! ?( v
: Z! D$ |8 E/ a
void main()
* i% _' {0 J" I3 n; a. z{int i,count,h;% Z8 a9 m$ t, W6 h' b
for(i=1;i<=M;i++)
* Z  F, S' F( F5 J* S{  if(i==M)
! o8 R- O3 M. h1 r# y/ b. m9 ]: Z7 ]   link[i].nextp=1;
2 n! N0 f$ i& U: o' H. C   else
( _. \3 p1 A, P, k   link[i].nextp=i+1;7 K4 ~9 [3 E% i0 ?
  link[i].number=i;
0 ?9 I, v& z, T1 A3 U! [}
, V! i. n6 Y0 U4 ~+ J5 r3 ?printf("\n");
1 m+ o6 K# F, S5 m+ ?8 l. Vcount=0;
: _2 r3 X! {( c! f) b+ W# l0 Ph=M;
# [: `5 v2 D: s1 v0 mprintf("依次退出的猴子: \n");
* m* {0 O2 m3 @7 H/ [& Xwhile(count<M-1)
- Z  U! A" E) M" n3 T{i=0;
8 P+ S" w: _/ e: Vwhile(i!=3)
* m5 W  M" w' z" n9 @{ h=link[h].nextp;
6 D) ?# u/ w4 b% F/ g2 i! B; l   if(link[h].number)
7 M1 t  ^% x* W6 x1 ~; y, G7 ?     i++;}
- C# f3 ^" w' x) m9 M! p9 k8 H4 V7 [* v9 E
printf("%4d",link[h].number);% N' C/ e# ]  n0 k
link[h].number=0;, k0 S& Q5 Z# C& p6 X
count++;
: M- Z; h2 }. A" S# G( X}2 e- y+ x- Z0 P; o8 o& A- H
( S0 A5 ~8 \6 l
printf("\n大王是:");
4 s1 n6 W0 }: B; o2 K8 y+ M  for(i=1;i<=M;i++)
# M  @( y, `) ]5 H: V5 k* \  if(link[i].number)
3 j/ I9 G( i% x    printf("%3d\n",link[i].number);
* Z- ]$ k2 }) W- U8 \) I. @, P9 m) f3 o3 ~1 o
: g& }9 S/ D! [0 q' ^) P
}
- ^: T, h: g  q+ Z
第三种是普通方法for循环

8 _& z' L* ~4 L% n" k$ Z3 t#include<stdio.h>4 n' b; U& y  F+ \' P
void main()
: c% U2 t. U3 F' u, h{ int i,k,m,n,num[50],q,*p;0 ~7 H: h7 r; A8 R3 R
    clrscr();
: S; F1 f5 z" q   printf("input number of person: n=");+ ]; S" @- z- e
    scanf("%d",&n);
# m! X# x' m# p. jprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 H$ ?! H/ ^* e6 ?( n8 s    scanf("%d",&q);
% T/ R5 i% {3 X" M- Q- y   p=num;# v: D- {1 f7 W9 q+ R2 V( v
  for(i=0;i<n;i++)- b5 N; y  k8 N! ?6 W7 ~% B
    *(p+i)=i+1;9 i. H0 F' x- ^  M) }1 @1 H
   i=0;4 f3 O* Y! [. Y
   k=0;, v8 Q: X, i+ ?- t
   m=0;) v+ G7 _7 B" ~' u0 s; {
  while(m<n-1)
. I6 C0 N$ b9 T2 D: }   {if(*(p+i)!=0) k++;
" h2 j/ v8 W" ~) u' Z! k# ]     if(k==q)
8 |0 f( {7 u7 [6 B: `      { *(p+i)=0;, n; m+ A9 l1 m& F
        k=0;1 Q: y1 b6 f/ Q
        m++;
6 m$ V1 D6 v, V! M      }: W% I6 ^, s+ y- t; d) Z! N3 ]
    i++;
* W( {7 W# L$ j# r    if(i==n)i=0;& P6 C( h) K$ {2 u# i# n
   }* n" z7 `* s4 {/ W% A
  while(*p==0)p++;; X. s' ^7 L! N: o9 @
    printf("The last one is NO:%d\n",*p);
4 R& W- @7 S3 S" d     getch();; ^( U' o& e0 ~. B4 P! N

; b1 Q1 c0 [. o; w7 k}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
+ F( B8 i1 q6 V0 }namespace 又费马达又费电; r8 l3 `# F. K0 e# A! j
{. a9 m+ l' D) @- Z3 A  V. Y
    class Program
8 A! e# ~! x' r7 K  I    {
3 J# a1 p4 `4 d0 L        static void Main(string[] args)
" Z; u+ d# n( c1 \# a8 A        {
: f/ k9 K  O! g4 I- p! i            int m, n;% b& I% W0 T; F3 ~  k7 C: b
            Console.WriteLine("请输入数组长度");. F7 o- u9 p1 H) y( \
            m = int.Parse(Console.ReadLine());//m为数组的大小
3 \0 m) L; s  o. y( S7 H$ Y8 ^            Console.WriteLine("请输入要截取数字的大小");
  {4 l* K. n5 _            n = int.Parse(Console.ReadLine());
5 V  X( F( j6 K4 ?2 K$ ]! B2 P            int [] numw=new int
4 H  y# X# n8 e  f, m' E5 Q3 q, p/ }+ T
&shy;&shy;&shy;;; E7 @3 q( A8 y& f, F3 _. u
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
, e/ |; D: m# E- n            {
! z( g. l& N% p& L                numw[j - 1] = j;
% v  H2 I9 r. J7 Z, w# k: P            }
6 D% u6 J% W( d% x8 F& \            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
+ R( z( ]4 l  N/ ]9 N( ^            while (d != m - 1)
0 K5 P. x+ K3 G' H, ~            {
7 N4 P* |$ r) a$ o% p+ d                if (i == m && d != m - 1)/ e- u, X6 I+ |
                {* F# E* _( G* P8 [! O! H
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!" J9 @6 P0 m" G( Y6 |5 p  _
                    continue;' g4 ]( a  {6 v: P- `7 `1 ^9 E
                }  j! M% o+ g+ |+ p5 V
                else* ]- L7 a# x: r. a
                {, s: C0 r3 o% n: x- W
                    if (numw[i] != 0); J6 _- C' D! ~) e
                    {  s+ \/ q( B' w! u3 _, F
                        i++;
/ S- u! Y0 x- x# c9 w7 a" M' Q                        k++;7 \, C6 f0 }( v' z6 [
                        if (k == n)
' q: H& L7 g- u$ G) b0 i                        {
0 }, x5 m* E7 L* t                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
1 E! p4 Y1 p; `# T8 O; a9 P) V" x                            k = 0;
1 g7 w+ E. I1 u              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
: E: j8 g+ l" w+ l: _& O% J1 z                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
- L8 |: O, p8 b1 t9 G& V                        }  I, ^; {( \( y0 U) J
                        else//输出暂时还没有改变数组元素的值1 |! |  q& X% x8 X3 P6 T' u
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);3 K$ F) Y; W( ^" u, W$ ^
                    }
: F" C' J" `, h, |$ m( A9 ~                    else
1 |1 P6 I( d/ z% d$ F( \$ }4 Y6 E                        i++;//数组元素为0,直接跳过,不计数。。。# ]# G! [) v) Q. a  F3 L7 X9 Z
                }9 t6 {8 O/ |9 ]. C% F9 Y* y. K' @
/ R1 O* D* f) w5 ^# V

8 C4 N' X9 p  V2 P9 y            }//结束while循环# ^5 u) s& H9 S) R  @
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦( M2 o( P; g: H1 S0 z- _! }
           ' P, r7 _* T0 ]% C/ M2 {
                if (numw[i] != 0)
0 a& s' f3 d( j! `, R: a% b                    Console.WriteLine(numw[i]);
* r5 D1 A% \; ^) f           
1 v9 [% l' t6 t2 Y5 z) p( ?. q/ j            Console.ReadLine();8 p! h: i4 s$ W) D& y
        }* L* z. n/ p* O, C
    }/ j8 @6 n1 G4 W; ?* n) h/ S9 V
}# u8 I% P) ]2 ^: J. s% m
小甲鱼最新课程 -> 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-6-14 21:39

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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