鱼C论坛

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

猴子问题

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

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

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

x
大家好!
' W- b* S2 M: E( V( h这几天我在忙着编一个问题,我用了一种方法编出来!  u/ y9 ?; T) c0 Q
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
4 V" f- t) t- g9 y! T注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 2 ?' i% c3 n! I
( O- M2 {9 Y) M" u1 ]$ z

) x7 q+ m6 H1 a- Q1 h6 F$ b, y- w+ E
                            题目
% s- |$ J0 s3 M4 C山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。3 o( _$ d5 q% Q$ d' P7 ?! f
第一种方法:利用循环链表
  ?# Q, e0 ]! F, F3 h9 M#include<stdio.h>, d6 w- s$ P/ n* I9 J% [+ X6 S
#include<malloc.h>
) o7 K6 Q+ j( r& W#define M 8            //共有8只猴子8 s5 n' y) i* V+ u) d0 X7 V% N
#define N 3            //数到3只时退出第三只7 o, D& m, o) |6 b, @
typedef struct monkey
' E2 R- E+ b4 n7 j{int number;% L! S& [& I2 h
int flag;
) Y" b& J& z) s" a8 `7 u: X0 C9 h7 Astruct monkey* next;
! L9 a. f9 m" i; Q/ K9 M* V}MONKEY;
( F  G4 N$ J# i; M2 a" ]/ x4 r2 fmain()
( b' R+ ]- f3 s# A3 y: l' D, B{ MONKEY *head=NULL,*p,*s;
/ ~9 ~+ s' y% i! C& n% K  int i,sum=0,count=0;
3 ?# O5 m2 ]" z. [# N/ ~5 ^5 Q  clrscr();              //清屏$ F& W1 @  w8 p7 w1 ^1 g8 H9 R! G  W
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
" _# w, e3 S% n( ]6 \  m  p->number=1;p->flag=1;
4 H6 n5 r2 z* P$ `' a, p" o1 @  p->next=head;7 D+ S/ y% L  j0 j$ p5 t* S
  head=p;5 D- ~' S. H7 j$ I8 S
  for(i=2;i<=M;i++)
5 ?2 v! L( t$ f    { s=(MONKEY *)malloc(sizeof(MONKEY));
, O+ }) I# K8 L, c, o     s->number=i;s->flag=1;3 [( q( T/ o/ s7 W
     s->next=head;
4 L2 t; w. B+ g7 r     p->next=s;p=p->next;1 ?, g6 G4 t8 S1 N
    }
* f, `/ ~: |) ~' X6 Z# a    p=head;
% r* K) S. d6 ^; T6 F5 \& s   for(;;)
2 a7 P6 G# w! n* P    {if(p->flag==1)% a% h; L" d" ]0 N- U5 A
       count++;2 T/ V# h$ s, i8 o" z' z7 m
     if(count==N)5 F1 T5 E0 ?( J& [5 ?( W7 u( `. W
        {p->flag=0;
0 C  z' |, r. j, [         count=0;* O+ u* j0 x# ]# P
         sum++;}7 c* C, e  m! w$ \$ C& O- S
     if(sum==M-1)
# Y6 _; A* ^0 E5 ?+ Q5 b        break;' p! m% E# K2 {  K3 t
     p=p->next;
