鱼C论坛

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

猴子问题

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

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

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

x
大家好!
8 A+ P! w# x4 F8 q这几天我在忙着编一个问题,我用了一种方法编出来!3 Q8 ]1 D8 M5 n
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
  K9 E# v( L& Y/ s& \4 I' o& |- k注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 1 k5 ~) e, P5 g

' \/ U  K+ m9 w  l, F0 P. b& {
$ p6 ]( j  ?% R- J/ }* e; R% o
                            题目
9 i9 s6 y3 s/ x$ _5 \& v, i5 N山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。0 [, C: E1 G+ I% b4 e8 M
第一种方法:利用循环链表( M# F! S0 e  l& R/ N  e
#include<stdio.h>
7 w5 E: }! S$ P2 P  O5 z' K4 i/ {#include<malloc.h>/ `9 _1 \. G! Y; P# F6 h  m
#define M 8            //共有8只猴子; W6 [& p; u0 w; U* N
#define N 3            //数到3只时退出第三只
3 x) r0 F0 M. b5 ^1 ftypedef struct monkey
% ?5 J0 ^, @2 [; f. S4 p  }{int number;8 C# \* z5 O  r4 v& ?& R
int flag;
: R7 d: ?' `+ ?) H, \struct monkey* next;' p$ ~/ O0 W5 h+ ^. {# D+ a
}MONKEY;7 G8 n. F. H# E: u0 Q  R
main()( f, f, P+ o* S- ^: J
{ MONKEY *head=NULL,*p,*s;
- x9 l# S: P9 D: b$ M' p! z" y; _  int i,sum=0,count=0;, L+ y% l0 l5 ?
  clrscr();              //清屏
/ y0 i# c. H% \+ Y9 Y  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存/ i. f' F7 M# A! e) ^9 k. {0 f
  p->number=1;p->flag=1;
7 i+ g1 p5 i0 }& `  p->next=head;
$ Q* ~$ U; H. V" f  head=p;/ j$ V! v* T5 H  s8 }" W- H- ^/ B4 Q
  for(i=2;i<=M;i++)
" v) q4 F* u' Z2 k    { s=(MONKEY *)malloc(sizeof(MONKEY));% ]: L/ z; P3 Z6 s% f
     s->number=i;s->flag=1;
: S( P  U4 R2 u     s->next=head;
* D3 g: c7 `* s) a( I3 b& L  Q* Y, k     p->next=s;p=p->next;+ v& x: i  o+ e+ A" C
    }
- H- u) T! X/ m+ p9 `3 J* q: L    p=head;
% X3 ~, j, t9 k, U* q   for(;;)! t/ k' C. v: d, b5 q* P
    {if(p->flag==1)
& e% f; R  M% x3 l       count++;1 h/ T: i) I  d6 A) G8 x
     if(count==N)
, [6 V5 e3 f7 u3 U        {p->flag=0;
, n1 b3 ?7 j3 v. }/ F6 e. D         count=0;" {) f5 K1 M$ |, `8 ?. W; E& X
         sum++;}6 O. W, f% f4 n
     if(sum==M-1): V4 Z* z  F: m8 a
        break;
/ ^! X  D* D8 S     p=p->next;! h5 d' h: G( m
    }1 A. ?7 w- Y3 i7 g( p3 C6 |8 ]
    p=3 N! C1 D0 }- R
    head;% {* g. ?: L" I6 c% l
    for(i=1;i<=M;i++)
3 J" J/ ~0 ?$ a7 S/ Z    { if(p->flag==1)
0 f1 z; d9 H/ h! M/ P        printf("\t%d",p->number);
+ N" n; T4 k2 `  ^      p=p->next;
5 E4 m9 O0 o0 U# h+ u3 z2 E    }/ r  Y, Y# H9 d4 ?6 X2 `: M9 o3 L
1 H) c$ L) c' p1 I% R% U  d
) D  o1 d7 S" r$ P- q1 i+ P- ~+ {

