鱼C论坛

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

猴子问题

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

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

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

x
大家好!
( t4 F; ?' M; \$ P7 k. U这几天我在忙着编一个问题,我用了一种方法编出来!$ c: N8 R9 D" m" E' T2 _
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
" j2 K% ^6 s0 e: H# M; U) c% h注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
9 b% c' N5 e) h. u+ p2 u+ j, ~9 U5 q0 {: @# K4 _

! m7 h- V# Y: K
                            题目
7 J- f/ l" {6 A: G5 e山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
: v& e# M$ m7 ^* h' E. |第一种方法:利用循环链表
5 f/ D0 |% O/ L4 u: w#include<stdio.h>1 y/ [- Y; u5 E& b6 C. `
#include<malloc.h>3 \1 n! N% T' V6 D; m- T6 ]
#define M 8            //共有8只猴子7 B0 Z6 r. r3 k5 J+ g
#define N 3            //数到3只时退出第三只
' x' _$ s* V" h0 |/ |typedef struct monkey( p! }$ }9 y- W2 ^0 C9 q: G5 J
{int number;
% f6 l7 }* e: C! {7 gint flag;9 [, ]. Y6 I. G& `! o  k4 X4 m
struct monkey* next;
, I( x3 u" t! G( h* T$ O( u* R. d}MONKEY;: y# f5 Y% B5 J8 j, ?
main()% N7 b5 N6 ^" E6 \, L5 M$ @
{ MONKEY *head=NULL,*p,*s;  b' o* Z1 G+ g) F  v  U. Y& Q
  int i,sum=0,count=0;$ U: L$ r1 r! N$ X
  clrscr();              //清屏7 g% |9 N+ r. Y% N
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存: U6 l" S" y- N7 N' a/ J! o
  p->number=1;p->flag=1;# \: E7 i" p( `( S+ I5 g& \$ a2 K- v
  p->next=head;
9 a, r) u9 P/ t4 Z' a  head=p;
8 u2 W# T: Q  |0 L" T/ K4 x* d  for(i=2;i<=M;i++)
5 B8 p% S- x9 `! E- Q# o" N    { s=(MONKEY *)malloc(sizeof(MONKEY));* X# R3 g& ~$ g* \
     s->number=i;s->flag=1;
# k$ C& o# D( W) q1 M. i7 W     s->next=head;7 E: M2 T5 t! Z7 H( W! B  d
     p->next=s;p=p->next;% H9 X# @' f( `; j+ \3 l7 j4 g
    }5 P; x2 Y. \- x; `
    p=head;' c9 j  l+ G% n# V8 O- R4 ^
   for(;;)% \+ E# U7 S* N
    {if(p->flag==1)0 U5 r, c2 s$ T! M
       count++;' w$ g6 q3 ]6 E/ b
     if(count==N)3 P4 w4 D- P9 s% l' F( }
        {p->flag=0;
: |- x" e6 g+ d) V         count=0;. K5 e( [% `6 Y, l  w& X
         sum++;}
