鱼C论坛

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

猴子问题

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

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

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

x
大家好!
6 v1 A7 \, E4 L( t# a这几天我在忙着编一个问题,我用了一种方法编出来!' e/ G# H6 t4 C% i% H2 }) u3 ~
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, X; D6 N9 o  o. u+ N, V
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
( i" B; Z6 c+ c
# B9 b/ C7 u1 q$ M/ t
! Z. F& O: F( c+ G6 \7 I
                            题目5 z: y% J( ^4 S7 I& n1 Y
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
; b+ k% M: p" @第一种方法:利用循环链表/ A4 M7 c) Q7 w; J9 h" G  J
#include<stdio.h>) ~' g# C' W" Y
#include<malloc.h>
( _4 w6 \! k7 c7 e, |7 a9 V% N#define M 8            //共有8只猴子
4 P" U0 k) F9 t! C, D#define N 3            //数到3只时退出第三只
- \; Q. |$ G' Q) \typedef struct monkey
7 `9 m* X- e1 O, T{int number;7 e( V6 B2 m2 `1 P8 H* X* A
int flag;
7 [6 A2 s' U& P+ g$ P' Sstruct monkey* next;/ |4 c' S# Q' o3 S5 X$ b. D- U
}MONKEY;2 I. g% _( ?) k6 s! n# e. ^
main()6 q% ?$ H/ B9 q+ }& r* c: l
{ MONKEY *head=NULL,*p,*s;
; {3 g+ z8 Q+ Z; Q# J5 D  int i,sum=0,count=0;
& G1 q, z  N0 \9 e, k/ z# P; \* O  clrscr();              //清屏2 u: f' s3 |2 [  n4 `  ?
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存+ q# s9 R3 m4 y9 Q/ d- m  y
  p->number=1;p->flag=1;
7 K6 @/ K1 }7 v8 @! y1 S  p->next=head;
5 O9 W6 H. c/ G( k7 O: [8 }4 p. ^* Y8 z  head=p;+ T2 V3 S6 N1 b/ ?& n, C5 d* G
  for(i=2;i<=M;i++)
! n1 k! o$ W2 i, k. P    { s=(MONKEY *)malloc(sizeof(MONKEY));! Z5 L3 A7 x- }% @) Y; a
     s->number=i;s->flag=1;
+ V, e) p7 a0 j/ M5 A     s->next=head;
* Y) ~" d% O0 c9 R     p->next=s;p=p->next;
) Q% u, ~2 c' j2 v( @+ c8 w0 n    }
) o# Y: s/ P$ v4 K4 D    p=head;5 I5 c0 p7 N5 ~, }: Z, P
   for(;;)
4 g  R' Y; ]/ e& n, M; \# i9 J    {if(p->flag==1)- ^. Z! @( X8 R: K" f
       count++;$ D* R, c7 x# i# |: I! \
     if(count==N)
5 z: H3 `0 K# h% E% J5 x. e6 O        {p->flag=0;
4 w0 v7 o8 ^- f* i; D         count=0;
$ W: G/ {4 f& ?- Z0 H, a2 F         sum++;}3 U% r+ L4 V" l# ^! K* c$ K5 K( k: [
     if(sum==M-1)3 c% q4 s$ f: ^; n5 t4 {
        break;4 s1 Q$ ]$ U2 ?2 i9 t- s; ?' W
     p=p->next;6 Y9 z; `: v% N* Z, u; T. _
    }$ I) s2 }0 o# ]8 E% O
    p=" d2 _2 w  d, ]* i) w3 _" V
    head;" _* U# Q! F5 [) \) e
    for(i=1;i<=M;i++)
