鱼C论坛

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

猴子问题

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

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

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

x
大家好!
. X8 O. l( S: U' x" C' K1 l( ]这几天我在忙着编一个问题,我用了一种方法编出来!. i$ r' x6 P8 b4 l, g! Z4 O% J
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
* E6 S! |, N0 U2 Z  T! t9 p注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
& ]" N& C$ J" f' M8 R0 h: m' j8 N' U" W2 n/ a& Y. M, ^: w

+ k! o3 y& `' M
                            题目
  E, n: X  q$ \8 C6 t/ M* u山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。- G, y( \& n$ P" T1 _
第一种方法:利用循环链表
% _3 t0 [. V& y( n2 b#include<stdio.h>5 F2 f) c: b* F) y, A
#include<malloc.h>
0 R8 |6 A" |5 U# [5 n( M/ r#define M 8            //共有8只猴子
* q, E1 Q4 e' e0 ]% u( d2 T" F: y#define N 3            //数到3只时退出第三只; W; c" t5 L1 l
typedef struct monkey
0 Y- F  l' Q4 B+ b{int number;
/ F( x5 F, \# L, H! Pint flag;
- Y5 b( r9 b1 B+ q7 Y' hstruct monkey* next;
: v9 G1 m+ z6 p  e, R}MONKEY;; R6 M/ F' T& z1 p5 C$ g0 f
main()+ P4 A1 L% O8 _/ p; k4 h) |
{ MONKEY *head=NULL,*p,*s;, ]) s7 B' C8 a* H+ {
  int i,sum=0,count=0;
) I% Y  r3 y" G  clrscr();              //清屏
7 e7 R  B' {, i( U9 \9 @! W  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存1 J5 H& y2 ]5 k1 Y
  p->number=1;p->flag=1;9 A1 R6 E1 h) ]5 M3 R
  p->next=head;
- ~2 }2 S" o3 n# ~8 W  head=p;4 D! ]- y- L& Q* `/ z1 z
  for(i=2;i<=M;i++)
9 ^1 \0 {* a- S1 m    { s=(MONKEY *)malloc(sizeof(MONKEY));( f4 l2 n# e; \  Q9 D7 `
     s->number=i;s->flag=1;5 X; e$ X# k9 P% e
     s->next=head;
9 i5 h3 L: G( v     p->next=s;p=p->next;8 a3 t% o" f5 e; A, R' f1 ]
    }
2 H5 _( K0 V4 g$ p9 ~    p=head;5 z1 S5 Y5 R. C+ W8 k1 l
   for(;;): C0 `- y; f& O! ^
    {if(p->flag==1)
, z  ^/ u. m9 g6 Y; ?/ T       count++;. |5 S3 J3 Y% K+ `, O  r+ K
     if(count==N)' K! z6 S" c& S& Y7 p" B0 B2 Z
        {p->flag=0;
% W4 L2 f. T" S) F! l" i! X3 Z         count=0;
/ x. q  I+ T6 }! F: Y: h6 E6 E         sum++;}
* R  h4 ?- r* h% t     if(sum==M-1)
, p' b) \+ ]7 ~: T) Q4 l( D        break;& u, q0 u; J8 I. K
     p=p->next;
$ y9 H* v2 \6 o, {0 s    }3 w3 ?4 }0 I/ ]" u
    p=
" {. {: O+ `" m  z3 I    head;
5 N4 N8 P3 k# w% Q- C8 h0 w3 z5 I    for(i=1;i<=M;i++)1 M2 G& P. [) ?6 A
    { if(p->flag==1)4 P! a9 P8 @: i  b) x1 O$ I
        printf("\t%d",p->number);. W' R% D% p- g' v8 F& X/ z) e& c
      p=p->next;+ J0 G2 A/ V' N, ?7 q. D
    }
