鱼C论坛

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

猴子问题

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

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

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

x
大家好!2 I: i' K0 J# a! r8 q" f% W
这几天我在忙着编一个问题,我用了一种方法编出来!. e4 l; o# Q7 W
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, ]7 C- K; a( j
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 0 P+ M5 S4 z/ f. Z

* u# b! a% A( e) D2 }. Q! C& N$ ?  ~# p( i, u
                            题目; o; Z- J% y3 t$ I$ J) a6 f+ y- C
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。8 i) f6 n$ c/ }
第一种方法:利用循环链表% B6 e  P* ]! u/ n; b
#include<stdio.h>
! J4 L  v% D8 c' R% D4 D" j1 p#include<malloc.h>! b6 {& ]: |: f6 A: S8 ^
#define M 8            //共有8只猴子0 l& c0 }" }$ y2 h/ d- G# J
#define N 3            //数到3只时退出第三只( y# S! z, Z% |& [. i& x
typedef struct monkey1 n: w& h0 V- N2 J3 d( V' I1 Y
{int number;0 V  V& c, y1 N+ \& p5 ^1 ~
int flag;
& |8 X$ ?- S0 J$ I. X% sstruct monkey* next;
: |! ^2 l; ~  E& {5 X0 m}MONKEY;
$ F3 C$ H$ L3 j) wmain()
4 P( i* q6 b# J# {9 \/ x+ C{ MONKEY *head=NULL,*p,*s;8 \0 ?% [  t1 y; U7 r/ g
  int i,sum=0,count=0;
; l0 d' K8 f- C  clrscr();              //清屏
& z: |# N9 i; i5 E1 w  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
' c5 [  c# W- T7 K  p->number=1;p->flag=1;$ G* m  |# K% [) ~
  p->next=head;) v7 K7 ^& K: q2 Y, ?4 |6 _
  head=p;) I! g  U2 r/ l4 ^
  for(i=2;i<=M;i++)
' O7 o* S) r% \: E7 z& w2 u    { s=(MONKEY *)malloc(sizeof(MONKEY));' {; R7 e- l5 a9 R% I3 B
     s->number=i;s->flag=1;, A" w1 T  z2 I+ \: j# |
     s->next=head;( R0 W) k5 ?4 ]+ O$ ^, m3 O
     p->next=s;p=p->next;: v' P* S5 q6 e7 N* F( m
    }5 [4 V  v  D' a: v
    p=head;
% N& \) Q" X- Y: h. v1 }   for(;;)
6 E" H" P6 M9 y% j    {if(p->flag==1)
" G8 M' j: F, B/ [& R" Q       count++;& B! l% A- t; U- e
     if(count==N)
' x$ \1 r) H$ M        {p->flag=0;
5 \* ?1 q& \  Z# o! k         count=0;
3 S0 E0 T0 `+ P7 C: F         sum++;}4 h- }1 D7 f) a0 ~+ B
     if(sum==M-1)& y7 @7 V4 p( l9 g! ]# a4 e7 e9 O" ~
        break;
4 ~3 d, e7 S2 s6 Z" ]* {8 m  C* G7 _     p=p->next;
0 J2 o. p  `& P/ G& G; W1 c    }
& s' c6 k% x7 O, R    p=" o! R# \; W& Q" g; s
    head;
* w# s6 x+ f# H    for(i=1;i<=M;i++)
* M: a. k6 }5 h0 @5 e* k5 E    { if(p->flag==1)
+ t! W" a+ w5 h5 e/ ?* I$ n        printf("\t%d",p->number);" Y, k. _1 ]3 ^; D" y3 S
      p=p->next;
0 ]2 K0 d5 W' h7 h    }2 [/ z8 ?" w- R0 e

3 i; L0 s* \3 y" m* F! B3 a! S3 t/ `% a2 d9 N- q. m, n
  e' b- f- n) J2 w6 k% q- N
}

