鱼C论坛

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

猴子问题

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

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

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

x
大家好!  G$ P# N- ^- l0 A! V0 Z. Y
这几天我在忙着编一个问题,我用了一种方法编出来!, R( S; u0 F8 j) Y
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!9 l. w/ ?$ h! m% f
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 8 Z. Z5 q$ h0 o8 ~9 {6 z
5 A- p* @& r7 r* h: c
4 T% I& J; v. m7 f" U, Y6 C5 N
                            题目
; f: S3 J9 [- A9 _" ~山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
- c% t) c& S0 P第一种方法:利用循环链表
+ F: ~# s. [: C" w2 j0 s! l) Q8 j#include<stdio.h>
; i! @2 n) R/ [. t/ {" h#include<malloc.h>
$ O! }" b: K. D* g6 w#define M 8            //共有8只猴子
5 t. }  |0 A! H& @) g% D6 |#define N 3            //数到3只时退出第三只
7 g6 y( `; b+ i8 E! Ctypedef struct monkey3 Z; y* g. ?: g2 j4 ~. @
{int number;
- Q( W9 T# v4 h1 M5 j- Z$ v' |8 ^int flag;
; s" Y- z, I1 D% U  h1 J  D  P) _struct monkey* next;
! V" D6 g3 i! p/ t& T( }/ z}MONKEY;) H3 n0 _2 x$ d) P( P5 k, J
main()
2 }$ O$ v' T# d2 Q3 f: J+ M+ }( G{ MONKEY *head=NULL,*p,*s;. c2 w: z3 p! |
  int i,sum=0,count=0;
+ f: ]( n- ^7 s! w$ F/ O- ~( i. ?  clrscr();              //清屏
, @3 }1 R% |9 k% S6 S) Q9 Y# S  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
4 V! ?0 T/ T( z8 A3 {  p->number=1;p->flag=1;/ o$ v+ S" e) k! N& u9 i
  p->next=head;( u% o! F3 z+ g( R/ B, o  F
  head=p;
+ n  ]$ C2 \2 ^+ ^; M; d* r% S  for(i=2;i<=M;i++)" x3 ?' _0 W1 ^5 ~
    { s=(MONKEY *)malloc(sizeof(MONKEY));8 x+ @! @, p& L
     s->number=i;s->flag=1;
( T0 Q/ R# J& o" q     s->next=head;
' q8 I* V3 |& U: N5 y     p->next=s;p=p->next;
4 X0 \' {, }3 Z9 ]7 h. ]8 }  z/ u    }6 ^6 h! p9 b( l0 i4 [; q/ M# \$ M% R
    p=head;3 }' x  l; @8 Q: S& j1 C
   for(;;)
' q( c( W- ~/ ^+ b& J) v6 {    {if(p->flag==1)
/ F4 d8 V! E6 r5 [       count++;# ?3 p$ _7 V% o7 b' M
     if(count==N)4 w$ z5 M& `4 T4 ^
        {p->flag=0;& G4 i/ e5 i8 A! J1 s
         count=0;7 ^$ v' \* t# S  v" b3 u$ z% q
         sum++;}# k. l. h8 m* K
     if(sum==M-1)
- B0 T1 @. P( x" V3 M  m9 i( G        break;
5 V3 Z' j% y! e& a& t     p=p->next;" x, r, ~6 x7 F3 c
    }+ ]( R0 e0 V+ G% y% K! U2 R- L8 _
    p=- `; W# D0 g( b/ `7 p9 o! h
    head;' O* B  J, r/ u9 y- j
    for(i=1;i<=M;i++)
. Q) b0 Q' h' v/ y6 Y* Z& X" h    { if(p->flag==1)
8 T( h+ ]  z/ F  @6 L$ r9 Z        printf("\t%d",p->number);
) W) Q! S' w0 W" U$ Z8 y* r/ _' D      p=p->next;2 ?' v) q  u# o/ V7 ~4 d
    }
