鱼C论坛

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

猴子问题

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

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

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

x
大家好!
# m( L% @! r8 D这几天我在忙着编一个问题,我用了一种方法编出来!
- o% T- q9 @' V) x但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
& X8 z2 X& c9 @6 C: i" F8 S; a注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 6 _- b1 d0 h" S. n

5 R- f# F/ s! P: k: u: p% s* i' v0 G6 l6 P" g
                            题目
. m# d% H" p6 g3 }: H山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
( Y+ j& k" C$ b& V第一种方法:利用循环链表
' y+ P/ J- w& c#include<stdio.h>
$ t8 d- H/ k# c# R! w- _* @* F#include<malloc.h>/ f1 L0 {; u3 f  _) G8 D
#define M 8            //共有8只猴子) h/ S6 z, e9 C8 |
#define N 3            //数到3只时退出第三只) Z7 v$ |) M' X7 \! E0 ^
typedef struct monkey; b5 V$ q' K  L9 r0 }( ^5 E
{int number;
* h/ x/ |: V4 w9 Y6 f9 f) f) r7 Gint flag;# K* ]0 F! k" G1 c/ e3 V
struct monkey* next;" X7 {# w; M- h& I  A6 G
}MONKEY;6 Y# g/ e* y1 N0 C
main()
# g5 n! P* |7 u; @3 A$ J{ MONKEY *head=NULL,*p,*s;; g& z- T3 b0 n8 }- M# y
  int i,sum=0,count=0;
+ z6 }1 i& f, J  N2 Q3 _( k  clrscr();              //清屏
! l4 n$ b7 |/ c/ Q6 O  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存) n5 b* h0 Q4 _% v/ K
  p->number=1;p->flag=1;
" o& z+ l* |4 k0 R. `  p->next=head;3 i8 i6 V0 Q$ N2 }0 A+ n+ U
  head=p;
