鱼C论坛

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

猴子问题

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

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

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

x
大家好!
/ U, t& U: V! ]) o这几天我在忙着编一个问题,我用了一种方法编出来!9 }* X6 L+ j5 X3 G  O
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!. j3 ]% {, U  L0 O0 @! q  s! S
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
# K6 k* w: I6 ~( c
+ E; S4 C; m+ @" h
9 e7 X/ @: A( r/ F* Y- Y" K
                            题目8 ~7 V* K1 Y' o8 U5 G: j! g
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
8 r9 W4 x: g8 U- w/ S( l( a第一种方法:利用循环链表
+ h8 K+ W# N2 l% U* u9 d& [#include<stdio.h>
. u# ?8 g% f* |& V9 J  Z#include<malloc.h>: B7 i1 o& y4 a6 `- a, y9 z
#define M 8            //共有8只猴子6 i$ m3 B  l* e/ U, o: x+ v
#define N 3            //数到3只时退出第三只
( \! g3 P/ G3 ^4 }typedef struct monkey( q% |5 e1 B2 l$ _2 A( j
{int number;
7 U  k3 a) d& G, Q2 [' V) G" }( uint flag;* H( B% Y' Z/ [+ I! ^7 t; A0 E
struct monkey* next;* n0 W, g3 ]9 u
}MONKEY;
7 p( i' `9 R$ dmain()6 h7 U" K; Y4 t6 T% \1 z, D' a
{ MONKEY *head=NULL,*p,*s;
- P0 ~! v9 v  }' O3 B  int i,sum=0,count=0;) P! r0 X' b  V' [) s7 M
  clrscr();              //清屏
3 F7 q6 I# x! ~$ T, i& }* m" Z" J  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
; Y6 x. W, ?8 s) n& s3 o- D  p->number=1;p->flag=1;- S& Q2 W# x- f7 q
  p->next=head;9 W6 _) c; {, C, B8 ]: V# `+ l5 ]
  head=p;
8 C( K  l6 |6 o  for(i=2;i<=M;i++)
  g# B: w# g  }# e* S' E    { s=(MONKEY *)malloc(sizeof(MONKEY));# G! _7 j7 I; b0 t
     s->number=i;s->flag=1;
% ]# p: ]& x7 Q     s->next=head;- f9 {" G, e4 A% ~
     p->next=s;p=p->next;3 o! f/ n# E2 H2 s0 N( R2 j% W
    }
  [9 R$ p; W1 K) H    p=head;. V8 N" ?. S; i6 b0 E! p
   for(;;)
8 W$ M% M3 f  @+ z+ g! L- A# P    {if(p->flag==1)
7 D  f% u6 r) q' p: M* K       count++;, W1 k( W4 ]7 s' U: W5 c& R& H" b
     if(count==N)1 [1 {4 t3 V! a( Z' R4 }  E
        {p->flag=0;$ Y. F. e( ?& ?9 O
         count=0;
5 R, S3 I( `3 W) _, J         sum++;}
0 a3 @+ o* ~- ?% m' `5 K5 p     if(sum==M-1)4 j2 [8 t  ~5 k. u. W9 R3 ]( }. i
        break;' j# @( {& _% H9 F
     p=p->next;
. L* f6 n( r6 i% r    }; H6 R8 f% o! I' F, H9 }) Q; I
    p=0 u3 K: u2 p7 I3 d# @$ {9 h7 G2 S1 _
    head;
; m) |' l0 V9 T8 W5 Q" K    for(i=1;i<=M;i++)
6 X  ?: f0 I$ s# A6 w    { if(p->flag==1)* Z! d* b7 n/ e& s: c& D, Z: i3 Y
        printf("\t%d",p->number);
! f, M% o% S# W! Z  p% [2 Y      p=p->next;! \$ J7 ]& ?, E" j
    }
1 t' E; |3 ]9 ]" C' E4 ^5 j2 |( @2 U, a' e

. I" Z6 m& J/ U. a& I1 U& E" g5 `/ {$ j
}

( d: r% s7 o, o第二种方法:数组
! }# L0 ]# v9 D( Z: P#include<stdio.h>
6 ~9 E% X0 f" m#define M 8' O8 B, W7 S  [/ @$ m; l# K; v
struct monkey& u% n6 _2 v( Q
{int number;+ y( _* p- x$ f. a$ w! O7 n0 K4 Y
int nextp;3 k" x! n4 G8 _" O* ^
}link[M+1];
: q; b: T3 r1 Y1 t
7 }. f3 R7 G  G+ `( pvoid main()
9 R* A* |7 S1 n4 @{int i,count,h;
6 u8 t% y. K: {( R! _$ o- Lfor(i=1;i<=M;i++)+ r8 v% g$ |% t" V4 \6 g
{  if(i==M)
, E! Q$ b- D+ p9 W/ C6 S9 A4 t3 l   link[i].nextp=1;
8 w% D- B6 m9 U3 b   else+ _) `( |& j. u- F
   link[i].nextp=i+1;( A  I8 ], b% @' v; u: ^; G
  link[i].number=i;
2 p* |, E1 x# M+ [- n7 l+ V}
3 O# y8 ]9 p. j5 M- B- S6 k! aprintf("\n");5 P- K# x& U5 Y9 }% b
count=0;) Q9 u, E) ]: h) O. N8 w, w& R
h=M;3 x# U1 f" O6 `4 g) p( R* Q
printf("依次退出的猴子: \n");- O5 S! E- c' s1 Z5 _% p. x# e
while(count<M-1)( [" Q& U, {7 N0 O6 |2 b
{i=0;2 `9 x* T, S) N+ H/ n9 Y0 }
while(i!=3)
: b1 A; r# ]8 b5 F& w{ h=link[h].nextp;; N+ Z- `: Q/ l9 Y
   if(link[h].number)) y4 v, _. ~/ n7 }
     i++;}
1 D$ O# `2 c+ t9 |
: W' x" w" K) z; i  jprintf("%4d",link[h].number);
) x' n7 L4 s6 l9 e  ?5 zlink[h].number=0;
' H1 O, F! G5 S6 D% U) ?( @: rcount++;
, q/ Z0 R" [9 ]# w# k* C5 e7 f2 g: A}
7 v/ {0 u: d1 E. _* o9 \  I) H2 h, `% J0 Q
printf("\n大王是:");3 J  ^( W+ A! M% p* n
  for(i=1;i<=M;i++)
8 b. s& r1 k8 U" I5 I5 p$ s9 g  if(link[i].number)
5 S1 W8 s, Y7 D# p5 l    printf("%3d\n",link[i].number);
' {1 {4 S& u- x9 A0 d' D* ^/ F, v  Z, O
% [1 Y% V: F( f4 M) n: j
}
' N4 @0 |* Y/ L. @" g& f9 s
第三种是普通方法for循环
& G! q  _7 o; v
#include<stdio.h>
& U- E6 O2 k( G2 [void main()/ Y/ _6 A" u: h
{ int i,k,m,n,num[50],q,*p;; n0 V; v) K- N: r* A1 c
    clrscr();
/ @( l2 E2 U9 E- O& [0 l3 J   printf("input number of person: n=");* R% O8 u, h4 w  O) K
    scanf("%d",&n);( y/ ]7 S: ]% E; |- K
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
) {6 d" {2 p- k. w6 M    scanf("%d",&q);  D& t$ a* |, e% U1 Y
   p=num;9 N; K* P# l2 W" }# g! h' |( R; @. @
  for(i=0;i<n;i++), q# A3 x+ b/ D- Y& q
    *(p+i)=i+1;
6 l2 l4 }  V* ?6 S$ k4 w/ m4 j   i=0;5 `5 J/ c) |9 F) X
   k=0;
9 i1 k$ u; u! z! h   m=0;
# |$ M' j5 {# }8 f& C8 f# u  while(m<n-1)& _5 C: {2 t; t6 L9 y! V
   {if(*(p+i)!=0) k++;
4 H4 U8 p' z$ }; E     if(k==q)6 q& ~: z# t2 D4 Q: `+ u
      { *(p+i)=0;
7 w/ U2 A6 p  x+ \, h        k=0;  {. h5 I1 c. [2 q
        m++;$ J# o8 i. f$ f9 Z! w
      }' E& R& |' W9 K
    i++;
% T/ [; K, u, B1 X+ G+ W    if(i==n)i=0;
) L8 I! q  V" S. A' W   }* e! X0 _. l4 p1 ^2 u' K6 p" V
  while(*p==0)p++;2 A; `" @: _) P' ]; F9 W. p& E5 w
    printf("The last one is NO:%d\n",*p);
: b9 T& E! o; k: N$ ^+ O4 A     getch();
! O# u) [2 c' P: n% \
6 ~& C7 t7 i9 B6 l7 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 l) w. cnamespace 又费马达又费电
* F' c: _8 ]+ K) }0 ]" [{
7 O" B6 X. q/ i3 V6 x$ {    class Program
7 g( l) z6 c/ x, d! o$ M    {9 g( O- D' ^( v7 S. R3 X! }2 d8 {8 {. p
        static void Main(string[] args)( {6 }3 f! d$ p3 n3 g& I
        {$ }* _5 u6 ]1 C6 \/ k  G
            int m, n;
/ ?) q& g2 E: z) h            Console.WriteLine("请输入数组长度");
7 z7 J6 N5 ^7 {            m = int.Parse(Console.ReadLine());//m为数组的大小
) K& |. q) \3 E3 l7 n7 U            Console.WriteLine("请输入要截取数字的大小");; E+ M& ]$ J: A, r& E& O0 f! r
            n = int.Parse(Console.ReadLine());& `2 n: a  D5 A- T4 I3 @
            int [] numw=new int
+ q# V3 T' z( b' E, h+ y% @, U1 ~! `1 @% m/ Q1 P! W5 m
&shy;&shy;&shy;;
! D2 T  d4 n' @            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
8 f% D$ o# D3 ^            {
; s1 O, X! j* P* N  B                numw[j - 1] = j;
/ \, [* i) K) T& W' N! ?& ?+ Y: _            }
: A# l1 g: _+ a# B5 ^1 ?  G            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
. t* ?7 g8 f  @' J) T            while (d != m - 1)1 ?, }: h* R' |
            {
9 w! T1 G# C, q' i' m* C  {8 Q                if (i == m && d != m - 1)
9 h# O/ l/ h3 n% s                {
: Q1 _/ A" K9 |0 _' y# z1 Y, X& P: W2 o                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
' M2 O: k! ^2 l. @/ b. A% v                    continue;2 J* |. D# b+ z+ I; e: `  P( g- X
                }
1 C* |, s) _5 r3 G& w3 k* H8 I( A                else
$ N$ @- r$ \5 p/ i$ H: f3 b. Q                {
; |" K  }: {2 q' x7 E# j                    if (numw[i] != 0)0 W- M* h0 B9 O$ ~+ w
                    {' _/ y; Y8 i  d1 j" J
                        i++;9 m7 C- p1 d% i6 K# M5 n
                        k++;
# A0 {) m5 u$ A$ h0 l                        if (k == n)
5 n. Q3 x: ~4 b/ S! m: y, @                        {$ \. W, X+ o% R! i- n1 [
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& O7 N  @' p9 b8 z
                            k = 0;9 l7 C3 y& W* v2 m$ ?& }3 V
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
4 N8 d4 w( g6 B( |; b  M: l) R" B                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);1 \* }2 _1 W. g4 s% o
                        }
- G" S0 ]; E8 d3 B( S                        else//输出暂时还没有改变数组元素的值' M+ W+ Q. W5 |$ s* \$ t7 k
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
' f7 C5 d& o; `                    }' [: P- v, u2 H) ~! @4 H
                    else$ [6 V. i% K; Z  _& O! x
                        i++;//数组元素为0,直接跳过,不计数。。。: q& X' y2 X5 ~- U& }
                }0 P) y/ u" W* c% |5 Q0 T3 L) a
& t) s$ ]9 r# h" A
- S! l( n& \) Y7 U8 M1 G& ]
            }//结束while循环" R1 r6 n/ B" P% `" S. a. z$ ?
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦" p1 j8 n6 a. h3 T3 P
           ' m$ H# \/ N, r, o' n
                if (numw[i] != 0)$ l2 v' o8 u. i' B" g
                    Console.WriteLine(numw[i]);
0 S/ d2 |! a  Y5 ^$ [           / }- n$ F) n5 c$ Q3 I
            Console.ReadLine();! S; b0 Y: J* o! E, s
        }1 e/ s, E. n/ a
    }+ M3 e- I& v' C, [* G
}5 K' c. j5 @+ }
小甲鱼最新课程 -> 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 22:17

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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