鱼C论坛

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

猴子问题

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

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

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

x
大家好!" L/ j7 R: F, i1 K* i1 o' b
这几天我在忙着编一个问题,我用了一种方法编出来!7 ^+ K$ X0 E  M, _. ^$ a1 @1 R# m
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
9 e& z- c" F! r1 x7 i5 {6 ^% C注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
* }/ E  S3 {* y& d9 ]% z. z: }) W" U9 @& |

0 ~4 I: z! }2 L+ \& |6 U
                            题目
$ X- E" b) Y% L* J. h" `山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
3 V& q) O' @3 Y第一种方法:利用循环链表
5 K# f6 s) J* R2 @! B#include<stdio.h>$ O! ?! K) _7 Q7 Z: w
#include<malloc.h>
7 |9 s& G7 z. c#define M 8            //共有8只猴子
& x) k5 k$ u5 S9 g" i#define N 3            //数到3只时退出第三只
3 v! r% T8 d& B& wtypedef struct monkey
/ g+ j+ E: X6 i% A- z+ S8 Q) F  Q{int number;7 s+ C2 r! c" W, O( F
int flag;3 B2 W5 {1 L8 v9 I  e# {: A
struct monkey* next;/ W, Y0 j" n: Z6 m
}MONKEY;
; w8 Y- c4 X" J: Amain()
2 i  F0 x1 k8 N: ~% C+ d{ MONKEY *head=NULL,*p,*s;
  E3 \; K8 T- U9 B+ A4 N& o, N  int i,sum=0,count=0;! B4 u7 o" T0 `" a5 C
  clrscr();              //清屏
