鱼C论坛

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

猴子问题

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

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

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

x
大家好!
) f6 m+ r& o$ s7 G2 X4 N2 ~这几天我在忙着编一个问题,我用了一种方法编出来!
& U7 q5 o, Z5 e! {但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
) {# O' s% T! u* u6 p注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 1 s4 {0 F6 ~) ?3 U$ [  N% j+ Y

& E1 w- R8 A. |; I" a9 _/ V. _( n5 C* C  K
                            题目) @" @5 P5 \" e& X
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
' E/ {  u4 T$ h; ?0 [第一种方法:利用循环链表# D7 K! Y+ H4 X9 c8 F% K
#include<stdio.h>: g5 W% Q& A: N0 |8 b+ q
#include<malloc.h>
1 n2 N5 c" D8 |#define M 8            //共有8只猴子
% A0 J! }) X5 i- P/ ~7 u" p#define N 3            //数到3只时退出第三只& t0 z$ I1 v. I4 u8 f& S: q& k
typedef struct monkey  s6 q  c2 K9 V# Y
{int number;8 ~5 ^& t! f' Y
int flag;
- |5 Y+ J, X9 E0 q0 Xstruct monkey* next;/ J" y) O; x, G! I9 _" K! u8 N
}MONKEY;
$ @0 \2 K( c% o/ pmain()
  y6 R& V5 Y5 P$ k{ MONKEY *head=NULL,*p,*s;9 G* d' W2 ~5 |4 Z1 c) |
  int i,sum=0,count=0;
9 Z9 X0 ~) J/ ^. t5 m  clrscr();              //清屏- V% R$ h4 Q' c8 a2 P! c1 z7 {
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存) l/ R4 r; {: L  q* k9 _
  p->number=1;p->flag=1;# |5 s$ l0 R5 s$ \
  p->next=head;
* ~8 E/ }0 Z( ~4 m% P  head=p;
4 \: J$ m; }" d) E  for(i=2;i<=M;i++)
% |. m. z, A8 @, c/ L. Z    { s=(MONKEY *)malloc(sizeof(MONKEY));
+ b6 X2 @0 o& P  i+ {     s->number=i;s->flag=1;
% k- e3 h0 q, S  [4 |# E" \     s->next=head;, h! G: H* R6 T0 g+ Z; E; n- L
     p->next=s;p=p->next;$ L& Y. ]/ d9 T# g9 z
    }: O( I" N3 n9 r& g# {
    p=head;
) _4 s7 v0 a9 `: p/ c6 F   for(;;)  E8 ]1 ^- o5 ^- r* L% T( @3 o: W
    {if(p->flag==1)  b: F0 i8 s6 s! ?& H. _' z( K
       count++;
) F' f# ~6 V6 ]4 G) P; L     if(count==N)  o9 k3 }7 E( Y( w
        {p->flag=0;3 a6 B/ w# V; l2 E6 N! p
         count=0;
  W# ~- K; T% H: z* h$ [) P# A1 k, b         sum++;}
- [* m8 I: f4 ^- Z  H     if(sum==M-1)
3 O6 z6 K" @# B2 K6 A  c        break;
. y+ b9 Y5 L' s$ U5 r% N     p=p->next;, `. h# L5 E* L* G5 s
    }) b1 s/ C) g1 s& ~0 j# h8 ~
    p=0 h" c% H8 f: Q9 J' ?* q% y
    head;
