鱼C论坛

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

猴子问题

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

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

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

x
大家好!, `$ u) ~% L9 _- m( L
这几天我在忙着编一个问题,我用了一种方法编出来!* i  Y5 G: b# W  w$ k: }
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
+ d& V* _4 p5 ?1 Y0 f注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
- ~) h* P! _( v4 |2 e
( R3 k& W7 E4 u: U4 k3 i2 Y
7 g5 E2 a7 B+ k4 l& G( g8 g2 O
                            题目8 V* f% J5 p1 e1 C7 h% y7 m
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
: e; F' ~$ S+ G6 y3 ?第一种方法:利用循环链表
2 I+ u3 S" y" B# J% @/ G#include<stdio.h>7 z) d" j3 ?& H) |6 n( D
#include<malloc.h># J1 S& R. i9 T+ i
#define M 8            //共有8只猴子
- R0 T# W# G# a#define N 3            //数到3只时退出第三只' C5 |- b0 a! n9 k2 C- M
typedef struct monkey; x% @& F  r  {& v: X; m
{int number;
" g5 Q1 o9 E9 G: R6 P/ uint flag;
5 O2 J2 g1 g6 U$ f: }# o# f! O' l* Tstruct monkey* next;
9 X8 {8 `0 Y, F/ x' }1 E}MONKEY;4 l* ~3 N$ i1 V" L
main()$ Q( I& C: N9 g! P0 x$ Z; T& G" X
{ MONKEY *head=NULL,*p,*s;
$ B( B9 R8 u9 O6 B( {! b  int i,sum=0,count=0;4 ]% W1 v: Z' l( h
  clrscr();              //清屏
+ k; f; x6 \8 A+ T  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存. W3 [0 u8 y6 B' d5 B
  p->number=1;p->flag=1;
# {; C7 m" i" T6 V; N  p->next=head;
) U9 ~- H3 p2 O& z+ v% I( E0 e9 }  c  head=p;
& k2 |0 t" ^/ y+ ~! P  r" N% ?* M  for(i=2;i<=M;i++)
: k5 n: V6 t. ~/ a) W    { s=(MONKEY *)malloc(sizeof(MONKEY));
" Q& w' B+ ^+ m- P, ]! B     s->number=i;s->flag=1;) e" p& _, U$ E+ u2 L4 H5 {: [# ^
     s->next=head;
* ~. o! |1 l: F" N     p->next=s;p=p->next;0 L# {4 ~6 w( }8 m) m: x1 i
    }" }# _8 g( m% E$ T
    p=head;: z5 W' f3 J3 |0 O# |
   for(;;)# {0 w" f8 t- T3 X9 j
    {if(p->flag==1)! n0 P: ]5 H/ N2 E" Z, m* N3 X
       count++;
  L& r3 V) [6 I0 H: g1 J, K     if(count==N)3 r  |: c: O8 m/ T) [: }3 r' F% y
        {p->flag=0;& M4 T* W) n4 z) R3 Z3 B  G/ p
         count=0;
% e; b& A$ a* p( \         sum++;}+ O' L% t+ w6 D4 w8 M1 f
     if(sum==M-1)
# s: V2 z" y! k0 r5 P  M$ u0 p* u+ l        break;2 D+ \. p: l$ T' W2 a! U
     p=p->next;+ n! N, ?6 L# y( Y4 u5 i% o
    }$ f& ?% V' z' L% M) ?( d3 V
    p=1 V* ~% A. {8 X3 h: H, @) J
    head;
% e7 b% y: I+ l7 }8 g) ]" V9 Q: E/ T    for(i=1;i<=M;i++)) ]0 i! k7 v* E  t  s/ E
    { if(p->flag==1)+ Y2 t+ b9 R) [9 x
        printf("\t%d",p->number);
" V$ r2 v) t. p) `  U6 ~0 h/ A      p=p->next;
2 X: a% c& D; ^# C# [; a0 P+ @% g    }( [) I! u5 w0 q" e  j2 H/ p4 L
3 t0 b% E7 h/ S, P

  g7 N7 y0 g" p. D/ {' `+ C
& Y# c5 y; u( v* y3 e4 q}

! Q' _0 O1 _7 h0 f$ n第二种方法:数组
" b, j! o8 J' z4 G8 j#include<stdio.h>
0 {- H; g: l, d2 [( @#define M 8
% ?4 B7 {) ?, Y& M3 z+ M9 ?2 ]struct monkey
( S! \0 N8 o6 C9 R{int number;
; g! z4 Y! x" d% @- Mint nextp;
+ C; }6 s+ n$ S) o, y3 L}link[M+1];
/ m5 o3 Q+ C" T. p. ~. C
, y  T$ y- r5 N/ f4 S. Kvoid main()
8 E$ b/ {3 @8 U+ Q- }{int i,count,h;
) K# F( s) J* D4 s2 h5 Sfor(i=1;i<=M;i++): ]# M. D6 u2 v6 }
{  if(i==M)
; j9 P, v3 Z  V5 L# I8 C   link[i].nextp=1;
$ r! H5 a9 O6 U. d+ {   else: a: _( a  k: D2 C' h$ t8 @
   link[i].nextp=i+1;( w& w. j# T: V3 M1 ?
  link[i].number=i;1 I! F2 S* U8 k$ j$ @
}" I5 ?. F  E7 H
printf("\n");. b5 V7 g7 t+ n2 k
count=0;
/ d# _) a" y# Yh=M;
% f8 ~6 g8 `% p3 I4 y1 }# z& ]- Lprintf("依次退出的猴子: \n");
# o1 ]/ o% V% ~' Awhile(count<M-1)- h5 a) d* a- p" D* ^% s
{i=0;9 ]4 Q: b- c1 T5 {5 @( ^2 \
while(i!=3)
" C  N1 s$ Z, l{ h=link[h].nextp;
- V% j/ L! g$ J- Y0 m# Y   if(link[h].number)
  o. o3 H6 Q3 @5 _' m9 V4 `3 e6 b3 f     i++;}
+ N. n* L$ ?: Y2 {) X% O
4 S( K) T) T' Z0 U3 S& ]printf("%4d",link[h].number);
8 a$ b4 O$ D8 [! i* O9 ^5 Vlink[h].number=0;
9 S- l7 N, G- E/ scount++;" u+ S  a! b( H" P' A% _& K0 [
}; M2 j- N* w$ v; ^
, E  Z3 W0 l1 i  N+ S
printf("\n大王是:");5 e8 e; v8 J0 N
  for(i=1;i<=M;i++)! Z+ u0 o& g' v8 I+ f: @( Y: Q6 N, t
  if(link[i].number)
& B! S4 b8 t4 C4 f7 _0 r# s    printf("%3d\n",link[i].number);
( q" a" f& n0 e, N5 h( `- o* R' N  D* L5 u0 ?& g

! ~! h" k1 _& m  H}

) C3 g+ \: u! \( h: i9 f3 A第三种是普通方法for循环

' \. r) |/ U3 Q4 G+ \& i#include<stdio.h>8 }4 |! {: ], o0 r$ A5 h6 ]
void main()
5 C8 k1 y+ i/ s( v2 ^6 T{ int i,k,m,n,num[50],q,*p;6 M: L: }1 t% Q; J, V3 X
    clrscr();
6 u. X# e: y* t1 b) {; T# J- \   printf("input number of person: n=");
8 [' ^  y1 @# x) G. n) A    scanf("%d",&n);4 ]# ~. U$ T, k- q
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
! E: J! @( |, Y4 A    scanf("%d",&q);/ D. ^# Y+ G, r9 ]: W4 l
   p=num;
' R( b$ X4 |+ D) E  for(i=0;i<n;i++); q% L; e$ `& y4 n
    *(p+i)=i+1;
+ t* ~' U# v. y+ ~3 @   i=0;" ]/ L0 a4 S0 n0 R
   k=0;
( A7 R1 r4 R0 i8 d. p: X9 u   m=0;
  \" i: E. X7 _5 Z, [  while(m<n-1)  S5 g, e' l3 P8 j$ x
   {if(*(p+i)!=0) k++;3 r1 M0 M# D) K# y# Z
     if(k==q)8 j/ Y" W1 m, F3 f. R1 a: P
      { *(p+i)=0;( h8 J" Y+ |: t2 ~7 h3 b
        k=0;: K% o7 c( y  p* `1 l
        m++;
2 J7 s" Q# k: J# n# h; c1 F& b      }. ~+ ^/ d) m6 }
    i++;
/ x: i8 i" P, c, n' E9 X    if(i==n)i=0;; p) H  j' {, W
   }
% f6 R! X" P) F, H' b; |  while(*p==0)p++;
6 e0 @% T" [' A$ _5 ]) B4 E1 b% U    printf("The last one is NO:%d\n",*p);
3 ]0 {7 b! H0 a8 ?$ T6 A! I% {     getch();
. s1 r- p7 z: |% ]* w' N' l8 c2 ]6 Y3 N. Y3 c/ B
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
; u$ H! Q% J) W& K8 ]namespace 又费马达又费电
. w( q* n( L) C3 x{
1 \/ p2 d/ p: D; ^2 A& c# R' @4 _: E    class Program0 X' p6 G) ?9 I' E' Z
    {' ^. n: E0 h& O
        static void Main(string[] args)
$ m1 H$ l- u5 K! Y2 J* @        {
8 q2 [; R/ N: H4 ?* g1 b8 A4 B            int m, n;2 M0 w1 b# |3 F; D" Q8 N4 U4 _
            Console.WriteLine("请输入数组长度");
/ }7 G3 [7 b$ ^* a" V% Q            m = int.Parse(Console.ReadLine());//m为数组的大小
5 i; X0 [8 N) Z! Q1 E            Console.WriteLine("请输入要截取数字的大小");
' o' i: ]* U9 a  v            n = int.Parse(Console.ReadLine());  N) O/ x. v3 ~4 o6 N" h
            int [] numw=new int( {: Q, i+ r, u! g% |2 J

5 x) B3 z( h5 k( Y9 Z* r&shy;&shy;&shy;;0 z3 h8 f$ }7 ?# h9 A
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
5 ]1 T8 u1 u7 r" S2 K( |1 X            {- J6 f5 r! o7 R1 Y; D) p" y! y) W
                numw[j - 1] = j;$ S3 B* K$ ^2 ]* N0 R- S
            }
& D* h3 X' ]0 i, O            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!9 P  |3 g8 V$ ?8 }) `
            while (d != m - 1)$ Q% C- M% |! Z3 l
            {
2 {" T$ {# j" P7 l) L' e9 R5 z: {                if (i == m && d != m - 1)
3 R% ?8 r) j" W7 l( h$ A                {
+ C& T9 i0 [; G: d5 |( b" Y                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
: ?( b6 `1 g3 C) t: a9 T( `                    continue;
% C, h5 j, l8 r- l                }4 p" B# ^4 S5 `# Z$ y! m
                else
, ?& A/ [- a& z% N7 ]                {
- m: y+ C4 r5 u& A                    if (numw[i] != 0)
/ c8 A! t* w5 ?4 ~$ P' R7 a                    {
2 y0 }0 Z6 r8 R6 ^- p  X; J& I                        i++;  K# e8 Z$ x. c0 F9 v+ b
                        k++;
7 S4 j3 N" V# B3 D5 G+ A8 h                        if (k == n)
9 i6 Y6 Y" k! t% o8 x6 I                        {) S4 F) ^8 u! U! C1 K% N
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了! v3 u6 G" Q( W! R; i+ F7 {/ @8 H
                            k = 0;, k* Q+ P% j( t  ^9 @0 p
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1- \" X% ~$ |/ s8 ]% G  @
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, C2 }, q1 M6 Z                        }9 N5 t1 {0 Q/ n( Y$ e$ c
                        else//输出暂时还没有改变数组元素的值8 `7 z# m, C' r0 q+ r( c3 d
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);) g% c+ S$ v; S9 `. B) q
                    }( C+ j4 b5 j9 y* C
                    else
! M+ B/ u! K- Z4 ]                        i++;//数组元素为0,直接跳过,不计数。。。/ d" w# G' p; R
                }7 `9 T5 _& `- B" h/ q4 c% t& k

/ T& s" J# c/ T8 ~
- x7 F, ~. k# }! p            }//结束while循环7 q! q* m% {  t- S
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
9 j+ B4 G4 F2 |- C  J           
2 m' N1 m8 O8 G$ q2 I8 v2 F                if (numw[i] != 0)) s. R% y4 K* e0 C" j9 t2 b' B
                    Console.WriteLine(numw[i]);. ]. C; R* E1 q* z2 [/ n
           ; \& \8 F" Y. K. g
            Console.ReadLine();* V& i4 F' |$ \5 r" r
        }
6 A/ I7 J+ r% ]6 t    }
8 L7 q# m( @, C& k, |% F3 H+ s}" p" q' M, M# y  \; X
小甲鱼最新课程 -> 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-7 16:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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