! U) b% S) R/ x4 |) A( Q
" R0 ?1 M& A8 ^5 d4 _7 m9 Z: {* ^9 D% i/ x* ^0 o* N
$ j# x! f& a8 R+ \: V4 E
}
2 S. Z  H3 ]4 d8 V3 [. X4 z% e
第二种方法:数组
/ g5 m* c! ]& A/ d/ a8 ^#include<stdio.h>
4 ^7 `: a, ^* h8 y- [#define M 8
& x: B! [$ z) D. L) c# C- wstruct monkey* C1 \9 Z; l9 J: T
{int number;0 H3 Z0 |$ K1 K' q7 k
int nextp;  T+ ^* a3 f, s! V0 y  ^- n
}link[M+1];
  ~! J% L0 e9 y* I8 l) x" z( t
$ U* Y1 w% o3 M: n, ?2 C! {void main()* h5 V: z# P- B# o7 d9 P
{int i,count,h;# N* m' y! W: c: L6 \4 c) T3 P
for(i=1;i<=M;i++)  ?3 b5 V7 e2 S- |3 V7 _" y! ~
{  if(i==M)- W" y) N  K7 t% f0 o9 v5 v
   link[i].nextp=1;% p9 ^6 [& h- q3 d  r4 }9 K
   else
2 M4 B' M5 {% f, C* N% \   link[i].nextp=i+1;  w1 w* V- h4 s, y
  link[i].number=i;9 m+ [$ t2 H6 }' [6 H  ^* m+ d
}
' }, q& @# r% {' \7 Q; ^1 Xprintf("\n");. Q- {5 T) ?! n8 S4 [- r, V
count=0;
- O& o1 U  A, Uh=M;
! Z. R" W- P# Z1 z& T: k# Y- }printf("依次退出的猴子: \n");
; ~8 Y, J1 {2 B6 p# U  x5 x- C9 awhile(count<M-1)0 y" k* _% r; B! y7 [
{i=0;; E" |2 D0 [: ~; E2 p
while(i!=3)+ c+ s8 q! _- D2 o- R4 M
{ h=link[h].nextp;7 l4 X8 h3 R7 e+ X- [$ S% [
   if(link[h].number)
( _7 U. M/ z  [' m4 f; N0 Y     i++;}. R2 `4 K# e& R% N

