鱼C论坛

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

猴子问题

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

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

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

x
大家好!8 G* W) r1 M2 `. Y2 Z
这几天我在忙着编一个问题,我用了一种方法编出来!4 B/ ]# Q& s; G4 J3 ~  v+ e* w2 n
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
1 M+ v5 g  u+ S注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
! Y* T/ k, C% p+ T
/ w& p& P; t1 ?: [5 V7 T
/ V) G# D% x; J4 e
                            题目% ?. Z8 P- \* H  \
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
# N1 \& f0 y( B# \3 e3 Y第一种方法:利用循环链表* Q. E# V5 S! T$ `: A, D
#include<stdio.h>7 T% j( w6 H; S
#include<malloc.h>
9 b- S( K% x8 E4 T- v& ?! M8 N/ a3 h#define M 8            //共有8只猴子
' |- H4 I/ J7 A#define N 3            //数到3只时退出第三只
# w* V# H. i0 I; g# C: M: k: itypedef struct monkey
- ^, D* @$ W: c{int number;  X  u9 H" g0 |, ~6 [* C: U
int flag;1 I; W+ |; B! O: a
struct monkey* next;
) U) b/ q- c# `# a  S2 X}MONKEY;
" M0 b* X9 \5 U9 K+ H* C8 L' rmain()
! o1 R4 C3 \" s( r2 i5 _" g( _{ MONKEY *head=NULL,*p,*s;
0 B9 s) w0 _3 m1 @0 ~) V" o  int i,sum=0,count=0;
8 d! F% N& A, ~! ^8 O  clrscr();              //清屏9 K/ @! [# p$ Y( a
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
( E! z9 w, C6 @) _) O0 Y1 W  p->number=1;p->flag=1;
, O( w9 @, @8 {  p->next=head;4 ?; v! s, S& N* G" d
  head=p;# S; r7 l' k6 ~' R! {' \' I
  for(i=2;i<=M;i++)9 `% ^8 U$ S1 X$ d! o6 r, `6 {
    { s=(MONKEY *)malloc(sizeof(MONKEY));. M; h3 A, H' c# g% s3 o0 A
     s->number=i;s->flag=1;
- B. ?+ C7 E5 y/ _  ]     s->next=head;
3 }) z: ~; j& g# [- W, d9 ]     p->next=s;p=p->next;0 t1 R, p& m  k  D. s& w
    }
