鱼C论坛

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

猴子问题

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

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

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

x
大家好!
! ?2 o1 p7 W7 H( Y. l这几天我在忙着编一个问题,我用了一种方法编出来!
# W. e8 k( S+ y$ K1 Q& `! ~& R但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
: i. |: w3 X3 B' _5 U注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ( t  d% B  y3 y2 u7 l! R: _

" z4 B( z! s& A$ X/ }. L* K! |1 J% W6 h! g
                            题目% T5 G/ G! z4 P4 r* E5 d- a( s8 n
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
! `; S' b% k# r7 G第一种方法:利用循环链表3 o7 }! j6 I) W9 I
#include<stdio.h>
0 i! `7 E" k$ m9 y' K- `) {% j1 i#include<malloc.h># c, C+ I5 t3 V4 u/ C& C$ N
#define M 8            //共有8只猴子
" A5 ^$ ~! Q% X1 |' y#define N 3            //数到3只时退出第三只6 k5 U* j1 z# h
typedef struct monkey' F( |! I9 f& f5 I* j
{int number;
2 ?7 p3 {9 b$ G6 n' U& hint flag;
) f: F' z, V8 c& I. fstruct monkey* next;
$ n! O2 |6 i: P. q; a) N}MONKEY;
, m! z$ n' a* P9 C# Kmain()/ x& X+ A, m# S. R( Z7 X" y2 B9 X8 N
{ MONKEY *head=NULL,*p,*s;- x. v3 O* o) ~" g
  int i,sum=0,count=0;
! v( I- w' q0 e# L( J9 O" h  clrscr();              //清屏! x2 |% B5 P  L/ b; n) a1 L6 \. }
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存" N5 A1 R% Y: M. e& ^
  p->number=1;p->flag=1;
; g$ \0 ~1 \0 [; p7 M4 a8 Q- W# m) ~  p->next=head;
7 F- A  _, e& X  head=p;
7 S5 w# l9 Y+ ^# Q- x9 n  for(i=2;i<=M;i++)
; R: @. S$ e4 _" k6 A- h7 {    { s=(MONKEY *)malloc(sizeof(MONKEY));
& W+ E, n+ @1 c, W     s->number=i;s->flag=1;, m2 l3 ?  w7 k5 v
     s->next=head;
* _. P; N: `' r! I  }, i     p->next=s;p=p->next;
5 `% S' o' Y0 }7 Z    }8 T; g, l' Y% H, |) c+ s5 Y3 r
    p=head;
0 K1 e. K2 b5 |8 b$ N   for(;;)
$ y" C2 W$ c; G    {if(p->flag==1)0 A( P) G  \, W! m
       count++;
, S6 m# Q' J! }5 b; {/ V! G( `( s     if(count==N). ~1 }! \$ R6 Z# g! U7 x  X
        {p->flag=0;
: W& t& J8 s" h; {5 L6 ~         count=0;
# a  D5 I1 g; G  ?+ P         sum++;}# o6 f5 }: c* t1 C6 `5 ~
     if(sum==M-1)0 W. W* d& D" W9 N/ Q$ X# r
        break;
5 K5 s; e# }( |* U     p=p->next;
7 z; t) |; e* r0 d    }3 ^8 x# H" z8 c$ `  a
    p=
) k( @& u4 E# {/ i1 g" G( p# {    head;
7 g/ N0 H! P" g* d5 H: N, k3 }    for(i=1;i<=M;i++)6 `! V  E  _; `& @: s, A
    { if(p->flag==1)
4 O, S; n  G' ]1 {, E8 e        printf("\t%d",p->number);
9 N2 B9 y! I, z      p=p->next;6 B6 R$ n! m. A; u
    }6 m; U& \6 z7 U7 w

# F6 U( j7 g+ g' t0 B* f. p7 F, f& H) C( u

8 N/ F- y! G% _4 i- }# \0 ~) }}
6 k) ~) Z: H, [4 p
第二种方法:数组8 I& v4 \' r; A' i$ n+ z$ ~, v
#include<stdio.h>
+ {% P3 T) U5 g$ g3 G#define M 8
1 Q, c# v1 B! K5 k7 G" [+ nstruct monkey5 w+ k0 ]2 n3 j
{int number;0 r4 d2 s) J9 E
int nextp;3 C8 Q: D& ^, U, f0 k
}link[M+1];# r' s  e4 V" k) I5 e3 H

