鱼C论坛

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

猴子问题

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

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

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

x
大家好!
+ F1 F/ Y; d2 u9 g这几天我在忙着编一个问题,我用了一种方法编出来!6 w, H' H1 o' p
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!# S$ B0 X" I; g" e
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ! ?, @! R" _, S+ C2 r* V5 K
3 l3 _0 x7 O" W  Z

+ a  C$ B1 d6 \! q+ ^: y5 r* f$ V9 G
                            题目
3 s$ T/ Q/ N& }, @) }9 }9 @  L山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
( K" g8 V+ _" D第一种方法:利用循环链表
  R9 O3 M: c4 n2 K0 R#include<stdio.h>
; F4 S4 J9 f# x8 p8 h7 Q- t; N' x: C1 W#include<malloc.h>7 J. h& O- U8 q: T: A0 D
#define M 8            //共有8只猴子" _& G/ q5 S+ ~' k. k4 E
#define N 3            //数到3只时退出第三只8 Z! P& A% d5 j, i, p
typedef struct monkey
4 X; i; S- X) F. ~- }, X{int number;# O. P1 j5 ^0 x' L8 }3 t" t0 w
int flag;- x5 G0 |: m- ?/ p  }/ A* y
struct monkey* next;
9 N; ~8 @) l3 ~' }4 |. K}MONKEY;
# g$ S' X+ V& J. n: c. E8 fmain()
1 \9 J2 a) D+ s; w5 ~{ MONKEY *head=NULL,*p,*s;
, z5 P5 b8 t" m# A' W  int i,sum=0,count=0;
+ D( f# B! x3 ?* A- g6 l  clrscr();              //清屏2 z# x* L5 M. O) M$ E) }3 Y3 J3 G
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
( u( O. J" e$ J; O* K5 ?6 S1 D  p->number=1;p->flag=1;' g  }# U. I3 v& s
  p->next=head;
" G2 I, y6 {& ]6 ?* Y: u  head=p;
# K) R0 Z5 a* i3 x* g  for(i=2;i<=M;i++)
" V9 l2 g( c  M7 w5 w0 o" Q, d% h    { s=(MONKEY *)malloc(sizeof(MONKEY));+ Y. h# B7 n" T! o- W# j9 V
     s->number=i;s->flag=1;- M; h3 J* u5 c+ M; v9 M* C: z
     s->next=head;3 J1 u5 I: f8 O7 y( s6 P
     p->next=s;p=p->next;
/ S5 J* q7 }6 E& |1 k% w) b  |$ O* [    }: t! ^$ Q' d2 k7 F
    p=head;( |7 o: W  M  V
   for(;;)( D1 _' G. e7 Q# J3 }' ~9 M
    {if(p->flag==1)8 X. T0 R3 @3 l% T0 r- j; n1 ]5 t6 ^
       count++;6 [6 Q5 I, b( |, D
     if(count==N)9 q, ~! o' t, i: x1 Q
        {p->flag=0;6 k; v( P$ V, r1 L& U
         count=0;! Q% K0 R9 W8 u
         sum++;}) d9 l8 I& [- @, J
     if(sum==M-1): X4 G* a; O) a- f3 k0 h
        break;" S* m7 q8 |3 m
     p=p->next;, [# i# l1 H$ r5 a8 Q  a
    }- O/ L, [6 H0 n+ m5 ?: _
    p=# ?3 s; S2 _) ?9 s. |3 \
    head;
+ D# h6 U; a+ O5 i% r3 g    for(i=1;i<=M;i++)
. L+ H# J) ]( P; J    { if(p->flag==1)& O' x; o6 ?$ v! Y8 }1 m
        printf("\t%d",p->number);% h: e- r: n* a: u9 E& v$ L+ c9 ]
      p=p->next;3 {$ H1 C* x+ G" ~# |9 A7 b! d% I
    }
+ `# u: g/ u& J! }$ p; T! E4 o
1 C0 s1 B" L" Y& P* [+ g/ v  \% R* u( w) j( _  s; g4 B, U) ?

, l3 d8 O0 N3 g}
6 d9 E8 {/ s6 J8 q* Y
第二种方法:数组8 T2 O5 A" T3 T" t) a
#include<stdio.h>
  u) G- I, \2 C9 g; y#define M 8: e0 `3 L9 ^* \! B2 b
struct monkey
2 I8 \- R% e7 X  Y. t2 v' Z8 Z2 c{int number;! j1 A! j8 x. \
int nextp;
; ?9 j; w( x8 I9 R}link[M+1];1 ^6 j8 X6 x, f, m' x6 l1 X

( M# ]" f* D; Q# {# \6 j8 ovoid main()
, k# A8 B: v" {( ]6 {/ C0 p# O{int i,count,h;+ G5 g) I  {( N) j
for(i=1;i<=M;i++)
+ `" ^" Z% y2 u: r/ D{  if(i==M)
5 k$ P* x: V6 S  G! C- K, ^3 G   link[i].nextp=1;2 g" V7 s9 {3 d5 q7 K
   else- f1 ?/ T6 Q/ P& O4 K) S0 l/ A
   link[i].nextp=i+1;
* ^: K1 k! y7 Q1 V! R' g# E  link[i].number=i;7 H1 j; R# A6 h5 e
}6 ~% l& e' A0 \+ w. ~# ?# U1 }. p
printf("\n");& s1 a! T8 i. J7 r
count=0;
* U, X  l+ H2 ~: d  n7 Gh=M;
) ^3 r& |9 b- G/ j; f3 Rprintf("依次退出的猴子: \n");
2 P) n+ }, Y4 o' l& ?% pwhile(count<M-1)
9 I8 |! o; D: W* h4 ]5 B+ z{i=0;7 A. H% n) y  _7 \" c- h
while(i!=3)4 F0 R- o: _1 N3 f1 I9 ]
{ h=link[h].nextp;8 t& j$ c2 J; J+ z: P
   if(link[h].number)# V' r& _1 O6 e6 ~
     i++;}0 Z( o  }- b; a- F

  P! e5 I1 I0 R9 \# Kprintf("%4d",link[h].number);
* ]4 S$ C0 L6 |1 E6 x8 slink[h].number=0;
2 k  S  g' A; B1 a! x" Bcount++;% }* K' G' t8 w& V
}
4 j' L8 `$ D# K3 e4 b6 A/ g  {
! Q2 l) W9 _( b% Aprintf("\n大王是:");
* W, h6 q( U5 G, G/ c, B  for(i=1;i<=M;i++). v9 F6 Z; _" u/ N$ B8 ?" w
  if(link[i].number), `2 z2 D1 M* ^
    printf("%3d\n",link[i].number);
( C+ u. L# n; X- v8 e, p8 I, l9 I/ N* w% y: V4 q# ?) _6 S, t% [7 d
" f1 W/ h# G( d3 k5 m0 w7 U, x
}
0 I/ I. k; U% e# {
第三种是普通方法for循环
2 F( A# @: c' a5 R# m% \7 b
#include<stdio.h>5 z% G; D- F  ], q+ F
void main()3 ^" K" F( C) t* P! P" N% ~
{ int i,k,m,n,num[50],q,*p;
& g: z9 J' Z6 u4 c5 [. i# B& e) `    clrscr();
% G: u5 P8 `9 M  i' D, p/ L   printf("input number of person: n=");
7 e2 |2 t& o# z  e2 v' {. G    scanf("%d",&n);* B) A( @* C6 X3 X7 v' ~4 Y
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
& y1 M: @4 r8 N/ n    scanf("%d",&q);
2 Y4 r2 P- V/ O9 U6 s) M% h% W- s   p=num;
' T( [9 l+ G$ ^7 w. f  for(i=0;i<n;i++)
) G- [$ L- R2 R, j' \    *(p+i)=i+1;5 k" P1 W1 h# \5 J7 K% }
   i=0;
8 s# e8 o% C' y$ r5 S  Z   k=0;
3 o% H8 m. m, N' v' K  w   m=0;
* p% q0 o- O# ^! N6 m  while(m<n-1); t* d* y) W8 w. C, |1 C
   {if(*(p+i)!=0) k++;, Z) g4 j5 L5 W
     if(k==q)/ {: Z( ?) w( i9 R: A
      { *(p+i)=0;
% I2 m7 N, m; x3 K3 ~2 y        k=0;' j" }2 Z; b2 \1 @
        m++;1 {2 n& c" S9 ~, }" Y% J. Q
      }9 {# G7 `/ C* O! E, B
    i++;
. ~) Q$ w7 s  O% S    if(i==n)i=0;
  C5 N1 B2 M& P$ j9 W- M1 A   }% t( |; c/ o6 S
  while(*p==0)p++;
+ O' z* f) o) j4 w    printf("The last one is NO:%d\n",*p);1 |7 S' \/ q: q+ a8 t, {, d8 a
     getch();
- U# d0 r. A' Q2 C# g& G& d6 T1 w, V
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;& e8 k: s0 o8 r, y1 Y  U
namespace 又费马达又费电
/ X# y  v7 h% K9 L5 n( T$ C{3 R# w4 e6 J% ]
    class Program
! p! t/ F! q2 E4 @- I$ v+ K' ~3 q    {
" b8 g- v1 d  u; J2 ?% x        static void Main(string[] args)
5 I$ P* ~# f. ^        {& A! O7 h2 g( |' a
            int m, n;
+ H% U% V4 F0 f: V6 k2 f            Console.WriteLine("请输入数组长度");% U; O1 N: H) d7 m$ t0 b$ h
            m = int.Parse(Console.ReadLine());//m为数组的大小
3 a& [9 C0 B- R* e) `; E  p; {& ?# e            Console.WriteLine("请输入要截取数字的大小");
7 G! ^7 C- u; C( |( l            n = int.Parse(Console.ReadLine());
, g/ R# ~* ?, K, V: l            int [] numw=new int% l- K- |: ^0 D1 b* {7 X% p7 z- B
7 I7 s3 u: R+ R% Q/ x
&shy;&shy;&shy;;4 J) I, X: D" t" Z5 l, v4 S
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数* \# a6 X: U1 E! \: L$ G1 k2 i
            {
0 P9 y* b. q5 B" }) w! [) ]% x- ?                numw[j - 1] = j;
; Z1 c0 ?5 @8 @, J! m            }" n  v" G, y$ _& X  @' ?) C/ f
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
7 c& x/ L: u4 M$ t            while (d != m - 1)
# m- D! k2 @2 k8 X( c9 q* L            {2 z1 Z2 I7 N: r, h% @
                if (i == m && d != m - 1)
( {3 j5 N+ t9 h& P6 ~. m* Q                {9 z  u' \1 E# W$ R! P7 J
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
& H6 u4 u2 a1 s. ^1 e                    continue;7 M! ?+ [1 W3 O# u" ~+ R
                }
! w9 {) q0 R- x+ R% m# F                else
( ]7 z- J; @. a0 _+ B                {
. u6 p6 g6 K# ?+ a( l" b                    if (numw[i] != 0)
( x2 b" P* `; s0 S                    {
( a6 R+ f- ~" f+ u& P" }( W& V                        i++;! ?* {: G# F; s" e/ V
                        k++;
0 q# P5 e) ^% t7 o4 `1 D                        if (k == n)* Z5 g, r$ j* K6 N
                        {& _- N! n2 X/ k" b3 w8 k* p# r. L
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
# x9 Y3 U  ?/ F' q, S                            k = 0;
; b# S' p% }, {              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
3 H/ i+ C8 ]8 B! a                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);9 j, H" E5 R4 ]8 W
                        }
4 f* T7 L9 J+ O                        else//输出暂时还没有改变数组元素的值
- W) ?4 v- x# d- X: g                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);  x/ t4 h6 S+ L. ~
                    }" w  ]9 T) |" q0 ^
                    else1 O6 ~6 J) L6 h8 m' P
                        i++;//数组元素为0,直接跳过,不计数。。。3 o5 o; w2 d4 z8 f& D0 F) I; c
                }
; P9 X* A' G6 J% t , ~$ ^; _$ ~1 i

' Q5 n2 l9 o2 u            }//结束while循环
8 Q/ a& W- w& ^# p% \* j9 m; p1 V            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
$ G. M, y, e/ [0 H           
9 c9 T. l+ i" w+ R; ]# E2 P                if (numw[i] != 0)2 @1 @7 s( S: P) ~7 @
                    Console.WriteLine(numw[i]);- H# g3 g; j3 E' Q- H3 i& k/ E& _
           2 Y3 v* H7 J$ \& j" C. W1 g
            Console.ReadLine();
, v( `1 F5 H& q* P! J        }: W" r  y- n* Y1 d' v. J. x1 Q) N- T
    }( r+ r0 W+ D+ M; G  z' ?0 y
}& ~  B6 A; p1 N5 e: n8 ~
小甲鱼最新课程 -> 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-7-19 09:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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