鱼C论坛

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

猴子问题

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

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

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

x
大家好!
. Y! f; n, d4 B3 K这几天我在忙着编一个问题,我用了一种方法编出来!" {2 J8 [+ k+ _7 c: J5 D) S4 f
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
+ Q; O5 w/ c8 e6 H" s; e注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 . J" y9 Z# }! X3 n; v& ]
+ L+ a* _- e2 f: z. {3 q

: e/ u: b( N* \( Z0 F
                            题目
) X5 h, L% N  l( f山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
1 M( `, x5 ~2 \$ y" C+ m第一种方法:利用循环链表3 u2 e) c$ _% U; ?3 e% T! m. `0 [* r
#include<stdio.h>
7 h* Z2 R- {& E#include<malloc.h>
! }" y6 D. C. P* ?* N% }8 i+ o#define M 8            //共有8只猴子
! e/ {4 _) w* }9 X4 }4 y# Y' S. N* @#define N 3            //数到3只时退出第三只  O  F1 A3 J/ J, T& I6 @
typedef struct monkey
$ A  x) B) D/ ]{int number;# t0 R1 N* F+ ~# u, O4 B
int flag;- V7 O" J5 R/ L2 K* Y
struct monkey* next;
7 B  ?  E) i+ d5 }}MONKEY;3 X( x6 o! {5 j+ D  h" I8 z
main()
7 ~7 ^! l/ X) ?$ h4 Q{ MONKEY *head=NULL,*p,*s;- m. |5 z" K; X+ D- T$ i* l, l- Q
  int i,sum=0,count=0;# H1 F1 y6 R! n8 l7 M0 M3 x
  clrscr();              //清屏5 M0 B& K  i( e5 l
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
0 X3 s6 B+ ^! _' X: W  `1 l$ S1 Y  p->number=1;p->flag=1;
8 O7 l1 f6 d" U7 g9 N: p7 H: h  p->next=head;
: U; q) u* W( ~  b) b' G3 [6 g* [  head=p;
% _, i1 a( o6 q( E  for(i=2;i<=M;i++)$ k" V+ T2 ~( ?% V# a8 y4 J
    { s=(MONKEY *)malloc(sizeof(MONKEY));
9 D9 k( W2 K- I1 U7 W7 p2 v     s->number=i;s->flag=1;
; |3 `# b, W! ]* \  f  H     s->next=head;0 a. g& c2 ~' i& m
     p->next=s;p=p->next;# K4 g$ G* Q/ D& z; W  {/ L
    }
( d) ?2 ?2 s" g# b8 l    p=head;+ k# w. ^7 r* M& b2 X& `) D
   for(;;)( J, N3 F) e+ a" Q6 ?
    {if(p->flag==1)' _( }3 X, ~" e
       count++;) v6 [1 ^: m' d  e6 D# X  r' t- F
     if(count==N)
  T+ Q0 u! h7 I9 I        {p->flag=0;
( ~: X( L. B% K, s         count=0;3 w! Q3 z& I+ {2 e
         sum++;}1 _0 r& u0 |1 M9 d0 N
     if(sum==M-1)2 c# k4 s2 G" k0 z6 @, m' {* }/ u
        break;
9 U1 }2 m/ v! M     p=p->next;# d: C4 K' V0 ?* F5 H
    }
: d# }1 A* \- F6 @& S3 ]* {% C6 o    p=$ n. [# ~0 I9 ^- P
    head;
- ~4 M2 {5 P9 I    for(i=1;i<=M;i++)6 [+ |7 E7 s1 C+ p% h
    { if(p->flag==1)
+ ^$ o, M4 C% z        printf("\t%d",p->number);5 A, e  [7 h  ^1 C* W( P
      p=p->next;( _; L- w) H. W* `0 T
    }
# |+ G3 f: e+ \& d# l, l* Q6 d/ J6 z7 B

. q( O% A9 a- c( x5 h% e. ~- \( b# [1 U  @; F
}
% o' p  ?' h5 ]! h0 k
第二种方法:数组
+ U9 |$ H1 b, {4 X! Q#include<stdio.h>
8 k4 ?& N& T7 N#define M 88 z6 U  h% P# ]% j6 _; A
struct monkey
% I3 k3 O" ^  [* H* d+ c; H{int number;4 v$ [3 I/ X* h6 ^) J
int nextp;
5 {& e5 ~0 d, c  B9 [+ z" l9 U}link[M+1];2 ?. m& E' e6 p( Z) V: C

% f$ I/ `3 q  u8 o( W2 _void main()$ I0 O) a3 R' e- P4 l0 B  ^4 S
{int i,count,h;
) p: h- M; ?& l  u1 R& jfor(i=1;i<=M;i++)+ H6 F$ j3 t% v3 w, z' Q; x% g
{  if(i==M)9 T2 S' s4 u" k) W  o
   link[i].nextp=1;. c* D" m9 g  l4 [" L5 ?6 b
   else) Z6 p' `9 v2 W. Z6 j. A, C
   link[i].nextp=i+1;
$ x- m  J' d8 _7 O! O0 F3 N9 D% j) t  link[i].number=i;3 z8 D) C; O4 b$ U7 P  N$ I
}
* C0 R. N3 A7 T6 `printf("\n");4 T; p9 G1 R3 k. t
count=0;
- p3 Z: Z% r! y! U1 n8 eh=M;- N" t$ c+ d6 C, _; O8 ]+ _
printf("依次退出的猴子: \n");7 I7 J  b  y$ d- k
while(count<M-1)+ Q$ \- _; I4 {7 L2 N# P
{i=0;+ [6 t# |1 G1 h" \" a
while(i!=3)
! J# {( `- s* k8 m' Y) \7 a$ {3 ]{ h=link[h].nextp;' n) Y0 B6 R. [+ x; b# q" }( }
   if(link[h].number)
$ t- h. S& D/ H$ K; @4 y     i++;}
1 F* k' ?- @/ p& l2 B2 \! D! ]
; |% k" _3 Q. Q9 Dprintf("%4d",link[h].number);  k, V( C  M- }
link[h].number=0;" m# V9 Z3 ]5 {3 B
count++;
: ]4 n/ h- u; @) w( |4 L}
0 \# J( l$ t, z; ~9 C; A5 V
) _, c% t7 k+ O, ^4 D9 qprintf("\n大王是:");
% E2 r6 o; b3 u% E3 w+ Y% h% H* W5 Y  for(i=1;i<=M;i++)( I0 M& K, U) l0 Q$ q" T
  if(link[i].number)/ E! e3 ?- f: j5 _' M+ Z
    printf("%3d\n",link[i].number);
. W+ V( _% l7 c  h" U, {. w( a, W  U: C4 x3 o: w

! g) s  _2 P% M4 f}
& P0 P7 U" b" c- j7 W4 J8 |
第三种是普通方法for循环
: H7 R. L) h# A/ h+ \' S7 U
#include<stdio.h>: u" q( M- j! h& i
void main()
7 a5 m( {6 X9 u+ m2 D# T{ int i,k,m,n,num[50],q,*p;# Z! |) {3 Q7 ~2 l+ x. v
    clrscr();
/ n  G3 q7 _5 @  k' ~: A, t   printf("input number of person: n=");
" v% V& J7 o, B* x    scanf("%d",&n);
  U% D% ?, i8 d3 }9 ^' i5 Mprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只* H# d+ T! r  Q# T) ^( b
    scanf("%d",&q);6 F# `  B5 c' }- u+ p' e
   p=num;
, J' ?' U/ Z3 m+ v, k0 A  for(i=0;i<n;i++)
0 k$ r+ Y% j  i    *(p+i)=i+1;
+ |* u/ P0 {( \   i=0;- r) a: m' s! {7 y
   k=0;" O% b" h1 s3 J5 \) ^
   m=0;1 C/ r1 S. e. B6 l: Y
  while(m<n-1)
7 y- c8 X( _: B, n3 [$ e   {if(*(p+i)!=0) k++;
8 x: [) h' b1 r; j: a# z     if(k==q)
# _! X: h# S/ T) ]      { *(p+i)=0;' e( D% t) O' V! K: D
        k=0;
1 e8 X' l4 Y3 m) Y        m++;* q1 Q0 l8 c) u" o- j4 w5 w
      }# k: H1 s$ @8 u- m
    i++;& ^9 j( o# F4 Y3 }0 _. k
    if(i==n)i=0;' J3 d+ h. V3 ?$ x: y$ `6 l- p( U* \
   }
% B5 P1 h8 [8 x7 B" c. C; |  while(*p==0)p++;8 z" N& B8 i' I* B
    printf("The last one is NO:%d\n",*p);7 k1 ^8 l2 f% x$ Z0 o
     getch();$ o  [* R- [5 ]  A! \( E" V# y
) Y$ |7 }9 J* m( g% K' c4 D+ \/ n2 _
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;, t9 `: ~# ~" ~2 h; \" h9 u
namespace 又费马达又费电' d6 n# W' `) B3 P* E& @, N* R
{
8 y; a8 T7 a1 {3 W2 K/ R. Q% \    class Program: h  i; f3 b- v
    {
% Q  P$ _% F! q7 T        static void Main(string[] args)( I. d. X. b1 g+ I2 i# H: T" M
        {
& N$ F( Q2 s7 \, y9 e& h& r; W            int m, n;
3 k- n; w0 O5 s! W3 ]            Console.WriteLine("请输入数组长度");
: R; g$ V, ~" `            m = int.Parse(Console.ReadLine());//m为数组的大小
+ J1 c9 ?- j7 l+ L) q            Console.WriteLine("请输入要截取数字的大小");1 X% r9 h. r4 g2 |3 U7 }
            n = int.Parse(Console.ReadLine());
( A0 I" m  P/ c8 ~, {$ l            int [] numw=new int/ o" g8 F' {, S

$ E4 B, X9 I- ?* v  R&shy;&shy;&shy;;
/ l8 Y; l  ?2 Y, t) D6 a5 O* E! O            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数5 b+ F! v$ @' s9 n3 g. D
            {
7 _0 V) e$ V! j5 Q# q0 }, R                numw[j - 1] = j;) b$ J. f  i- P" F
            }8 A/ @. ~4 V' i8 q  q
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!5 S3 n5 Z$ \8 q: \
            while (d != m - 1)
! H6 L$ {2 b0 A" L6 o" h            {
2 z; Q8 P' B* V                if (i == m && d != m - 1)
! K$ Z) ~2 e2 i6 V, ~, R* S                {) A, d3 ^1 w% X% H3 b/ z8 |
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!& f8 r1 c7 l: J3 g* N
                    continue;
1 g4 v9 U! F$ |                }# d- g) d3 j) [8 C2 K% m/ Z
                else+ ?! |/ ]9 p4 _7 T% x
                {# O; c9 ]' V  }- n. i; ^
                    if (numw[i] != 0)& ?6 M" b" ~$ d
                    {
+ [3 X$ ?9 S7 ?( a                        i++;/ k$ F+ P1 T4 H
                        k++;
0 W9 ~7 `5 g1 b                        if (k == n)( }0 D6 s4 m5 q0 l* S
                        {8 S+ p5 w, Z$ l* \/ n* j
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
9 e& G4 e" r% E                            k = 0;3 q: j! Q! e8 g( ?- M; L
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
9 u- c3 t1 \4 z2 q4 E                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);7 W( K4 M3 f0 A& W# s; I# W+ x) U
                        }& ~) B- H" F* }1 s3 I5 Y  W6 o
                        else//输出暂时还没有改变数组元素的值2 b* Z, s/ T; a$ N& Z/ a1 Y
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
6 O  I! o# i# P# w                    }
( R4 r! O7 D: p                    else
. ^- q2 m! G7 i; r* V! l                        i++;//数组元素为0,直接跳过,不计数。。。
& T6 {) S; r& X7 u                }
- ^+ F. I5 A0 v3 v+ v5 O4 W
1 w" ]7 @7 B/ b: u
1 i, j3 ?9 d. T            }//结束while循环
5 [, v5 d/ M' Q. V; n+ B' I% l            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦; N2 ^! g; f" S4 d9 G0 Z/ `/ K$ U
           
' i- K2 g1 t' R                if (numw[i] != 0): }$ U% O# ~* `4 v, Y, v
                    Console.WriteLine(numw[i]);
, r0 D2 a4 ~7 ^# }( d4 {           
; b, O# Z% m& y4 u            Console.ReadLine();
0 p+ h0 a  i  d! X        }
) E4 Q1 K. v, b/ z$ b9 L8 R    }( v& M7 Q' p5 m* y( a0 R
}
: x4 G1 G6 W, b+ \# x. b$ n# [* v
小甲鱼最新课程 -> 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-9 23:44

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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