% o# A+ ]0 b2 g' |; y; V  for(i=2;i<=M;i++)2 O9 O9 H" q7 m9 Q1 S( g
    { s=(MONKEY *)malloc(sizeof(MONKEY));
" p% S, g2 L  R& `: y$ s: A) I     s->number=i;s->flag=1;
+ c, w# P+ U! ^0 Z5 w) u$ f% z     s->next=head;
% h0 W* y8 E9 }     p->next=s;p=p->next;' P4 R3 A/ J; y
    }. a6 C6 D1 ?0 M6 D
    p=head;7 r( `; E1 _) y; z
   for(;;)0 K; q4 {; \: c- d
    {if(p->flag==1)
+ _: S+ M( _" r% M9 y5 U3 P       count++;
! \. P6 \  P( j* F- q9 M     if(count==N)7 h0 {( Q4 V3 R* _, E' ]8 {/ I$ c
        {p->flag=0;$ d- ]; q' l; n; s
         count=0;$ r0 x5 i/ m  w# R
         sum++;}8 R1 y9 g, y" W- }  i
     if(sum==M-1). K& A% H) b4 ~1 O' ~7 u8 M1 S; c. s
        break;
9 Z6 S0 N  P/ Y& h& F: w2 p9 g( N     p=p->next;
$ j1 `8 P- u; R4 t! N    }- {/ i2 Z# g% a
    p=' q9 Z# n) z) U8 P1 s4 M" F
    head;
- L/ ?" p* A) ~' Y    for(i=1;i<=M;i++)
+ y" y' `7 P0 o7 Q  ?; S' @/ P' s    { if(p->flag==1)
# R' A0 m+ |5 F        printf("\t%d",p->number);2 |0 ~: T& P: B
      p=p->next;
0 \& V% I0 r/ j    }
9 u% z% n+ {# c8 w4 Y, n
0 ~" {0 d) F$ F5 U7 s7 S1 Y/ j5 k- T' q% ~9 t* h$ n. d, P

* G, A9 f& {4 R3 v0 I6 B}

$ D3 i6 D+ F% j+ h8 r第二种方法:数组
5 a4 q4 p; c/ K& E$ V#include<stdio.h>, k# x4 T8 A, m3 T
#define M 8% u/ d, ]  o8 [+ r( d
struct monkey0 E( p5 i4 [1 A" R. F4 J" R- i
{int number;! p; p+ Z& [$ T* z% [3 D
int nextp;) @1 R6 u& ~0 d* q$ G/ o* \9 ]5 x
}link[M+1];
1 x9 e9 \2 F! |* n) Y3 q& z: V) \- S  F0 M
void main()$ o: J/ ^9 d, c. d2 [
{int i,count,h;
" a# Q6 g8 _' p1 p. Y4 f3 qfor(i=1;i<=M;i++)
, V$ M# w! X" h+ d{  if(i==M)
4 ?0 B; j3 ~! ~2 U4 |   link[i].nextp=1;
  {% t9 L' S; T0 q* [# A/ H   else
: Z; \, f3 n6 b   link[i].nextp=i+1;
5 q- z! k3 m. w0 K, n! P# j  link[i].number=i;+ b2 N8 g& e/ U  u) S2 R
}
" J6 _7 h3 J3 N) G9 rprintf("\n");2 _2 |/ g* p0 |
count=0;) ?+ ~% F/ q( p4 [6 ~
h=M;8 U) x& F5 q  n- i  R! }
printf("依次退出的猴子: \n");7 \8 Z& `$ ^" x$ r  c0 ]" @' L4 _
while(count<M-1)
8 T- u* O( _9 D, _! l{i=0;
* P" A8 c/ W& s" awhile(i!=3), r8 t$ h( f5 f! m" O  F
{ h=link[h].nextp;, m5 N) c3 ^4 r5 ], y
   if(link[h].number)
( L0 H! c- K9 ?, z4 }, o     i++;}: X" {4 L: H% K; Y4 j3 \/ w  f& Q7 c

7 n: ^+ T3 ?5 n- Rprintf("%4d",link[h].number);* I" B# z: s( W9 v& v+ ^4 D- y
link[h].number=0;% ]+ y0 r! j$ y( k3 r& q
count++;1 y7 N3 f1 C2 H9 B9 E9 A: \
}5 M6 O; t& h( Q, [" F4 ~! A2 M

( _  c1 a. c) f! i+ A: _5 Qprintf("\n大王是:");7 b/ e) Y& _, M  x
  for(i=1;i<=M;i++)
2 q2 F3 F: e; C. l6 ~* s( i  if(link[i].number)1 f1 _$ k/ \- K) j  f
    printf("%3d\n",link[i].number);9 {2 V0 o3 \. {
6 U! W0 M- c0 Y/ Y* L* a

- g. w0 x; u! H6 |6 i}

1 R/ n) o1 F; [6 d) L8 W第三种是普通方法for循环
# P" O0 ~' Z. Y
#include<stdio.h>
  H' v( {; J5 J5 g, f- dvoid main()
3 U3 j! h, J+ x{ int i,k,m,n,num[50],q,*p;% b. v1 L& o( N& k! f; ]
    clrscr();
$ a( m+ \- d3 n6 w2 l+ H   printf("input number of person: n=");. v) S: ]8 Q% t- |9 K( i
    scanf("%d",&n);
& a6 G  y4 \; p- f, F" ?4 lprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只* Z) R5 \# P# \# {! ?& O! ?
    scanf("%d",&q);& @! j7 l: O6 ~1 n1 O$ ]' Z* k- P
   p=num;7 y% {; I0 S! f/ ^2 |2 G( c# A
  for(i=0;i<n;i++)1 }0 f) s" V) k1 `: K# h0 ?% {
    *(p+i)=i+1;
) T$ j; ?5 n0 G- f8 ^! P" ~   i=0;
8 @$ i: V/ G! j: `   k=0;
2 y9 ]7 O2 B6 b5 a" ~5 N   m=0;
3 X1 \2 ^' Y8 q* H0 j. a  while(m<n-1)
4 z9 h% z$ [, c; Z( N- |   {if(*(p+i)!=0) k++;3 H4 U' f$ O' s" G! P2 T
     if(k==q)
5 W/ x( W7 h/ s' k# F+ f3 f      { *(p+i)=0;
  @) W, K& N& u& e1 `        k=0;$ C# Y3 {) u  R
        m++;9 k2 Q% m3 I  h; G# z* F
      }. K' j: i  J% S. `9 ^
    i++;1 N. C+ K- d0 m0 y
    if(i==n)i=0;% \! {. P% z, f' Q; m
   }) }0 N$ u& [: \7 ]1 O
  while(*p==0)p++;
