鱼C论坛

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

猴子问题

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

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

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

x
大家好!! H8 ?5 Z+ A1 A( \; Y% s  j5 h
这几天我在忙着编一个问题,我用了一种方法编出来!
( \% W& z1 ~. I, U但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!" B. M! t4 {  F9 m' E3 M0 N$ A
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 " A0 |5 M. t( m; S% Z% \1 m

% [! R5 S" A2 n( Q6 i* s& b% Z) x- @; p: V. R2 l
                            题目
+ L7 F  [5 L7 A! n+ Z, L5 `山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。1 u( T4 p7 a7 Y4 Y5 F. O# ~) a
第一种方法:利用循环链表
0 B0 R- x7 M( ^2 q% t/ t8 v1 Q#include<stdio.h>! X8 K( i; d6 |- |0 z: z( n
#include<malloc.h>& F  O/ e8 `* |& X2 J( [( m
#define M 8            //共有8只猴子
8 u% \3 q* L  b( t#define N 3            //数到3只时退出第三只8 z5 c, r/ V3 S- `
typedef struct monkey  S9 n, j, q5 `
{int number;4 V1 o& e( ^# p" a
int flag;# \% ]+ x' u3 ~  G2 V
struct monkey* next;
" ]/ X$ B5 a! n1 G7 p2 _7 E}MONKEY;
) B; I: _% o! a1 n5 j, Bmain()
; y- N% ]4 g! H1 F0 n: K. J+ q* D{ MONKEY *head=NULL,*p,*s;
2 Z1 h3 U: Z# w. ^5 F: v' Y  int i,sum=0,count=0;! G/ o: F2 _' k$ ?# }; i
  clrscr();              //清屏
+ _) L& X) H1 }1 }6 m. G  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存* W4 k% Z; `. _! d! G* w
  p->number=1;p->flag=1;+ Y* w  l1 h: n
  p->next=head;
/ y4 q% t& F4 Q$ ^( T  head=p;
0 o$ A5 Y- x. @2 A  for(i=2;i<=M;i++)
( o; v8 o2 Q! e7 ^) e) Q( i5 V    { s=(MONKEY *)malloc(sizeof(MONKEY));' G" o+ S5 s- v
     s->number=i;s->flag=1;" A0 b9 X& z! m+ R3 [+ }
     s->next=head;6 Y* a5 M0 [! `9 X" |2 ?& K
     p->next=s;p=p->next;
9 g/ ]! T  K* F( }* |6 k. W    }
+ M/ B5 _+ c# {( x9 Y    p=head;/ `1 R4 H9 @9 o$ j( d& j: e
   for(;;)
9 y6 v0 m+ P4 X: X% S    {if(p->flag==1)% }% O0 y- W) K) k8 Y2 g# _
       count++;7 J0 ]1 z0 B7 U& c0 K
     if(count==N)) P- E4 _5 ]: c: o) p$ V, ^
        {p->flag=0;4 E' ?" g7 ~6 D% T  S
         count=0;1 M( e' x2 k& x4 ^$ y" q
         sum++;}( K% U' d6 p. y& B
     if(sum==M-1)8 y. P# K1 j$ k% s
        break;
$ l2 a0 `4 |0 v3 ^1 j: j     p=p->next;
) o' M* S6 E' c* W5 e/ T    }
  d+ [+ j1 E' t9 K! A  d  t1 Y% q    p=3 {& j# t* R5 U- l1 U
    head;
" w& X( {, _- t9 w  O) m: x    for(i=1;i<=M;i++)1 n- v! U/ ~. Y
    { if(p->flag==1); v7 K8 Q5 w. ]& q
        printf("\t%d",p->number);
, ~  D1 x( T+ m* `) U      p=p->next;9 F8 U8 K- E" O& C* @
    }' L; V( L0 _& r

8 Z' U) y8 h' z$ B# y6 p) b) Z) {# ]9 z& \
- W$ m3 r) I( k. v
}

! {6 ~) `" s1 ^7 f第二种方法:数组' z7 p8 H8 X" g3 x
#include<stdio.h>
! s5 k. M5 h* @0 K7 c# u1 j1 e4 k#define M 8  D! x9 {7 W" w( B: W6 u3 d
struct monkey
) @9 {4 x' D) i6 N  X9 ]" c' f{int number;
/ D+ h& H6 S2 U+ r, C( B  sint nextp;" G! e$ \" m$ ~
}link[M+1];! m( d0 j; F4 a
+ ?6 `  ?* E8 r2 ], M2 T
void main()/ A2 n7 O: @( j* {9 H+ s2 Q
{int i,count,h;
- a. B5 w* Y: ~! E/ l! jfor(i=1;i<=M;i++)
- n% [3 ^+ k3 g- y; r0 Z{  if(i==M)$ W1 Z2 x# {' P; }
   link[i].nextp=1;
' X# D, R' d9 W+ x& A: s   else
+ g4 d. |! c! o   link[i].nextp=i+1;5 u8 K$ X. ?  N$ B, U! E
  link[i].number=i;
. e$ k, e1 C& f2 p/ x}
7 t4 n6 k$ _: ?3 f, s) o9 ^printf("\n");
  G, s+ l& }; }5 Xcount=0;# Q2 T+ t+ r9 M9 h( y
h=M;
$ h3 ?7 h* g7 P) Fprintf("依次退出的猴子: \n");2 Q& }- N, v/ M; e
while(count<M-1)
) x8 x# N& j  r; A8 ~{i=0;
' Y3 C! Z2 P: Q' l, p- nwhile(i!=3)/ e3 g; w, K+ ?: }) ]; A
{ h=link[h].nextp;
: W3 r3 {5 v+ _- n   if(link[h].number)
) E3 m3 }9 C/ ]+ Y' T6 b     i++;}
( d, W$ [4 X- M5 x- m+ r0 r6 M' R0 @1 e, e
printf("%4d",link[h].number);' x' u0 h( t2 b7 G9 r7 V3 a
link[h].number=0;
* P, E9 `9 V* Z3 W1 ?4 z) \# ]count++;
  `( K1 j5 L9 ]3 X' v}
7 Y$ j9 Q- s0 q3 ^; n5 x4 _& @/ n9 d' e+ M
printf("\n大王是:");9 S! ^+ e6 \$ J1 y; |* H4 r7 W
  for(i=1;i<=M;i++)
2 `+ r: E, p; p$ |/ Q* y  if(link[i].number)
- x, N0 d8 B* Y+ w+ V7 @    printf("%3d\n",link[i].number);, Y" C$ ^* |; p$ o5 O) J1 N. d( b7 o
/ S1 [5 T" g- D& m
, v; c. L  E$ s/ o
}

8 k9 N2 Z" x" ~2 w8 E( L6 G第三种是普通方法for循环

$ R; j# \/ l. U5 c% N3 D& a7 o8 U4 O* i4 j#include<stdio.h>$ o! z' h/ |5 h4 C1 J
void main()
$ L- b$ w' d6 T7 \" B{ int i,k,m,n,num[50],q,*p;; @; f* k) Y1 h7 `
    clrscr();
9 {0 @  Z" ^+ R4 c1 A" {. t   printf("input number of person: n=");9 s) [# w* X  }: o, l
    scanf("%d",&n);& v5 `& z- ~" g& |
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
: E7 d2 x, f9 g5 ^; Z    scanf("%d",&q);
# N$ o1 B! T' v- k   p=num;' V) @/ z- x" B( t# g8 m! b* V
  for(i=0;i<n;i++)
  W; b/ |- C$ y% [. A, P    *(p+i)=i+1;: h- {+ l+ ~/ ]6 w' L
   i=0;
0 U) T! W: ]0 l4 j& Z* I. b   k=0;/ Q) `( @/ m  f' x  |
   m=0;
2 I( S& k0 Y6 c. o3 H, C' M. {# ]  while(m<n-1)5 d  ~/ N1 }/ |  d+ N, m7 U
   {if(*(p+i)!=0) k++;1 Z- S7 [# S5 a
     if(k==q)
5 x+ h; J; O0 a5 f/ B( c4 o1 r      { *(p+i)=0;2 c: R4 _# Z5 n* m% H& ^, M
        k=0;
+ k% v4 g! M; [* _- P2 B/ y        m++;& ]  ~; h! d6 L' t' v1 P
      }9 s+ j& A, D- M+ @' r9 R
    i++;& I. Q  u+ B7 Z% W
    if(i==n)i=0;! M3 L& z, o% Q% f# X; ?2 Z
   }
, [9 i* B4 r, Z1 u! B% J  while(*p==0)p++;- B# `% j) _' M
    printf("The last one is NO:%d\n",*p);. ]8 J3 i0 W& n) c2 @
     getch();
! Y  d; ^* {) ~% ?2 ^' y+ u( W- k
- F9 n4 A1 A9 _8 k9 y- C}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
5 q5 S% e! h$ M0 ]; m9 U! |) ^namespace 又费马达又费电
% D0 _$ Q$ c) }- P{
6 k6 j, i! o4 V5 H* N2 z6 `" z    class Program
  G* q; N* Q3 c2 M, V4 I  E    {
( C" }. U! J  A0 \) P+ d8 V* i) D        static void Main(string[] args): f+ l; @; U/ p# P1 p
        {8 M. f  o0 {( C
            int m, n;! Q3 h. o# K" F0 V: g1 y( C
            Console.WriteLine("请输入数组长度");
% ~! H  Y+ Q* i' {% q            m = int.Parse(Console.ReadLine());//m为数组的大小2 @5 k& w+ {) V4 v+ C* p: W
            Console.WriteLine("请输入要截取数字的大小");: U8 T2 x% o' {
            n = int.Parse(Console.ReadLine());
. c0 `, ^" n! ~# o& U6 d            int [] numw=new int
8 [4 ^( T3 V5 r# W
. N4 G$ Z% F- }&shy;&shy;&shy;;/ q' o7 x6 O9 H' o2 V
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数7 b- Z% m  T$ n  S9 G% H$ M8 D! ^
            {
" l& {9 {+ J1 s                numw[j - 1] = j;
% P2 }/ d  @5 _% [            }
" x% M7 N# R# [# h, _  q6 V            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!* p/ h  r0 T5 _* U+ x/ n: t) o
            while (d != m - 1)9 M( ]1 V; {& v& G9 n7 R' n% w
            {9 I' g0 t. H" `5 P2 G
                if (i == m && d != m - 1)
# y- `# Q/ {/ m8 g2 h% o                {; L/ M5 |9 i" n: h3 ^/ R9 ~
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
  u1 ~( u; d  B$ C+ T; Q8 j; k2 N                    continue;
( T) }) S$ m; G. e! J                }# D' l; [+ q/ D( G1 `3 f/ R
                else
+ U6 Q6 s  r4 {                {
8 {! J5 T3 r0 k                    if (numw[i] != 0)7 ^5 [6 _* F3 |% S2 e  O! ^5 p
                    {9 T# S# z: D  _4 [' p% L1 K/ l
                        i++;+ @3 y+ t6 \$ W$ ?% Y& }7 O
                        k++;0 D6 s& w8 _2 X% u: z- k: y
                        if (k == n)
6 T" K' G. Q: ^3 ]( c# Q: M                        {, M- J, X7 c" I; t. t
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了, B' f9 W% {4 V( p) e
                            k = 0;
' D' w( a7 B+ M$ b- u9 j; H8 t              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
8 w( b/ p6 N! P* M: Y& u4 w                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);7 R3 C* D4 x+ r" j8 D2 }2 }
                        }
6 X2 R  ~4 n, p5 N/ w                        else//输出暂时还没有改变数组元素的值7 L- R, A% x7 J/ s4 |8 v
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
. w! |1 r9 B& q+ }                    }& @7 e+ v! M' Q# i6 x
                    else
3 Z) S* t; k1 T                        i++;//数组元素为0,直接跳过,不计数。。。
5 y9 g) Z2 ?, Z, M                }* F3 p7 S) u# h+ f4 e( |3 ^+ V

. O8 L  N' S8 y' E4 i. y/ p1 R
& Y+ g. ^2 t% r: `            }//结束while循环* V# k% e( s8 F5 d+ S
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
4 `, p0 ]) K1 ^) o% a* i           
7 a) c% P; n3 H2 D( z                if (numw[i] != 0)
! p3 p2 ?- J/ f: e) a7 x8 Z1 R                    Console.WriteLine(numw[i]);
+ v  D- `3 [3 n5 a           
$ ?* d  k0 Z, X5 T7 E7 r            Console.ReadLine();& W' _# P: w1 P9 Z. D
        }0 X/ y6 q" z( _/ g2 ~' H
    }
& \" r$ Z. _' e6 V% s& W* w9 r}, }/ }& `( e; U! y  V+ C, w
小甲鱼最新课程 -> 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-1-30 17:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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