" ]' j& H5 J! g: U" _% N' {0 A. W+ s9 E第二种方法:数组
0 C) R2 v. r. @" P$ t/ |+ Y" j8 z#include<stdio.h>
) b8 t' g  P# u. F# s( N; v#define M 8
& R5 N1 a/ u+ r! d5 M4 |struct monkey
+ o% q! k, S" [9 L  \, Z: W{int number;# O- {3 g; n  r7 |3 v! }
int nextp;9 h; _# _; M% F# ?
}link[M+1];2 M3 X6 ~( k% S

6 T4 u0 c% F- M2 J9 S2 Xvoid main()
' j) U8 J, v, k  {, s! q5 F{int i,count,h;
: p& ~8 K  J1 M# cfor(i=1;i<=M;i++)
5 U8 q: r3 W, W( d( j" p. A+ B{  if(i==M); K0 ?! L6 J" R/ F" @
   link[i].nextp=1;
7 d  \. o- F. p1 E. F: w1 ^! |4 Z   else4 j$ ]) f% [8 W$ \, Y
   link[i].nextp=i+1;9 o2 H" [1 [6 n+ l
  link[i].number=i;6 i: L: R: e# [5 L: x
}
5 \) j' O3 |8 V" V& l4 N; A1 vprintf("\n");
: s) D" K3 c- \+ `7 M8 Mcount=0;. w0 a% {. S0 e/ u6 P, B+ a
h=M;
+ F5 g/ U9 U" v' Nprintf("依次退出的猴子: \n");5 S3 x3 x: E  w2 P9 R* ^9 l# ^3 I
while(count<M-1); N( [4 k! w$ m. p0 q
{i=0;! F# N$ a; J; C# B2 b' t7 F
while(i!=3)' \& \) |5 C) t' n, u' S# T
{ h=link[h].nextp;
. p( |; U7 t* R) o* |/ s# f0 l   if(link[h].number)) ~5 {4 p5 x( R8 Q5 _
     i++;}
" r9 [2 v$ F$ p1 Q, Q3 h1 h$ t# P% A' U3 `' B6 C4 E1 q: U
printf("%4d",link[h].number);" f, _" G6 `7 i, G* n) L
link[h].number=0;
5 b3 ]. ~9 a' Z) Mcount++;; F  b# P: e! \0 f0 {- K
}
- G& j' k' q2 `8 r/ `3 S
4 h3 c" G7 M+ E# y& y- _printf("\n大王是:");
$ v  q/ y2 G$ x6 q' R3 `  for(i=1;i<=M;i++)6 U2 k2 U5 R- S
  if(link[i].number)' C& y; X/ ~/ s$ N7 D9 b, }6 {
    printf("%3d\n",link[i].number);6 T" i6 b2 l  {7 s, u' t& Y  o
/ T- n% T7 w' H% W+ M" J
$ i, X( `( D" U6 E: i
}
5 X0 e. J9 ^, e3 D8 I
第三种是普通方法for循环

7 ], h/ |4 J8 ?. k6 [- b#include<stdio.h>5 g* u" t+ B  F% i
void main()
8 q: x0 G4 w- \( n- O7 v{ int i,k,m,n,num[50],q,*p;& L. @' R0 h) w; i
    clrscr();% q0 W# g. D$ `
   printf("input number of person: n=");
! {  T: k4 q  a- W0 {" \2 F& q$ d  B    scanf("%d",&n);
3 z0 p) w) G  \* }6 D; u! X, Hprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
1 c( D/ N0 l# g* h* K    scanf("%d",&q);2 L! T( A9 D( Q! {+ Y
   p=num;
# H) P, J. w9 h" N/ z+ L" k4 D  for(i=0;i<n;i++)9 c4 X6 e1 p8 E8 E
    *(p+i)=i+1;4 ~& @- Y0 c: {8 b& x% C
   i=0;; w8 t( U: l2 C$ g9 w5 ?  {
   k=0;$ l% _& Q# v8 [; L
   m=0;3 t3 K8 J% j0 `) x- o% N
  while(m<n-1)
: ^  ~( d" T; J: [1 B8 J" H   {if(*(p+i)!=0) k++;* @) z1 O" G; F% \% D4 ~! i/ \
     if(k==q)- T. C  |  `/ x
      { *(p+i)=0;
4 R$ h$ C: B2 Z2 l        k=0;* z, {1 ]' M& R
        m++;
$ B  i& l3 Q& Z: P9 H$ [& H4 W      }
. o6 Y8 H/ H: m4 y8 N    i++;1 C; R1 T% J# K- K
    if(i==n)i=0;. n' D" w, X2 i# O! Z% ~
   }
1 L$ R5 C* h3 H7 h  while(*p==0)p++;
3 X6 F+ N- x: |& y    printf("The last one is NO:%d\n",*p);
+ ?: n/ f( H% `7 g) z4 O) {0 h$ G8 i     getch();& b' c, o% }; k7 u2 x. `9 }
; Y: R4 J6 `* ]! g
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;/ ~' B/ d, Y. I. @; n6 c
namespace 又费马达又费电9 _# B' ^4 g' [0 Q% r' E
{
( S+ p9 v* ?. j2 }' q$ i5 V    class Program1 K) \3 U- y6 X  H* ~# ?( k
    {
% e6 t* M1 p$ Y8 ~8 |        static void Main(string[] args)0 J+ \* p6 l" _% b: {0 H! w
        {
( E% g" c# Z- g' R3 v            int m, n;/ i& D8 M/ m: Y" r/ `! p0 `% x  ]: i, E
            Console.WriteLine("请输入数组长度");
4 g/ h' e) {/ _6 o            m = int.Parse(Console.ReadLine());//m为数组的大小/ C; b/ c6 w6 `
            Console.WriteLine("请输入要截取数字的大小");
; B9 }5 r6 A: ~% p; P- {4 o            n = int.Parse(Console.ReadLine());: ^7 |7 a) Q. Z8 Y/ e1 [3 M, L
            int [] numw=new int, V% w) r  k8 J) h3 ], _: ~
7 U5 z' s" V5 _0 F$ r, Q
&shy;&shy;&shy;;
: U& R; x" {  x( ]$ w            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数% u* h( B- K; X4 h& ^
            {
5 B/ r, [/ w. B- @7 o" X1 g                numw[j - 1] = j;! z7 t1 M$ U) l, y3 {
            }
- `2 \1 m! K) s+ c' U& r0 F& E            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
: u+ ~$ |+ o: r5 K  ~            while (d != m - 1)
) P8 \$ z8 e* O4 C$ o( c            {
& y# }. a6 t0 o                if (i == m && d != m - 1)
7 i) F1 }. ~2 O1 V. E, D. z+ _                {4 y' P( `' |2 v$ H" m( a; @$ _$ y5 h4 ]
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
2 m8 z! V% b) r2 {  p& G                    continue;
; P, o4 K. E% j& g6 N/ ~                }/ ^7 P, }! X" X3 ^
                else
' }$ M9 x+ G  q! A3 G1 b                {) L4 I, |" E6 _7 q* o) C
                    if (numw[i] != 0)
6 r1 }( }3 U( s& D4 B                    {: S# K% j; A2 Z) t$ U  ^* z8 X
                        i++;; ~1 J% H7 [0 `6 V" h
                        k++;8 z/ ]1 y3 D% ]* D4 |9 P: K
                        if (k == n)$ O0 i/ k% E# J* Y. G9 a0 i8 `0 m) ^
                        {5 V3 P5 D1 _9 s8 k1 w& i# T; j
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
" _( X# {3 ~2 f/ d                            k = 0;& }. E# B# j5 R% c; C3 m! u( N
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
# ?* N& F4 w3 ]2 j& a/ g                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
  |9 Q" ~3 H- a* a/ O( L! `) |; Y: E                        }) R8 M2 ~: I8 S7 i1 G
                        else//输出暂时还没有改变数组元素的值6 ~! C! h0 r7 Q8 @2 }6 N
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);9 N7 h7 h$ R% R1 p9 s2 J
                    }6 q4 X9 v3 `7 y. g- V% E/ f( i2 R  ~# D
                    else
, t/ G( k. t7 ?7 d' s. n- p) s                        i++;//数组元素为0,直接跳过,不计数。。。6 f2 F4 j6 `' h7 [
                }
. [  t$ t8 A' g/ \% A  V ) R8 C$ k4 C* m2 y0 _  m
4 U% ~; F8 h' \+ A' g! k
            }//结束while循环* a  Q& ^" D8 c8 n
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
' g! t" i  Q4 Q3 m5 s7 G# ]           
$ e: n% o+ \1 D% }% H6 Y. u                if (numw[i] != 0)
# w; j: F, i  A1 Q' t# i( m                    Console.WriteLine(numw[i]);
0 S, e% e3 D0 g. ^/ R( f- k8 l           , }8 W( j/ x" A* J% Y0 l7 t
            Console.ReadLine();. \0 R6 n" W2 a
        }6 X" Y' w0 g, z" ^6 r# _) v+ ~
    }
* I2 F+ ?! O( l" ~' B}( J: t1 y7 O* o; P3 K
小甲鱼最新课程 -> 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-9-19 23:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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