+ j! |4 T- O3 W* ]/ d& Y    { if(p->flag==1)/ P. ~- k- k. l8 X: y  Y5 V
        printf("\t%d",p->number);9 X$ N! ~( t  I+ d4 ~! r
      p=p->next;
3 x( {) q( s# q7 a4 Y    }# j) Q; ]! f, t4 O  z
4 r, X( W7 [5 Y' `0 H( z
$ D. y: r$ `" a+ u7 ?! h( e
$ H! U+ a  }, W
}

$ k* Z# B4 A- m& I, R第二种方法:数组) R5 A( a. b9 S; X& N
#include<stdio.h>
3 b) t' z! e' H#define M 8
& `8 K+ Q- s: w4 a$ w3 Gstruct monkey: U+ i) ^$ s+ [6 ^* b
{int number;
& {! L* }# }" I- M: E6 y* I. `0 hint nextp;5 t/ B8 J, x8 s2 ?5 i
}link[M+1];3 p) z2 i. p8 [" I; {2 n5 P
5 w; r# n' [2 a8 O: x& q; s- E
void main()
6 B$ q) q+ ?6 U5 f. ~$ h{int i,count,h;
0 z; b8 v+ j; _+ ifor(i=1;i<=M;i++)
* f  F8 K5 M& a/ u( \; h  y{  if(i==M): l$ H' k5 l* W9 x/ [" |
   link[i].nextp=1;, S! s# z+ Q, H" b( Z- i1 R5 e/ e
   else: G) P" c8 ?* E* g# a  C
   link[i].nextp=i+1;; F/ o0 [0 [0 O/ Q
  link[i].number=i;
& u, u3 s. q- H) Z}
9 K# z2 X1 Q- R% C# r3 {printf("\n");$ p3 f& Q; Q& m  N  l- h
count=0;
# ^+ F8 G: T! N% e9 N& kh=M;" x* ]/ E) t) g/ F6 r" K
printf("依次退出的猴子: \n");/ F" i2 J- F2 {) U: Y5 V0 e! ^
while(count<M-1)
# f3 H# n0 @2 }( i1 _% N4 n{i=0;
1 |/ |1 ?, h3 P$ [while(i!=3)
& a# ]& M% n" j  h- x) t{ h=link[h].nextp;8 L1 H* d6 `! R: f- `1 z; V( d5 ?
   if(link[h].number)' E  P7 r7 i4 u  q5 q- I
     i++;}
6 x# E" e2 x! l6 {9 D
1 _$ w9 R1 H; n6 Iprintf("%4d",link[h].number);7 X0 {9 V( ^* I4 Y
link[h].number=0;* v) E& C; M* f& S
count++;; O- \& j7 S# {2 u5 f9 e3 J
}$ g4 P2 Y7 E7 K9 ^7 B1 Q7 ]6 A( ?: K) u

4 E5 M3 b% B; P/ r* Xprintf("\n大王是:");1 a, K/ a' w# K. c
  for(i=1;i<=M;i++)1 X: R- ]7 u' P. T, Y. T
  if(link[i].number)
' w3 w0 x7 U6 ?; g/ s$ x    printf("%3d\n",link[i].number);
+ y$ J7 ]# }$ O) ^$ ^! X5 `
1 z! Y  x& w, A0 ]) [1 \2 X/ _+ m  D; @# R  q- e; ~7 E
}

, a5 I. i, U+ H( b3 O; c第三种是普通方法for循环
" ~9 @$ h% Z, K* }
#include<stdio.h>+ l. d8 g) ^7 E9 a- i
void main()
4 O( v$ a, l9 i{ int i,k,m,n,num[50],q,*p;. Y: K0 G/ s& _0 F+ r+ S2 u0 Q
    clrscr();
1 c. W3 {" ]5 k3 u   printf("input number of person: n=");9 s. e4 j4 [5 e) y. M6 B! l
    scanf("%d",&n);
! C. E: x6 q; s3 c8 Sprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
- ]3 s$ F' u* v! Z; ^2 e    scanf("%d",&q);
% Q  k# H! h$ n( m2 S7 w* c   p=num;1 l9 u0 Y, O0 j2 u$ i" _
  for(i=0;i<n;i++)* p& O, X8 f/ @+ S, M' T
    *(p+i)=i+1;
7 S) B! |4 N0 k6 J: @   i=0;, ~, w- d% B" @. T
   k=0;/ G; ]4 y" m! M; F
   m=0;
6 b# x" A7 y. S. t5 W4 D  while(m<n-1)
& z. P# s" S* \1 e1 V9 d# D& I7 D& [   {if(*(p+i)!=0) k++;) ~, ]5 a6 A7 `- M* `
     if(k==q)" F* M- S" z8 A9 A5 i
      { *(p+i)=0;- r3 ]1 P6 x1 I8 ?3 `
        k=0;0 R6 [5 d6 g$ n4 `2 d
        m++;
5 p! a! V: W- V; N& ~  f, i* Z      }4 M( Z% Y; g5 Z6 \
    i++;
, \- n, U! f$ P4 J' }  H& e+ ?+ a2 H    if(i==n)i=0;
6 t4 V; z4 P& @! i   }: E1 I0 q( q2 L, [& o( c
  while(*p==0)p++;, F2 w; e& Z8 o4 O
    printf("The last one is NO:%d\n",*p);
& V$ b$ S2 A5 |$ [     getch();0 j2 B' \  r4 o( ~& V  F

, K2 V+ s, P. a, Z% F  @; M}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;0 p3 r' N+ t6 y# `4 x- g9 |
namespace 又费马达又费电
+ ?7 }, l! \; c: `4 n- t# f2 T$ M{
6 O5 f8 N& t0 _/ C    class Program& S& Z) S) ~9 \4 C7 R! ~0 ?
    {
. B$ F( o" W# I9 |3 k3 p        static void Main(string[] args)
; J. ?5 n- X* y$ o" H- d( ?        {7 ?) ~' w3 y; _0 u5 j1 l1 ~
            int m, n;
4 K9 s9 C* D) A1 L& k/ r# |            Console.WriteLine("请输入数组长度");
2 n" R* B/ o6 f  B4 a: |            m = int.Parse(Console.ReadLine());//m为数组的大小
6 H* c# P3 t' p0 K' j            Console.WriteLine("请输入要截取数字的大小");
& Q; K3 K) U7 C9 O9 d            n = int.Parse(Console.ReadLine());
5 u1 r; [9 W: r+ Y, V3 \. S            int [] numw=new int
4 V* o( W, c6 Z/ t1 i- Y
9 R' ^2 N: r& L5 w! a/ B&shy;&shy;&shy;;
! X' H- A' }# S" K: m  F" o            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数/ J4 O4 T/ f, {" b% p& p
            {
0 U( g' O4 d' ^, B                numw[j - 1] = j;
4 I( U) G7 D- z0 T# {: Q            }2 ~5 a* b3 T1 T# v/ B& |
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
& Z% w# J4 ^1 S# b; Y8 \1 z9 O            while (d != m - 1)
4 h; h$ S- X- n- \            {
8 r* O0 q, z3 L  k5 X                if (i == m && d != m - 1)
6 [  d. v8 k! G3 N  p1 R                {  M# A" B! z% @- q0 e! }
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!- S  o, T* B$ P. A9 [0 M; \9 p
                    continue;
$ Y' k  R: O) g! g                }- Y& U( r; C, c! P/ h( s
                else
, @$ X4 C% l- r                {# {4 I- |# ^7 j9 x5 V, l4 l5 D
                    if (numw[i] != 0)/ k& ?* n- i9 C
                    {
4 ^" P  @3 u# L0 U                        i++;0 {% K( P/ h" t) L
                        k++;2 Z% G8 U! h7 q# t0 y7 z* b
                        if (k == n)3 r# V( a# Q2 _3 ?0 |
                        {- c% _5 x! B6 \+ F* O0 h
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了: D4 J! e6 p# h" }- K
                            k = 0;
3 o! y' p$ T: O8 X              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
9 i! ~9 d* ]+ r9 q) r                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
$ J9 f2 t7 i4 g' a7 }. r5 s                        }4 X- y6 J, A4 L$ w$ h/ D1 Y
                        else//输出暂时还没有改变数组元素的值/ V' j0 H& m# q- g3 D; J% {) x
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);$ k5 i- u3 l7 q4 Z
                    }
, u4 C6 J* X( y! `3 _. n0 Z                    else. b; j1 U; J* ^) `2 f6 p  {
                        i++;//数组元素为0,直接跳过,不计数。。。$ z2 h: m" s9 u# M
                }
+ i5 X, ?5 y5 o- |
, N: a5 K3 {! n+ [/ P! f* K, m7 ~3 H/ J! W% l
            }//结束while循环, R0 G, i' i. k4 U: R, j! ?
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
$ ?, _+ C- X: T! ], y, T           3 f5 j1 x( f7 `4 v4 ?4 b
                if (numw[i] != 0)
* a7 c; q0 C: w/ U                    Console.WriteLine(numw[i]);
! @+ w  n, L& U- A           : U; B8 T  i& U, d7 i1 |6 u
            Console.ReadLine();% o# s. R5 D4 P/ x9 X9 L2 a) H: F
        }' t& w  x4 t; w
    }8 X% X% Z1 }- x. R9 Z
}# ~8 K8 H5 z8 ]7 _4 h1 C
小甲鱼最新课程 -> 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-8 07:32

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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