& D4 @/ D6 P# a" b- L, Dprintf("%4d",link[h].number);
) y* l9 B( D" r- Elink[h].number=0;, ^4 E( c3 e6 M/ V  W+ j
count++;3 D* p- j- V! O4 F
}
! [. b/ X' y, z$ J# a
! E! M3 _; N) y1 o" P; Sprintf("\n大王是:");
* o& Q5 P* Y& B& L- o/ d  z  for(i=1;i<=M;i++)
) v: p: F- z9 W* `5 M' r  if(link[i].number)6 n, Y  {& N/ x1 o
    printf("%3d\n",link[i].number);
8 @* @3 j  M0 i. H5 X. ]0 c* d
9 L& D2 K( J& H; _' O: U6 g8 q& M. e' L
}

1 v2 S1 d. E3 }. F第三种是普通方法for循环
) r* J* B( G4 j6 e, J, M
#include<stdio.h>  Y/ p( U2 O8 C; o  W
void main()" C2 w0 \) j$ o# e0 @
{ int i,k,m,n,num[50],q,*p;. Z# ]: A; h, A/ r: ]0 U
    clrscr();+ P5 Z8 K2 I$ x! D; H5 H
   printf("input number of person: n=");( v; v, V* a3 W
    scanf("%d",&n);
) \; r: W. y& D+ yprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只' _+ k0 j4 ?7 k  w
    scanf("%d",&q);1 Y$ ^$ h$ i7 }; o: a
   p=num;
) g- h8 Q- S6 o- K( b  for(i=0;i<n;i++)9 {' T2 Q# M  Z3 T1 d/ ]1 b8 D/ p
    *(p+i)=i+1;
. d. ^/ p) \6 m4 H* o. v   i=0;
) X9 v% N& A, ^; N   k=0;2 a$ z: m; u; X
   m=0;
' p( z* Y& e" ]- I; y0 i5 O  while(m<n-1), }' h: A+ x( k  \3 p
   {if(*(p+i)!=0) k++;% x+ G& J7 q1 e: Q( ]
     if(k==q)9 R& q* J) k- _( ?; r- b& h# y8 q
      { *(p+i)=0;
  w7 m7 z- f( F( h& C7 e        k=0;
( F, f9 a8 \( o; E* [" O" z$ P        m++;  U. t/ ~2 ?6 h0 _8 B! m/ [9 s$ ^
      }" d3 I: X4 h$ E2 T' D
    i++;
# R4 v! o. @! e/ B    if(i==n)i=0;
5 i9 p1 I1 P, o# g* l! @   }
& g* ]+ P$ i, u% X+ ~% c0 Z  while(*p==0)p++;
3 H4 `0 L/ j- E1 N4 j/ t    printf("The last one is NO:%d\n",*p);! z% \" \3 a& _. s
     getch();1 n* [9 f+ v, [/ ~9 x' R# N2 ?
$ Q! a, p* w1 s( T) i4 k
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;4 D; Q9 g) v( ]8 o7 d8 _9 d  u( P
namespace 又费马达又费电
2 b: u$ ]! Z2 @' e6 @{7 S: }; t5 d- b( U4 P( @( b$ r) I2 R4 b
    class Program3 [' j& E( C, i5 }( M. q: C; L
    {7 _, c: n9 W7 p; C
        static void Main(string[] args)
* C2 F! [8 N! f        {3 {1 ]7 z* }3 d6 W9 C6 L
            int m, n;% V5 {, ?" x8 Q9 m
            Console.WriteLine("请输入数组长度");) Z( o8 R+ [) F" G- \$ _
            m = int.Parse(Console.ReadLine());//m为数组的大小
/ H) o: [( R* W" T            Console.WriteLine("请输入要截取数字的大小");6 u2 d2 q; O, s% {) K! i5 B
            n = int.Parse(Console.ReadLine());" k7 H6 l0 l$ J- t5 N- x
            int [] numw=new int
, d% O% I# p8 }% g7 t0 L7 J. y
) T9 x5 ?3 v5 P% W0 f, v  x&shy;&shy;&shy;;7 C- g7 P2 r2 M) y) W4 s
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数* ]5 g1 p" K: N
            {
  @, H+ K: q3 r/ V# V1 Z                numw[j - 1] = j;( F  O1 t6 J- T6 x3 V
            }5 q' o1 ~7 g. l, ^; M- k% f
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!8 d) N3 H2 h* {0 j- p3 @* y) p
            while (d != m - 1)
* `0 a7 [8 ^2 b9 j4 M# \            {
$ s$ I% e0 F6 N* J# I* K. z                if (i == m && d != m - 1)
- U5 w! {9 a; Q                {& R; ^0 i( X4 O9 d( s; f
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
+ n2 s/ R9 v1 C+ G& Q3 f                    continue;
6 b# ?9 R9 S3 C$ Y: W2 S                }7 F! e. s) J/ z5 ^8 X( X
                else
  M. y" D- J/ p% m6 ?0 [; {( J8 s4 Q                {$ c7 m$ {( }4 M/ b, ^% G+ a5 h5 |( [
                    if (numw[i] != 0)7 I! Z; v3 G6 N; ^
                    {
2 ]# i( M9 L0 r. H) Q                        i++;
$ N! C: a. ~( J% S                        k++;0 m0 m) S& K3 z0 l. s1 R3 }
                        if (k == n)
6 z6 S# Z5 f' R/ b; E" {' p9 R                        {! [+ H( A$ t: H7 U- P
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
" k& F$ U( T, l* {7 c: @                            k = 0;& S6 M8 X4 s6 O
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1% ^) Y9 {& Y4 J0 L
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);/ q. I7 t. d- N1 k0 r
                        }+ t6 m# }. B* f* n
                        else//输出暂时还没有改变数组元素的值
* X8 `$ d; u& k) ~$ q1 e: p                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);5 C! e( w  N& E' P
                    }' T* ]9 D' I" u  r
                    else: ^0 M5 r: p+ w1 m
                        i++;//数组元素为0,直接跳过,不计数。。。6 Z; Y3 s( _. s) @: h
                }- O4 V( z3 [. t

% e, p6 J8 c% x6 q: _
& P$ }$ ^7 S9 b; U/ P+ N            }//结束while循环& O. S8 q: |4 J& K
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦; \/ W$ o6 i0 ?7 ^5 H9 f4 C
           & {# n2 Y! @# h5 W
                if (numw[i] != 0)
/ m3 C% C+ o" ?4 N  {2 w                    Console.WriteLine(numw[i]);
) v2 p3 h6 J# m" h8 z           
/ v9 K4 R: @2 x5 E! z9 I            Console.ReadLine();% k1 G2 p5 w5 _6 o, L; i
        }8 y& g9 U; I9 ~" V
    }
# s: a6 Z& ?7 D) Q9 X. P, h}" o: e4 S) e; 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, 2025-11-14 22:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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