9 k+ R% I& n% [$ ]4 B6 h
- {5 R- h" q% \0 ], d" I/ m& g( l' p* [$ _. p4 g
6 h, F, u! w8 C$ M
}
: n- U( I/ \/ i3 n+ a
第二种方法:数组
( p8 ~' [9 N9 T0 C. o#include<stdio.h>: p: z% h" }" U( h0 c  J
#define M 8# q  y. f; v9 y, t3 e( Y1 j" `
struct monkey
% r3 J8 e# P; b  @9 V3 Y: X{int number;
- ]: c: i4 F# ?' M) k1 S- w1 eint nextp;
7 U+ ?8 i" p+ ^( F$ n}link[M+1];
: {2 C9 x6 R& f$ F; A7 @/ C% B7 y- Z8 |4 Y8 ~: z; J
void main()
6 a# M" u' L& x{int i,count,h;, o' T5 D- _0 ]2 @& V4 Y$ t5 G
for(i=1;i<=M;i++)
% V% f/ u( f  G{  if(i==M)
1 R- s& Z& Z3 U3 f   link[i].nextp=1;2 T" Y: x! B5 r1 g
   else4 J) Q1 Q* D& ~- x5 R, |
   link[i].nextp=i+1;" O4 _1 Z, Q* a4 A1 G3 G
  link[i].number=i;
) S2 t; ?% |1 `3 K, b}- _. U% G7 x0 |( H5 Y
printf("\n");8 K' G5 A: j& R1 c
count=0;& ^( S0 z6 c8 N0 M  }" m
h=M;
. _3 c+ N# d6 ]2 o3 P: jprintf("依次退出的猴子: \n");6 E: k1 ?5 c! I7 ?% G8 L
while(count<M-1)
% F7 ]* G. J$ A: y{i=0;
. |; ]6 \" {- d5 U# M/ Ewhile(i!=3), [9 k& n/ ]" H  \( ~
{ h=link[h].nextp;
9 i5 S" w+ f, Y  g   if(link[h].number)
1 W& k0 M# u3 Q& g  S7 G; ^     i++;}
$ i% w  O) b8 T: u# m, L' w7 t1 ^+ M2 ~4 f
printf("%4d",link[h].number);6 D+ y" J  K* r2 A6 t
link[h].number=0;( K. W  R# l5 D3 w& v' T
count++;
5 I) W1 B! z2 ~0 d( ]3 U$ d1 P+ i5 Q}6 c/ z9 b; L3 S. c. @( I

& w% p1 ^7 c# Y3 f6 V% f1 rprintf("\n大王是:");
+ s5 j' J/ [% k" ^) u- ]  for(i=1;i<=M;i++)4 C/ h3 h3 ?$ r" R: L  p
  if(link[i].number)& J3 s9 W- E$ [! l4 X
    printf("%3d\n",link[i].number);5 f+ o, _# M* p
' g0 Q6 c$ L* U$ o1 A
8 `* j8 h, M  u7 v$ \
}
3 s" |1 H8 W/ l' \) e, e" j
第三种是普通方法for循环

  n2 L: B( |# W1 E6 ~#include<stdio.h>2 m7 X8 a2 Y" q: O' P
void main()
9 K0 l- s( j( p* Z0 }, r{ int i,k,m,n,num[50],q,*p;
4 a8 w! N" w+ s; P0 Q& Z% ~    clrscr();) p( v; c9 t8 r" `
   printf("input number of person: n=");
7 ?$ H4 @2 R- N/ f/ G2 U% u    scanf("%d",&n);0 x, _. F% I4 C/ L% k" d6 V! G
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
4 M, j% l# G0 W( T, I- o! M    scanf("%d",&q);
& K$ x! \, ^4 A5 p# l( ~  s   p=num;
$ V# R; K2 S! \+ p( P  for(i=0;i<n;i++)
7 Q, ?. q9 `0 T! V; h8 x    *(p+i)=i+1;& f  Q8 J6 E' \$ c' h
   i=0;' ]6 d% H: x& ]9 N* _
   k=0;
8 O! B  A6 @! h   m=0;* Y- ?: R, q' j/ V
  while(m<n-1)5 A. l9 n9 {& R9 L* H* s1 u
   {if(*(p+i)!=0) k++;
1 }4 S! F; [$ o8 v- X) F     if(k==q); k6 a* V* D' n( F. e; L% M
      { *(p+i)=0;& Y( o0 v7 d) c4 ^
        k=0;$ @8 L1 V  e8 q
        m++;
$ F/ o/ D6 z, P$ G2 a  u* p# @8 j      }
4 U4 v# [( s6 W* }) \" r: b4 W    i++;
" u1 q6 O$ y- q" f/ x% B    if(i==n)i=0;
  ~1 z( v% t, X   }
* a- ^7 j# g! c  while(*p==0)p++;
  t" k8 A1 L4 S- c    printf("The last one is NO:%d\n",*p);
2 Q3 O4 ?- {8 ?( I6 n     getch();0 d. d: F) E% z: a
, F6 I* ~9 f& N! P' P* n) K. F4 G
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
/ w- m  j5 o5 Lnamespace 又费马达又费电* U' M- \' Y; e; p" `+ b& h* O* J
{
2 v5 {0 l" j- [% P) n! R    class Program1 B( q! @% m/ p# P/ u+ i
    {
6 ?" [4 }$ I5 R        static void Main(string[] args)
! a6 S) O. w) c8 p/ ^        {! Z! |; v0 l! k* D/ y% \
            int m, n;
5 Z2 E2 n( @0 X8 D" r! j3 p            Console.WriteLine("请输入数组长度");$ \4 i8 w1 k7 O6 V, y% g
            m = int.Parse(Console.ReadLine());//m为数组的大小! }: ^6 }- \6 N" f( L& A
            Console.WriteLine("请输入要截取数字的大小");2 O7 I' c' i7 D2 F8 H; F
            n = int.Parse(Console.ReadLine());8 k5 n) W* I7 m* @$ r
            int [] numw=new int5 |+ @, t, @6 w. Q& \
9 l- U9 _) `  \- Y# u5 q7 ^
&shy;&shy;&shy;;
+ G0 D0 ^. r0 B! C            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
* Z! ?# d  V) @6 S- V            {
, L/ p# H! Y0 @% w6 O                numw[j - 1] = j;+ y: E$ N- Z  g/ D; f+ S
            }
' Y) [# f1 Y# S7 i) P            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
. O1 a( j- g+ d# ~( l7 \            while (d != m - 1)
6 A, r2 L/ a5 O& @            {0 |: @; I7 Z+ L- ~# v' ?) o5 i
                if (i == m && d != m - 1)
+ ~$ _" D' M9 _. g                {
2 p1 P1 l+ h' z( A7 G+ Z3 R: n+ b                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!9 x- y! E! b4 ?: Z8 O
                    continue;4 Y3 W3 V/ I' E' z/ t2 }. a9 e
                }
; U1 H/ B9 r, ?; H2 y# i                else8 c. P+ p" U! R6 q
                {
& M1 _4 Z, s* l1 z, c' F3 f                    if (numw[i] != 0)
9 P. f$ ]/ g7 Z2 `2 {' i" R: K+ F7 A                    {
1 y5 \0 Y. o! E7 J) @$ P/ D- n7 f                        i++;& R5 C0 E& _# E+ R
                        k++;% @9 P3 _1 D" Y) U# g
                        if (k == n); @  I1 f' ~7 J
                        {
, R( K5 _- N. F0 K                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
3 j9 U" f7 g7 S                            k = 0;
( D$ M9 V  a2 q4 J8 O              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
0 k2 B; ]3 m! g' ~5 t                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);$ O, K: q7 h0 s, O; m) X% }2 Z
                        }% \3 }+ L  W+ i! B, U% j* n) W5 N
                        else//输出暂时还没有改变数组元素的值
# Z  B: I8 u4 z! i5 d" I                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
) l1 ^. {2 _& z' f                    }  R: |& l, j1 v7 F6 L6 ~
                    else
) q+ M" S9 u6 i/ |7 h                        i++;//数组元素为0,直接跳过,不计数。。。  `# x3 @, X9 [  Y6 z
                }
& f/ w6 _9 I9 E8 o 7 t3 |8 |" b9 _( g6 ]9 S; }; ^

  A) \9 ]! \$ r* l( j" a% a            }//结束while循环
2 O  o, h+ _5 M# T            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
1 C: R0 Z! m5 F           
- J3 S7 B1 T# I1 y1 m                if (numw[i] != 0)
, W* H* _; `- _) L2 }% k4 j                    Console.WriteLine(numw[i]);- q$ u7 v% ^7 v* ?4 X- X# L. W
           % s8 U: T. o$ k/ C/ F+ e
            Console.ReadLine();
& }& R# l# p$ k# E; G        }" ]8 o# M5 w: y4 Y( |
    }4 ~' G5 h+ d% n" R
}
) [; N9 p- L9 P! n
小甲鱼最新课程 -> 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-16 12:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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