鱼C论坛

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

猴子问题

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

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

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

x
大家好!1 [6 G; L+ Z/ c" y. m- q
这几天我在忙着编一个问题,我用了一种方法编出来!
7 G0 J. V  L- F2 j但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
7 t) @: j- k  }2 p注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 3 ^% d9 E; ^) N7 `4 u9 b/ _8 Q; I1 d

- n& z- ^; d/ Q9 R7 C3 C3 H' ?; s; s0 b; f5 F  ^8 q: v
                            题目
8 h% f% ^8 N( D% O8 D6 G+ K6 G- J山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。) j& S( L2 S4 b% p
第一种方法:利用循环链表0 _5 ?4 B# U+ k( X* E
#include<stdio.h>
8 c  L; s: V; x0 D#include<malloc.h>
4 R! c, Q6 J1 M3 ~- g3 u#define M 8            //共有8只猴子( h; r3 ]1 H/ L3 v
#define N 3            //数到3只时退出第三只& Q& o) r1 v* B1 J3 Q0 ~8 Q" A
typedef struct monkey6 P5 i6 I6 z# h; E' E; Q, m
{int number;. w$ O; d+ K. K! o* Q/ d
int flag;2 T! P; O0 w" w- D9 ~
struct monkey* next;
  q# F* m' r2 d. U+ p9 H# r}MONKEY;
/ q, I" }8 p$ V* xmain()
7 U8 N, l% f8 T) x  ]& G{ MONKEY *head=NULL,*p,*s;8 d* P% l7 g; N9 G# G
  int i,sum=0,count=0;# N, a8 D5 Y; g: r# ^+ v
  clrscr();              //清屏
5 d6 c/ ?* S' E  v  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存& s+ _" [1 f5 ?2 E
  p->number=1;p->flag=1;9 N7 s- o; o  y8 t
  p->next=head;% y2 O. [& J! Q- n' Q9 E: `
  head=p;2 j" B' e% D2 x
  for(i=2;i<=M;i++)
+ l% r# ?: ]7 j* Z0 W# ?! \    { s=(MONKEY *)malloc(sizeof(MONKEY));
1 H. {  Y5 T2 z0 t3 }# H4 [     s->number=i;s->flag=1;
7 F7 ~  ~  s2 B+ ?  V0 U     s->next=head;6 L$ O4 O" `) k1 k: g3 w
     p->next=s;p=p->next;
' T. D. r3 l# n5 x: v: f    }6 p7 m, g" K- W  W; p# u- q" c
    p=head;
2 L& i3 l. _) b5 X( m: R   for(;;)
  G1 d. G. k* p! W# I2 C    {if(p->flag==1)
+ M: Y8 _+ e7 ]7 m5 o4 F       count++;" w& [! a& ?* P3 ^9 ^) M
     if(count==N)
7 A# W- ]+ ~5 f7 _8 ]        {p->flag=0;
  A7 ]- k  j  D: a; R9 d  i         count=0;: [3 h/ G2 T1 w2 n/ f1 f# w3 ]
         sum++;}% Z* a; a: V* l
     if(sum==M-1)- j1 N2 I8 U7 g1 e1 Z
        break;
! Q9 ^2 E8 J0 L7 Z     p=p->next;
) Q7 L6 `: ]6 m9 X    }8 V1 V0 a4 m/ ^/ f7 a7 ^8 T
    p=
5 S( r2 s# f6 E$ r8 @5 t! _6 i    head;
, t% g& \* U! w/ T    for(i=1;i<=M;i++)
" ?. x% ?, T3 i) ]    { if(p->flag==1)5 y9 k4 ?* @/ }' m/ `5 Z6 a
        printf("\t%d",p->number);
8 g: A( D9 U6 A. v" h! `! U      p=p->next;3 b8 {+ {# K4 r
    }, o- D9 C; X, f5 Y* Q5 r: t
