鱼C论坛

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

猴子问题

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

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

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

x
大家好!* Y4 _, _8 T, d0 v
这几天我在忙着编一个问题,我用了一种方法编出来!
2 o9 L: m$ A* }7 E' ?6 ^但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!* D1 z5 f! g4 E
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 0 P0 l% f1 K4 p/ \6 _
8 T7 x8 I7 Q* z: v8 ~

/ C$ ^8 k3 X5 J7 T  z: b3 v% J5 j" Z
                            题目
' c$ R5 \; z! d6 q3 A$ D& p山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。! d' V" z$ t9 ?. J$ t; |
第一种方法:利用循环链表
- E- ?1 w" ?( W4 K6 F#include<stdio.h>
% k; _; W- M8 r" z#include<malloc.h>
! B7 W' k, B: U2 f, d/ ?* j9 x#define M 8            //共有8只猴子
5 Z5 _9 \/ U- l  ?4 q1 ?, W* h, B#define N 3            //数到3只时退出第三只0 J- m, @6 y& {- R/ _8 J: u
typedef struct monkey
. ^; x- r: c7 M3 p; c{int number;7 ~7 B! V# m# I( ?2 F
int flag;
+ E- B7 L) R- Y+ ?. p5 D1 Wstruct monkey* next;
' i$ V+ M# V* {' k8 Z2 V9 x6 \}MONKEY;
$ ]4 T- y/ D( J' T- g& Ymain()
  j- v& u. _  t2 k6 f+ h' f{ MONKEY *head=NULL,*p,*s;* F9 }1 L2 o& f+ [- x: ?: n! Z- Y- Y, I
  int i,sum=0,count=0;
9 h3 [  w  k4 S- ]: y  e7 h9 t% E  clrscr();              //清屏- F7 k3 F+ U& f6 S
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存; x$ ?7 o' }/ ]. k6 k  M
  p->number=1;p->flag=1;9 n- j6 T. E+ a( ^
  p->next=head;( O3 ?! m1 R6 j
  head=p;
9 j: s6 a3 T% p& b/ q5 o  for(i=2;i<=M;i++)8 e9 v0 f* c$ H6 ?, m" }# ~. v
    { s=(MONKEY *)malloc(sizeof(MONKEY));
, m$ n  j+ c0 C* u; ~; e( C5 X' @# H     s->number=i;s->flag=1;& q" m+ ]9 V* r. q/ Q8 f" f
     s->next=head;
& v4 u3 [) h) Q' R+ ]     p->next=s;p=p->next;
0 ?5 W+ A8 z7 A    }- ]6 Z  ^' q# f' S7 H. t; b
    p=head;
2 @- `9 o2 ^: h2 k   for(;;)
. X0 q0 h# C, O/ z# s- y9 ^' V( X2 |    {if(p->flag==1)
+ X4 L# f. l- j* w: D% y       count++;- H( i% i- Q) u' A  n
     if(count==N)
, s# j& h9 b* z        {p->flag=0;5 T" S' g& \' V- O+ A. g) Y! H$ h
         count=0;
% [4 P) H/ L( M( F+ C* ], Q         sum++;}
( W9 f9 x7 L8 _9 ]) ]6 U3 M& @     if(sum==M-1)' `, K7 B! v& [' I
        break;9 D0 H1 X# o: C5 }
     p=p->next;6 O$ r; o; D. }" A; L
    }
# c6 C  D, m. F1 s    p=# f# |: P5 w% v$ b6 S3 J
    head;: r3 [" D/ B- H# z/ w$ Y2 `. i
    for(i=1;i<=M;i++)
4 @# V/ M( ~! w* v) k) o    { if(p->flag==1)
5 z6 |/ G* V5 G: k# C! q        printf("\t%d",p->number);# w# \; P& A; V9 F4 S+ {( N: I
      p=p->next;
7 U/ ^- z/ w# E/ E9 _: M    }' B. ?9 W- i5 q- @( M7 [5 f/ i( v

& e1 `# |% P. |" r) ^1 t* c# V- C( f+ h

& s' W$ ^. @: h$ r/ ]. |}
0 Z8 j, A9 q1 M. u, r8 F
第二种方法:数组
6 q' z. Q" |4 l' H# q4 J( M, Y2 _' B! q#include<stdio.h>
' H$ b1 j' `4 |6 b  J% `" r#define M 85 A8 t* U) Z5 \  |  Q) S3 E
struct monkey# ?) u: ~: C' K" G' M9 M. d
{int number;
* i1 M( ?  R* p0 U2 ]2 ]int nextp;
; p+ N# p3 n1 r}link[M+1];
" @7 j! ~/ u& ]' J; m! @
. S5 M9 X" m' r0 g# w, I4 g3 C  svoid main(): D. ^( m1 ^. l9 c. B: e
{int i,count,h;
/ G8 M  T" _2 O# l6 b+ E; mfor(i=1;i<=M;i++)% j3 m" {5 F: }, }3 Z7 w- v; N
{  if(i==M)0 `; d* k% J2 m8 W1 G3 v- h
   link[i].nextp=1;- r: h2 X# P; A  I' }9 v8 K
   else- U1 D& Z/ o( U- m8 v
   link[i].nextp=i+1;
' e0 g* @7 C( F) p  link[i].number=i;
  R; E: Q0 \" n! C: Z4 _: z}/ \! [& [" V" h. H2 `8 S
printf("\n");# Q7 m1 ?  R- @; Q$ K1 d8 C
count=0;+ A' d% {! g) a
h=M;
1 e: D0 w) n/ R: `/ |7 ^, t' ?0 w! }: tprintf("依次退出的猴子: \n");
& e5 _1 o0 p- J# ~while(count<M-1)
% s6 y' O$ U6 Q  J{i=0;4 T8 d8 y3 w( p* Y6 p
while(i!=3)
4 t' _# O' ~" S4 M/ M7 ^! i2 S{ h=link[h].nextp;
$ n; V/ _* i# L9 o7 ~5 f   if(link[h].number)
, E  O- S' m3 E; D0 p) @     i++;}
$ ~4 ?1 `6 c( t/ G3 \$ q$ ]! F8 u) L. k
printf("%4d",link[h].number);
  D8 e, E* A1 r% glink[h].number=0;
( v1 X; V3 C: x. Q+ ecount++;
/ @8 r+ s0 ?! a}" U% q0 F  g$ x6 w3 ~8 {3 Y) P
# A9 B# o! {5 b# a
printf("\n大王是:");3 P- u1 ?& V# w) |7 J) C- ?
  for(i=1;i<=M;i++)
/ p, K4 w" f% `* n  if(link[i].number)  X8 k: U$ r1 A9 a9 d
    printf("%3d\n",link[i].number);7 h! d: c8 G7 P$ q6 J* J2 S

+ F! H0 A3 {4 X& j- _
( }! R% C3 k6 g}
  @  t7 Z: U% U: K% n& P5 G
第三种是普通方法for循环

" c3 s* @& R0 m- R# q#include<stdio.h>) I5 K3 o* e% k% g
void main(); n( A- N3 v- g7 B- k. K, ]
{ int i,k,m,n,num[50],q,*p;
, A- q2 b4 y. P! P8 i, H    clrscr();6 m- X5 F) {0 u6 Y9 J9 G, o2 C' g
   printf("input number of person: n=");0 ]/ f+ S/ C+ B" g
    scanf("%d",&n);7 [8 D* p/ x1 W5 {4 K# _4 }
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只+ E6 v9 m( {' s# R. {
    scanf("%d",&q);
0 [; U; ^4 t8 k8 l+ y6 I   p=num;% B4 c; g0 Q  H& P
  for(i=0;i<n;i++)
3 s6 u* K1 T$ C8 \    *(p+i)=i+1;! E, f5 s, u  z: r" s! ~
   i=0;1 w7 ^" e; e1 H% m( R
   k=0;
# j1 x2 {. _# Q6 z* Y9 P   m=0;
7 v" _: E- k- {; D  while(m<n-1)! \( J' ]9 P0 q5 ]' q
   {if(*(p+i)!=0) k++;5 d( ^/ G2 o" V& Q
     if(k==q), S+ C# w2 T" U* M2 |1 K
      { *(p+i)=0;
  d% }5 _& G; U6 F# R& ]        k=0;
, M3 }/ M. h" D( L: _5 c        m++;( h' _+ \( l% `( Y5 z
      }
& W3 j# x  @9 _" c# y3 X" Z    i++;. l9 m) _% l$ w
    if(i==n)i=0;$ Z% I6 x6 \2 X: I8 V
   }
) T/ d  |1 g- K: \  while(*p==0)p++;
, h. ?; v$ m0 V1 S    printf("The last one is NO:%d\n",*p);
: r( S! N+ S& W8 ^     getch();- }1 t/ P- c: N3 ]$ b3 Z& A4 M
6 @6 F# q1 m5 D) M; B6 {
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;' i. [+ R: t6 V- L- i
namespace 又费马达又费电, s4 `- _1 X4 r) ~. V, t  E( U3 p& @
{- L3 A, |2 V6 R0 c6 I1 }: m
    class Program
+ W: z0 [, x) Y+ z    {
# S5 p, ?9 j! L" z2 y        static void Main(string[] args)0 n0 M- o+ Q4 O: S: r
        {
! b9 W$ a  C( v7 G$ |            int m, n;
  }+ i5 D. j' \2 l- M. s            Console.WriteLine("请输入数组长度");
9 ^3 `* G# b- n; w            m = int.Parse(Console.ReadLine());//m为数组的大小
. S& c& o0 M7 r            Console.WriteLine("请输入要截取数字的大小");
* O$ A3 S( y: Q4 Z$ T& F            n = int.Parse(Console.ReadLine());0 H" m( \/ [$ e- L. |; u
            int [] numw=new int9 ^6 S% S3 w. d! u) r, h
6 [. S! o; v% n
&shy;&shy;&shy;;
% ^  }  f( i* [            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数7 ?# B) J# x9 f4 [1 N$ z6 h
            {
# d4 P- m+ h) p# W8 x7 p& [                numw[j - 1] = j;
, \1 g& B  T6 ^3 {3 i            }
- _4 W' Q+ ?+ B- z6 J/ w9 Y* s            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!, l5 t2 ?& q( ^' S- d6 Z: g
            while (d != m - 1)- s0 w5 H6 ]0 X( Q# N
            {
+ R7 A6 h4 \+ [: S  }                if (i == m && d != m - 1)
5 Z: p+ x7 f/ k& c$ c( ~: _3 @8 Q                {
4 i) R- w4 i; t                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!. Q+ Z: w. C; g" p
                    continue;
. ]5 X- z5 E5 n+ i4 N                }
2 \; n( f; z3 g                else
0 ]! K+ Y+ o; l, h                {
) ]  Q/ C3 |( t7 B                    if (numw[i] != 0)! l( ]; |) Y3 V. T3 T: Q9 G
                    {
+ [: H7 ^5 K% C: D3 N8 U$ G                        i++;
2 h" J5 I1 a1 _                        k++;  l0 k. s7 h1 s% \# A
                        if (k == n)
# L, a. g1 h8 T/ |0 j                        {
% h4 r! N7 m5 N1 e4 u3 U9 g  k. n5 @                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
: S' M% U% U* ]. x( z                            k = 0;/ n8 b# y* V5 J$ y) g
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
( J0 X. s  D  Z                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, }$ i' e( W# e% Q$ f                        }
; m2 ?- H5 Z' g4 w6 ?2 X* I                        else//输出暂时还没有改变数组元素的值% M( e* K0 f. v$ Y
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
! }( A, |( Y6 ?# Q! z                    }, o# n/ W* m4 d2 i* p9 p& V4 z
                    else
, ?; T9 @- t  H4 ]                        i++;//数组元素为0,直接跳过,不计数。。。
# e" g( R, J  ?5 F1 G4 q                }2 P0 m( R4 q  p3 v) Z
1 }6 C* q7 |+ z, r* J7 f

7 ]- E( a- d/ x+ y            }//结束while循环6 {' E2 x$ L$ `, l
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
, d+ N2 S: R: F8 L: H           3 A  C2 z+ R3 Z0 t" O0 T8 z
                if (numw[i] != 0)" q4 X) n  C: ^; F+ z$ P7 ^
                    Console.WriteLine(numw[i]);
* e2 M* s5 Q8 O: l# K1 |* S           , ~7 y% K7 i  K. R% c5 N
            Console.ReadLine();7 j6 K  I/ n+ w) S( E0 F! Y# D% L
        }
" o3 c0 R( Z4 o1 M* T    }
& m1 r. x- T- G8 S, Y# u- x}1 R- V' s6 M: D" z
小甲鱼最新课程 -> 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-4-21 01:50

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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