鱼C论坛

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

猴子问题

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

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

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

x
大家好!6 ^) e5 k, V: m
这几天我在忙着编一个问题,我用了一种方法编出来!
4 {% a8 R$ C! y' [但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
. s; u3 }4 Z, Y/ T5 b1 g0 N* ^- c5 n注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 8 W9 C1 K1 D' ?! g" @  L
# @! U! s( C, x: t$ _

7 W, S/ J2 P5 z' w' r# R" ~
                            题目. b+ _" d6 P# M6 J
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
& M& g! ~7 v1 K第一种方法:利用循环链表$ |- ?1 ]: P  M1 o; i
#include<stdio.h>1 g7 w& Y/ }* M9 d4 Y- g
#include<malloc.h>
' R9 w5 F7 H) f( T. W, O#define M 8            //共有8只猴子* o. {% o# f6 h$ Y
#define N 3            //数到3只时退出第三只+ c& e; @1 w9 k) a- D1 ^3 x! p
typedef struct monkey
9 c  y& U# |+ B. T3 k! n{int number;, r  n8 ]( _/ m3 g/ v7 \
int flag;
5 A& c4 w  I/ ]7 a! z7 [! i0 R# Qstruct monkey* next;# J' G' G) t6 o/ a( f
}MONKEY;. l9 L7 o/ O: x
main()
, X; Y; C' |! s( a  Z# N0 z{ MONKEY *head=NULL,*p,*s;
0 b' a* N5 @; ^  int i,sum=0,count=0;9 g( U6 `- T9 G' U6 q/ l7 X* L0 d
  clrscr();              //清屏. Q2 A. A6 h' _5 j. i% T
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存+ ?: `1 F& }5 l0 G
  p->number=1;p->flag=1;
3 o: X; n. Y" Z9 `6 [0 O( i: {  p->next=head;. i+ k8 ], C9 z$ v
  head=p;
* C1 p1 q( k! X1 d* e0 g. y  for(i=2;i<=M;i++)1 M$ [7 ?  n6 O6 S. ?7 n. H: E1 H
    { s=(MONKEY *)malloc(sizeof(MONKEY));
% t  V. I. ?; I# C, b     s->number=i;s->flag=1;
/ }0 l2 r3 g. ?  S     s->next=head;
3 B- ]! |# D5 f     p->next=s;p=p->next;/ I. [, l" J5 j. H! j# o, B* ^8 _
    }: O4 f3 J$ U; z" s
    p=head;
$ w" ~% Q7 v# r/ g   for(;;)( N! C" w% N2 f6 W
    {if(p->flag==1)
1 ]5 P8 s2 j2 |1 O& V( f       count++;
5 S+ a2 u! h- }  W9 k6 r% L     if(count==N)) ?2 i# c( ^- _- d# u- ~
        {p->flag=0;
; J5 _+ Y2 I( _- \. n         count=0;
& W# j2 f* U$ p3 O' s2 d% r         sum++;}) L* C! ^( H1 l9 u
     if(sum==M-1)
& r* [, r* |; m/ o6 D5 R) n0 g        break;
# q& b7 n" }# `* y# _6 W. o' F     p=p->next;5 D( @  l" j3 [% }5 e+ N
    }! q2 d( }4 G; {
    p=
" E! p3 n7 g) J/ q% E    head;
( o& h& D3 Y: K6 o8 o- Q3 `- C    for(i=1;i<=M;i++)0 \2 H& Z4 d( y& W- a& H
    { if(p->flag==1)+ W3 [5 g- x& ?% @
        printf("\t%d",p->number);+ T4 H/ t; ]2 ^! a
      p=p->next;
1 X) L1 b3 A2 w+ }    }) Z9 P1 J( |# W: _* e/ O, y
6 `2 N3 ?" ~9 M& e  ]

  d! r8 A$ p9 H8 h) [9 {# J& T1 `, y( t3 r0 Z
}
) e8 P0 H2 V  \
第二种方法:数组( a2 r5 A; u# g) u# }( _2 t: f5 n
#include<stdio.h>
5 U5 f$ A2 u7 [9 E#define M 88 G* k" m4 w( P. O( _9 u
struct monkey9 a: ?7 e" B/ ?; }& I
{int number;
9 F# C% H% j+ ~int nextp;+ P/ Z' u+ ~7 I0 C: y& Q
}link[M+1];4 Q7 O$ M% Y" v- O: b8 t2 L

2 O' `. {3 c; ?3 F' Cvoid main()
1 M# L  E: v8 F{int i,count,h;
4 q0 V$ \  K( R/ v2 y/ Cfor(i=1;i<=M;i++)8 S3 l6 l7 Y# O1 L: F, }
{  if(i==M)
& W0 o( u. `7 |   link[i].nextp=1;# Z4 H% ]5 J7 e
   else4 l' w" w# {& k9 U  r* n0 b
   link[i].nextp=i+1;
6 z4 o! x3 A! f# ^3 M  link[i].number=i;' X* v$ p2 k( r' l, B
}
( _; `* q- F5 g- V2 \/ ]printf("\n");
* y9 R/ R/ T. c6 Qcount=0;
6 x. x, C( n$ `" D/ Ah=M;! F1 l8 `$ e9 ]
printf("依次退出的猴子: \n");
0 Q8 g8 A6 g2 I2 F4 |" y9 x: O* a! o, @while(count<M-1)
" t2 `* z5 t" J8 D8 b( Q3 a{i=0;" s: e8 R2 n; e& p3 H0 ?( s% j
while(i!=3)
: S$ C( g( Q% H% b! _+ D# `2 H4 W{ h=link[h].nextp;4 ?- y4 I! W: l8 _! x- G
   if(link[h].number)" D6 P2 @3 F1 g# r8 L; O
     i++;}
7 @: A" w& E) b  T- y# o5 r
# j" ?0 E1 ^6 f) a: c& {' q7 @, R: n0 a# Dprintf("%4d",link[h].number);$ r* F( J1 N* t( @  H, g' G7 g
link[h].number=0;' R6 e) I) o3 n2 N7 d
count++;7 Y, ?( ?; R/ R3 U! t3 J
}
1 W6 t3 D, N( p9 p/ a3 ?) ^$ q/ r
printf("\n大王是:");
0 S6 n1 m, Z! b5 l: v. ^  for(i=1;i<=M;i++)
* u$ S( i; x0 H& m) l, w  if(link[i].number)% M# ]2 D& A" c( m+ a" n
    printf("%3d\n",link[i].number);
5 T/ \  G( w$ L
+ B- n0 N6 t, b6 o& T1 F9 n' W# n4 m7 K4 d
}

2 b$ V6 y* @/ `9 r8 f& ?第三种是普通方法for循环

; L9 {9 p' B* A8 P! B* J. W$ T#include<stdio.h>
, ^; K' O- z8 b$ l7 l' vvoid main()- E1 l- W$ {: k7 A
{ int i,k,m,n,num[50],q,*p;
1 @& q* U7 R, U& _3 w8 t% I' O0 D0 a# }    clrscr();
. ~# L! O$ |) j; e% T3 X   printf("input number of person: n=");
7 v5 ~, f5 _- ^    scanf("%d",&n);
/ h* M( a. n* yprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只7 \6 g( r  j. o3 ^) {
    scanf("%d",&q);* F" b; U- f3 k
   p=num;8 {9 T4 q; Z; Y/ r. g/ z9 F. k
  for(i=0;i<n;i++)
( A( v; x) w1 J" W: j9 ]    *(p+i)=i+1;
& R. j4 k5 l1 z. ?6 t, q   i=0;% V; D6 z; g7 z6 k: d1 V
   k=0;  T/ Q" R3 w5 c
   m=0;0 E9 F/ `1 J! }6 O7 V' l
  while(m<n-1)6 h/ O2 N' V5 \
   {if(*(p+i)!=0) k++;
, M/ m4 H- g( @& U% Y     if(k==q)  X: U, _8 x3 |) M& A
      { *(p+i)=0;6 x5 S  m( \9 S$ h
        k=0;; x+ u9 R1 \. H' k) o5 f/ I
        m++;
7 F" x9 t' v7 X      }  h* g2 N. E8 A6 E0 B% G
    i++;
6 C1 K! ?1 a9 h    if(i==n)i=0;7 Y- {( v! E, r& l: O
   }4 B, }4 j# M% d$ x7 ]6 g2 \5 I
  while(*p==0)p++;8 d: q! O0 e3 {
    printf("The last one is NO:%d\n",*p);* e1 K3 l9 Y5 Y2 {) u
     getch();
, U2 |: {! P: E' @0 i8 _- h
# ^& k7 j( V9 I5 Q% Z}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
( W5 ~1 }0 W% c( q/ h- |namespace 又费马达又费电3 U$ p0 r4 Z2 L5 J) a
{' ^) X5 r& u$ Q" Y; Q7 i, N
    class Program
8 A0 Y0 t8 r6 o+ l. x    {$ S* W: d; e2 e( q, }( w
        static void Main(string[] args)( \9 d4 E& s0 D, T) R- m  q: |4 F
        {
# T- n! ]2 U7 V( n6 @' `7 ?            int m, n;
& w" \9 Y: d: d& _            Console.WriteLine("请输入数组长度");% s, n% n/ d, H' s2 H' U
            m = int.Parse(Console.ReadLine());//m为数组的大小
; m1 K+ {# S7 ~            Console.WriteLine("请输入要截取数字的大小");
8 F- `  l7 F* U' K. ~3 c! e            n = int.Parse(Console.ReadLine());
, U: S8 c0 r0 p, u- _            int [] numw=new int
7 A# t' v; o0 D$ \% d3 o
$ _; ?2 K) B9 }& A- V4 x&shy;&shy;&shy;;
/ u  p- G& I+ |            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数6 Q* D5 Q' g4 q. U0 [* c
            {
2 u; A6 @; {) ?                numw[j - 1] = j;$ `  `- w. c. `' f
            }. r* z; {) g: h/ |& I. M0 M) O
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
( [* G  n8 z8 T% G- e/ h% z, ^% g            while (d != m - 1)
+ ~# a7 g; K! M$ v0 [            {
" p" G' w& Y2 z- C. y8 p, I5 K                if (i == m && d != m - 1)/ u$ G+ S  c- g& F
                {7 R5 _- n' {& I3 l% K2 q$ M
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!8 D; h! n  P0 l, E  I( w# Q
                    continue;* Q" a0 j8 q# C: y& a
                }
7 x/ K4 X0 E6 U% Q+ g                else- A# R* D# k  n. L1 ?
                {" I) n5 l8 r6 S9 H; ^
                    if (numw[i] != 0)
1 T+ \% x. v" e, P& f" A                    {
4 W% U4 U  i9 B' T0 y2 b/ ^4 k                        i++;
* P3 j  E3 P) c% B' k8 H                        k++;
6 Z5 k& S: s4 _; [# r3 a. d2 h                        if (k == n)
2 W3 p- P+ `% m, j7 j                        {
5 c3 Z; |+ U' u& x  l% e. W                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
! A# [1 _6 C! x0 \  B. m/ Z" [                            k = 0;% T9 s0 X5 ~* l0 u" A8 p
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1) B- w6 w, U3 z$ A2 m% b
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
& |8 l. E" B  x* s                        }
* z7 i5 K% X' \6 }. t# w& ~                        else//输出暂时还没有改变数组元素的值
/ F) p% R: q- z) k* q, n                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 u  D& J! J0 V0 |                    }& P8 O6 p7 d  Y. M
                    else% ]: v! p7 H$ o1 d
                        i++;//数组元素为0,直接跳过,不计数。。。! P& G" L/ y1 Q- X/ s# c: ?  A
                }9 E* G9 a) F0 _; d2 N
% N* p8 o8 c. a7 s+ H" C6 u' |

+ D' N6 {2 t7 T/ q  W            }//结束while循环
' N* L, r5 p3 L8 n. L            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
1 ?+ z9 t2 \& _. \! s/ O           
/ ^% N! r7 k$ c7 _9 X& ^                if (numw[i] != 0)
; I& c' y) f# v6 Z( f' O/ k                    Console.WriteLine(numw[i]);
# U' V6 l8 h# I2 |% S+ R, b7 {$ L           
6 i7 P$ H+ \$ I            Console.ReadLine();
6 _- v" \1 U% B        }
% a) V8 a* M, K7 J    }
: q) ]2 D$ n" t" G2 x# v}
1 p- h- w/ x- i6 ?1 N1 `7 A
小甲鱼最新课程 -> 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-2-10 12:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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