! L! ^. V& Q. {5 P8 R/ A! U: T
- e- v1 S: i6 G7 A" G) F7 a

- B6 o8 \. x9 P' G/ C}
' e1 ^5 K) I: X' b5 a
第二种方法:数组
* A, Q, ]2 U5 `#include<stdio.h>
# p3 J, q! L- k% \: j9 c* f+ S! p$ {; B#define M 8
9 l  f8 m) i+ J6 [4 Vstruct monkey
; `! G5 l/ A; Y& w5 U{int number;, U6 z0 ^0 A- f% k  b# ?
int nextp;
! M, \; H; p# @0 t; X% J6 h}link[M+1];' |( N" Z7 G, S: _
' s% B3 }) ^4 x' _: x
void main()
. b) w9 X: i+ k2 H/ v% `( w; r{int i,count,h;5 o" a6 [+ }' v9 W2 b
for(i=1;i<=M;i++)+ t6 s5 a# J, ]  ?" V( G
{  if(i==M)( p) W! `  q9 K+ Z. \% m8 g4 V
   link[i].nextp=1;
  r( {& r" N4 Q- o! u) D   else: K" B, A5 B" v
   link[i].nextp=i+1;! z9 Q! t6 J; W( Z% L# j
  link[i].number=i;) [! A0 ~7 t$ `2 q- E9 t
}7 P& \9 Y, w7 O, J% A* d7 ?
printf("\n");: Z$ v) Y* x, g. @0 F4 ~& d# l
count=0;
/ Q( g; x9 N& _5 a! Nh=M;
& N2 r& P: m* L6 e8 zprintf("依次退出的猴子: \n");8 b0 J- k$ G  h; h- Y' {
while(count<M-1)
  y4 y& B0 A( A/ f{i=0;
+ p3 a4 N; x  D9 x9 d% F3 ywhile(i!=3)3 a2 [* P+ [8 r6 c
{ h=link[h].nextp;
- s) W- F# s& e  W2 ]   if(link[h].number)
9 k! G8 `5 a* c4 G3 [4 k     i++;}
* {0 F- l7 k5 I* n1 ]
( _0 P9 |5 j! ~# G# @printf("%4d",link[h].number);
& e# x3 ]" M. h, m+ Glink[h].number=0;
2 T: X5 C# f# H9 N7 \count++;
8 t0 z' h' E6 `7 x4 Z# S}$ n. ]; D1 l9 L: e

# D9 J$ k( r6 S8 Xprintf("\n大王是:");
& `; i2 T1 V9 i7 w  for(i=1;i<=M;i++)& k4 B  }2 P& i/ b' }' [9 {
  if(link[i].number)- K8 Q, ^9 H3 w6 ]% e: [
    printf("%3d\n",link[i].number);: y$ }* I& h; X6 w' N2 ^
! I2 ?8 V; U! K) k( E2 j
* e) V0 u- R1 I
}
3 Q  X% q+ r+ O1 j/ w
第三种是普通方法for循环
& a0 l- }% i1 x+ ~2 g
#include<stdio.h>
. S& A! N2 M+ {7 I- d, W* D" pvoid main(): r( u2 z$ x/ E4 |0 E5 j
{ int i,k,m,n,num[50],q,*p;' U4 v* M0 r& e4 |. ~
    clrscr();% m5 U; A# E& B( D8 F# R7 d
   printf("input number of person: n=");0 I' p9 L) K: F- N! y
    scanf("%d",&n);
! |$ Y& ?; @- K* T7 g  Pprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
5 w! X! |6 F: i: M3 u% Q# M& j6 T    scanf("%d",&q);* x) a' U1 V: `4 ?, B
   p=num;5 K" M- I: P( L3 d5 D% t
  for(i=0;i<n;i++)
5 R) M+ ?: n3 ?    *(p+i)=i+1;: Z$ I& c7 x0 \; u" }
   i=0;
' s/ _( P: @# }1 r1 S8 I   k=0;
6 _$ w5 F8 e4 @8 |1 g. w   m=0;
) S) D* e! a1 d7 z! l0 H5 u: d  while(m<n-1)
# y8 a1 l1 d. i5 U   {if(*(p+i)!=0) k++;) r0 h' r* e6 `# l  D! w. P
     if(k==q)
, \( G/ F$ J. z0 K      { *(p+i)=0;
# d0 |0 K3 @# Q* q& k        k=0;
& t+ F# Z; Y" [5 l  Z8 U* f1 Y        m++;
- u2 ?1 W" s( p, f9 ?      }
& Y3 j& t+ q0 d8 e    i++;: x1 W  ]. \+ C$ _" L
    if(i==n)i=0;
" q, o) l5 R2 F9 U2 s( C$ K, m   }
" q; Q8 B' u- A  D, I: x. T  while(*p==0)p++;' B3 ]) `6 v2 h4 \
    printf("The last one is NO:%d\n",*p);
9 ^) _" G, o. F3 R3 ~7 C( k" \     getch();
5 x+ @' y) k* t1 \0 G3 w( J& k( X' [
, r: S4 A  s5 i/ P}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
6 b' o6 o1 t. ?7 ~! d" m  Enamespace 又费马达又费电
; ~. o0 A6 B5 ~, w, `% D0 a{
( K8 F4 f) y9 @# B" [    class Program8 N# @+ }, Q4 {$ |5 k1 {) A8 i
    {, x& E5 k" ^# L" `/ D2 Q- u& U; Z
        static void Main(string[] args)