* ?: d5 [( z7 m  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
# D. P1 ?0 [( G1 z- _  p->number=1;p->flag=1;  W2 h+ |+ u$ U" q% B0 C
  p->next=head;
+ H' ]: T  V- g' G0 N9 i9 O+ ?6 d  head=p;
+ l8 i2 |  P# i9 j7 j1 W* W( B# E  for(i=2;i<=M;i++)2 Q2 ^9 Z& Y5 C4 v" M0 j+ q" t
    { s=(MONKEY *)malloc(sizeof(MONKEY));
" S9 p% F7 s9 N# o) E4 ~/ p     s->number=i;s->flag=1;
8 X5 j& ?: a" q# M) S5 ]% e, D     s->next=head;
: S9 n7 `" o: Y     p->next=s;p=p->next;
( k* o. V1 H7 k, x2 w    }' ~* d1 w" @8 d  C- z
    p=head;/ s- E2 |3 F+ Y- s+ j
   for(;;)4 }& {7 q) K  \3 `
    {if(p->flag==1)+ c7 w0 \$ j1 H% v- D7 A
       count++;  S- B/ R- c  U( d$ r
     if(count==N)7 E$ S1 H* s6 V1 U$ U% d# d) w
        {p->flag=0;, u, ~7 \( `4 |* C; J/ k
         count=0;
, s% }: S+ S8 D, q6 X& h         sum++;}
/ E( K6 @* O. i. A0 y     if(sum==M-1)
) {' r' f4 P/ h4 T% M- c6 H; l        break;
+ k  J# e" Z5 ~+ G6 }     p=p->next;
( @/ U$ ]3 I, x5 \7 H) G) E    }
* X1 l3 e% v5 s' x) H) p    p=
: p& Q' z1 d: v0 x5 m' a" H    head;
5 d+ r& v4 C8 \; [. F* X    for(i=1;i<=M;i++)( `5 s# F! [& j4 u' Y9 c8 \! x
    { if(p->flag==1); X: l, n- M- R9 P. A) G/ \5 V
        printf("\t%d",p->number);
% r! q7 {3 j' `0 T) y2 {- T      p=p->next;+ \: ]' s; w0 Z1 [7 c0 l) o1 |+ K" T
    }
& V* F+ U2 o( V1 ^. G/ ]0 e- R
" e: a! \0 \& T3 q0 n: b9 f( O- v
. h, t+ X9 ~7 s0 C) B
. |0 J6 e5 M+ {' T7 L/ I! K}
1 ~4 @" T7 g; t' U2 F0 ~7 M
第二种方法:数组
# x- u, A" Y9 A. L5 u: [6 {& _#include<stdio.h>$ C! }+ Q2 I# r. u5 B' A  d- o8 O! L
#define M 8/ `8 Y% D* F/ \/ e9 f8 m; [- i
struct monkey$ j+ w8 B% @. g! |% w" _. s+ K
{int number;
- b( d' [# }; f7 ^int nextp;8 ~- s: s+ o1 Y6 \# L1 a
}link[M+1];: W; V, W7 f  Z& X) ~6 D* r6 s6 O) f

( I, J, ]- N( |+ T5 jvoid main()
3 J8 u1 U( z. E5 Y8 v  }{int i,count,h;
4 c# U( `( \  z2 x7 f" V6 v1 Kfor(i=1;i<=M;i++)
; D, ~  f: h+ i{  if(i==M)! y9 \! H9 N. p8 w0 L& V. Q
   link[i].nextp=1;
+ R& t" b3 j- }0 L   else
8 E; G- D% X7 l3 ~$ [: I3 u# [   link[i].nextp=i+1;% `- j& R& z, \& |7 z
  link[i].number=i;
1 L( v) K3 u/ O9 b$ Z}
/ z0 j6 p: J7 U( |printf("\n");
: b) o6 v& }" C5 zcount=0;
- b6 z# C7 R5 @% c3 th=M;
1 P* k, k. d1 ^0 g  t' Q& }) ?5 v/ @% nprintf("依次退出的猴子: \n");+ l- G' a: g, q3 ^' P
while(count<M-1)% S6 F  B1 a1 S
{i=0;* T: D9 T' Z7 h; X9 [. ]/ j
while(i!=3)
  g, ?9 f* {' W4 |{ h=link[h].nextp;
; @: l+ d# B3 O& s4 J   if(link[h].number)( R2 Y* c1 P+ n/ f" b; [2 R
     i++;}8 G' n9 j1 q2 R7 F8 I
) [. v/ s- u) G; N, e
printf("%4d",link[h].number);
3 Y" L8 X' b# O# Qlink[h].number=0;+ ~  P% I& x/ k, a; j% G
count++;3 q3 n/ [$ W: X) c
}
9 G- Z  e5 R& W! s* ~- y: E9 n; @' q0 l; w" y! W! o9 r" n; Z
printf("\n大王是:");
+ r5 i9 o& Y3 ]( }: n  for(i=1;i<=M;i++); E, W) h& f; b# n. w8 \9 q" r
  if(link[i].number)
, T4 [: {9 A5 f7 \; C    printf("%3d\n",link[i].number);
; Q- F5 `, U5 i, P2 r* }) V
2 I$ U; w- P  |; k( {9 @' k
7 h' c- R4 N" h; h; K}

: ?4 n) v7 U9 m% M" }- V5 T第三种是普通方法for循环

2 `& z0 ]+ u4 t#include<stdio.h>
1 S5 a& ^* d9 f8 \0 ^% x$ jvoid main()+ m) ^/ e; w6 W9 n. k
{ int i,k,m,n,num[50],q,*p;* X# F5 D9 x' w
    clrscr();
/ o" U$ X% E+ L4 V6 l4 |   printf("input number of person: n=");+ n  {1 g' K6 \0 C* m: o, D
    scanf("%d",&n);/ [9 C) V2 l" q
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
# k. _7 Y' O  L    scanf("%d",&q);3 q: }+ H" P/ n$ v- |
   p=num;
6 x) V2 g- f  ?4 F# _9 v, \  for(i=0;i<n;i++)
% e3 ]. @% c7 ]+ @: G: n$ X    *(p+i)=i+1;2 n" f& K4 p5 E4 Z* v
   i=0;: U8 N& p  |' D- `7 G
   k=0;
: J5 T# C, ^/ Q9 ~' ~   m=0;
2 x7 T0 q$ g* m7 K: T7 t' m8 U' c  while(m<n-1)" R0 G6 H9 _) G9 P" q6 D
   {if(*(p+i)!=0) k++;6 s$ u8 c2 o% L2 q
     if(k==q)
9 u7 Z( s  D8 U6 v      { *(p+i)=0;: L. T0 P$ N7 ~6 O7 Z( y* _
        k=0;
3 C; {. w4 |' \5 n/ `        m++;7 O5 K6 V& J. |4 j+ l5 k
      }  v: I' I3 \2 r! Z- }) u
    i++;. A& d  b; h: a) [/ @6 }7 |
    if(i==n)i=0;
% U- _5 R. w; x! L   }
( {8 r. Q6 K9 B' W; P7 d  while(*p==0)p++;% Y: L2 B' g7 ^4 t* g$ T. {. ~
    printf("The last one is NO:%d\n",*p);) T9 h& q7 z1 A, v, |6 j$ R
     getch();2 t- v3 j; s9 W# v% Y" O
5 @4 Q0 i% _* g4 M0 h
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;( l) R, ^& a( r1 \& H
namespace 又费马达又费电
  F  `) L5 n# O2 [( i{
% D8 a. I6 m6 M' P" |$ i    class Program
: Z7 }' ~% S" L: `! x  r5 ~, q    {  Q. w' u; u4 Y4 j( v3 M4 Y. f
        static void Main(string[] args)
( d% W1 v% S4 w# O# W        {
& P/ f; p1 w! ^9 G# R3 P# e* K            int m, n;. D+ G4 [5 h; A8 L& [; T  T* H
            Console.WriteLine("请输入数组长度");4 S( k  t) |! Y5 i
            m = int.Parse(Console.ReadLine());//m为数组的大小$ Y; B3 z" ~' E) T# V' s
            Console.WriteLine("请输入要截取数字的大小");
+ x$ K- Q# y3 L$ V; {            n = int.Parse(Console.ReadLine());
4 ~& C+ Q6 M- ^. Q1 g& x2 y            int [] numw=new int; @- `0 G6 k( t8 Z, K% j$ F& z
7 P5 {: r6 z6 l: n" C
&shy;&shy;&shy;;4 o! c5 F6 R, e& \' O
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
# G5 Q4 A1 `' k3 R! j5 y3 o/ b            {. l6 k  \3 r. e5 ?! [% ^7 b
                numw[j - 1] = j;( v9 c+ O9 a: f3 x' y8 c
            }
1 h2 C% A) a9 \$ G            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
; T, v4 v2 ^& y) C# j+ }( G            while (d != m - 1)' ]3 f( ?" U% o5 J- a4 Q$ ~% `: z
            {; N4 g5 S/ z4 _5 d6 h
                if (i == m && d != m - 1)
2 S7 I# p+ C/ |                {# U, j" H3 k% Z) @& y3 h6 j% C
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
4 F. N6 u6 \+ x* x# B                    continue;
8 c6 d1 Q$ v2 C                }
; ~: V* e- D4 Z0 w1 s                else
% R% S5 }; b* a2 e                {
( D1 _0 }* ]) U1 d                    if (numw[i] != 0)
/ z% c$ e* `* c5 _$ v* S. E+ y                    {+ {) ?7 C8 N3 U# h
                        i++;$ `: Z8 v2 ]% [8 u( Z8 ^: Q
                        k++;
, \& r0 \$ e0 a  J5 u) l                        if (k == n), c! r9 F: l+ k& ]6 i2 ~( ^
                        {
/ U6 r3 ?& {& T1 i                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
9 x% H( D/ U, ]9 {( R* d: ]                            k = 0;
. Q) B/ h- m/ q3 @- x              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1; t( M1 w. d2 W" z, P
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);2 o* u$ I# n7 \. e# _# E
                        }
3 l3 s3 k& L" \! j7 s- k( ?                        else//输出暂时还没有改变数组元素的值
) i* \7 i7 N# _9 K/ k" W/ i6 {/ @                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
/ T  G6 v" B1 t1 J: O                    }
; u: G% E' y( e9 Z5 t6 R                    else
# L5 }+ ^- d4 b% i5 {                        i++;//数组元素为0,直接跳过,不计数。。。
) y+ }3 a& S( W! R9 w* J                }8 U" X; X1 \$ l; f& A

: f( {6 l7 u# z3 T  B( e, J, v% }2 I+ z! p7 i' x$ J) O% o& {
            }//结束while循环$ P" M- A' R2 Y4 z; y% W( r4 X3 C
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦: h" A3 n% }) B8 C9 ?
           
8 D. S& M# j% s" d) H% ?                if (numw[i] != 0)* Q. ]& N- v8 D# q6 }
                    Console.WriteLine(numw[i]);
, T5 j8 z. A% B' C7 `. |           * }) K: M9 Y" D- k. E0 G  k
            Console.ReadLine();/ g( G% d5 b( G' `$ p6 v
        }" p* @% L$ ?2 ?3 g
    }$ u. U" c' q( O! R/ ~4 ]2 Q1 v) X: f2 Y
}
) m! a8 t6 \/ f3 ]( j. }" ?
小甲鱼最新课程 -> 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-8 09:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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