2 c2 G! |- \) Q6 s3 a- L    printf("The last one is NO:%d\n",*p);* {" r& W& B0 \& x) U! K
     getch();! z6 G$ s# A! J! x

# f$ ]( k, _, q* M1 Z9 B8 {}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;7 c- @) m5 n& ~; P- ~
namespace 又费马达又费电
. J8 K' S) U. V5 _. ~- K{" \; _' b; _2 f% P
    class Program
( ~$ {. n+ n- _$ g& G- y# w    {2 `8 W2 A" p1 l/ ]4 T; K0 d: h
        static void Main(string[] args)0 X& J* i/ B$ @/ o, b' `4 o; ?: M# Z
        {
, i! [2 @! {5 B' ]! h& [+ P, y1 |            int m, n;/ w: j$ W& Y, O8 [5 S+ o5 m- h
            Console.WriteLine("请输入数组长度");4 |1 T' T. I* @1 u
            m = int.Parse(Console.ReadLine());//m为数组的大小1 `& b% o0 `2 e, I1 q" |  I
            Console.WriteLine("请输入要截取数字的大小");
2 D# [) e" H" \            n = int.Parse(Console.ReadLine());% |* ~# Q, n6 p/ P' o
            int [] numw=new int' n" ?& F$ W& N) e* u, K- }& {4 ~
3 `- r7 r! ~& E* ]+ v  h
&shy;&shy;&shy;;$ r$ Z2 F; W$ `% X+ W
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
  ^% c/ Y6 J6 e- U! _- `            {
' N( Q7 `  m- U* J                numw[j - 1] = j;& c/ B2 R5 e7 _1 n; v9 d
            }
% W: s4 z2 g, e# w            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!1 b; m( w. ^: F) `3 C6 L5 j
            while (d != m - 1)
( `0 y2 F  a" `( E3 ~5 K1 t            {; g0 G# l6 D& @, I- T
                if (i == m && d != m - 1)+ U) S3 s4 ]! C- a+ y
                {
8 \2 W5 P. ~4 w2 E1 ], e& \' }+ F; C                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
( E3 H/ A1 F; }  n! y                    continue;' z8 ~9 J! p2 `. O
                }
. j5 y4 h) R& i9 e3 U                else4 e7 j! V3 j( V3 [
                {0 ^1 c$ L+ e' e" |  a
                    if (numw[i] != 0)% L& N) p4 X; F. D
                    {8 P/ T1 k6 A$ Y4 @
                        i++;2 d' K7 v. B& V
                        k++;
  X( `0 ?0 r; C, E2 }- s+ i- _/ n& i                        if (k == n)/ D3 I: U; w" S- I6 u
                        {
. W( X) \9 x; f( z0 f                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
) M7 E. ?  S6 J) |6 R; @                            k = 0;  N9 U6 }, z0 D; L& z
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
- a! L0 c4 i9 U4 c$ _  P' Y* k' @                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);  G, s  U4 H. r. Z/ v) y8 [6 k6 T
                        }* ~* s/ \. x3 {+ R  ^; d7 L
                        else//输出暂时还没有改变数组元素的值- ~+ ]4 \& V$ _) l5 q
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
: }  @  {1 c5 X- J                    }. J" t2 c4 S4 o4 R
                    else6 r2 ^8 x6 N- O0 A# |
                        i++;//数组元素为0,直接跳过,不计数。。。, ?, j9 h& {* B' E4 ^  [
                }
! F6 v" V4 K1 H7 n' F8 C $ \; E; |" \$ c) O

0 Q& f0 Z! @' \5 i& h3 k# H            }//结束while循环
3 z7 A4 |4 v! U  J            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
) L- ?3 H' T1 j: ]4 p; U# Q           2 P! F- z, _; ^: O! U
                if (numw[i] != 0)
( ?/ ~3 t1 `# i' H1 G$ r! r                    Console.WriteLine(numw[i]);) x; a' n& A) S/ w) j  L: B
           + k* [) h9 ]) o2 E  \  g
            Console.ReadLine();8 c8 Z; ~5 G) Y
        }" e2 D0 J2 @2 F* u% d0 O9 k
    }
/ O2 U( B" y0 n4 Q}2 a3 \* h7 G  {, X- h! R2 B$ M4 H1 S
小甲鱼最新课程 -> 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-4 21:05

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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