$ V8 d$ ]- a) E# y* L0 ]% Y5 F2 Wvoid main()
. j3 T# x% {  f& f  b: q{int i,count,h;$ K% J5 p9 |( u
for(i=1;i<=M;i++)" n% \+ Z+ ^3 N1 R# U: z
{  if(i==M)
: r2 y, O. l0 N5 _5 ^! V! ]# |   link[i].nextp=1;. x- j& `" ]3 C
   else' K7 {3 j  V9 r
   link[i].nextp=i+1;& ]( d! _. [8 @
  link[i].number=i;
/ ?0 _9 q: ?" z) x* }}- p3 e* K! w0 s2 S, k4 l
printf("\n");
' l( g1 s2 x9 ~count=0;5 l2 D) I2 L- G& a3 |
h=M;. l1 c3 y# H2 }! A
printf("依次退出的猴子: \n");# Q* k% r" ~( X- ]) I5 n+ P
while(count<M-1)
; W* G: b9 ~6 M/ w+ q8 B{i=0;
" y' N3 o, r' ?. d! k0 Wwhile(i!=3)
3 g1 Y+ J8 o& a8 p7 ?{ h=link[h].nextp;
5 v! F6 ~9 i( L+ e/ D+ J0 J   if(link[h].number): I. O" j( V4 E6 H9 V9 n, B! C2 p. B
     i++;}, x" G6 |8 Z8 a" V. c) Q( r4 r
1 J& i) \( r/ G) o
printf("%4d",link[h].number);
- |  ?5 `  R3 z) q0 r8 ^link[h].number=0;
6 W" b# R9 C7 ~count++;
; |; s$ S3 g7 h* G& P}
$ O( J) I: c. f! O; M4 U: @6 L( u* O. t# B
printf("\n大王是:");
, D2 ?0 z, H5 K  P1 f% Z; o  for(i=1;i<=M;i++)
  p# T) l( f: ]7 H' x; A  if(link[i].number)
1 {3 `' s8 t  H3 r6 J1 R' l    printf("%3d\n",link[i].number);
2 W2 V* g6 m3 x0 K3 X1 W( M
: _/ Q! H) }' ]7 q' d
' C3 D8 {1 c5 ]; ]9 G0 `2 S4 C) H}

5 e) s- I2 _  i( }4 `1 \第三种是普通方法for循环

. P+ f$ n* F  y, f) p# H2 N0 W#include<stdio.h>: _* }4 G4 f/ I% T" c6 M
void main()
) Z6 K3 E& v0 E  e0 s/ A- Z{ int i,k,m,n,num[50],q,*p;
. a1 R+ A3 w$ V9 C1 E1 Q& [6 @    clrscr();7 p% I* C/ s% d  `; q
   printf("input number of person: n=");+ a1 T, I* F* C3 N% `( J; ?
    scanf("%d",&n);# @7 r1 t. y/ k. g! e- J
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只" S2 ]+ ^8 S9 T/ p' z$ n1 Z
    scanf("%d",&q);+ }. L7 C# m& e4 p
   p=num;- \6 R  N, c3 u; p' F2 p  c
  for(i=0;i<n;i++)6 p" G! y; K' \9 q% N" V
    *(p+i)=i+1;  {9 l2 i1 y0 J- l& K
   i=0;& B. K( ?9 y* o0 q/ G: H
   k=0;4 c3 v6 U: w" Y* U. I8 o; W" g
   m=0;8 b: \* u6 i$ F3 D" O6 k
  while(m<n-1)
4 d4 l/ N# ^7 A/ n+ y5 w+ q   {if(*(p+i)!=0) k++;
% q4 P2 Y; l" Y2 Q     if(k==q)0 @, z1 j9 P' {2 |$ K5 ~" i( _* O( ?
      { *(p+i)=0;
; k% D2 x3 ]3 t        k=0;
7 g8 }, H1 o) \! U8 U        m++;
' R8 i1 y$ y  ~8 R) O0 q      }
# A, W: \/ d# c$ y3 L# {8 J1 a    i++;; v8 i6 N& d- c  @/ ^( @/ h5 L
    if(i==n)i=0;
- G# n4 M, r  N+ o   }
! Y6 p( ?' b$ U& L" e$ E  while(*p==0)p++;
* }( {. u3 w+ l1 s" [    printf("The last one is NO:%d\n",*p);- B. t( d9 }) B
     getch();: Q+ [+ d, y' L, A) k
0 e' H3 R3 D% N8 r% M, X
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;# c1 C6 R9 ~- V. j, m
namespace 又费马达又费电
9 F9 i) J0 R) \5 q$ r$ o: X{1 s1 t$ @4 z" H8 m  f
    class Program& M: [3 Q3 C( P% M
    {1 J& \' C3 b- \9 B0 E+ M# ]4 x
        static void Main(string[] args)
9 L  N% `7 `% x9 n5 X8 G        {
; C. k* X6 v  r9 B/ S. O& e# j& O            int m, n;8 z) d* a" w7 U8 A
            Console.WriteLine("请输入数组长度");; F/ j7 k' y+ h+ `' t3 x: H8 G
            m = int.Parse(Console.ReadLine());//m为数组的大小
5 n3 W1 B( g0 u0 N            Console.WriteLine("请输入要截取数字的大小");" `2 p4 @$ M8 [; i: E  b0 ?
            n = int.Parse(Console.ReadLine());' Z( @  @" h. I" O: y& F1 l; v
            int [] numw=new int: w! J, V7 m+ N8 B7 b9 D0 F

) K  M" ^* G# t$ f& I&shy;&shy;&shy;;
$ W7 A# F3 k. e2 t3 H$ e  j            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
/ n: z* A9 Q, p$ S& Q9 l            {& h+ l4 Y$ ?0 z% o! Y
                numw[j - 1] = j;
+ e' u; h8 m6 F/ c7 ~$ k6 T/ M) j            }
0 |4 o9 m1 J' e  F  f) k- ^$ ]            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!7 q% B2 Q( P2 b7 @6 q! b% ]
            while (d != m - 1)
0 A: v9 j7 y) O2 J, u            {
- P9 e4 l3 W4 n5 g) w                if (i == m && d != m - 1)8 l6 _: Q3 v# j9 J, P( @$ [2 B
                {
# g  a" k/ P' {- L0 g                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!3 d+ j6 @6 _& m2 ]3 f
                    continue;
4 Z( k+ ~/ _6 ~+ l* q; H- N9 P                }8 m. h* p4 p) y
                else: B  J' S/ |1 @! [6 ?! W
                {
% t+ \* _2 E9 E# a                    if (numw[i] != 0)
4 P  ~- b6 D" E- t& d8 e$ y( Y                    {; a7 w, D2 B* y" t4 S; W/ D
                        i++;
8 z3 P* t$ V& C# h/ O6 N                        k++;3 f; K4 a4 e9 v* }9 A  \* M
                        if (k == n)
% G) p2 J+ b2 ?$ Q2 R% |                        {
+ }" u, @3 S4 ]                            numw[i - 1] = 0;//把在n位置数组元素的值改变了0 R1 \) F+ A/ o* c* y+ G: T
                            k = 0;
% h) E& w! y- h& {/ Y              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
2 G1 ^! B- G5 F* J                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 s6 z& a$ c+ i  K/ E! y1 V% Y                        }& l& K- ~8 f! l5 z7 O9 U, L2 a3 ~
                        else//输出暂时还没有改变数组元素的值4 W9 }" ?( k: b- E2 X
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 u9 ^1 l. n2 o, ]3 t                    }  X; g$ F; m% @4 @
                    else
: k( w! x4 e" `% E$ M                        i++;//数组元素为0,直接跳过,不计数。。。# a# l! K* X4 f6 d
                }6 ~4 `2 b; i# J$ k  O0 ?+ W' ]

3 H# Z/ n( f2 I  S5 L7 r; ?. {
7 _: R8 d" q7 b3 N+ w( M            }//结束while循环: ?  k( _# S$ W! k/ |8 e
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦9 u8 X1 F, c. a4 F- C5 s3 ^% ~) [
           & ?* e, n. \  ~& l( j
                if (numw[i] != 0)
  K" d1 ^. k% }; t8 Z$ Z                    Console.WriteLine(numw[i]);0 F; G" p; L( {# ?( U, |4 P
           : c. |% H) A& }( H4 B7 V" W: S
            Console.ReadLine();
0 k  O; l" a% J4 m0 I7 x: p        }
5 z7 @+ r, c- |2 V    }
% g9 \  x, ~. a6 N1 M}
& W7 d! k0 B: H
小甲鱼最新课程 -> 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, 2025-7-19 07:45

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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