% B2 [; M! O  j/ U; K    p=head;" _3 W$ @5 y2 G# L5 `
   for(;;)
4 s; J2 G# U. x. P  p    {if(p->flag==1). _9 j5 \( t  h( T8 H5 U( _  n
       count++;* b8 ~, z) T- f1 {% X8 t
     if(count==N)* \5 N5 l( U4 c, I( z
        {p->flag=0;- c( q. N; ?8 m" N; S; c7 O
         count=0;7 X- Y, ^  l  F, K$ e# g
         sum++;}
9 w& h9 A6 n: q9 c     if(sum==M-1)
  ]- H2 ~+ w3 w        break;
* W% o8 `0 E! O$ c0 o+ r     p=p->next;( S" [9 Z$ c. r' K7 j  F+ q8 @  _# h
    }9 o  m8 u6 y+ h. l
    p=3 K- F& v% Z+ W8 G
    head;
) g& e5 L0 L( o    for(i=1;i<=M;i++)" t' S6 ^3 T& O
    { if(p->flag==1)
+ C3 c0 ~. Z( h" ~7 f        printf("\t%d",p->number);
, X  a, _8 S4 }7 @) z+ S      p=p->next;. x3 M$ p8 R3 g6 f
    }
. e2 @3 s, _+ {. O2 s
& @' O6 a3 `3 w+ F( y; t* Y: N
) h6 T( z5 F* p1 D0 J1 ~% J5 P& B1 u( [+ `: A8 F# c5 a. g
}

% T4 g, N& F4 y- P" x. u" P5 [第二种方法:数组# P% Y7 [# X/ K* b% ?
#include<stdio.h>
; P7 d+ [' N$ a+ A6 f- i, {7 `$ f#define M 8
* G' ?* @) N2 W" c% N+ \8 i3 Istruct monkey
0 h/ W# Q* X- R0 T. D% X9 _{int number;7 W) P- o! G6 [8 T# t4 J+ H
int nextp;
" ~4 f& E" V; K: ]% K( I}link[M+1];/ ~9 Y. u- M, y/ c: F1 s$ d8 E6 N8 P
& P. Q  r' M) V! v
void main()$ W8 G/ ]) s2 T% N7 P
{int i,count,h;
$ R$ i& g, z  W8 j# nfor(i=1;i<=M;i++)7 f5 n# X  z- j2 J# H' K# y( ^
{  if(i==M)
$ P" D& @8 I" D. P   link[i].nextp=1;" L" c6 n7 G& S1 ], v
   else
. [- J8 Y1 G8 X+ F& a0 @2 j   link[i].nextp=i+1;
+ l3 Z3 v& y% n' a- S8 K% f  link[i].number=i;
1 H& o0 F5 h) W) ^% R}
+ t4 h5 z5 o  j/ Zprintf("\n");3 F) n- ?# o/ X$ g
count=0;
" f7 @1 _- j5 Z7 L. y3 k) Q/ i6 ]h=M;* z! C' h5 S* j2 w" e, ?
printf("依次退出的猴子: \n");6 H! l! ~1 t  U( S
while(count<M-1)( ]9 h( O+ u" o( j5 y3 s/ x
{i=0;" x- X( p; \, U4 c+ C
while(i!=3): y; X5 `) g) B, r' g( b0 m- c! @
{ h=link[h].nextp;# ~8 o* r( I5 [3 V3 {% K
   if(link[h].number); C+ u3 o% _4 n4 M7 b  x
     i++;}" Y7 Q1 P; F) m. I) O# l
/ ~+ M& T) a0 s5 D; ~6 n
printf("%4d",link[h].number);, j  V7 h& \, z3 G0 a* y
link[h].number=0;
, h# d: J4 R6 M& }( U5 wcount++;% J0 c' v; p  ~( }
}
5 }/ d4 A" t! I) T0 h0 t
% N$ O" X/ ~) o8 L4 k- j4 rprintf("\n大王是:");
2 b' t0 z) k" v  [$ a! d  for(i=1;i<=M;i++)+ g1 Z, ]) B& U+ N* q' [  O
  if(link[i].number)
; D% o7 g, [4 M5 u0 H, C( q- o    printf("%3d\n",link[i].number);# b; B( w- h# _4 x% v3 K9 Q/ V

. F. t0 E' N. X0 @
* l2 w8 o9 I7 g  j, }. S}
: S2 w( o; q3 a. ?: t
第三种是普通方法for循环
" p0 \, _8 o, A2 A" H4 y0 G
#include<stdio.h>2 _/ {# o: ?$ r8 }) P
void main()2 z) n+ _& h; u% z' B; i0 F
{ int i,k,m,n,num[50],q,*p;! T9 F) p- p; k8 [
    clrscr();
* u$ R5 |$ }/ P) y) O   printf("input number of person: n=");: U' E# e4 [% d8 J4 F6 Q
    scanf("%d",&n);$ K6 x+ v* R* `  J2 l4 l
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
6 v. U! b7 ]: B( J3 d+ x    scanf("%d",&q);  y1 B+ ^3 S3 F: x2 \2 t
   p=num;
3 _4 E. F. D6 ]/ T6 M  for(i=0;i<n;i++)  e. j; S; w! Y' a: o" p) G
    *(p+i)=i+1;# R- K  `6 ~7 ~8 J0 s3 _2 `; b
   i=0;3 t, l9 w8 u7 W5 F# e" o
   k=0;
8 a+ H, a6 c4 r! \* Y0 E   m=0;
) M, K5 p0 Y- o  while(m<n-1)0 s/ S. c0 E# w" t. g% w
   {if(*(p+i)!=0) k++;
  J0 K' T3 F6 t, Z1 k, k4 `, T# U: ^     if(k==q)8 Q/ i% t- |  L& a+ q" ]
      { *(p+i)=0;: R( C; _" K7 f$ @
        k=0;  R3 O( S) t. T) [
        m++;
9 m" |# ~5 w2 d6 N# I9 w) ]. t      }: L3 w9 v  ~1 E, k, z, D: T  N
    i++;6 T$ q/ M) h% p1 D4 l
    if(i==n)i=0;% U: I$ a: s& ^% y9 J  V" W1 O
   }3 H/ d) H4 ]7 n7 H
  while(*p==0)p++;
% B6 f0 ?' u; b! w9 U* F    printf("The last one is NO:%d\n",*p);
# l8 c+ n% D  U- S- E  z% i     getch();
5 p% P6 ?- _% W" ^. n" s! e. {4 L
/ E/ R! J* w* B2 F- u) L" F* p}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
  b9 E/ w, v9 @# u# snamespace 又费马达又费电4 `4 q' {% [: f6 `' d! ]
{; e6 @) W9 w. g( P
    class Program  `  Q* S. |7 @) H# }- `8 S
    {: a; G; r' O. B
        static void Main(string[] args)
, ]; N0 q0 N* O' K        {
* h) P6 }- b( L. L( D) i- L            int m, n;7 D. r: ~" N! A2 e
            Console.WriteLine("请输入数组长度");! L6 Z. r& U9 B+ N
            m = int.Parse(Console.ReadLine());//m为数组的大小
0 V, X3 M# h+ M  Y3 i            Console.WriteLine("请输入要截取数字的大小");6 `0 z! K' U8 R( |4 ]8 w+ Y
            n = int.Parse(Console.ReadLine());
1 h: [  A( S. E# k" I            int [] numw=new int
  A  i: L2 m0 y9 |" X# V4 W" E* K' x' L! P7 B$ z
&shy;&shy;&shy;;" G) S" M& Y# T* \
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
+ G0 s( O* d* Z/ }- z            {
8 E7 m9 m6 _0 e  I) b) d+ s                numw[j - 1] = j;
5 i% a8 i3 M% w9 Q5 c2 H1 Z            }
5 V3 x- @0 ~! W8 N) o! J8 n* m            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
8 _+ X& E1 r) V$ b& I            while (d != m - 1)
; y" P/ z+ \8 p            {
, p6 h9 ~, `/ m8 `                if (i == m && d != m - 1)
" l! s; T2 L8 B' [# k+ b& F                {( c# g8 R8 j2 ]* ^% D3 a, t7 Z
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
% G( J, Z4 f8 m$ H8 o% f- u                    continue;+ j- C4 ]* P7 u# g7 N0 ^2 f
                }: b8 W/ ?( `7 L/ @. {0 ~: N' M
                else
+ C1 J6 y  i( c% R                {9 m5 N* q6 t# B5 c# g. r
                    if (numw[i] != 0)+ w' y& G, r' N1 Y9 @6 @
                    {/ z+ G4 |- a8 q. o6 q
                        i++;# \2 q- L: e/ G9 J6 I6 ?/ C
                        k++;
& |& F( a, S" q                        if (k == n)' ]% E' u! Z  l+ [
                        {
/ n6 a; i4 v5 z- n1 _3 _4 ]                            numw[i - 1] = 0;//把在n位置数组元素的值改变了0 Y8 A7 ~. U; g4 ]; J6 [. \
                            k = 0;
, Y6 P  A) Y# B              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
  {9 i, g) p/ F/ o2 R                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
; h0 n. |$ W/ z& _                        }- Q  P9 v) Z% g
                        else//输出暂时还没有改变数组元素的值
4 P( ~& x; e& b2 N; D                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 n4 ^4 U: F3 V$ q* y3 e
                    }
" {  Q. R! ?7 U) t6 p                    else$ h: |; Z; W0 b9 n
                        i++;//数组元素为0,直接跳过,不计数。。。( ]3 Q( s& ^( G8 |! h  P$ s
                }  w2 g/ x6 \6 C  x# G& s0 P
; S& R7 T# ?/ B! M
+ r2 |& `& z# m$ B( T) L7 S. |& G4 V3 U
            }//结束while循环3 v, B% [$ I6 ?- u* ?: ]/ u5 U
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
9 K* R; f2 S4 G, M           + g" k& g" B- g& m" K9 o: R7 ]
                if (numw[i] != 0)
6 y* }3 u0 k0 g9 ~3 e/ [. |' ^                    Console.WriteLine(numw[i]);% z; O4 f# t# G) O0 a; h7 ]
           & P. m4 v8 t! E3 ^7 B
            Console.ReadLine();  b. e- |, f$ H' {+ }( b9 i# E
        }
9 J% }7 e( \7 A( D) O1 e. t7 m    }/ J5 k9 ]! Q) E0 j) C7 ^) l
}! S) P  e$ m' B
小甲鱼最新课程 -> 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-1-20 08:01

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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