8 h4 r' \. c( T3 \5 k+ V; }* A     if(sum==M-1)
- i2 C) @4 ?3 ?- ]: k$ n3 m, M. a        break;
! p9 R: u& U) I3 _' N     p=p->next;
+ B. d  v. ^: K& ]/ v! a    }3 e5 |) G+ K& Q( U- A2 \
    p=
( F, v6 Q5 \5 B1 y    head;/ i+ P6 F5 ]/ c0 ^9 I/ |
    for(i=1;i<=M;i++)4 w% O& D+ \. ^0 C6 z* ~
    { if(p->flag==1)# d; p7 l, w; p1 }+ P7 {9 e! N: I3 V: K
        printf("\t%d",p->number);
2 r7 |4 U% h9 U; _, {$ G; O      p=p->next;. `% X% [6 ?9 |6 h. u
    }. C! b) H# h' T3 T: u
; R8 P$ h+ C. `" i* E  E
" H* |& ]* T$ [/ h% @% F
$ t6 |- i8 S" J5 L6 Y9 M
}

+ s3 c1 i  z$ x, r% Y, Y* V第二种方法:数组
7 w+ v: d8 N' O: B8 l+ y#include<stdio.h>/ R; ~+ O/ P$ v9 D( Q9 N; y
#define M 8
. a; V0 `' P2 C# d: K3 E4 L% `struct monkey2 Y& X' B' V. H1 z' h! A/ g8 m
{int number;6 [' q9 n: ?: P# b
int nextp;! M2 l, ]" U, l" A+ \/ e: n
}link[M+1];7 J) c8 T5 R0 U4 e

4 g/ V/ y2 j- H+ Rvoid main(): m7 Q. J) p# o( v0 v  Y
{int i,count,h;
1 z9 j6 W3 H3 ]for(i=1;i<=M;i++)
7 a( E, J- `( \' W+ P8 a{  if(i==M)
4 ~4 H; l, ?. o" c! K; d   link[i].nextp=1;+ @* j- ?6 y) |- K
   else
& v  `: G5 C3 Y7 I   link[i].nextp=i+1;
/ s  w, l: r2 I4 h  link[i].number=i;$ h! H2 c! l0 V7 `
}
6 j5 s4 R& C  v4 ^printf("\n");' }9 ?2 i+ B+ i' O! ]  }' M( U
count=0;5 k; e  v' l7 Y
h=M;0 g5 a8 \  A+ j$ _0 U2 O% m; Z
printf("依次退出的猴子: \n");
; M; O3 o5 S  L6 w! ewhile(count<M-1)
8 _$ w' I9 M8 \( q# p" U{i=0;
6 N+ i3 r: x8 P/ d" xwhile(i!=3)- m) e: e. w( R
{ h=link[h].nextp;
2 M# ]' o% f  }& a; a; J   if(link[h].number)8 B) |6 b$ I) M: w1 X. `
     i++;}
2 o6 s4 k  |+ F  T  b
3 t* j% x: q7 vprintf("%4d",link[h].number);
6 @; t: t7 ]4 P" ]' f5 [9 ]. Wlink[h].number=0;, I: A: V/ m3 W9 V
count++;
% R$ W6 b1 C7 a' f: a7 E9 U}& w, R8 ~+ ^. E0 e# X5 z/ {2 E1 I

6 f# G3 M; }$ }# k- |printf("\n大王是:");4 B9 n$ \. F; N4 e( [% ]
  for(i=1;i<=M;i++)