# n, Y. U$ k7 A% C- b; \. `$ L        {
: b2 h# h3 O: X0 P! b( X            int m, n;
; F$ H1 |) ^4 n8 _            Console.WriteLine("请输入数组长度");
2 v. V. d8 l7 a$ W% \            m = int.Parse(Console.ReadLine());//m为数组的大小. W7 a4 Y/ G+ R' q& q: s
            Console.WriteLine("请输入要截取数字的大小");
+ O6 M* _' }5 E$ Q7 S' |            n = int.Parse(Console.ReadLine());0 ?: e9 x/ _) Z% L: ?
            int [] numw=new int* C0 G' h( n2 t0 e% M$ A1 X
# t. Z, o# }) h0 A
&shy;&shy;&shy;;& j* a4 C5 A/ h6 b8 Y
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
. Z1 _6 `0 R0 ]# J* N            {
: X. [1 @* k7 p* }2 r+ W+ Q/ n8 g; d                numw[j - 1] = j;* z! y# p8 d( F# N' `
            }
  N, e9 ^) I, Z; c) z9 }, W) s            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
2 p# `: z0 Z5 Q( _            while (d != m - 1)
% e3 }% u) l1 l: \3 C% r3 t9 z% j) {            {
+ B/ E# H; K8 J5 j, c+ P/ T2 _1 w( ~                if (i == m && d != m - 1)
  K  U5 P) A( l2 p: z: }                {9 Y  s! ]: S1 c; w- T
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!, k& U# v- q" r( v) I
                    continue;
# E) o/ @+ k/ {% X                }
+ o3 o2 u9 a3 o2 n7 T                else
  l) _6 r1 A- l0 H                {+ C, h# T; T- T  p* E% Q* ~3 `" u
                    if (numw[i] != 0)2 M8 W" C& T0 _! Y# k
                    {
6 d2 R$ M! \+ N' F8 Z+ j                        i++;6 n, x1 E0 Q- i* w
                        k++;8 [+ N# w& x+ q1 _4 s6 _
                        if (k == n)
6 n+ Z& T( K0 W' l0 {! u6 I                        {
: M+ y) a+ P1 p+ I$ U! z" C                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
/ Z% O3 F2 P% d; q$ S0 S& Z! N+ D                            k = 0;4 W: }# K, C5 B9 c! V, m
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小10 X  _6 B% j5 s! M8 Q
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
! k3 Y& H6 N* s3 m" l" Z                        }
5 t2 D) ?4 M; w' a% [9 w$ N                        else//输出暂时还没有改变数组元素的值# l$ z* t9 L5 t4 D' d+ d" |
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
: s; j0 L( g3 Q+ {( s                    }
" j+ N: P- q, b" b' m7 [8 I                    else1 ?( Z" {; N! X8 h, [; a
                        i++;//数组元素为0,直接跳过,不计数。。。# a: ^; L  }3 Q/ ^! ?
                }6 G( {# d' e+ M7 P' h
9 ?. |1 l  ^8 D' ?5 J  `1 p
- M, q: u4 \" S. g  ]
            }//结束while循环
) W7 a" F9 ], v, [$ k            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦4 D7 |7 H  T- O8 K. m6 `! E
           
' S2 N; V+ U& [. {2 `0 Y3 l                if (numw[i] != 0)
2 P% C9 L$ s$ D  g                    Console.WriteLine(numw[i]);
" O+ Z/ y1 |+ s9 Z           
& B9 f2 b( C( G' W! U            Console.ReadLine();( F. u1 [3 C7 {$ c: E
        }
2 A" `  I+ \: p, I9 e    }, r, h5 T8 G9 L
}
2 v( j! j! q6 a1 i" {$ M% |& E  B
小甲鱼最新课程 -> 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-11-10 21:33

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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