鱼C论坛

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

猴子问题

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

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

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

x
大家好!
% f8 _6 |  _0 N+ Z这几天我在忙着编一个问题,我用了一种方法编出来!
2 h& U9 y/ x& \9 L; M% }# A但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ v7 T2 g( `- G* X8 z0 B7 p4 Q
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 1 r4 j- |3 {2 `; y
4 J/ P' {  B. {% H" M& M
; p+ o2 O' Y- H4 @' S
                            题目. v. K0 E+ A$ O; a
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。( x4 u- t% q6 @! d3 m2 `: N% ~& w
第一种方法:利用循环链表3 ~, s& I( Z+ [! S
#include<stdio.h>
+ G3 o- M3 i# B  w#include<malloc.h>
& j6 B# [: }- X3 h& v4 Z#define M 8            //共有8只猴子; \5 P( w) B: R# G8 F: A, l& u+ O
#define N 3            //数到3只时退出第三只
6 k. k4 x  b0 K3 F( o- O- G8 Ptypedef struct monkey1 {7 X7 d, a. A; N/ x0 Y1 f3 i$ k
{int number;+ x* o# O! v* b# {) i. M
int flag;" \; O6 X, ^1 p0 A
struct monkey* next;
" v9 m  b( {  ]# F1 n}MONKEY;
$ f! g& A( g, M' U& q1 X* x4 Z% imain()
6 r9 ]1 ~0 s& F# d( N{ MONKEY *head=NULL,*p,*s;
$ |: `1 U! f2 t" M7 W" y! i  int i,sum=0,count=0;2 I0 x' i& E6 N; V
  clrscr();              //清屏9 `7 O' l' D8 A$ d
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
4 ?! G  O" O  c2 h4 W! z6 V+ _$ R! q  p->number=1;p->flag=1;
' L9 ^) G' {0 t( J& U/ H$ |  p->next=head;
2 a- k; h7 I) L1 U4 J. c  head=p;2 T8 H$ \4 o5 s9 l) {
  for(i=2;i<=M;i++)6 Y3 R" z9 |0 M$ }, s7 [' i
    { s=(MONKEY *)malloc(sizeof(MONKEY));
  b6 o' h  L9 ]8 g     s->number=i;s->flag=1;! c2 p! @) m, Z4 d6 `
     s->next=head;0 P6 }8 p7 f: Z$ H" _
     p->next=s;p=p->next;
4 Y" j8 o2 o% o; `% E    }
7 H: ^& f% t9 y( u8 i9 N3 m6 _% y    p=head;+ h( P3 y5 c/ D, o$ v
   for(;;)' x+ S' Z4 P5 G5 g: C$ t
    {if(p->flag==1)
- v9 |3 }0 p+ i1 p" |, e       count++;
& @( @( M& H5 Q* F) m, {; ?     if(count==N)2 F9 m# \4 S' m
        {p->flag=0;
# l2 ^' K5 ^6 [( A$ n  S3 @0 Y         count=0;
6 a  a2 M3 ~/ }         sum++;}( s# {# e, X& M1 V2 y* U1 {
     if(sum==M-1)
0 b2 [. S0 e( }0 ~7 Y        break;
5 }+ W7 X6 Z4 G$ ^     p=p->next;
, v% c; g- U4 b/ G+ C# F    }% K/ N/ z: q+ r
    p=
6 H" t3 L5 }6 y2 G! ~" ?5 I    head;
1 Q, o) y: P+ ~/ H+ M. w5 A+ b; i! e  \    for(i=1;i<=M;i++)) X0 ?6 S3 L# l5 I6 v
    { if(p->flag==1)2 |) x+ h0 M8 E0 v
        printf("\t%d",p->number);0 p4 [/ F/ a. ?1 j( R
      p=p->next;
7 f# W! Y0 x. j# o    }
1 F* \* H( Z; i+ b: D" j0 H$ g! Y6 k5 X

! C- Z* O/ V  L9 q" f/ o) L% ?2 s8 @! |
}

- |$ U6 ?- x9 Z4 D0 m  o' K$ Y第二种方法:数组8 S- V6 U4 o8 C, s7 s+ U  O% q
#include<stdio.h>
9 t1 P9 R8 H2 i' u- n3 B5 p#define M 8
% f! x/ ]" M" @- Z# Z& Ystruct monkey
) i& b! ~, A/ c' Z/ O{int number;
! `2 e, c4 R1 ?, t/ bint nextp;! s% ^& l* r8 b7 Y% [9 e! {
}link[M+1];
7 D. s$ U( d* L* w/ ]7 V, E/ m5 r* q, V$ Q
void main()
* S* ^4 X% {$ F/ V1 B{int i,count,h;
+ H6 D2 S1 I8 |& r8 z0 B/ lfor(i=1;i<=M;i++)6 ~  ~8 d, m1 @' |4 v
{  if(i==M)# c# W  o% g( Z4 ~
   link[i].nextp=1;
9 D1 V: E. \/ S% k" j' r! ^. o   else# I5 G6 S# M7 @" O. b+ E" g
   link[i].nextp=i+1;$ }" |$ [; L* a  P
  link[i].number=i;
! S% [; l5 f' V: `" l: g}' s$ F* h4 Y* {
printf("\n");  Z6 ?0 e  t" H( p. b6 [! N- N$ ?( @+ i
count=0;7 H0 j% @& I6 L3 N  X
h=M;. o* i, ?% w- Z  q
printf("依次退出的猴子: \n");, p# f& O1 _4 k. C
while(count<M-1)
2 d9 m* Q$ V1 O( F/ d# U{i=0;: {% S3 ]6 U7 r6 V" D
while(i!=3); p1 T* {4 P/ v# e" F# v/ |
{ h=link[h].nextp;* y$ W$ S8 U; K# Q  [% F) n
   if(link[h].number)) ]4 W% a' G% O/ w% s, @- W
     i++;}
; G" U+ ?* T% \( j- V  O
- ~9 S  y8 D5 _, S! }7 Mprintf("%4d",link[h].number);/ g( F1 C# i+ R5 [: g) {' C+ P
link[h].number=0;
/ ^( s/ y5 d% x* Qcount++;
" S* @% D0 p5 ?}) v# I: [  \$ E' X" V" I
' B+ g7 T/ r& i. U# V8 g
printf("\n大王是:");' [# I. s# b0 w
  for(i=1;i<=M;i++)
& V9 Q3 x; m+ q6 h; T! o/ F  if(link[i].number)
) i. _6 P/ G+ \7 \% d- w6 Z; p0 b    printf("%3d\n",link[i].number);
/ _) j; U4 _1 [
0 j7 b6 J) S& j; K" w: A7 a( W. S$ V5 Q! k, S7 J4 i
}

6 P+ H9 }# r2 O' H第三种是普通方法for循环
; v' K; R4 k$ \
#include<stdio.h>
1 O/ W# e: r- ]0 H% o$ dvoid main()) @6 b4 M2 m; X4 T3 E. q
{ int i,k,m,n,num[50],q,*p;
' K! B3 }6 K1 _% _  Y8 T    clrscr();
6 D5 A  }6 g; d1 x, c   printf("input number of person: n=");& R( c/ J- R1 [* @3 m
    scanf("%d",&n);3 N2 N4 y, g7 M4 `
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只1 f1 b' Q, i+ b* `
    scanf("%d",&q);" P4 O: K$ F0 a# S$ B
   p=num;
! o) n: x3 X/ |8 f$ \" e  for(i=0;i<n;i++)
% F4 N: x# c# `) ~3 d. C    *(p+i)=i+1;
$ c3 U5 ~: M6 g) H6 I* S   i=0;( b* p# g( h8 z- a0 M* W
   k=0;' L- N/ n8 \' M- O7 [1 ^# k& a1 S7 I
   m=0;# y- V0 A$ x  @8 q: C, D
  while(m<n-1)
1 ~( M0 v. l5 ?   {if(*(p+i)!=0) k++;
5 u2 c0 s7 b  P) ~1 S     if(k==q)
  f% N7 U* K9 n' u/ L% o- h3 f      { *(p+i)=0;
: N( G1 ^) [- T' [9 J4 z, W        k=0;8 L! q8 R% a8 d! k7 P' a  A
        m++;
0 v; s- K; r; U3 r      }- a) T  K  x& Z# t# }, ~5 w( L  a1 T, M* g
    i++;
7 @, a( l( @8 `4 k2 G    if(i==n)i=0;
3 Y: d9 k9 T6 {- d   }9 r7 m0 |3 {9 o  U& |
  while(*p==0)p++;
& g1 a' a$ b$ D  r# C    printf("The last one is NO:%d\n",*p);6 j/ ~  c' L* d. ~, I7 l. B, [0 v
     getch();
, E- W6 @; x& C3 Z. o! \1 I5 T; E7 P$ u) b' [& y
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;4 s- Q$ @1 q" A; a
namespace 又费马达又费电
5 e1 n) b4 ^& ^; W{
5 Y/ n- M) s8 G! G( j/ ^0 }    class Program
3 d* L6 k/ P* H8 T* k2 k6 w* q    {
( `" E8 H  @, b, s1 b        static void Main(string[] args)
) e! c& W  O  K2 o        {
7 u4 a& N7 O! U0 x            int m, n;
5 g1 m# I" o3 C$ d            Console.WriteLine("请输入数组长度");
9 ?, l, |/ v! e% U            m = int.Parse(Console.ReadLine());//m为数组的大小) R. I/ ~6 y$ }( C. u
            Console.WriteLine("请输入要截取数字的大小");/ e: z; e( N9 y  n& R
            n = int.Parse(Console.ReadLine());% V% L" T' c7 ~, o: F3 B
            int [] numw=new int  z7 ]  K9 p+ L% A3 P

1 v: H! l9 ~+ l2 t0 ]& @% ], V0 w&shy;&shy;&shy;;: o5 T" F; ?# s, U% V
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
. d% O3 b# Q& R" v3 J  w3 N; Y, Y            {) T/ T+ Z4 V& d- s! }+ S: b
                numw[j - 1] = j;
( l$ C" m/ W4 b; e4 U  N            }
" b5 X* ?4 ~9 M1 [$ X2 _& b            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
. T2 O( ~. s- R; r* ]            while (d != m - 1)1 T3 J; \3 N) p
            {( {) F6 q6 C4 n( r! ]( h
                if (i == m && d != m - 1)
$ o0 N  [' }6 C  H$ ]% P7 ?                {
* c- Y2 ?9 i4 l0 H' |5 ]                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!& N1 C/ M9 @; z1 T8 f
                    continue;/ l$ i, L! g0 I$ {
                }
) h: I, c. Q, h$ S0 w                else4 N6 I, k+ \  o1 ?& H
                {
% n; {  a# {: h2 m                    if (numw[i] != 0)
; X1 O# d. w+ P( `) E8 E, i. X% K1 J                    {  B6 X* W( ^* z# a) P
                        i++;( l$ j" @) v- \4 P9 O9 j& ]2 G
                        k++;" ^4 W/ q) u( t
                        if (k == n)* u$ D$ d  e+ e+ s
                        {
5 J- t) O5 w1 K4 Z- `9 N                            numw[i - 1] = 0;//把在n位置数组元素的值改变了; l6 B* F: K2 O  }( w3 a
                            k = 0;; @; V  g" c, ^, W4 ]/ p
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
  |8 V2 ~6 v4 F5 a  Q                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);5 S5 @" G1 p' G7 _) U) o
                        }9 P8 V. |; X! i* k
                        else//输出暂时还没有改变数组元素的值2 ~. U4 R0 P) ?$ l7 w# U. d( X
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);( m$ S3 a, R+ K, p
                    }8 v5 ~8 _8 P# x5 P7 Z2 H& M- b
                    else' F+ h: ]9 o" b  a$ T" x1 C
                        i++;//数组元素为0,直接跳过,不计数。。。
/ o, b& B% i' Q* w$ V8 J                }1 ]7 N& `4 P* b( q  y7 H: M
  y! I+ @( `2 p$ [

8 G3 s( \7 m  [& |. u            }//结束while循环( T. s5 l- q0 k' ]9 D
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
/ b0 \( S, _) E6 S; w3 z7 J           " Q% t- G6 ^! u/ b9 D; H  y
                if (numw[i] != 0)
$ A! I9 }" s  `) [! D* t+ W                    Console.WriteLine(numw[i]);: L* d5 {4 C$ o, }4 J, o
           1 v+ f. D+ n4 K/ y" k7 ?
            Console.ReadLine();
- x8 H- ?3 V5 K! I7 m: Z  l2 P/ q        }
, v# \5 z% L) x( d% O  Y. t    }9 d/ V) _9 D# _4 R6 b
}
  W# s) H. Q% F, J; W8 K3 L
小甲鱼最新课程 -> 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-15 03:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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