/ Z$ M( ]$ I# H) Q) W( G}
, S1 _) T1 `; y& E% Y( m
第二种方法:数组
+ [$ |/ X% X6 j2 P* n- b#include<stdio.h>
% W2 `! h0 s4 F* m5 |4 \) A& G* ]#define M 8
6 R3 A' _$ B5 q4 q% o! Gstruct monkey
1 v( T( a0 J! ~: N5 j& }9 {6 t7 n{int number;
( r' C6 @/ ~1 Rint nextp;- x0 t9 D( T2 L7 @7 L
}link[M+1];
% Y8 k7 ]: r  y* M' O4 l8 G1 r/ ~1 X9 A0 b
void main()
" x4 h. i5 H/ M{int i,count,h;* G* g) z  `% e% N: R: U+ s
for(i=1;i<=M;i++)
/ t' j% H* I. V. I) X; Z# L{  if(i==M)
  V2 I3 I7 E0 {9 w% m+ r   link[i].nextp=1;
0 c' M* ?, ]4 q# B& u   else
. d  X: y' |3 p2 U   link[i].nextp=i+1;! E4 D* L( q( F0 T- A/ E( y
  link[i].number=i;
: \8 p/ b0 @) [; G}
, [  i7 t  }, z9 S$ l' o3 O( Uprintf("\n");
& Q( y! C8 b$ F# }# p0 B  \5 kcount=0;
, j/ F% J, W9 b" J. p) ih=M;
" n- L8 c, M7 W/ oprintf("依次退出的猴子: \n");
( E5 u, f1 R8 V7 Iwhile(count<M-1)" [$ D% O' r/ c1 l2 O4 p
{i=0;5 s, Z( L0 Y2 g  m2 T+ S: \
while(i!=3)" J6 i* K, B$ a2 h$ F
{ h=link[h].nextp;  a- i7 D  z: v4 P5 y
   if(link[h].number)+ h2 {6 |( d& Y# q% u/ _7 R
     i++;}' _6 @- R; Q2 N% q- O( e4 `. k
- B% E# v- E2 |
printf("%4d",link[h].number);0 H9 X2 X' o% v
link[h].number=0;
8 \- y) m$ L& {# m! X: Y; ocount++;
, z8 b% P% b! h! e& q- m$ g}
' B6 M( C  Z3 I7 j" L
) ~8 G' `) G+ A" n. gprintf("\n大王是:");* G9 ~3 m" C: I$ N3 U7 E6 a
  for(i=1;i<=M;i++)
6 s2 V; Z9 W- Q  if(link[i].number)* t8 B. o5 W5 ]9 ?( F' o8 s
    printf("%3d\n",link[i].number);1 n* @7 v8 I3 f  ?8 A+ D2 y
4 r% m8 w+ A( `6 U4 |/ `. r

* i$ }$ z  d. g* v: c' X}
2 T$ t: ]1 ^2 I) }# {- A
第三种是普通方法for循环

/ L) o6 R; e3 [, l#include<stdio.h>
& V4 Y: c+ J$ {" jvoid main()
; {( S* X* y0 V- `, O{ int i,k,m,n,num[50],q,*p;
1 T1 Z  O" {% ~- ]) `7 ^    clrscr();
+ P& P7 v$ M0 r* G2 Y+ Z7 o   printf("input number of person: n=");
( }' Y, r0 p# o6 L$ j! I- i/ O    scanf("%d",&n);
: n- [: O. a. z, \, ?+ Yprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只; W& _; [5 J& ]& Y; J; v
    scanf("%d",&q);
- C; h) }" d5 J. A( f5 y   p=num;* [) M; o# r8 c6 Z# Z
  for(i=0;i<n;i++), K, n6 d2 k1 }' E6 C+ a
    *(p+i)=i+1;& u2 g+ j" ~4 t) ]
   i=0;5 s& S3 y2 [: H1 D5 g
   k=0;
- a2 e; Q- O1 O5 V   m=0;
" O8 H- R. `5 T6 d5 R) B  while(m<n-1)
. X' p& h* |$ \: o% ?4 X   {if(*(p+i)!=0) k++;1 S5 \) `5 H3 W5 C$ @5 J  x/ S
     if(k==q)5 e; J  M+ A3 l) h2 C
      { *(p+i)=0;
4 t5 |" j- b8 _+ U( f/ Z        k=0;9 V" B% F. U$ L5 ~
        m++;9 ^7 C+ R' F4 r8 [8 m. c1 h% {
      }, [; l1 r6 Y  t" F( r
    i++;
# O0 J, \: x( `) x    if(i==n)i=0;
; U5 j( n% k- ?" ]7 Z0 o6 ~   }
4 O6 F' B1 `3 q/ h: n7 F# T( V  while(*p==0)p++;9 B. H: h. d: P3 }6 E
    printf("The last one is NO:%d\n",*p);, K6 l$ t, U$ f" E: i
     getch();4 \6 `5 S! @5 p. K' ^6 m

  w4 m/ Q" \1 {4 {}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;0 a! e7 Z' Y$ B1 b
namespace 又费马达又费电$ F, E- O8 B, u( u
{7 K5 C/ k$ S$ f, i
    class Program: L* r, J0 @8 A  L2 T6 a; s
    {
9 r$ N; D4 ^9 a2 G5 }) I3 \% ^        static void Main(string[] args)
' d3 r1 w7 [& p4 {, F        {+ w2 l' Q' Z( ?7 L1 u5 g2 e; ^6 l* k
            int m, n;7 b* w# b7 v/ I3 Z
            Console.WriteLine("请输入数组长度");
: H! i% ~( I' Q- A8 q            m = int.Parse(Console.ReadLine());//m为数组的大小+ F' z3 I4 R6 l2 D& q+ ?8 g
            Console.WriteLine("请输入要截取数字的大小");3 y4 K/ P% h  \% Q
            n = int.Parse(Console.ReadLine());& Z4 a. i4 T: [6 a4 L/ K# m
            int [] numw=new int
# d7 R8 X7 _& C+ o6 Z; p9 s# f! W- q" S% d  f" l
&shy;&shy;&shy;;
0 z2 @( ~' A: w- A: V7 Q: D            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
( A2 Z, a  K/ y            {. o7 b3 N" M6 l9 P& ^) x
                numw[j - 1] = j;0 y& C+ U2 s: C$ o
            }& w5 L3 B0 U7 f% t! S  R, N1 }
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!) P$ F- k- L8 _0 W% c& c
            while (d != m - 1), X4 J+ U9 r* j# W
            {
1 F9 V9 y6 U: a) L# u* n  M                if (i == m && d != m - 1)
( O2 U6 q1 }$ j9 R$ v6 I. [3 K                {
1 U( Y" p( k, Y! L6 z                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!! W3 Y) K# O3 b0 U% N
                    continue;
: R7 S: F# C; ^! m, ]+ Q                }
2 ~- B+ R; S* o! A( z& [                else
! x  F: K1 m9 D% W) }" j6 I$ Q                {
# c5 a+ J. p; E/ h9 W                    if (numw[i] != 0)0 \8 g6 ~$ P" M% d3 P
                    {
5 x) q* w- X% L  U% q& _                        i++;
3 [, }+ c$ b! T- P4 _; U# u7 A9 |                        k++;# K$ L$ a. O( Y- H
                        if (k == n)
8 I* Q, Q2 P( Z. [                        {1 _1 v  l) [* t3 b8 }# i
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
2 X: h) _. F) z0 f8 O1 e$ [                            k = 0;& V) A9 s) y' {" q! S- B. D
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
: t/ }5 P$ |2 w                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
: s- ^0 h! r1 b) U                        }& b# G5 B  A) l( a8 Y2 n
                        else//输出暂时还没有改变数组元素的值
2 M6 P: H* x5 m, ~                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
* w5 P# Y% H6 x/ {                    }5 X/ l1 U" a0 D9 {) V4 L* y- u
                    else6 n' ~' o4 o2 `$ r* ]" d& b
                        i++;//数组元素为0,直接跳过,不计数。。。. [! i- N* F: x; C- r# s# k6 {
                }: |  T) Y- t. d. L
3 {8 N! U( O2 a+ m5 f8 g
+ k) H0 F1 h& c9 F- M$ P% Y- U
            }//结束while循环
" A$ p' ?2 _/ |; k0 {9 a) i            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
3 D. H+ V% z' ~7 v2 f3 `& y* C0 Y9 W+ f6 t           
' Z# T4 {! o" a4 |* {* ~5 q                if (numw[i] != 0)
& [( t7 B) N* p' F                    Console.WriteLine(numw[i]);7 l1 a9 v& V) [, [- L
           
! {- A1 T- T4 X2 A# e            Console.ReadLine();  Q5 I4 P' t/ [: K9 F
        }
/ J) h, _& i% o6 x% J& P    }
+ Y$ j7 X& `- b' q$ j$ ]}6 U4 |# g; s( V0 v; H7 I4 s$ p
小甲鱼最新课程 -> 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-16 05:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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