( b7 _) {# `6 k8 O; D! p6 M9 A    for(i=1;i<=M;i++)1 y( X. A/ I6 {! o  |8 L
    { if(p->flag==1)$ z% a% @( E# `& M& O9 Z
        printf("\t%d",p->number);
1 S& y* n7 @* b0 {2 p      p=p->next;
! W* }! o5 J8 d    }" i5 F# J( W. Z

+ N/ O% _' U( y! h3 {- ]# g0 N* r2 D' l9 O
( G/ I' a# M4 y" J# d
}
& V: a$ F9 n( z# }6 K9 r
第二种方法:数组! O7 y. S5 M  }
#include<stdio.h>
! C  L4 W1 p6 G#define M 8
! T8 B) ~* x$ v1 l( R4 C: a3 lstruct monkey
! L  |* N. [# n" b- f{int number;
! y2 U; H: C' h( F) Zint nextp;0 g: C" F* V8 G# x
}link[M+1];- r% j! l) }" i) C# w0 `
) {+ O9 V% K, e& P( {1 _
void main()
( m4 W6 n  E! B9 w  T{int i,count,h;
2 G: F' b6 c4 X; i0 ^for(i=1;i<=M;i++)
0 @/ d/ |* c1 ?# D( ]{  if(i==M)
; }4 b  X5 O0 V# x6 g" k7 ~   link[i].nextp=1;
9 K6 J# j) ^% O% P: f/ C/ Q/ w   else
) D4 k" O5 v' ]! o& ~   link[i].nextp=i+1;5 ?/ H9 ^1 T# q) u" N
  link[i].number=i;
4 f8 X1 {$ f% p# Z& c! V}# W3 s$ n0 L$ J. ~' s. F; l# n
printf("\n");0 g* S4 K* N- g" o) N0 c
count=0;
2 l3 O  C/ L6 A7 R9 yh=M;
4 e9 ^- J# D# @. k$ J: l8 Dprintf("依次退出的猴子: \n");/ ]; h; a5 g* q3 C. [! x
while(count<M-1), I7 H+ P8 c: p+ [) j: f
{i=0;
; @; A/ h0 k8 p. A1 L' w2 {1 Zwhile(i!=3)
$ u7 H  p7 y7 u. P. ]{ h=link[h].nextp;4 X! t! G  F. q
   if(link[h].number)
7 @. [" b7 _$ v/ a# B     i++;}
& }* }+ c4 b* O, J$ g
, V+ c2 Y3 ~+ p& Q( u, Sprintf("%4d",link[h].number);
/ j5 m- \; L/ d- I" {( |/ tlink[h].number=0;
( ~9 c; V4 O- O8 z  w7 Jcount++;
- T6 M+ W5 x0 E0 k. F}
; x# {9 r6 m) m7 Y& Q! {' C+ z; W$ g3 W4 L+ I
printf("\n大王是:");
. ?' o- y5 P! u! v' O  for(i=1;i<=M;i++)
: F. z$ z- H9 l; S. {. E8 p# ?! k  if(link[i].number)# V7 q5 s7 ?2 s" h+ X% J3 _8 _5 X
    printf("%3d\n",link[i].number);) x+ [- L. f6 K9 e! t% K* g

2 _, A% ?6 r4 X; X' L. U! |% V" f
}

2 x: Y  J( o8 t第三种是普通方法for循环
% `2 _: u9 H# O
#include<stdio.h>
/ x' e$ m8 m* l2 W; jvoid main()3 }6 b2 L7 V& c) i& J
{ int i,k,m,n,num[50],q,*p;
! U! O' a- z: K3 J8 Y$ F- F    clrscr();
. U2 l- Y' O; n$ j9 [! C: j. y* I   printf("input number of person: n=");% {1 E* S9 m- \" g6 @) F
    scanf("%d",&n);
5 H' p8 Z- f! ]2 `: R& R' u3 F; J  g0 E- Fprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只5 g$ ]5 Q( I; D: C- h
    scanf("%d",&q);
1 `2 k1 H/ [& W$ d   p=num;- s6 o9 r. Y. X7 d' u( Z
  for(i=0;i<n;i++)
) w- q, W9 \  j    *(p+i)=i+1;
9 O& k" O3 S0 x& D# Y   i=0;4 K1 o" M4 @" p$ J0 _
   k=0;5 K) ^* E6 W" p' S
   m=0;
7 r4 {% r$ Z' a8 p6 Q8 _  while(m<n-1)7 H* k) H' q" o: d) _0 A+ L
   {if(*(p+i)!=0) k++;) e/ h0 |8 l  [+ u
     if(k==q)
, X" I/ R" }" R$ Y( w2 C! W/ b      { *(p+i)=0;/ b* P) G! o( w; x: S
        k=0;, Z  R, j+ @2 V' x( r# Z
        m++;- J5 l, K% h: |5 g
      }
5 f: d9 w4 N# V/ T3 y) h/ J3 a. f    i++;
2 ^" p4 s4 \- }, ?3 l    if(i==n)i=0;
8 z* A* m; R8 a# K6 R. }   }+ [( {5 T! C! A% y" q1 u8 U$ o. ^! Y
  while(*p==0)p++;
9 _# W, u) t! K5 U    printf("The last one is NO:%d\n",*p);
& F- ~+ s) `8 M     getch();
  e! H3 ^" a! p! B' r) E/ j. w5 ?5 x: E7 h. P% b
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;0 N) W6 p1 R/ {% B
namespace 又费马达又费电* c' _2 V7 {9 _2 M- y8 O# F2 g1 g+ I
{
/ k2 G" Z7 K; X" S    class Program
9 d/ o0 E4 U+ p  l" W0 w& u6 ]$ o    {# ?) r/ A; \' N3 v
        static void Main(string[] args)* p4 {( e% x! Y+ M) w
        {
4 G0 D, c% O& o+ V            int m, n;( n! B( u) l, T/ U' I6 h
            Console.WriteLine("请输入数组长度");4 ^, X  u+ V% G$ Z4 u) D& @) V* j
            m = int.Parse(Console.ReadLine());//m为数组的大小
/ J0 n5 z& G: h; {" t# ~( L7 W            Console.WriteLine("请输入要截取数字的大小");
. b2 r* C' R$ [9 H7 X            n = int.Parse(Console.ReadLine());% ~4 ~# x, v' X8 g' _! [
            int [] numw=new int8 ~9 w# \/ f2 [6 v" I

5 x6 V6 l" @% X5 T  M&shy;&shy;&shy;;
* r9 H+ {9 H5 {7 a: q  B            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数$ J2 I# K8 y/ Q0 }9 D
            {/ i' u6 m: r( D" w/ K5 @3 i
                numw[j - 1] = j;3 G* D: P% o6 }4 |" D5 z) r
            }
& X+ x" O& p! n- J8 i8 b4 _$ x            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!" F4 r) D2 P! v2 `5 H2 C, [
            while (d != m - 1); r  S1 f' u1 }1 b7 l& r
            {
4 J1 X) v: g8 Q* @9 b& i                if (i == m && d != m - 1)( u5 j1 |: {3 J
                {
( j; P" O, p- e6 I                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!9 {5 e1 l% ?8 ?/ f. q: q  E8 Y9 L
                    continue;
" S$ y# J9 ]1 B1 i+ T( W: N                }; y5 Q5 ]; F) P9 U" n; z
                else, D/ z* F/ W) J0 e# {$ T, q9 D
                {
) w: J0 z' F2 P0 P6 m                    if (numw[i] != 0)& W; s5 `0 q( Z) b/ y! e1 n
                    {) X- F# Z6 }- T9 ~  W' ?/ o
                        i++;
% g$ R$ v# k' T. Y7 D5 p3 b: z3 ?                        k++;
0 J! E" [3 J8 G" W                        if (k == n)# {7 _2 \5 \# S7 H9 x/ j
                        {
. I( R" \7 ]/ x( l9 f% H$ A                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
; k5 F. m) j- H: \                            k = 0;! F2 W9 F( b$ z6 Q7 ?! B: _8 q
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1  e1 _& ^' a7 m% A2 i) |
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);3 g/ p$ T. R5 G8 y0 y+ F
                        }* g* x" W( {6 g4 m: P- O4 o0 F' R
                        else//输出暂时还没有改变数组元素的值5 H8 o7 K& u' s% r9 q& t
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 I* C' R6 M* z3 h) F' W7 D                    }3 h( T% C+ b; d9 \' v
                    else3 Y- u. Q" a9 l- |5 W% C2 Z6 _
                        i++;//数组元素为0,直接跳过,不计数。。。1 {! [9 N' P' I6 @* B
                }
) E- J! g0 L0 D' c; Y, t " e- L; s7 f; f( j% [

: g( B5 P/ |; t5 V  {9 J" S6 Z            }//结束while循环
! v& I( R) ?4 }; K$ r            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
8 R" D- j7 j( ]  h           1 d& b5 s( H, |4 e
                if (numw[i] != 0)
( l6 L; u: _! b8 D, C& [0 ]: O                    Console.WriteLine(numw[i]);3 I& V6 M  p) O7 o# s( o" a
           
6 \- p/ Z4 k/ z0 J# ~            Console.ReadLine();
8 X4 t( V5 V. G% ^) i        }
, U% v. s+ h1 f/ Z+ d    }
7 n' d% ^% ?7 C3 `- K+ n}7 n' Z+ ]& C" T7 E8 ]! Z9 w2 `
小甲鱼最新课程 -> 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-3-14 21:33

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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