5 L; A9 r. D6 Q9 [- U% i  if(link[i].number)
5 u5 \' [  D" f1 T0 L. p- T    printf("%3d\n",link[i].number);
( r; [# [# o- S' w
4 w1 `# J# z4 J5 ]: W, i# r) V
) d3 h+ p) n0 G% W9 T) S& t}

. a8 ]- K! h4 O; k8 k5 Z第三种是普通方法for循环

6 v: M8 c3 n# p' q#include<stdio.h>* y0 @, z4 C( T  B  A  ~
void main()! V) N1 t  j. {5 w& p
{ int i,k,m,n,num[50],q,*p;
) {/ P. \* i! R2 N, O    clrscr();
$ ?/ F3 S* d3 N& I% x   printf("input number of person: n=");
) I! p5 H8 B' |% r1 F    scanf("%d",&n);
, r. z3 W0 o1 L7 Y$ S+ `printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
6 J, R% F  g; b1 T& o" W; g& q- p0 ?0 A    scanf("%d",&q);. m( z/ o5 u! P7 N# [
   p=num;
0 ?6 I8 z# m, H! m/ I' w+ p2 f( b  for(i=0;i<n;i++)
$ @8 N1 y4 d: T2 H' O+ b0 D    *(p+i)=i+1;
/ {$ ~- b% @2 j7 a# ^9 [: Y   i=0;
+ B9 [) f- ]$ m; y, w7 h% c2 E   k=0;
/ u" X7 F- a5 X* P( ^4 m   m=0;" \+ t  y& s9 o4 W& I7 A" F
  while(m<n-1); z; i2 ]/ S7 W6 j0 D9 ~
   {if(*(p+i)!=0) k++;$ H& F5 v8 V( \" }( Q
     if(k==q)
0 `, Z: E' m% f+ \1 }1 t/ e      { *(p+i)=0;
. N; Q2 R9 x/ h9 s* M, G. ?        k=0;" \7 [8 S( o1 h0 S) q. A
        m++;
7 a5 c. _' ?% F+ A6 z      }
. ~* `6 e* @# {) `& T/ y    i++;
# w, ~& ~5 n4 B5 h2 r0 f) @    if(i==n)i=0;
4 Z# q/ }5 Y4 r" V) `1 B   }/ J: ~$ X: S4 o4 O
  while(*p==0)p++;* n; L. e( N. @) @: Q: ~% I
    printf("The last one is NO:%d\n",*p);, T/ B. |0 O8 r" g
     getch();
3 c2 \0 K, h) |8 S' ]% X, I# L8 |- q
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
( |; I' b" i* a3 T7 }namespace 又费马达又费电
9 J/ R7 t( Z+ t; A9 |% I4 t{6 K% a, L! i& e0 c
    class Program7 O( K# b0 r3 W
    {
3 i0 G, n' q. A6 E        static void Main(string[] args)
: \/ H+ K" u( ]* A        {
$ {0 T) U' K& `# J3 o            int m, n;
7 ]' u, a9 G0 b( O            Console.WriteLine("请输入数组长度");
3 N# W& r5 h9 s4 r* L2 ?            m = int.Parse(Console.ReadLine());//m为数组的大小
7 Z% H5 ?9 Q6 C8 f) W& S            Console.WriteLine("请输入要截取数字的大小");, @5 b: ?* K  X: g- l( K+ f
            n = int.Parse(Console.ReadLine());
3 U4 s3 k4 C$ u7 M$ w+ {2 ~2 Z: x            int [] numw=new int' T! f6 o, U% Y
4 r1 o  T0 |  `& l0 t: a
&shy;&shy;&shy;;1 \; `% e1 H( X, |, k  B
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数: w1 y1 T$ r# C8 M
            {$ y' `/ n( `8 d% D# a
                numw[j - 1] = j;% E5 G- C2 N3 ]8 m& z6 f" ?9 W
            }7 j4 o7 O7 Y7 c+ @5 H
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
, c. T: B+ j. H9 |            while (d != m - 1)# s+ G& ]2 y. M, \" ^* i
            {) n/ Z$ I  x; r9 x5 T
                if (i == m && d != m - 1)' h& l( X& |- P& R3 ^
                {$ n% y0 @- Z; |: u# K% a
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
5 x& v- j7 @6 R" B6 K                    continue;
7 F; c. P8 x8 _, H1 K' H1 ~" a                }
/ S/ q% p7 R7 w9 v                else
' D) v$ k9 r  B3 ?                {0 O$ b" M; i- s/ i
                    if (numw[i] != 0)) t, k" O( ~# H) @( d3 N
                    {0 K9 L' d# ^6 V7 s) Z, `
                        i++;
# W. Y3 [6 p/ |$ s8 Z                        k++;4 t7 e* @3 d2 b% @" |
                        if (k == n)
6 V$ J, K8 S5 i7 H* n4 y! D, C                        {% {, ~% P9 p% a0 X1 i; o
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了1 b4 V. i* q; q& g  `
                            k = 0;
0 V' H: [  S* V$ Z8 `7 _              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
- m" v. N0 Y- T, a% e$ a- W7 [                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
; k# R, B4 `& f) ^1 S                        }
! j7 J, b0 b/ B7 H2 J                        else//输出暂时还没有改变数组元素的值
3 ]* X- ^8 V1 f, J0 a# G                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);& K6 w. Z% r% v. n) p( p# b# `
                    }
! P" X* K8 V+ S                    else4 l- q3 |( w8 l8 y
                        i++;//数组元素为0,直接跳过,不计数。。。. o; @; g8 |% k. }+ l/ k) E
                }8 G4 N9 f# {9 v6 S5 C" X: A* R* h
  z2 R; ~. V7 J1 M' D* u- j
0 q3 N# d) U' Y7 R4 C/ P
            }//结束while循环
0 S; x& X# y! o* r) I$ E            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
( r- o7 |9 w1 ^' t$ o1 ?) N% q8 K           
8 _8 v" X' {/ L                if (numw[i] != 0)) @. N  @) F" V" y+ b' ?
                    Console.WriteLine(numw[i]);4 w8 \6 E( ~  r; A( |6 R; R
           % {; o1 P* x7 s5 h
            Console.ReadLine();" K. ~/ ~8 V# R& m6 t8 d
        }1 f. r# Z7 F0 ~  N1 j- s0 @
    }; x/ t: o$ b/ `" j
}7 v3 k+ l5 {5 m
小甲鱼最新课程 -> 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-3-15 04:13

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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