鱼C论坛

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

猴子问题

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

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

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

x
大家好!- H6 L1 F' @+ x  y
这几天我在忙着编一个问题,我用了一种方法编出来!
0 j$ ]: _6 u% v0 N4 X3 J但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ Q! b4 s7 z' u+ s! y" x2 G+ l
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
- i9 ^, b2 S4 B/ ^4 N! s" r
; R, W' a5 x  A% Z8 }
8 |) h2 h: t# `% v* B) m0 V1 M4 `6 m& r
                            题目
* h0 b/ v- ]6 y, d山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
* ^0 H8 z9 e  c# T: @1 v* o3 Q第一种方法:利用循环链表5 a! o. O9 K: G2 p- S" ^9 n
#include<stdio.h>/ F2 ~( Z, d* q/ l2 B3 z
#include<malloc.h>
5 }8 W" j  e# u! J- R7 y4 u#define M 8            //共有8只猴子0 x8 e, y% N  z' I" M" h9 Y
#define N 3            //数到3只时退出第三只
6 W9 F7 a3 A2 d9 k" O$ c6 Y' u! j$ Jtypedef struct monkey% f. U- o2 Y# ]: U% @4 N- {
{int number;) D0 V6 f  l4 P2 L
int flag;
" F: s8 ^$ I* l& E0 C% hstruct monkey* next;
( s1 i4 J2 N6 D) Q8 Y& R+ d}MONKEY;
, L/ M+ N9 F+ E! t. M5 hmain()4 X2 U  I) _* n
{ MONKEY *head=NULL,*p,*s;1 l+ d* U) ?7 G3 I
  int i,sum=0,count=0;1 N  L  G: T3 ?% H) b1 Y8 Z" `4 {) J" O
  clrscr();              //清屏) t$ ?- |& I! ~/ }
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
1 C8 e  i9 R9 Y4 ]! b, u  p->number=1;p->flag=1;
5 @- e! E# p+ y" l  p->next=head;& Y) M; Y/ ~& z4 g& z. b7 z
  head=p;8 y, g0 {7 Z/ R' \6 ]; G
  for(i=2;i<=M;i++)
! [3 P0 f/ @; C) Q    { s=(MONKEY *)malloc(sizeof(MONKEY));
) a/ d' b. [+ ?     s->number=i;s->flag=1;
0 F' \: o4 u5 A- {     s->next=head;
) \/ h5 ]4 v: ~8 F5 s     p->next=s;p=p->next;
9 K% T* s3 R$ F" X2 t4 y    }7 g; ]3 c1 m/ E  s7 q9 H6 P  v
    p=head;( }" _- y0 \/ A; a
   for(;;)6 s3 w0 r0 I( `) Y
    {if(p->flag==1); k6 @1 H& S& Y* W) }3 b2 @) [
       count++;# W1 b7 \, S5 e  x3 i- i+ d
     if(count==N)
  O( P# T9 l' Z# t3 B; z& S        {p->flag=0;
% F. H9 M6 e8 f' c: F( R" g% j         count=0;: _) E9 y" E+ w: h
         sum++;}; a' i7 E1 @- L' ]+ Y- P6 p$ o0 L
     if(sum==M-1)) u' {- ~8 R% X5 L3 B+ D' v) U; ~
        break;
! q: ^( L8 Y/ |1 q) m# h: @     p=p->next;: @; V# ?4 A# r2 y
    }* v+ ]: F; \3 V% m/ ^8 j3 l
    p=
1 @; r: F$ \+ F+ h* L7 u9 E    head;
. a% q) S5 a' m1 {2 Q- X    for(i=1;i<=M;i++), `1 i/ B* U& q$ K
    { if(p->flag==1); U* q$ M) ^0 p/ G- i1 {7 @# n
        printf("\t%d",p->number);9 i! d5 F1 B3 y3 e9 b& {4 r
      p=p->next;- o; t, \# b8 T) @
    }
( H: [3 A+ `8 m# Y
. ?6 D7 e* U, D( e% G! |
  D4 o% m! h# E
2 q" ~2 Y2 I( [3 q/ f}
% v5 U3 p2 ^8 ^" s3 k
第二种方法:数组, u4 f* {3 ]: b  Q
#include<stdio.h>3 n7 }! f. P: ^
#define M 8% f; I: K; {% a- M8 ]1 O  |2 c
struct monkey
4 y, x$ O0 l; w' R2 E{int number;+ c) Z* }7 x$ T! a- X/ t
int nextp;* w* o+ u( T( P9 ~- @
}link[M+1];
% h  T1 l$ @* c; z! x! Z+ Y8 Y! G1 E" c# N, L; U1 _* X8 U2 K
void main()
5 H# ?# B' e( b% O8 w8 u9 l{int i,count,h;
% S9 _  L9 ?+ [: ^for(i=1;i<=M;i++)
6 V% S' P) l: }- `0 S& e8 v{  if(i==M)
; {; R/ j" M' n1 h   link[i].nextp=1;
) U7 D. B. L, T6 u1 W1 J# f   else
: I5 E" Y  P8 B: x0 m  d! R+ H   link[i].nextp=i+1;% u$ |0 t& M# G$ ?, f& a8 }& O
  link[i].number=i;. W8 }: E; r7 X  m5 o0 I& D6 P6 r
}$ G( t( f1 |5 N% n
printf("\n");
: Y/ H7 @$ R2 c: P, \count=0;
  d% H  K# D$ t- xh=M;5 u8 h: l' J1 T% p$ ]; ^
printf("依次退出的猴子: \n");2 c- b# h  e4 ~- @  E( ?& L, b
while(count<M-1)
+ C' ?5 L! S" o" w$ N{i=0;
+ K0 G7 \/ C# N0 lwhile(i!=3)( r6 Q$ N1 o9 ^8 c5 z# {- g2 c8 v9 Q" d
{ h=link[h].nextp;
, |/ v% D. v; d2 o   if(link[h].number)+ N1 L/ b( J* z8 S/ m$ ]
     i++;}
0 O7 ~+ J5 Q  K2 A+ _8 Q1 Z
2 G' y* Q' G. Bprintf("%4d",link[h].number);/ E1 e( C: b5 U. ?. s8 }* j
link[h].number=0;+ I6 y  d2 n, y2 g! @1 r7 N: i
count++;
/ B. i" T' A& _9 D5 ?" q}4 _( W. `3 Z3 z$ ~9 z0 P
. p, n7 V/ O' V. l2 L. {( F
printf("\n大王是:");( l+ q: k  `" A& Y6 A# `
  for(i=1;i<=M;i++)3 U! i. b: d2 \3 Z6 _
  if(link[i].number)
4 i0 ^, c6 D& A. y9 L+ w4 O- q    printf("%3d\n",link[i].number);
& f( \, [% G1 I* j$ L- X) o( A' v% {
1 Y" e  W2 [  y/ @! V" x' ?. n4 G4 a0 c1 X: V
}

$ P) m7 r9 m6 K4 A- B第三种是普通方法for循环
! j7 V( |& l) T
#include<stdio.h>
/ n; k' s, a" g8 Hvoid main(), Y8 |7 B% I5 X$ ?
{ int i,k,m,n,num[50],q,*p;8 q- Q+ S; L5 J7 d" N
    clrscr();  b7 W7 G/ Q. b
   printf("input number of person: n=");
; H% ]9 p$ V( a& i. ?1 v5 I$ D    scanf("%d",&n);
$ U" G3 q7 p  s  j- q% M: `5 tprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只8 m% J3 ]+ ]! j! z  G# Z
    scanf("%d",&q);5 b$ j$ n- h" R
   p=num;
9 N# X5 `& h0 U  d: r$ [. w& ~# q* s  for(i=0;i<n;i++)
0 b& c9 [* V" G) K6 w    *(p+i)=i+1;
8 r$ l& z# a' g3 J9 x   i=0;
6 J; @8 B7 `- `* Y0 l0 w   k=0;
) ^4 w$ E' s  l) l% t% u& ?9 E   m=0;8 P  j2 h6 c& M7 W1 }7 p$ ~
  while(m<n-1)7 ]( W( `7 A. t" g& h
   {if(*(p+i)!=0) k++;( ^, M4 B2 M7 `2 p! s
     if(k==q)
# h; E. n% K& q' Q7 N; o1 e      { *(p+i)=0;( Q; h0 Q5 X2 C- h! Y% L, E, e
        k=0;
0 m4 W0 g# |0 G0 o* {        m++;" o; m- [- @  S, L
      }. w5 L4 D: F9 Y3 H7 U- Z% @2 p8 F
    i++;
" l0 ^" f; t# c: _, [    if(i==n)i=0;  |/ I3 E' _8 C
   }5 f  L- w3 d2 ?) w
  while(*p==0)p++;
& @/ u; j5 p6 F/ c1 q, {3 V    printf("The last one is NO:%d\n",*p);) F5 T6 ]: F6 N
     getch();: K+ W) G7 [* G8 w
- H4 N& E( |) F& d9 x2 Q+ h3 c7 t
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;6 M/ Q3 C6 _8 O4 n& c) w
namespace 又费马达又费电
5 a( ~# N- t& y5 P) t{
( g6 `0 l- m" b# ~/ R' L' ?    class Program/ ~) n" K8 L: {  K7 W
    {2 R# e4 R& c) K0 C& c1 s/ Z7 K% }9 c
        static void Main(string[] args)
# a9 X2 i6 I) f/ g4 K1 b  l9 \        {
, u, A; M- l; d( X* [/ l, R9 a            int m, n;
& w7 }; p7 a% }& A1 J4 K! }% D- K            Console.WriteLine("请输入数组长度");4 o% p6 u6 y  S+ R$ ]0 y
            m = int.Parse(Console.ReadLine());//m为数组的大小0 ^% P& S/ W4 c8 m/ p* [/ G, }
            Console.WriteLine("请输入要截取数字的大小");
& ]; g/ p0 I+ s4 e8 Y1 ^            n = int.Parse(Console.ReadLine());
; S8 K2 k7 h' L. o0 W            int [] numw=new int7 v$ D, ]3 t$ j" V, [; b
* c/ f  ^. \2 W0 C
&shy;&shy;&shy;;
* C; E! U1 z( H& ^0 A) o: ]. z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
$ l& Z2 ^5 e) A            {
/ Z9 _# |6 U% k8 r$ M% N                numw[j - 1] = j;, \5 V# [9 @7 T7 n6 ^: P7 v# y
            }
8 v; R* Q0 ~: I            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
7 T* B0 a) V: ]% V  y, d            while (d != m - 1)
/ j3 `5 @# p; g6 P- W4 D            {
; m  P/ P* S1 R3 S2 M! i                if (i == m && d != m - 1), j& Q% J& j6 P: }+ k0 q% F
                {8 O' z0 k6 D( t6 G- {8 n( V4 w- {
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
  h: v+ l8 C  s3 w                    continue;
% o/ G' V5 Z! V  V6 S4 J. P7 U                }
! F7 q! p; S& _& x: r                else9 j' }0 \7 [( ?8 |& X
                {
5 k# r- c+ d1 W                    if (numw[i] != 0)# B  M( p/ U& U; I- {
                    {
% s  N1 B8 `. `% B8 a$ n$ W9 M                        i++;
: |" F3 _% s3 w  t                        k++;
1 h5 g0 w' d& n6 H                        if (k == n)* X. P$ L( Y/ U" z5 W0 X( v* v
                        {
/ ^( B0 A+ q+ E' C- g, T" T4 h8 C; j! A                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
5 ?& _$ e, Q. e$ q8 P; I) W# R                            k = 0;
# y' E- {6 F- i; K& r4 i7 F              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
6 A6 T, U( W4 Z5 }- K                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
0 E$ K/ \, H( z& |' Q% p                        }
- w3 O% {; d) k                        else//输出暂时还没有改变数组元素的值
6 Z' i  J% `# j5 W1 V+ v  y                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);- z6 D. q9 u  @1 i4 w
                    }
& M9 d  V# o0 P) [: |& M                    else9 [* z' ]9 A8 K
                        i++;//数组元素为0,直接跳过,不计数。。。  [; w. R( Z! P% J- c9 M$ Z1 i
                }
- W: d- B) h$ N4 @" U& X1 h
+ i+ \( `; y" Q" F3 p/ A! h7 t
9 ~8 c% z& M2 ^! v9 O- b, j. T            }//结束while循环9 F% I1 L, R3 J" `
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦3 c5 ]/ e2 E3 z9 E0 F
           / T' [7 @4 Y+ R
                if (numw[i] != 0)1 ?4 L9 ]' g/ W# x) {+ K+ I4 [
                    Console.WriteLine(numw[i]);
+ I  Q$ ~7 `; q. D, C           
6 H5 M) G# R7 ]$ I  u            Console.ReadLine();
7 m- P' r/ d9 {/ c! y8 ]& t        }/ e4 _4 w- M2 N# I. b9 z
    }
( A. w8 x3 M) V  w3 ]/ C. D}: _* ^. g- M3 C  Z
小甲鱼最新课程 -> 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-3-28 12:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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