鱼C论坛

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

猴子问题

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

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

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

x
大家好!
8 D$ p2 j6 [- B1 k7 |/ T这几天我在忙着编一个问题,我用了一种方法编出来!
& R0 Q, @. y1 V/ _$ [6 Q" h: {但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!. O; [6 T( S) Z+ z( h
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 8 Z- s4 ?6 g2 H: x- e( I

  w% M, S/ A8 q. Y0 |8 s' }# b7 U! }2 h; d1 C* a, J/ G
                            题目0 r. Y) k" [; Z4 }* r0 ?+ s
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。4 ^' I3 A/ c8 A5 W
第一种方法:利用循环链表2 K2 D, x$ _4 f" w+ N
#include<stdio.h>
% `, V7 A. X0 O* Y9 g' X#include<malloc.h>
: k& R4 p1 h7 M: R5 A5 f6 B2 W#define M 8            //共有8只猴子
2 M- Y* g( |3 B& g3 c#define N 3            //数到3只时退出第三只0 z# \, Y2 `+ v( }1 Q0 ?
typedef struct monkey0 P% l# a  A3 g+ b: r. }0 c# O1 ^; ]
{int number;
& m6 ]3 E$ }: }; E# G3 p, yint flag;
% z6 l- u0 v+ v* }) Ostruct monkey* next;$ j) Z1 v8 L+ T" i! y' X
}MONKEY;) ]2 a2 C* A6 j6 b4 [
main()
! L' H5 z) g4 W( z) C- \1 ~4 A2 s/ u{ MONKEY *head=NULL,*p,*s;
; Q/ B3 Z* s$ _, p. c  int i,sum=0,count=0;, R4 J# a. j# `
  clrscr();              //清屏$ r8 G7 Y( D7 ]6 V9 D. [6 e
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
7 R1 \3 g; ]: M1 J  p->number=1;p->flag=1;
9 j8 g6 e" ]% S+ i+ n. d  p->next=head;. U: L' p( h7 j$ r$ c
  head=p;, M& ~' j' n7 F2 f5 P8 Z: S( l
  for(i=2;i<=M;i++)
+ {( ], t9 X! o( q$ L    { s=(MONKEY *)malloc(sizeof(MONKEY));' t5 d) m. J8 m
     s->number=i;s->flag=1;8 D+ {2 A0 X4 F" O
     s->next=head;
, f% z; X6 v1 x: V, N6 w     p->next=s;p=p->next;- t  i- Y2 O! \- S
    }0 R5 M2 ]; n# D9 y  M
    p=head;
. k: X& U7 ]8 i2 W; [+ K   for(;;)9 M; Y. l% A" Y& [
    {if(p->flag==1)) c& `5 t- w9 |% R! r, i0 c
       count++;9 f; h$ o$ D5 |( x% [% G
     if(count==N)& x$ ~1 t" g& k% U" ~1 ]) d
        {p->flag=0;
, R( q% e( k3 _/ V! ~, ^# t# J         count=0;8 U; ?% N2 ^2 R( w% c
         sum++;}
4 D* n5 t& O1 l2 U1 `     if(sum==M-1)
# b% e7 Q% l! p5 b        break;
& K5 g& D$ q. T: i5 v/ h     p=p->next;4 y) ]/ b9 ^4 `
    }
# i1 M/ f; [5 J4 P9 [5 f5 K" ?    p=
# P, Q0 [7 {& Y4 v    head;' v5 i1 R. O9 g/ w% k; y5 y* C* g( u" ^
    for(i=1;i<=M;i++)
, w  b# a* d' P. [    { if(p->flag==1)
' }! E# c9 o" ]2 L1 q2 S        printf("\t%d",p->number);. @1 J& |+ u, A
      p=p->next;* m5 K" L! A$ u- `% B1 r
    }8 {  M( H1 d' z9 Z7 x
( x& {- i1 a8 h+ ~+ q

0 C1 s- o) p8 W; ^; _
; a" ]6 R  u% C% y}
6 R+ z- K# e0 ~! p: e7 i
第二种方法:数组
6 y6 @5 \& D8 p: A1 c#include<stdio.h>1 E. J+ S/ X; m$ o$ r6 \
#define M 8
# Q$ R. E0 e4 |struct monkey* P( B; ~0 L0 X
{int number;) g3 w- {2 E" [3 h. n
int nextp;: P+ n- J% a  o; H' s; K: s& D, T
}link[M+1];* b$ |) f% e3 C4 G

) F& x- l; n9 n6 |0 x$ [void main()& g+ c) T, U0 ~8 r& r8 l# m. P; t
{int i,count,h;4 |. y+ u/ A$ j7 l4 i
for(i=1;i<=M;i++)
) Q0 s: w; ]% ?5 f; j+ H" f{  if(i==M)8 @- e9 k1 a: h
   link[i].nextp=1;2 s, p/ b& p4 k3 E
   else9 o% r* F; `+ b  j+ `0 d4 d3 `3 y
   link[i].nextp=i+1;1 U( H; W1 d* w1 R* v+ f9 X2 G2 H
  link[i].number=i;3 {" S& N" s7 y
}
# V; s# @0 h9 t  }3 ?  A& Dprintf("\n");
7 |  \; q( B1 H0 z' q+ e! Ycount=0;
5 B) P% p7 E8 Q/ H8 R: bh=M;
' |) ^+ s3 q# z0 Eprintf("依次退出的猴子: \n");% H- a5 M, ]1 _7 x; ^
while(count<M-1)
- v7 G' z( @( t{i=0;
/ V/ v% w9 C! H0 I" t0 Rwhile(i!=3)
0 n0 u3 o; z. A! u) A2 p{ h=link[h].nextp;
9 w) r7 g# B# Q) M$ w- [3 c5 n   if(link[h].number)2 X, J4 D+ U  t6 H( K8 c9 E
     i++;}
& F) l' o. C: E+ N- ~( S, Y
3 S6 F8 \( H$ fprintf("%4d",link[h].number);
, h# C" a( s5 ~4 X* xlink[h].number=0;
# k! D3 O3 t" I0 tcount++;
1 l) b. ~. K! t. J) a' S( r- K}
9 T8 _* e- N5 {. s% q$ b7 N) [+ E1 f/ V* G5 i: n6 @/ l4 k" j
printf("\n大王是:");
  D4 c2 v7 Z; X0 k  for(i=1;i<=M;i++)
3 a& ^/ m& U1 k8 e  K  if(link[i].number)
, t3 j4 y( R( u  O* u    printf("%3d\n",link[i].number);
' |4 I2 }% Z3 y. Q) c" p' O$ s2 Y+ _# p3 }
  d- I  R" W" l$ j4 f3 N! r) p
}
* p- z9 Y* ^. ^
第三种是普通方法for循环
* z9 Z, C+ Z2 N2 t; H4 g! ?
#include<stdio.h># P0 W8 z; r. ]. D6 W( {/ u
void main(), s9 v/ J0 c/ }  A' h2 a
{ int i,k,m,n,num[50],q,*p;
% v( O$ f8 y. @  G  S/ w! Z    clrscr();
3 H" k3 i. l8 n, I5 ?   printf("input number of person: n=");' f* {5 D4 v) |
    scanf("%d",&n);
  d1 v& R  y( t# }printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只2 \3 w- r  O$ S1 O
    scanf("%d",&q);
3 B6 E/ @5 l9 h& o( W   p=num;: z' ^0 Z; O& ^1 k" f+ K8 R
  for(i=0;i<n;i++)1 y* I- F  d4 U1 s
    *(p+i)=i+1;
6 y5 P6 T+ K7 Y9 E7 S" U* h! Y   i=0;6 d: D, P9 ?& P! a1 j
   k=0;
* {- B( e  V9 ^) _   m=0;
& D' ?6 {# g5 v) e' W  while(m<n-1)
  a1 a5 V) l  h   {if(*(p+i)!=0) k++;$ I% ^5 F7 @$ _: W; ~. i2 q
     if(k==q)
8 H; k' i2 R8 a( y4 [      { *(p+i)=0;
3 ~2 Y! S+ P1 O, M0 g5 X6 }        k=0;
: P( g; N; Y- N+ V, ^8 n        m++;
/ C8 m1 I, ^$ v      }
, n7 v) z' u& s8 x* X    i++;
1 J# L$ R. t  e    if(i==n)i=0;. c* `7 I# W+ h" A4 u/ |' M
   }6 @1 Z2 |/ |7 x! y6 ~& }+ M: E3 H+ l
  while(*p==0)p++;9 C! ~7 ]$ I4 K8 `7 ^4 z$ b
    printf("The last one is NO:%d\n",*p);9 {1 J- v3 D' Y/ ~" R
     getch();
8 ^! j1 t% l7 h7 K& s" A
$ l$ ^3 b& r9 a$ \* d( C+ K}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
& X0 Q2 y( P6 Bnamespace 又费马达又费电
) p: {+ e2 p# e) @) l{
4 V3 f+ v3 L* E    class Program$ _( f) H% s' W
    {
& z, B! o. B3 i& }# r4 w5 H        static void Main(string[] args)7 n% L+ |$ I: v3 ~: g
        {
, b1 U% J, N% m            int m, n;
$ z+ `3 ]# x- O            Console.WriteLine("请输入数组长度");" p: l; V" J! O1 Z. Y; ?' I2 H/ X* a6 E
            m = int.Parse(Console.ReadLine());//m为数组的大小* h, R+ Y8 D; q# u& Q, I
            Console.WriteLine("请输入要截取数字的大小");
