鱼C论坛

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

猴子问题

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

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

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

x
大家好!
4 z# s: ^* k4 f7 T( I这几天我在忙着编一个问题,我用了一种方法编出来!+ p& v9 P. s- t" L  H
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!: `/ I$ o$ B0 i. }- m' B
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
) h2 ~* r7 p. ?: L" R# z0 O, g; n1 a- V; @

$ ^. g  n6 E! r+ f; _4 @- _# M
                            题目
9 I1 G+ S+ d$ N. L" p+ I0 f4 h山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。+ G; e5 q$ T+ |  d. C/ E
第一种方法:利用循环链表
( v3 M: G: ~+ z  a: y#include<stdio.h>
. R$ T! o2 ~, D4 S6 |8 F' S#include<malloc.h>$ ^( D9 K8 t+ K! m
#define M 8            //共有8只猴子% [. ^1 p5 B7 |& m# Y  P
#define N 3            //数到3只时退出第三只8 R5 O1 ~$ y% d: k7 z
typedef struct monkey
, }9 W, m4 p6 _. r, A{int number;* K  r2 Z/ W1 P7 n. \  n1 Y' K/ q
int flag;
/ v7 G1 I/ ~( Y" p" H2 H) H. kstruct monkey* next;: w1 w4 w! b5 a: o  k5 z
}MONKEY;
9 @3 w* e3 [6 t) |main(). a& F# l; }: y  `* ]' I
{ MONKEY *head=NULL,*p,*s;
! b  E6 T. u2 M; m: T  int i,sum=0,count=0;: ?1 y3 N! B' T( W: E- ~3 w. ?; G
  clrscr();              //清屏
3 V' Z$ L( w, i$ w# ?  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
$ z. A' C1 N5 Z8 o  p->number=1;p->flag=1;$ L# [- _2 f0 \& q, g
  p->next=head;, [. M0 b9 z: C- ]( O$ z' Z
  head=p;
4 h& s, h3 f9 E1 i  for(i=2;i<=M;i++)% b# R1 K! d% Y& A
    { s=(MONKEY *)malloc(sizeof(MONKEY));. X' k- x( H) b2 @: X
     s->number=i;s->flag=1;
& r' }/ k2 z" e( g) C     s->next=head;5 ]8 R* [9 _" y* _
     p->next=s;p=p->next;
1 X6 x6 b, P, p& n. H    }
2 f/ E, J8 b5 L' t, v7 G! }    p=head;# l3 m9 l- m. A  K
   for(;;)
$ l: M" |+ ~( w9 @' b! z    {if(p->flag==1)
' T3 S' a8 A1 i& e2 `       count++;( K1 d3 C! ?+ x# F0 s6 T5 c
     if(count==N)5 D4 [- X8 W( Y# q* y/ X- ~
        {p->flag=0;0 ^/ F; p, }( o' _4 R/ o
         count=0;, L" f! [- J" g2 @
         sum++;}4 j$ X1 c7 ~. x4 Q
     if(sum==M-1)
, e8 Z/ c2 D6 k+ a% j- G) S        break;
5 L4 l. Y8 I2 N- q3 ?/ S1 h/ v& A     p=p->next;
! A. Q' F" f8 i' ?$ C    }  e6 W7 l& V5 r7 i1 E+ }
    p=
: X' U4 s6 P$ Q    head;5 ?& a" c% |9 M3 F0 U
    for(i=1;i<=M;i++)
5 O% o, L- B; B1 u  @6 ^    { if(p->flag==1)
1 q' D2 q, I0 Y        printf("\t%d",p->number);
9 G; u0 ^, O- m- I      p=p->next;& b' F, m! g$ H* A' G1 e' g  f, H8 C
    }2 |3 V  c5 F# d" m8 L7 U! f

% Z0 y3 }5 h' @2 m# s
6 V% Y5 W! ^0 H8 @; J& c) O0 S7 V8 m! l# W% |: c
}

$ B  m/ o  e8 N- e( t1 C第二种方法:数组/ o0 i; B% Y5 x) _4 j
#include<stdio.h>$ ^5 @& f# @5 I. s  V4 v4 T
#define M 8& x: s& o5 {: X, n  }0 x$ R
struct monkey
  }* j; X  g! J/ A2 i* p: w2 n{int number;; j/ [/ i' |* u) A! x, S# T
int nextp;4 D% w" e  e7 O9 m8 o5 P3 ?& X
}link[M+1];( k1 r- G3 o  }6 C7 \

) w: o, l9 [& Q3 N* ~5 mvoid main()7 V; v5 {; k. U0 e' k0 P% `7 W
{int i,count,h;7 a' @) `. X/ H' ]4 @
for(i=1;i<=M;i++)
# C0 i$ Z( F* p1 I8 E# U- \5 I{  if(i==M)7 X! S4 P# L% i- A- `
   link[i].nextp=1;' _& l4 ~# Z& P, F9 O/ `5 R
   else
+ ]9 Y. K# h. {4 |* ?   link[i].nextp=i+1;
  O- n6 a( g2 X3 Q  link[i].number=i;  D! i2 s6 [4 |! D& N
}
$ x5 Z! Y/ E9 O6 N* Nprintf("\n");
+ T% D  n: }4 a# p/ c# p  }count=0;
* J$ y0 V+ K, y# {& P, ?. dh=M;
1 B; k. v0 w9 P: B8 Q0 Mprintf("依次退出的猴子: \n");
/ F- \7 m; W/ [2 f. D* {' J) `) Y$ ~while(count<M-1)6 K: y0 C' ^. T! i, ~9 z, u" @' N4 m
{i=0;' Q6 F; r/ L7 D2 A% Q# p4 c& _
while(i!=3)) x, C6 N# \6 q' Q3 P
{ h=link[h].nextp;! _8 a7 r8 [3 g% \
   if(link[h].number)4 F& E7 W( }2 [
     i++;}/ c" F) y0 m9 j( d7 n
) ~  K6 X* @7 z  E
printf("%4d",link[h].number);0 B3 I8 q1 c, T
link[h].number=0;8 }! a" |& G/ t
count++;8 v2 Z( u* H; r, A, V
}
; e! U9 }' H8 S8 q: P# \. Q  l$ J, b
printf("\n大王是:");
9 D8 e1 e6 X" ?8 o3 w% U) B  for(i=1;i<=M;i++)  h% Q% X0 n8 q  v) O8 L, C
  if(link[i].number)2 n3 I( E2 ?6 N' ^
    printf("%3d\n",link[i].number);& r  G. Y. z* p) ^1 ?

& L$ t( s- u- \+ C( b  s+ F
9 h. o. n5 d: o' e( e}

! ?1 ?1 r1 N& c+ M% c  s2 f第三种是普通方法for循环

- t4 O) K& v- ]3 ^- E#include<stdio.h>
8 K# A/ _7 W8 x  |void main()
4 L: U9 H8 M6 c: B2 |3 I) W{ int i,k,m,n,num[50],q,*p;
4 b$ T2 c. w; ~    clrscr();
$ ?# W, M( J; c  l" D   printf("input number of person: n=");
- M7 ~% J, m' _" r" p7 `    scanf("%d",&n);- S8 d$ R5 j, w! A
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只" b; L) o7 F4 G4 ^3 |/ x
    scanf("%d",&q);
# Y* {$ _' i# ^   p=num;+ _  ]" `1 J& F% u0 {/ V0 C
  for(i=0;i<n;i++)
3 ^' {: w. @2 w  y    *(p+i)=i+1;
  u" D0 T# V8 U- \' A' s   i=0;& u0 f+ Y5 O& e, \: K: {
   k=0;
0 }7 ]6 K; a" r8 i3 s& Y' Q   m=0;
% r+ d" p9 s5 A  while(m<n-1)
6 J/ y" ?" }6 x" s2 C   {if(*(p+i)!=0) k++;8 V1 O2 Y7 y4 a) k) {/ ]9 @8 q
     if(k==q)9 r5 }. \) ]$ F1 t  _" o
      { *(p+i)=0;
8 R+ T- x' k2 W( v- t, {        k=0;
' l/ `( {5 U9 E# @        m++;
- m# d- H/ e1 P6 g; Y  B      }
6 C  r. g; a& M( L    i++;2 v; N) N) p4 c2 g8 ]& C/ \
    if(i==n)i=0;
