鱼C论坛

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

猴子问题

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

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

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

x
大家好!
7 K# F6 w; [+ A这几天我在忙着编一个问题,我用了一种方法编出来!
/ Q' J$ X; O& ^$ x8 Z但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
+ J, |& M8 j; N! w- Y' e注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
/ b: v* s5 D6 c: p
1 m5 ~( V5 S/ S8 C( g6 U4 n4 f- l  R
                            题目6 x# e, D: D, O" X8 ^
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
: E' E0 j, E% s4 Z; }第一种方法:利用循环链表
( {: S# [" Q5 q( `) _: F#include<stdio.h>
5 z( [9 k7 e4 r  t7 j: I#include<malloc.h>
* E6 }. l! }/ `* j: |8 B1 ]1 W  J#define M 8            //共有8只猴子: ~  P+ m3 i3 \( T
#define N 3            //数到3只时退出第三只
8 t6 L, ~# N5 q5 ~( [! i' atypedef struct monkey
- I- r2 U% M# e$ E{int number;
* |5 |7 w  J! P5 f+ p3 w' zint flag;* O+ B2 H; ?* l- s/ l; |7 ?
struct monkey* next;
# r0 \9 ?9 e- G# X# ?. X}MONKEY;8 [6 `7 y7 F. n
main()# s; G1 e" s0 S" K
{ MONKEY *head=NULL,*p,*s;
4 @) Q9 E7 y9 G% u  int i,sum=0,count=0;! T+ l. H' V7 U  ~
  clrscr();              //清屏
5 e  G! [7 Y4 \* T2 d! a/ e  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
2 x. m% H6 M$ R3 G  p->number=1;p->flag=1;$ d% U- C* s0 |' Q6 g
  p->next=head;
) G3 w' m4 ?0 o& r) U  head=p;
; I1 p; Q9 P# B6 e5 s  for(i=2;i<=M;i++)
6 }7 E: w5 R: v3 M2 _    { s=(MONKEY *)malloc(sizeof(MONKEY));
  U) E5 u( H. Z' s8 ~$ o     s->number=i;s->flag=1;) a9 b" i6 [/ h3 e1 \+ b
     s->next=head;9 E9 U0 J% U1 Y: ~: L/ ]
     p->next=s;p=p->next;
+ ^/ l/ ^# F! a4 c5 f    }
0 o  }+ d  {( d4 h7 G8 `    p=head;
, Y, e" I( I, J  U   for(;;)
5 u+ m, u  @) L" t2 J3 ~    {if(p->flag==1)3 H/ ~8 g& |* C
       count++;
: L6 Q9 y1 `0 r: i( }     if(count==N)
8 q5 \2 Z" A! U3 }5 b        {p->flag=0;
; r! j5 Y  _, u1 H; @         count=0;' b) {: r2 D: C% {
         sum++;}% A' r6 z8 E3 ^. Q! p% }
     if(sum==M-1)
0 h( n! l/ f% W* v) {        break;
- W0 V. ~/ v: u6 S     p=p->next;
- O  [* v$ I4 J    }6 P* M( l& \* O. L2 G$ s6 i% J
    p=5 z0 J7 i+ M- [7 A
    head;
7 G* Q& `& p1 _: I" F6 w' h    for(i=1;i<=M;i++); x7 w. u( `" e" X
    { if(p->flag==1). u3 q) X. ~6 m' ]
        printf("\t%d",p->number);* v! c! _+ T) W  ]# `0 A
      p=p->next;6 e7 V( W! `  x
    }
  @6 z& f5 }6 z3 m7 q# @. B& X0 g! u1 P% @4 b! N
6 B1 C1 z8 x7 s
5 x5 {! t1 k% J
}
. m% h+ Y. J3 w: k) O
第二种方法:数组& B% o5 h6 G% y; B1 K
#include<stdio.h>- F3 i8 A9 L7 T
#define M 84 }3 B8 @4 z/ _$ N, _3 U
struct monkey
1 b% W* E- }/ A  p. @) r$ x2 [{int number;
) T( X9 ~8 w! t/ cint nextp;; [4 e- P  u; y9 M- w  N
}link[M+1];
' q# _) v2 k! H  N8 J( k/ ?6 A, B; |2 `9 I7 |6 M
void main()
' n2 f4 l( x0 m# x{int i,count,h;
+ K8 O0 F2 g  K# jfor(i=1;i<=M;i++)
& {. l% f3 ~5 s2 P: y* h/ o{  if(i==M)( G3 G/ r$ n" T% I
   link[i].nextp=1;
4 a7 j- ^* O( C2 h   else
2 P9 r& `2 i$ z% `' a% I   link[i].nextp=i+1;+ C- m8 ?4 o0 l% B
  link[i].number=i;
( m3 u  g2 E1 u8 j1 d9 e* t}" Z  Z) I$ h" P( W& ^- y/ @
printf("\n");
4 P" O) q- E8 V5 B. C+ x' Mcount=0;, I5 U- `" d" f+ Q$ d% ~
h=M;2 t( u9 @1 I+ k- s# n3 P2 ~* K
printf("依次退出的猴子: \n");
' P; i- s1 V! `8 z, L- h4 D( s! zwhile(count<M-1)
- @" c) b4 H7 _1 z5 `, Z{i=0;/ _6 }' u' b, k6 o+ L0 I: R/ \( W
while(i!=3); G" H8 r5 O. p: Y, q
{ h=link[h].nextp;
+ e2 O- {- y# [/ r& I# [$ j. n   if(link[h].number)
2 S% f/ e, C8 i) }& i     i++;}
: {" s. s4 [) _' Z6 `' F8 u+ I0 P8 P7 z  M; Q
printf("%4d",link[h].number);
+ x: j5 ]' Q& a/ h$ X5 O5 j( x6 blink[h].number=0;
' C* p& ?0 c1 n* acount++;
0 y' V+ n- ^" `) ?7 a1 t}' \  f6 d* Y$ }/ k. l
0 s: I. Z  G! o  t( f" a8 b
printf("\n大王是:");
1 e. o) l. y/ M1 z  for(i=1;i<=M;i++)# ^) T; v  p( \) {" g9 U1 Y
  if(link[i].number)
8 o8 o/ i! {# \& f    printf("%3d\n",link[i].number);* w# C# g; x" _+ n

! P) l. ]/ k( R2 ~1 k4 B% u+ a2 ^, {& l& `" j5 f% D$ w
}
5 _) h6 R1 Z, ~0 D# z6 y) x
第三种是普通方法for循环
* o/ w; v& h1 X
#include<stdio.h>/ b; `7 V, W1 s; S5 D  j' @* t  P
void main()
7 X' t9 U0 i9 \$ N# S3 S) Q, }2 O' \{ int i,k,m,n,num[50],q,*p;1 L2 K, \: x' z; l
    clrscr();
* U" ]9 h7 G# {& n: u  A; E   printf("input number of person: n=");
% K# H2 _' x9 r( k4 D( A    scanf("%d",&n);
  [1 i/ P0 v5 o! F# r$ xprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
, i4 S+ i1 s; }) i) ?    scanf("%d",&q);9 a& a, Y% Y' Z; K9 L0 r1 j/ L# K
   p=num;
1 s6 i7 H! M) H/ x2 Q9 Y  for(i=0;i<n;i++)
$ E: t& h0 n& N9 @/ u" v    *(p+i)=i+1;; F* W, Q5 }* N" r6 y. ~& u
   i=0;
& v$ k7 M1 t  w) C5 b% O   k=0;6 Z8 i7 i  Y7 s" Q3 @; x
   m=0;- b8 g" e# Y, L
  while(m<n-1)  N: N5 Y0 H7 R, W! S& V
   {if(*(p+i)!=0) k++;, {2 l' l: `' E0 G! V( B* G
     if(k==q)3 L0 A$ j: A& ]9 S' ^
      { *(p+i)=0;9 G$ K& M3 B. j, i, D8 A
        k=0;" f$ \. t" T  X/ |( L
        m++;
2 c( k# y- f. x- O' F5 y- L% F% t      }
6 c! ~3 V. q' i9 ?7 ]    i++;1 t9 k! t$ U$ g, m, s8 [
    if(i==n)i=0;
1 }4 O- h$ i0 T3 t% M   }& _$ v( o1 L; w1 O. V# U
  while(*p==0)p++;7 `! b* p, @* P- ?. K. h# O* X' j
    printf("The last one is NO:%d\n",*p);
4 b4 ]! F% V5 s( H& \     getch();
: t4 \% Q5 c- s2 k1 S1 U6 B1 O0 j. r
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
" I! l/ o% Z5 x1 C6 [namespace 又费马达又费电
' u0 |3 U8 X1 [) J% Z& U3 N; {{
9 @, n( [( b% D: b/ e9 A. W    class Program
! |% C$ q1 n* ?7 e- F0 w0 y    {4 v) g- m8 U+ B9 s
        static void Main(string[] args)
% J. N* ~6 q4 H, _1 t        {
: B+ D8 h. P3 ?% K9 t            int m, n;  r6 V' L9 g" h0 ^+ v
            Console.WriteLine("请输入数组长度");. z  D5 G6 n& T( {
            m = int.Parse(Console.ReadLine());//m为数组的大小
+ Y& W, I2 p: X4 n            Console.WriteLine("请输入要截取数字的大小");
' p  B: l& N1 |            n = int.Parse(Console.ReadLine());
+ }# L6 t- R/ S& U8 T: F            int [] numw=new int" c9 X9 j' E6 y! {/ V4 y
! h7 F' l: Y$ k' I& M: F# p
&shy;&shy;&shy;;
& {8 l$ O5 K1 J. W! R( k+ g8 @            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
* n! I; S& P. g5 \2 z0 R            {! ~+ U2 W* a: k1 o( l5 j
                numw[j - 1] = j;
( G" b' j6 D( P            }- _+ q7 @) S: n% _
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!3 B- n  X- q9 k) Q# n. s5 E
            while (d != m - 1)
7 l+ B; t  a9 c1 \5 V8 `            {8 s1 {* p" Y! P2 x% ]. g
                if (i == m && d != m - 1)' }0 Y5 N  @- j/ ~' q
                {
( H7 s$ j# _0 h8 D) [' N                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!; I% u  s0 e1 X
                    continue;( ]# r7 Y/ x5 G) y
                }- g6 i7 e% V' C* \# f! V: e5 ]
                else
8 \' d. t# I6 p; h9 R5 J; Z                {/ B7 E& @& w7 E  G
                    if (numw[i] != 0)
' m7 D* Q" p. m5 a; m4 s                    {# F5 J. E+ L' D
                        i++;0 s0 L7 D3 h+ j  \$ r
                        k++;
5 S& R0 P' q- u- _# [: `8 s                        if (k == n)6 {5 i; o1 t- u: p* m: K' o
                        {- F" j5 J9 g7 O9 P: F
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了6 F+ ?- a3 N4 F$ ~: N: g# u
                            k = 0;
, y$ _) m8 y5 n* _              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
- g" m) T$ I, q1 k- s8 x0 @3 |  G                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);0 ~( H3 r5 @+ ]5 ^
                        }5 N, D; t; S: C1 m& @
                        else//输出暂时还没有改变数组元素的值
" y) J& \+ e; N- G2 ?- l  b3 m                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
5 d" P1 T  A% ^, D, F+ c; i, [                    }
+ Q2 n1 J! m0 u/ _, g- g                    else
% J) b0 P3 B' o2 {                        i++;//数组元素为0,直接跳过,不计数。。。
% H& F' m, |# F9 m( ~                }% Z. y4 S% e# \0 ^3 S* h. d1 z& v

3 V- N( d* w% N; J$ s: X
7 C( n' d: O% ~            }//结束while循环, ?) A/ K" y3 D. L/ I; @# X- I3 U
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
/ o% p, G) ?, s+ x' h           ) ~$ ^0 [) X- a+ A& H0 i
                if (numw[i] != 0)# E2 P2 N, A, r# {3 F
                    Console.WriteLine(numw[i]);
( j% c) @  j9 N% i0 h, T           
! F( m5 {" i+ D6 [            Console.ReadLine();+ T) e5 m3 f6 I8 U" w* L
        }3 L: q; q! M) B5 e# Q) Z
    }
3 ^9 [# r' s+ g$ N8 R6 k7 t4 o}
7 F- B. t2 d7 l# y7 @3 C) D$ |) ]
小甲鱼最新课程 -> 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-27 19:35

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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