( g- D/ g, H* h+ V            n = int.Parse(Console.ReadLine());
7 c& I! i/ x- _            int [] numw=new int
! s; I8 \2 M3 O$ C; v& P! |9 p: T$ i6 J- U9 i0 g+ ?8 O
&shy;&shy;&shy;;
: {  q7 E5 [& W; I8 o            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
1 t3 j2 n7 f0 E- @$ ]7 \            {0 ]0 C1 A( p9 r$ u
                numw[j - 1] = j;
1 u# R1 O3 J4 W            }9 G. }: i- K* w  w' _, `2 ?
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
8 `- L9 i- E( @: H) h            while (d != m - 1)
' E3 {) U' B, s/ s& e, v# |0 Z4 z# {            {
% t) s* V9 p7 k) ~4 v( b" G$ D                if (i == m && d != m - 1)
1 Q6 Y  [# w  Z1 B' o8 a                {
* @' B8 M. D  a! k& ]2 A  R                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
, E  R1 e" H: F) l& W                    continue;
) m3 b/ z; e; }$ t# s+ ?                }, |/ p  z5 z3 |6 Z) x
                else0 \  f4 E: |" _5 F, s) p
                {
) k8 Z' X7 X+ Y                    if (numw[i] != 0)& N8 D3 f/ u8 w4 D! w
                    {0 i/ i9 t( m1 C
                        i++;7 K# N  A- M7 F- E! p
                        k++;
. Y3 i4 k( q8 E# g* f  e                        if (k == n)" |" X+ L' I8 x, Q
                        {
0 c; P9 w; D: h* ?8 ^4 |1 p                            numw[i - 1] = 0;//把在n位置数组元素的值改变了0 u3 r! E3 e5 T2 ^# X! Z+ r. R+ W
                            k = 0;  Z) h  V/ q  g( o. P/ v
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1& s" `# s! j& }+ r8 O) @( o
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);& @- l, f2 M, ?( B* O( B1 W: j
                        }6 d* d. \* M, S! p" E+ U% t
                        else//输出暂时还没有改变数组元素的值
! Q, p" _/ N6 \8 |3 l" s                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
- M# T7 P0 G; L) B                    }8 {( L) Q0 E7 [' r- H0 c
                    else
6 x/ i" p4 l1 H                        i++;//数组元素为0,直接跳过,不计数。。。9 T( h, O5 k8 J4 n
                }
/ ]+ n3 {# L+ Z, @* n- M, p
. ]# s1 e  {0 ^+ E- \, T1 n. [$ A2 t/ b6 ^; ?& n
            }//结束while循环
: g5 g+ [8 ]: I2 d# C$ R2 Z+ ^            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦; l) d5 g3 t1 Y8 u
           
' L1 [# a. Y: ^5 V9 M' O* X                if (numw[i] != 0)
6 c- L. }  y& e8 h8 F                    Console.WriteLine(numw[i]);4 w( o. x  Q& C( ]8 @
           
) y8 O0 J8 y+ `! ^# w/ O8 q            Console.ReadLine();" \. m% P, Z) a
        }
5 c! V, i6 ]& ?4 q. c6 d    }
) t6 k6 R5 g+ R1 O3 q) g}1 {' b( B) d! f& e9 v* S
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-2-19 06:37

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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