0 J6 t$ E+ b: B0 y" O+ ^" {   }' P7 L% V8 r8 t8 o5 `$ e, S
  while(*p==0)p++;
0 J- n0 }$ s7 w; X. `    printf("The last one is NO:%d\n",*p);
+ g4 U1 {5 Z$ _; ?! |: d     getch();
/ a7 `+ e, ^0 m5 n( {
  q5 w7 z3 I. I) R( J# }; l2 B}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;) @* I( I  m( Z: U0 v
namespace 又费马达又费电. @" B8 E9 `' V. e' Z3 f7 Z
{
8 h( B  B1 M' T0 p4 `6 S8 h& L    class Program' X  t" Y" g3 S3 `, h8 d
    {
, x; ]8 `. Q) w' K        static void Main(string[] args); G5 w! d5 E, i# q  g- G& ^
        {
! u( b& I$ b( o  w# W; V            int m, n;
; \8 ^7 Z$ r% m            Console.WriteLine("请输入数组长度");# L; a. e& q- ?( [& \! \) d
            m = int.Parse(Console.ReadLine());//m为数组的大小
; _  D- M4 A% Y' Y            Console.WriteLine("请输入要截取数字的大小");
9 w5 n& o/ n9 F: }0 R% b7 D" K            n = int.Parse(Console.ReadLine());
( Z$ B" t! ]/ }/ V: e4 u            int [] numw=new int
" p1 U( C$ C8 j- h. B$ X3 f/ Q; l( N& m# Y( E
&shy;&shy;&shy;;
+ }7 _7 D/ u8 v, j0 m: m0 A            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数" R  A5 U2 a6 e, @5 A) |$ `, G
            {( t- l9 f9 v& I  {
                numw[j - 1] = j;
: W! A7 _4 h" O, D" v. I: t            }
& Z: f- P' {  C- `2 T4 F            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!8 N, ]; N8 k$ o1 Y  d
            while (d != m - 1)  W$ |% x+ D5 H" L) l
            {. s6 F* L9 w9 r( e
                if (i == m && d != m - 1)2 z2 T9 M$ U, Z: u8 M2 _/ A
                {
7 h% R$ p: {3 k6 _                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!. ?. ]  K1 R. K; z. F
                    continue;
, Z* s/ R. W* X. p( m8 h) S                }2 a- s' d( s7 ^7 b4 C/ r7 ^& c
                else% J' @% ?9 V" ^8 h
                {
( D& F0 {8 B5 w) ~! f                    if (numw[i] != 0)
2 h: U) d* Y/ |( l) \6 S                    {
7 b1 B8 F, ?2 a) K! f+ C# K) [                        i++;$ \. q2 u0 U7 [! x
                        k++;9 Q) R/ ^+ ]3 I5 W% n. N- E% E
                        if (k == n)" X; P# U( N$ V2 y, V! j
                        {
' p# c- _' L& H( y( J) P$ r                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
& o: w* c, X+ a. g( d  N, j: s                            k = 0;
+ v$ m9 X- S% h0 v/ F2 R- Y5 l0 ]              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
  e6 I! c/ R* q- d0 V( `                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);) R1 d! `0 ]/ q5 M- e
                        }! j+ t1 N% X6 t9 @; ~0 _& S' p( s
                        else//输出暂时还没有改变数组元素的值
) \0 N8 S# K9 {; S: _; ?: _! U7 M                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);  O- j$ w) h( u, v* ^
                    }. ~/ ?3 L" z/ ~5 G, Q7 C
                    else
+ E# w8 Y5 D; H, X$ k4 e1 ~                        i++;//数组元素为0,直接跳过,不计数。。。
, L0 w" l( G& v* L. |                }
1 @% g, s2 N1 P4 z8 C ) O" f1 I4 }9 j1 X" f

6 L- U  ]! A% t5 t            }//结束while循环
" n( Z. w. [; J  S; B            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦% b1 g3 d8 I7 R* E0 Z
           / D. W; g$ c# b8 ^
                if (numw[i] != 0)/ u( N& `$ k% ]1 X/ `
                    Console.WriteLine(numw[i]);# ]8 h) ?& G1 L" I: f: T
           
% i: a* S! _2 J0 [! z5 T8 k7 `            Console.ReadLine();
: Q0 g6 w5 L. i2 K4 C7 `8 s9 D        }$ z9 n3 c7 a/ ?
    }
2 E; B$ T% ^( J, A4 M}; j7 e6 g* M* `5 o, o8 |
小甲鱼最新课程 -> 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-2-12 06:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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