2 m& |8 f3 \, A- r+ w    }
% Y6 O% e1 F& v: j    p=
# t; Z/ a3 G4 h9 N' F$ d: t  F    head;  z- D! `( @( z' w: @: t5 x
    for(i=1;i<=M;i++)% z7 c% i' W( k- R0 e# r/ }
    { if(p->flag==1)
/ T0 H! C% A' f1 e        printf("\t%d",p->number);
" k) B( n% t  L: Y1 w$ V. d) Q      p=p->next;4 t% w3 b( w- E; V- [
    }4 r0 I9 H+ E( I+ A6 F/ u. u
/ ~; T: j% z  W, b2 ], ^' @% v  C
. H3 o3 A# M1 Y7 I; p5 c

) X5 f5 p. o( C* U+ W' h- p( e}
$ k9 X) O6 M9 W) T& B! W1 G% t/ z) G
第二种方法:数组
$ \# B7 L) x0 Y0 m5 Z5 L( W#include<stdio.h>
6 d8 a9 l+ @( a- ?( b4 B#define M 8# w, U/ x) E& k' u; b
struct monkey4 D& j) e9 _; }, F: f+ m5 Z+ O
{int number;; u+ m! o8 ^6 G! S0 G
int nextp;
1 F/ M% W: ~! V}link[M+1];
6 Q& |& b- ]( `: ]" z! O, _6 X; T  c8 ^; v- F, h3 G! U7 y- q
void main()
; s/ K' i) m4 H! v2 o" d1 X{int i,count,h;
! T# w/ z  I$ I! T% R6 O8 \2 h5 q7 sfor(i=1;i<=M;i++)) ?& g' ^2 j! m
{  if(i==M)2 \5 j( _# U1 X& u3 o( t
   link[i].nextp=1;* i1 D1 o- u! b: @/ ~
   else
8 y! q* V5 u7 w1 @# F/ t! w$ X0 t   link[i].nextp=i+1;. n4 B; G4 S5 A7 D" T7 `% l; F6 ~
  link[i].number=i;
3 }- f3 d# s# Z5 u}* k. W2 ~0 T9 u, d: S- ~) M' g
printf("\n");
! P; `5 f; D7 a  ^count=0;
8 J& V5 @$ a! d8 H4 k  zh=M;- k9 U1 P: y8 E0 k. W
printf("依次退出的猴子: \n");7 {7 |% e( U: y
while(count<M-1)1 ]  @7 d( i* k5 }+ ]$ ~
{i=0;
) U+ q$ W  W9 d* ^! C6 h/ rwhile(i!=3)
, N/ ?, V! Q' Z2 M1 P" G& i{ h=link[h].nextp;; {, _  m8 R0 ]
   if(link[h].number)
/ x' `  Q: U" j     i++;}: v( ^1 d! z0 }

3 e# j7 h% n0 V/ M) w+ V4 c$ t" gprintf("%4d",link[h].number);5 {! ?4 m4 j: f) m% E$ z
link[h].number=0;. R: }  u$ k. f& ^3 s# O* V6 x
count++;" r  I; z. o5 }8 A' S8 A
}# {7 r( ?# Y1 |3 t; G+ ^; w8 t
/ B7 C7 y& ?7 I* e2 T5 n1 ^" N
printf("\n大王是:");
; k/ Y# a; r" O8 y4 t; s4 K  for(i=1;i<=M;i++)
) x; L, T9 s9 S# q) Z3 T7 }% [  if(link[i].number)
1 i; X8 f( B$ X8 e    printf("%3d\n",link[i].number);
  J/ a0 l: q0 d9 g" ^: z' [" o9 t& f/ l' a/ ~

  a& a  J! Q& \* C) X}

" b6 ^5 I& ~: J5 t" h第三种是普通方法for循环
: m  z* ?" D9 I  X
#include<stdio.h>& M/ l+ q' X+ e* b7 h& V9 G
void main()
* |  t0 r2 q* i7 H5 S{ int i,k,m,n,num[50],q,*p;9 H( _7 q" W- H5 _  u, t  q; z
    clrscr();4 |5 X" u$ z0 _# Q3 p7 N
   printf("input number of person: n=");$ C( l) m- n  S+ J7 A% s2 J: T
    scanf("%d",&n);
) C# f. s8 Q; |printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只2 |# B6 e" a& {. A
    scanf("%d",&q);5 d: d1 X2 k" R% Z/ @1 B+ |4 e
   p=num;
  D: k" ?3 E8 w) t% y+ [# O2 s  for(i=0;i<n;i++)$ P6 {  d* v+ _6 w
    *(p+i)=i+1;, Z9 Z" o3 @$ M1 ^' L5 H1 a
   i=0;) x% I; A' \  m7 ^8 C; [
   k=0;, x4 Y0 l6 [' Y& {' w- c% G2 K# \" k% ?
   m=0;
1 p5 w1 R4 M% u" y2 \8 j  while(m<n-1)" k% ^) {2 j0 M
   {if(*(p+i)!=0) k++;
6 m/ B9 c8 r) w     if(k==q)
. o! z6 C! O* ^9 c5 H" t0 R      { *(p+i)=0;
& a# ^# y% \4 n        k=0;1 e4 C# R$ B( Y2 f1 i
        m++;' I+ b; ?9 L* F. L" D* X
      }
