鱼C论坛

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

猴子问题

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

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

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

x
大家好!1 p: l' J; X9 V& h# x# B
这几天我在忙着编一个问题,我用了一种方法编出来!' s5 c, Y1 s& w
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!# {: o: Z* Q0 e8 v  _$ t% F
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
5 L; J- O' B/ m6 O1 s" \& w$ }+ f+ A! L# h9 a% @

6 e1 o$ w' K$ _4 u; w3 g# r1 q
                            题目
$ z" E' j& ], n6 W. w3 ?8 N# x5 T山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。9 U, E! s  q5 M  ?  Z
第一种方法:利用循环链表
9 f" o- W8 m" Q# \4 L$ U* g#include<stdio.h>. x! A5 J, N) V, D" s! c  C% ]
#include<malloc.h>( r6 j2 N4 O+ e8 o$ y
#define M 8            //共有8只猴子6 {  z7 a: X! H; [- S
#define N 3            //数到3只时退出第三只# Z( r) ~  S1 j" U# H' N- D, j4 t
typedef struct monkey7 k6 n. Y8 \* J8 ]
{int number;) h$ Z6 E( O9 j( _  R
int flag;4 z; g. Q7 @4 T0 J* u% S
struct monkey* next;
& r6 ~1 U' _# L}MONKEY;8 I5 F- f+ C0 ^6 Y- D3 @% W
main()
8 B; l. f( k' ]2 q4 [7 k  Z8 [, v0 D{ MONKEY *head=NULL,*p,*s;. ^# o0 J. I) R
  int i,sum=0,count=0;
! x2 {( g8 r( A' J& t  clrscr();              //清屏* G4 n6 j0 x# |- n9 q. F: ~- K9 D
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
& b0 Y; H0 F5 f6 @  E1 y3 H: ~* L  p->number=1;p->flag=1;
2 L5 [3 J3 s0 T( @8 A& l! [  p->next=head;; p5 F. a1 E; x* F
  head=p;) C, T( k' Q/ P
  for(i=2;i<=M;i++)
! Z" N" @; d* R    { s=(MONKEY *)malloc(sizeof(MONKEY));, G6 G, a: U. _  C. T- r
     s->number=i;s->flag=1;
) f1 ^6 a; @7 P, o     s->next=head;
/ V: k7 B4 s- Q8 J# A* k; r     p->next=s;p=p->next;
; T, @* M$ F% y4 `2 n; S% r    }% d% Z7 h/ Q* w& @  }
    p=head;
. V8 {: g4 A1 D" Z- R7 e   for(;;)
& q- l6 f, R( W    {if(p->flag==1)+ l5 u8 C! S: U5 r  m
       count++;
) ]/ ]5 t- M$ e% `  A9 h     if(count==N)
. B$ m; T& B8 I# S* u# `8 O        {p->flag=0;8 s2 x2 D7 W/ ]
         count=0;9 s: M1 c2 h5 U+ u4 m1 A$ C* [7 |, M2 U
         sum++;}
  K7 |  S7 o- V2 f- W& F' |0 K2 T, |     if(sum==M-1)  M4 b) k& ]4 H' [8 f
        break;
! K6 r% L& Z, `- ?     p=p->next;
6 y: G* V8 ^8 r8 ^0 R, b    }
+ q, K! g$ ^0 ^5 g    p=0 F- u1 ~+ f2 }
    head;
2 m7 ]4 s+ B- _4 A7 H8 {    for(i=1;i<=M;i++)
: b# }' J* D2 u3 e" e: U4 S$ m7 C    { if(p->flag==1), M  v/ f: C  B' }
        printf("\t%d",p->number);: J8 u# S+ ^* q+ C( x
      p=p->next;' k' q1 i& A; c* z$ P. d
    }
7 `2 _+ N6 ?# L' B& i( u2 F
1 ]8 D8 y- @4 Z- w5 X( g( a1 Y: J4 ~% s- m3 C

  M# X& L7 d4 W4 @}
; ^9 _1 i5 y; m4 P+ |8 O1 d
第二种方法:数组) ]  t( R/ p) v8 m4 i+ x/ Y
#include<stdio.h>2 Z  r# I5 m2 b7 g5 f! K/ y
#define M 8$ r/ k3 i# s% X: d
struct monkey
' k0 G' N. G% m; `$ w. D: P{int number;( E( b9 q5 U' `' T
int nextp;
$ E% z) \# Y( o}link[M+1];
8 n+ d: e. n: [* j; a
7 g7 q8 ?8 H1 T6 v! l' A9 k" }/ q# nvoid main()
, r5 z9 t* i% v; Y{int i,count,h;, R# U/ P7 m2 Y% A
for(i=1;i<=M;i++)0 U! N: D9 h9 e  |  r7 w* g( D
{  if(i==M)
- `; r; V& X" ^4 v   link[i].nextp=1;
1 A. y$ ^7 ^( u6 G3 Z   else
0 M  o3 l- {2 B; @3 G% x& w0 C   link[i].nextp=i+1;
* j0 f9 u$ L7 v  link[i].number=i;6 T3 @' A3 {8 J% E
}
2 b' Y5 M$ z' Rprintf("\n");
5 b5 R( A+ e, A$ {  O. ]9 Vcount=0;
3 H$ K% z! _8 W2 eh=M;
, n! f% V2 y  g# Y- g! Oprintf("依次退出的猴子: \n");
& w, S6 s2 ]& b# }while(count<M-1)
5 ^2 g* A( n1 P{i=0;
$ O/ ]1 `" m3 G+ Iwhile(i!=3)4 T8 W% p1 n: Q2 A+ r
{ h=link[h].nextp;
1 V3 v) F0 G( d- \; D, c   if(link[h].number)
5 [. K; k) L  _  e6 S7 l     i++;}' z# b6 ?, Y( ]* L# H  M! w) q! M
/ k+ S) T5 _8 J& }& X
printf("%4d",link[h].number);
+ Q$ P2 [$ V# Y3 D: a6 hlink[h].number=0;9 ?8 l* @3 }4 Z2 h. {2 m4 }
count++;
: b; C* v( R. M}
' ?4 R- f& P" u4 T4 \# A2 p7 Q6 c: i" U! Q4 i# B7 [& d
printf("\n大王是:");
! I5 ^' g& \" h% V3 @  for(i=1;i<=M;i++), E6 V: x8 {4 y7 `6 U' @  Z
  if(link[i].number)
6 V* D1 P5 k# s$ S! `    printf("%3d\n",link[i].number);* P- \$ H0 G  ]7 K
* I" O+ d4 o5 d5 _' t5 o
  |- c8 o" \, E# |- [( c3 p
}
$ W2 \2 l) s# a! _2 w
第三种是普通方法for循环

6 j8 a9 q3 b* m0 J#include<stdio.h>
2 D8 L/ |- n' }" }6 T6 p; tvoid main()$ F9 \3 w% @3 E! v' x' M3 G& x$ r% G
{ int i,k,m,n,num[50],q,*p;6 J' V3 b; b# j/ Z% u) J
    clrscr();
. x1 N  z( ?$ |3 w+ h( V   printf("input number of person: n=");5 p. g; X6 T) N% P2 b/ n
    scanf("%d",&n);4 K- E% O7 N1 W, L! ]5 j7 N
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只  t, x' P5 C! ?
    scanf("%d",&q);; r+ G" K8 g% ?! T+ q. s& Q+ p
   p=num;
: x6 ]$ o) s8 I) b$ e2 Y+ I' G: Q3 p  for(i=0;i<n;i++)$ Z" \* \2 j- I, x' F
    *(p+i)=i+1;' G# z  Q- }# K  |% I
   i=0;
. z$ ~1 d% i- M2 f# C0 M  G   k=0;8 W% @* S; o/ [$ F% v. K
   m=0;
4 J  h* p" f. e% _' z: W, M  while(m<n-1)* Z+ O, ?1 i! T$ w1 w: T( d
   {if(*(p+i)!=0) k++;
( o) o& ?3 @% G1 |8 c' X     if(k==q)1 }5 @4 h3 Q! x; x4 U- f  F. ]
      { *(p+i)=0;0 h$ K6 q4 {1 Y6 a2 f) v
        k=0;# C7 i! }/ X* \
        m++;
4 a* U; z, E6 v$ A      }
; _) C$ `  x  x3 g" E    i++;4 C  e% [% j0 U" K
    if(i==n)i=0;, l" P: u: t. w2 V
   }
4 K: V+ v0 n4 v( d  while(*p==0)p++;1 P4 p0 `! [% f2 F
    printf("The last one is NO:%d\n",*p);3 o1 [1 l0 J. \5 {: e
     getch();5 u% m9 `6 F% b8 d% O

7 l* f* b: x3 _8 s+ [}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;/ |9 b8 F+ w& F- v
namespace 又费马达又费电
6 ~0 `+ U, q& c/ v1 N( ]{3 p" _- w" \, Y
    class Program
2 O' a$ q2 G0 K    {2 W1 O$ y# [- F9 E
        static void Main(string[] args)4 M( {7 C7 Y7 t
        {
, L% e% w% M' m$ z9 Y, ?3 z3 G% J; r            int m, n;
+ ]2 p; c2 y5 \# P& T! {% X& v6 W            Console.WriteLine("请输入数组长度");& `0 u- ]. R1 C" _* @& H# Z- y: j
            m = int.Parse(Console.ReadLine());//m为数组的大小* _+ a) i2 m) g  H
            Console.WriteLine("请输入要截取数字的大小");$ f$ G+ \" J  M6 X
            n = int.Parse(Console.ReadLine());
# y5 Z1 N4 Q& B0 Z6 F3 b/ w* G; a& ~            int [] numw=new int$ W9 {  _  m3 B& D8 s3 r; p
; H) c, X% g' V! f
&shy;&shy;&shy;;. {4 \! v: _4 H; Y1 p
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
3 T: E5 o) ?+ Q  G2 W            {
& S/ ?  ]: c7 [$ R# F                numw[j - 1] = j;8 O" o! B9 t' F0 N8 H2 _0 B
            }, a& D/ a% ^9 i( k7 @) h5 f: K; L7 g
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!+ h' M$ }/ `$ q) z
            while (d != m - 1)
& I' `2 ?& ^! }, q' l  C            {% [+ L% v3 A0 S' w/ R
                if (i == m && d != m - 1)( a4 h9 ^3 b  A& s, M, g+ _
                {
1 r, Q0 Z. B2 _2 a6 \# R4 k                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
0 {5 Y  s  k: l, U) C                    continue;
8 @- B) m$ D" G9 U9 s                }
5 I& L% d7 T  L4 k                else
% N: i) S0 }# ^( O8 ?# B                {
# e- y0 }0 I* j. L# D+ N                    if (numw[i] != 0), C5 G% i6 F6 H' }( z6 @2 W# y
                    {
! s. f. J1 A0 C" m. v" u7 ?                        i++;5 S/ o. p. P! |; G  {
                        k++;6 u% M4 t( Y8 U3 M9 V' ^3 U
                        if (k == n)
  _  Q5 ]! [- T5 Q8 p                        {) F& C0 C1 E3 r
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了5 X' c5 ]" R: f" A6 v! s* f
                            k = 0;
( u. v6 `' k* I8 o% @: U- N              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
3 f9 G" s$ `. p( J, x                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
( @8 v, p! M" M0 E4 y/ u3 R0 l- @% n                        }) h# D( ~& M; h: S+ S
                        else//输出暂时还没有改变数组元素的值
( K- Q. _; R' v" m; H7 {                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
$ b2 J8 w1 {3 X/ R# m                    }; X5 a6 B! ]* [) m# U& A' Y7 ~
                    else
- \6 w+ x  C8 ~5 K- d                        i++;//数组元素为0,直接跳过,不计数。。。) i+ ?7 _, z9 \7 \1 A4 u
                }
' `+ {6 u5 E. F& C  l. D
9 ^0 U9 C5 E4 ?( X" G3 M; F: R6 [3 X$ M2 @) a! [7 O% c
            }//结束while循环; C2 {( J* ?9 U
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
* u% {* X. D9 f           $ I+ I5 M) m; l
                if (numw[i] != 0)
' N' O; W8 v& \4 d/ n  }2 M/ l  r                    Console.WriteLine(numw[i]);
8 I1 I) B" ?* q           4 ^' H: c+ s* C7 i. h0 e$ @
            Console.ReadLine();+ V4 E  y9 q# S, Y
        }2 M4 b8 v2 x5 W4 P
    }
( U! I$ i0 s# G  c! |}% Z0 S% [0 Y+ V3 i( X) P" O2 Q
小甲鱼最新课程 -> 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-6-12 02:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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