鱼C论坛

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

猴子问题

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

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

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

x
大家好!
4 k9 [3 O8 q  Q7 R8 o这几天我在忙着编一个问题,我用了一种方法编出来!
/ ?: Z5 p+ }4 Q% s但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!8 G) y8 q) q1 h0 n4 b$ r
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ) W! `0 `1 y$ k" f

& k, O" H9 J* V: }2 u" m8 p: p: g/ S' J) }3 m
                            题目
, I6 N7 q$ t, A6 c/ e: I山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
; `  r- |: t5 J/ [第一种方法:利用循环链表
% U' h5 W7 j) g2 C#include<stdio.h>) q: r7 x3 Y: G/ h; l5 d5 G7 l# _
#include<malloc.h>! q4 g+ M# q. j  m
#define M 8            //共有8只猴子
- x% S1 d7 U) z* T! H5 n9 V4 |#define N 3            //数到3只时退出第三只' e; x+ h/ v- l0 R6 `: ?
typedef struct monkey- @5 T9 [. q8 e% {' R
{int number;
5 h8 m0 M. Y+ b& Tint flag;
/ Y& g% X: v& r0 m- _; a( fstruct monkey* next;
* h4 X# S! W2 H" A}MONKEY;
+ b+ C" f4 X% g+ _/ Z+ lmain()
7 z$ F: o1 v) ^{ MONKEY *head=NULL,*p,*s;+ ?+ A; |( o1 K1 A/ _* W
  int i,sum=0,count=0;* q* E* h4 m1 B/ N0 Y' o* \  r
  clrscr();              //清屏
8 F! r4 z% y6 W) E# O- I7 ]* |  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存+ o1 U2 L4 B9 F4 U0 n: W% m
  p->number=1;p->flag=1;4 @; W0 K3 l) ~3 _3 a
  p->next=head;# s- m. ~2 N6 t+ W" @) q5 U+ q
  head=p;
4 K6 c: Y- C, u1 f' e& U3 @3 e  for(i=2;i<=M;i++)
) g& V3 I. c, Q1 C    { s=(MONKEY *)malloc(sizeof(MONKEY));
# Z- l! x" C, c# T3 N     s->number=i;s->flag=1;7 t  g5 E1 s9 {4 {0 l6 }
     s->next=head;
0 l" o' u# j6 X: r& B4 n1 _     p->next=s;p=p->next;5 U' k7 H; U- l5 V0 N! H
    }% q( c+ A$ G- E
    p=head;7 f" M% R- i  t# \" A
   for(;;)* Q" k7 r# O; M' ~7 T
    {if(p->flag==1)0 c; a, M% b& B
       count++;: }. _0 [  v. V0 i/ Q: v4 |% w
     if(count==N)
" h/ Y6 R  k8 O0 E. e: I- G$ E        {p->flag=0;$ U0 g, C* n+ ?/ |
         count=0;" W# ]1 x: A# c. ?" V; B! r; Y  T% S" @
         sum++;}( ]( V' F' v% j9 G* @
     if(sum==M-1), {9 s5 Q, M( R
        break;4 y3 K0 H2 I$ c' P' j
     p=p->next;
1 Z& [0 d' [: r) Z) O5 k    }; Z4 m( {/ y0 u. ~' R
    p=
# z, q8 G; K; _! U- V# n    head;
( {! I$ s' N; D' r! D2 k    for(i=1;i<=M;i++)
. U; X3 ^; P* ?& h7 k    { if(p->flag==1)
8 R" J/ l$ B" Z4 n7 e; L1 r' V3 T        printf("\t%d",p->number);
7 l: F# T5 H4 M$ x6 f/ e. A4 p      p=p->next;
$ t5 r) @- K* j8 `- x. ]    }; A# M' j: G- Q( P% q6 y% c8 e

& u# Z# e/ Z9 b8 q
' P: @# S4 a) W- m5 m" H/ K% h' }  a2 @+ _  B; I( G: ~+ ?
}
. U; g& x: B# u0 y/ F' I0 l' ~
第二种方法:数组
: G, ^6 [5 m- _1 T1 Y3 O- ?, l#include<stdio.h>% F8 F& a" E* y
#define M 89 H1 n% i( F. j8 `
struct monkey
& M3 R! i! k* n2 `/ T{int number;
7 `( b3 {% q/ q" L: iint nextp;
' w+ z3 H7 u: ^}link[M+1];8 L3 c! V, |$ L7 H+ F

& {  W! L" d: s' c1 X0 f3 \void main()
* l0 H+ Q* ?. r4 z2 I{int i,count,h;
: X8 m: O$ }1 |. v6 |7 yfor(i=1;i<=M;i++)
1 ?3 \) Q5 D7 q* \/ [$ s{  if(i==M)" |4 B8 M' f" U( N
   link[i].nextp=1;
+ R8 C. `/ D+ N7 H" A! b   else
  e! i: P) p/ V8 e& H5 R* Z   link[i].nextp=i+1;
' a3 N" Z! T: J7 C3 U, I  link[i].number=i;
7 w- S& ^" [6 X, c, l3 H! ^}+ I3 M7 f7 Z, m* S- \. A7 V
printf("\n");
+ q3 V. i) ?6 h. L$ c; kcount=0;
  q. m* Q/ ]5 \4 p+ }h=M;, p8 z; o) Y- n9 Q! z5 ^. j
printf("依次退出的猴子: \n");9 _- s* H% p  w9 h7 \& D# \
while(count<M-1)( e2 Z- i1 v1 }$ R4 d5 ^
{i=0;7 ]2 v: D. J& T
while(i!=3)# n  J- l- A5 c1 \7 U! p3 ~$ U
{ h=link[h].nextp;
9 Y# B5 T+ ~3 T  J' u   if(link[h].number)/ e7 G8 f# \- M* I
     i++;}0 y1 k1 H4 |9 O# K( w; }1 Z

8 L0 n" P" h! s3 [printf("%4d",link[h].number);
6 i* F& E% G5 s6 ^1 r. t7 E+ Xlink[h].number=0;; o) Y& h3 k" y( E% P
count++;7 l7 a1 U5 r4 i$ u9 F) @+ ^/ L7 }
}$ n* b; l% H  F6 k* i+ \
# K! |- m/ H) l/ H8 k/ ?' ^: E
printf("\n大王是:");& W, I: u- {2 |' \8 ~6 w
  for(i=1;i<=M;i++)% R  S! w, O/ @0 B
  if(link[i].number)3 T8 V* h6 b' W, l0 z6 e) A
    printf("%3d\n",link[i].number);
) ^# [. @$ q' ]5 u7 h0 E7 A. X% p) ?) k' M7 C! \$ w% {+ r* {
) u3 A. s3 b8 Z3 ~! S+ a
}

! a# W5 Z" x( d' X$ h第三种是普通方法for循环

, E; k6 ^$ {+ ]- k" r3 @' i#include<stdio.h>0 M' G! t( E$ V, v: X
void main()+ F7 F+ a- f4 w4 \  K
{ int i,k,m,n,num[50],q,*p;9 V' _2 }( D( J0 _; e$ q
    clrscr();- l; O; @" F: |$ |( q% T( E+ Y( p
   printf("input number of person: n=");
3 D5 J! W5 w$ X, R# f; P    scanf("%d",&n);" O) M& _* W* s8 W, U
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只1 O, j1 ?! Y* R# Y
    scanf("%d",&q);
3 {5 O) V/ j; \  [& Q% Z- r   p=num;
' o5 b# K2 t* }7 G% L: q  for(i=0;i<n;i++)2 c2 l8 ~) o% a9 f9 ?0 j. D4 F% p
    *(p+i)=i+1;; r/ n' _6 D# H2 _8 c$ o* Y
   i=0;
% `# v+ |  r( l6 P0 Y% u7 ^1 c; F   k=0;; q5 t1 W/ l  ~7 \* x
   m=0;2 B. E1 ~" J1 U- \- ~
  while(m<n-1)
* M: X5 z  J) V$ V# [9 V5 `! R5 L6 N   {if(*(p+i)!=0) k++;& h. c3 {' {, I. M0 }' S' t) {
     if(k==q)3 Q" a, d+ B4 J8 t5 L! U
      { *(p+i)=0;
8 x9 \' k6 K  c        k=0;
* F. y' `! x/ y6 H2 a6 _: T( A        m++;
4 D$ q' M! S! {. v      }
5 T( j9 W( k* _: X8 C1 n    i++;3 U  q3 f) c2 b( C7 M
    if(i==n)i=0;
/ b4 n- _  o: x   }
  l7 W8 @' I! o  C2 r  while(*p==0)p++;
5 c' b' R; u( x$ j    printf("The last one is NO:%d\n",*p);& r6 K3 W: a9 `- A" f. q' C
     getch();0 h4 I) w0 _! G  z5 e2 n
& U! }+ _- X" `7 c
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;! |8 \, C5 e$ e* J7 ^  y6 u
namespace 又费马达又费电
! O" Y; g. u4 O& G+ g% l{
6 f3 `" M8 I2 V. Z* G5 a    class Program/ R$ e* y* e  M
    {6 Z4 F2 Q6 N7 {/ _8 K: @
        static void Main(string[] args)
" x- E( e. D& o% h. x        {9 a, x+ ^+ C' V: {1 z0 Q
            int m, n;' ?; F3 L. `3 f8 T  l) l* d
            Console.WriteLine("请输入数组长度");
5 w* |# ^6 Q  _4 @            m = int.Parse(Console.ReadLine());//m为数组的大小
& @3 x" T3 r' Y8 B5 w$ q2 d            Console.WriteLine("请输入要截取数字的大小");) F" t2 s& D7 C3 @' u8 n
            n = int.Parse(Console.ReadLine());
8 b& N* m3 w- d2 o3 |3 ^            int [] numw=new int
( h8 k( h$ |: U4 [* X2 \( t" x; N3 P% ~. r2 c/ b
&shy;&shy;&shy;;
% p0 z3 H( ~+ ^* f" D            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
% H0 @/ S. i* l/ Q3 b4 f& Y& a' X            {4 E$ Y- V  k3 ~) D" Y  S4 k  c
                numw[j - 1] = j;! h. C. G3 z& b  z
            }
  D$ K5 ^% t; f            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
" u% y" Z' s$ z            while (d != m - 1): P9 t! J3 m+ c+ s# T" @
            {
; t+ M9 E/ g+ u# T- w0 S6 N$ j                if (i == m && d != m - 1)1 K, G- T0 v) m
                {7 B7 `. w& T5 b6 m- L5 v+ a& z
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
: Q1 B! V* E7 v3 G7 j                    continue;2 Q, ?8 q6 [: j( C  F0 j
                }
' T( d  \8 z; N) {                else/ v' r" r! o8 N0 ?3 i" V2 h$ v- i
                {
: c  Y+ P+ B/ ^" p" w                    if (numw[i] != 0)
: s3 O0 s. f$ N                    {7 t5 [% t/ ~- F% c* v" M# j' d
                        i++;- a  X, P( [( e9 S' g% s( G* M
                        k++;
: p* w+ z' h: a) z. @! n                        if (k == n)
  Y( J0 P% }9 ]) e: O4 ]6 `                        {
; m  j& y. ?) ~& \                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
0 y$ A, a/ j8 p. q& O1 J                            k = 0;
, C3 g8 F  E! p) n* K8 v# t8 f              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
  O7 s/ w# y3 G) B& l; h: T                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
+ Y: N) r+ p) k% z+ Q" U5 u                        }
6 ?6 h/ s4 g( H: I7 ^% D                        else//输出暂时还没有改变数组元素的值, c. O( F1 S, L  m- n
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
9 K0 Q+ o& d! U! N3 `- T$ C- ?                    }
; V! M" j* D# J; d$ ]" O; \! m$ z                    else
# |' g2 a" q2 l$ A                        i++;//数组元素为0,直接跳过,不计数。。。7 Z  Z! Q9 r" P# E$ f
                }
4 W0 }: {; ^/ ?# y
' U" K( B# k% w; m: s# [
! D; Z3 C+ X. |0 o  p/ P            }//结束while循环
1 X3 Q) |/ C% D' `% B( ~            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦" q& D1 d, z$ \' N& w  p
           
3 ~( d6 g% g) h$ Z% L                if (numw[i] != 0)# |$ h* J# S6 G. r% D$ R4 M
                    Console.WriteLine(numw[i]);
+ d0 b) f. p8 J1 P           
& l' h/ U2 n3 _            Console.ReadLine();
5 a* X! ^' v. q0 F        }
7 T+ _" o+ B; r) @; [' w4 ?    }2 m6 ]5 K- a) c" a2 V
}- e( [# W' c0 T4 c2 F8 ]# @
小甲鱼最新课程 -> 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-2 03:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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