& s5 S3 R; `9 b$ x" N    i++;4 u( u  b; k! i, _
    if(i==n)i=0;
( r4 l$ M* N6 \' a   }" W0 s; B" @* o( M) p- ^
  while(*p==0)p++;. s8 W, d8 s/ z3 W" ~  _" x
    printf("The last one is NO:%d\n",*p);
2 b4 H. C1 R$ Y' q# ?3 r: |" X     getch();+ n. t, D9 P1 M8 b1 V
# y1 T' o: u9 H/ ?# j
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
1 ~" G; w! L: z3 p2 x+ E, i4 |namespace 又费马达又费电
! r9 b3 {0 V! A3 b2 X2 b4 r{, _  M- `) x  X' T' Q5 |0 ]. J
    class Program
+ J/ |- Q$ Z; U    {6 t6 p2 X/ e1 _; G( I% o) t
        static void Main(string[] args)
) P' `' a- q: O7 t; H: }        {# u4 c# R$ |3 K" H$ Z
            int m, n;
. n0 X: V( R8 ^8 p: a            Console.WriteLine("请输入数组长度");
4 r1 w- V& n5 Q; q: M" x            m = int.Parse(Console.ReadLine());//m为数组的大小* l5 Y6 ~: t& j
            Console.WriteLine("请输入要截取数字的大小");/ q; d& H) {  c
            n = int.Parse(Console.ReadLine());
' K6 K0 O2 H( G5 W            int [] numw=new int
, q- t( s) C* z% k0 }- y# E8 K, y8 o  I, s
&shy;&shy;&shy;;
/ Q2 X* h2 N0 q1 G; s" _            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数1 K  ^1 W, J  ]& y
            {4 z! [: [4 H' b' C& ?4 T
                numw[j - 1] = j;7 |1 U0 V' A9 O) z6 l0 b6 U! f( A
            }
& n% C+ r% D8 Q% f            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!2 f5 r. {/ K" ~: Z2 b
            while (d != m - 1)
1 T8 u9 V" n9 T+ t( r! ?, O            {8 h( ?% U3 B" W6 x2 z
                if (i == m && d != m - 1)2 ~) r( s" p) N0 w  H
                {
, i7 g4 l( }; V( {/ w% K& S                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
# R: M: o) F7 K( W                    continue;
. ~/ v* r* E4 f0 ?4 `$ }                }
5 v# B3 x8 H' D6 ]- R. N                else
. `- }+ j* R2 }  g( U                {% A3 P8 _6 A4 Y+ y/ t; J5 b
                    if (numw[i] != 0)
7 e5 @' p6 h) G& P- r                    {
0 O( W0 w) Y% D2 Q" ]5 q% Z9 [                        i++;
8 Q/ V! l. L1 K' X% y% t$ _5 w                        k++;
, R" t$ I/ k- y1 G$ l                        if (k == n)
% `+ }: L- \2 K  ]                        {1 U) n8 h5 A3 z7 v. m
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& w- s: x# f$ p% u
                            k = 0;) K6 [; E# _1 ?! B, E
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1* V: {0 T* v. Z5 ]
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);7 Q* h6 o2 n9 v- g
                        }5 t* z7 ^7 w2 J9 k* t' C
                        else//输出暂时还没有改变数组元素的值
4 ?+ Z" w% P1 F0 |* [" _                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 B% v& T0 ~+ y1 E! F                    }
* ?# ~/ U  y+ q                    else
/ v$ S2 i+ o* w% i3 p! S                        i++;//数组元素为0,直接跳过,不计数。。。
3 m+ }' w7 H5 d$ k2 @% c2 U                }3 h( J9 y  C6 s1 L5 `; s
/ z( y3 k0 V6 x6 F8 i
0 i" A  s2 c: V( [* u" j1 a
            }//结束while循环, w+ O0 d6 \6 \1 U3 o* e
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
" o* x7 F8 M/ U; e9 S# @           
" M# ^4 y% a7 B. j; a                if (numw[i] != 0)4 I' l9 B1 X; I9 N; _, N
                    Console.WriteLine(numw[i]);8 ]- ]6 b0 x2 v5 Z" k# [
           % G- B. x9 S/ C7 V- C8 {
            Console.ReadLine();1 W' v" Y8 m$ Y( k
        }
+ B( L4 W+ X) p9 f2 h    }
, u. [  ]8 k8 N: D0 \}
- G& Y* \( ]) s4 G& ~
小甲鱼最新课程 -> 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, 2025-10-10 05:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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