鱼C论坛

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

猴子问题

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

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

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

x
大家好!
6 E- n% S0 ?& G; Z' M' z7 a8 G. m这几天我在忙着编一个问题,我用了一种方法编出来!
$ n4 C: p1 ]% K2 ~但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!* k3 r1 ~3 i1 W6 x! f3 i  A
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 0 {' H$ n: j/ m  |' R. H

# M  G9 v, V* p) c; {4 _5 U& z) \8 |3 h( p# x
                            题目
  ?- h- j& c! d) F山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。5 \# n& Q' |3 l2 w* Z# D9 W
第一种方法:利用循环链表/ I: X  T* ]( _+ r  [
#include<stdio.h>
  c4 |. ^* T: p#include<malloc.h>
& C4 x: y+ a+ F#define M 8            //共有8只猴子
  p  B$ D& z* l% S8 s) u9 y#define N 3            //数到3只时退出第三只! N: {/ _0 Z* V& }; y, V
typedef struct monkey
- _1 Z* r/ d( d{int number;2 ?# u, Q. P' E* @8 O
int flag;
1 n0 n+ V6 ]& N$ T' B# @$ wstruct monkey* next;8 j2 D, B9 U7 q# j1 ?& o% h; w5 m. J
}MONKEY;
! t7 t7 ^9 N( p! [+ @main()* J8 d4 P9 ]- g
{ MONKEY *head=NULL,*p,*s;# M0 v" Y% B: g+ B8 H) i' [) i
  int i,sum=0,count=0;
$ L, x1 k7 |* @$ K5 [  clrscr();              //清屏" M: p7 ~) ]3 U7 R% `  j! {
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存; E+ L$ o8 D  j3 i) y
  p->number=1;p->flag=1;
4 D" h: \1 c6 R$ p; f# u3 P  p->next=head;
& f, \7 `4 |7 U7 j: k& D  head=p;
# T. n" w: s( Z$ l2 S+ {  for(i=2;i<=M;i++)4 C$ Z* Q1 B. p/ Y! I
    { s=(MONKEY *)malloc(sizeof(MONKEY));7 t4 Q5 b( W$ f3 h  ]4 b1 I
     s->number=i;s->flag=1;
7 S+ c( T& w5 l     s->next=head;
1 B7 S9 N+ h9 Y     p->next=s;p=p->next;$ f0 p% i0 x4 ]1 V$ U
    }% a# _7 o7 Y9 s! C0 b! N4 @# U
    p=head;
8 L0 j5 c( F  V, W/ W, f   for(;;)5 Z: F2 C* R, ]1 d; [  G; P7 N
    {if(p->flag==1)- g* o0 W% Y0 e! R  g. A- {6 L" ], q9 P
       count++;' N( |1 m- |0 T, h
     if(count==N)
' J6 Z1 e- r' s$ w        {p->flag=0;& l0 o  n2 ?, y6 b7 c" c8 X6 g
         count=0;
1 p6 l3 Q" V( c2 |' S7 |         sum++;}
: B1 s. z$ L/ o3 `8 o8 f; w- A( Y+ r     if(sum==M-1)' r! Y3 r- V% Z  O" p! Z
        break;
7 V  ^7 P+ j( A1 u1 [     p=p->next;0 n! c. B% F5 u. L
    }
& [# n  w  r" ?+ f    p=1 w; z& `* z( ~" r2 {" i) j
    head;- [4 o% a" p( a2 ^5 O: V
    for(i=1;i<=M;i++)
/ h2 n! Q3 E! b* R5 _# x    { if(p->flag==1): d" t8 e9 W" p' S
        printf("\t%d",p->number);
- p! E5 g4 X5 Q# Q( D      p=p->next;
$ p: j$ _1 k0 m2 T  N# @% u9 M) Q    }* N( G" a( D5 S+ i! W
  |4 a6 i( F5 J7 D' {; U- t
# t, ~% w+ O! t; m0 z

' g1 Q6 }  Q& u7 Z* e( ?}

; k  G/ ?  b* ~# I& ~8 Q第二种方法:数组
4 \8 l) n; w& ?* D0 d3 {+ @/ K#include<stdio.h>* x% q% F% S3 n  \6 c' M3 `
#define M 8
% @+ I. m( o& z. ^- Sstruct monkey: ^! ]3 o. X' F! S! p5 ]" g
{int number;
% J- m9 J' C5 ~0 Z/ r  Iint nextp;
5 W! K  `# E- {( k1 x' t, ~" e}link[M+1];) s. W' U( a4 Q
/ S3 }$ g/ a/ k) d
void main()9 l+ O; n' i9 E
{int i,count,h;% \  S+ P; {7 l2 t# A* [* h* P
for(i=1;i<=M;i++)! k; H- |9 F7 m3 _) g0 w
{  if(i==M)
) o7 ^2 A0 r: v  {1 u% z# _9 B7 C   link[i].nextp=1;
: P9 x  v: F) {. C5 V* p" b   else
1 g9 _/ f$ g0 H+ W1 K: M   link[i].nextp=i+1;
9 V, s1 y" N5 H9 u. E, E3 l  link[i].number=i;8 W5 b) L. I* M- t
}
' N3 d' B$ E* w. v0 Iprintf("\n");* O) g0 ?) f9 `5 {$ q' ]" D& {
count=0;
+ i! A# d* w7 \- ~! Sh=M;
) n7 `; M* t, p: S; Y/ f! Xprintf("依次退出的猴子: \n");; A, w) h: |3 ~- `0 ^$ s
while(count<M-1)( b- a& n  E2 T* J3 f+ @% }" F9 M: o
{i=0;; L$ R. x' }3 b2 ?7 u1 A9 b9 Z
while(i!=3); E: N+ ~6 a- T; a2 T$ E
{ h=link[h].nextp;. O% T8 V: U# W+ W) Y" B
   if(link[h].number)
+ q' l% t' Y8 V0 V  ?& k     i++;}' f9 h/ W* h0 |
) ?4 [# ]/ E# w' z& M( h
printf("%4d",link[h].number);
5 P; ?, v- r, b! ]5 Tlink[h].number=0;
; _( W3 @' c* }count++;
. v( e7 Q# w0 J( _}
" Y4 x$ @) @0 X2 L4 ~/ H; b; o& M; j& N. h7 G" r8 V
printf("\n大王是:");" L" c( i' ^# z9 S/ w. A! @9 N
  for(i=1;i<=M;i++)
: x/ S1 E2 r4 Z3 Z+ p$ z  if(link[i].number)
5 f7 t# \9 Z2 `8 u% l) H0 X    printf("%3d\n",link[i].number);
% d/ x6 @8 x  o: K0 L! H: ]% y9 [( [0 @. ^/ t4 B2 c6 U- l' Z

  E3 y: e6 L3 p: x' w& C# [}
( ~0 @) z! r0 w7 O" [
第三种是普通方法for循环

4 N9 ~, m* u: M#include<stdio.h>
0 a( ^. w5 j, ~1 [" N/ L& @  z/ Ivoid main()2 \# q! [+ {$ C! L$ S: C& x
{ int i,k,m,n,num[50],q,*p;- ]) Z3 A% [6 K
    clrscr();
% F% e% @$ g$ `/ p* \   printf("input number of person: n=");1 r. }3 |; L( P. p
    scanf("%d",&n);9 _# u* o) n. u! S; ]5 `3 V
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
4 \0 ^5 W, b+ f& P: v* M" d) Y    scanf("%d",&q);$ }: ~% p( w, t. A7 h
   p=num;
1 ~6 k. g! o1 b& k* y$ y( N1 ?2 m4 g8 |  for(i=0;i<n;i++)$ h1 G6 m7 J& U5 h" T
    *(p+i)=i+1;4 q- J/ M2 f) o, \9 P2 I
   i=0;
- L: I5 @7 q* H9 `2 [3 H   k=0;
5 }# v6 b" _3 m4 ^5 B8 B; s   m=0;
# U. D2 T/ @8 o5 c6 i& m  while(m<n-1)  {3 F( s' K& w8 Z& G- l% u
   {if(*(p+i)!=0) k++;
# |0 u$ l( Z+ L* ~     if(k==q)
" V* \  G- v9 _4 U$ w# U      { *(p+i)=0;
1 P- M# {7 h& J7 b+ m( \        k=0;
% }2 C3 D% M) k; x' h* C. @        m++;
& P% p, q8 w1 _/ ^/ f( N      }, x& C1 t; Z; b4 z
    i++;. ]0 M, p6 `. |' D/ A
    if(i==n)i=0;2 U2 N4 d+ O8 H3 S( v; p
   }
. V& k' h" U9 J( Z7 W  while(*p==0)p++;  ~  g$ g% o! ~0 k* R7 P2 n- r
    printf("The last one is NO:%d\n",*p);
' f8 u+ P9 M8 u5 `% J' @     getch();% X9 p# V/ J- p" n( p! D1 z

% @- O: {- z( m; {: \( a}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;2 q/ ^  [9 Q; ^) v& {3 |
namespace 又费马达又费电* P3 |; i: x! o4 }) I7 F1 m( W
{( L: \  \$ A- \) r: n9 {4 s! A
    class Program
% [7 ^! X$ G. p    {* K% D/ _+ a2 [- u. z; d
        static void Main(string[] args)6 C2 U1 `) Q. d
        {
: P0 M# u7 x6 F" i5 e/ v8 I5 G            int m, n;9 ?' f' e/ `0 f/ i% T
            Console.WriteLine("请输入数组长度");' [4 {0 r0 \4 h( P* s
            m = int.Parse(Console.ReadLine());//m为数组的大小0 P8 g8 @& w2 w4 w5 e' ?2 N
            Console.WriteLine("请输入要截取数字的大小");
3 L: C" T' v) P. }/ Q" G" [) _$ y            n = int.Parse(Console.ReadLine());, o' G( x! \2 i0 i. H2 C
            int [] numw=new int& L( B9 n* X! t. x; N

  g9 S6 q; M3 l. D8 o: n&shy;&shy;&shy;;
9 N8 d% t. M' V6 S, S, z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数6 {4 ?. h" t: O4 Q% x
            {5 a$ v* m4 ^! z( Q# D: }* K
                numw[j - 1] = j;
# o! H0 g$ q" X9 ~% ~* _            }
5 I! f1 Q/ |( @& ?: f( s! t& C; A% D. I            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
3 h2 t+ v% a- `7 ?/ g# R9 z9 u            while (d != m - 1)
+ y$ w* @% k0 G2 j) l. N            {
# F6 g' K( o. c# Z* p. D                if (i == m && d != m - 1)
6 s# Q# y, _% \! ]2 S* |                {
* Q# l! _/ U8 T" s1 {1 L                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!6 _: o3 x) P$ S% m% X5 S
                    continue;9 G1 @! J( `9 i( i
                }8 t7 X2 L8 o0 L; ?3 N0 f0 |
                else" h; d) g% F0 W+ l
                {
5 z5 \) s3 ?# V! m                    if (numw[i] != 0)( q7 @+ F1 ~, g; f5 F
                    {* h, e& O- V/ C) b( h9 |0 b1 O# y
                        i++;9 u$ \+ U1 l$ v* F& C
                        k++;1 g9 W8 f3 B4 B0 L# Q2 ^) ^: D/ e
                        if (k == n)
& x& |  n. `' @  t& F8 M% S                        {% U2 F$ t/ q9 @6 x& k) i* T# }& Q
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
0 S+ l; z4 D! P$ Q  f. F                            k = 0;% v3 F+ y/ q4 Y! a; N# U
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小15 M. L4 t2 M! ]4 L
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 P" P0 J/ D: y4 K# t! v% u- _                        }
9 ^, D9 P3 l1 c! o  Z8 f                        else//输出暂时还没有改变数组元素的值8 m0 i$ `+ }6 m, Q
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);! P! U- V+ O0 j" d
                    }
. ]8 n) b: m' R! V; g                    else
$ X0 t. W% n+ k, g6 U9 p1 U6 b1 S- ^                        i++;//数组元素为0,直接跳过,不计数。。。! x: f( J2 D. N3 p7 Y; R+ d# \
                }4 P$ V1 r# L; E# J5 H. |

2 j* N6 }7 y! Q3 L2 i+ c+ N& y
            }//结束while循环
" s7 [1 r" H- o. d7 V7 h- D            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
$ w- E/ i  \3 R$ f" _7 k           
, u4 \* K1 |& N1 S                if (numw[i] != 0)
  Q1 I- R/ b4 |9 f$ L% ^! r                    Console.WriteLine(numw[i]);
5 l! n3 a) J- A9 R" h6 O1 _           # C2 V( M$ W0 [" ?7 h. S
            Console.ReadLine();; J3 U' a1 u5 D/ Q
        }/ m  Q8 g! T: d) q. l
    }
9 |7 S3 N% E8 }, ~" b; k}( Y+ R9 _! u/ k$ }# S, N) ]; @" ]
小甲鱼最新课程 -> 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-3 09:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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