鱼C论坛

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

猴子问题

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

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

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

x
大家好!
' D0 _* P" Z2 U6 v这几天我在忙着编一个问题,我用了一种方法编出来!
3 B/ L) i- h/ q( T2 K3 x% b但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!; |$ ]" J  k. S0 n9 i
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
( R4 v* X7 l# }7 @# Q0 _' |/ t2 i2 \( f" D

3 j! S( i( l1 `% M: x+ c
                            题目
* M, @; k  [1 L1 p; R山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
& ?6 k" J9 n0 [6 d$ U# h第一种方法:利用循环链表% @* Z. k6 H% I% F8 g
#include<stdio.h>
3 p# j$ Y. X0 v$ v& G6 T* z#include<malloc.h>
) g  [9 V; a5 B8 K' U8 M. o) U#define M 8            //共有8只猴子$ F; ]( p  z, }, X7 j% B) a
#define N 3            //数到3只时退出第三只
  N, F3 A, r: V! x3 K2 Ftypedef struct monkey
( M! c6 O: h, Q6 J0 I1 p' Y1 }5 {{int number;- v5 {3 X7 c& a$ p, Q2 z
int flag;8 ]' m4 G1 `! e) ~1 B5 h9 K& ?
struct monkey* next;
1 Q. r' j& E7 n7 P6 V}MONKEY;; T# U+ Z( Y; G! D. z* V
main()2 [$ C! G0 @  }# S
{ MONKEY *head=NULL,*p,*s;8 p2 Q, _2 y! m6 R2 s) C; ~. y
  int i,sum=0,count=0;
' Y0 R) V; f2 i& q. X  clrscr();              //清屏
, o8 L( \' B5 O# g  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
9 T2 V5 F: m. `1 T5 ^  p->number=1;p->flag=1;
. v0 t; E8 `: l8 q! Y8 h  p->next=head;0 v; T4 Q  k9 w
  head=p;
% b! }6 x/ L# B, m4 T  for(i=2;i<=M;i++): S; q/ r# `  U5 c, P9 E
    { s=(MONKEY *)malloc(sizeof(MONKEY));
% `% Q7 U# D9 h/ ^, H     s->number=i;s->flag=1;4 w% \2 {/ J* S
     s->next=head;' b' B7 x4 z% Z8 a
     p->next=s;p=p->next;
. F& q% }- T- n7 U    }: }$ P0 l- ^) \" v$ w. F% {
    p=head;: B9 e) Q  w0 P& V+ |) v
   for(;;)
. B) j; D1 c# c1 ?7 b    {if(p->flag==1)$ C0 M( X: `; @
       count++;: u3 H2 C. {% A$ c3 C
     if(count==N)
3 N4 i/ S- L2 G/ s  H& K- q7 p9 H        {p->flag=0;' f% f4 ~' {' b& k8 p% f5 r
         count=0;: `; N% a4 P+ ^2 i/ ?
         sum++;}4 |+ H* b4 i* Z( q/ }( ?! Z! c: T" G
     if(sum==M-1)7 S/ g, }! T2 [+ `. g7 W
        break;) w( O! |' d9 a, `' q
     p=p->next;: A1 T( ]) R& k) v. Q% Q4 E
    }
5 x: q' \6 y& @$ C, _! |    p=
1 F- N, ?$ c* h7 I1 ]9 \7 E' X    head;7 G1 ]' U* e# D8 U3 Q( R# b
    for(i=1;i<=M;i++)
4 ~/ ], N* _& p! B3 r5 |3 @9 {    { if(p->flag==1)
/ ~: g6 ?: |( O+ L; i6 x        printf("\t%d",p->number);
; s6 U/ r* Z/ Z* @      p=p->next;7 ]! p. P& l) E8 Z3 w' h- h6 q
    }
6 w9 N( f+ B% o
$ u- M* D9 @3 I/ t& u3 s3 r$ B1 {$ F/ B3 ?3 A4 n; n

1 o( b/ d7 G) s5 d$ U2 j- P}

) w6 x# p2 r. O第二种方法:数组
8 w1 i$ N' R( u' }0 E  T#include<stdio.h>8 S! i- b  D# j% ~- S
#define M 8
, C% @% ]4 Y# `" X8 d  Z- y8 o+ x# Ustruct monkey
8 L% p2 Y% O4 v) ]6 e6 ]{int number;" i0 E7 b7 E2 L+ V7 H
int nextp;
2 i( I+ \  q( l5 `}link[M+1];3 ]8 I' o/ m, `$ r# o- U3 [3 R
4 e6 c2 z: U8 U, m
void main()
* f$ F+ }7 i. k' R) Z{int i,count,h;
  t7 n9 W2 h: S" y% rfor(i=1;i<=M;i++)0 d* r; U: x( L/ e- l( x# G
{  if(i==M)9 l+ L0 q2 Z  R! s/ Z0 ~) n  w/ C( k& h
   link[i].nextp=1;8 g4 w1 k7 y) G2 a0 F) m
   else9 d* A2 ]0 I7 ]+ }0 _& I  h
   link[i].nextp=i+1;/ Y# B6 n: [# q, h5 S' ?7 v
  link[i].number=i;( F/ K' c# B7 b  d
}' b% U( k0 C$ U' u3 h' ?  m
printf("\n");
5 r; S& W. H- ucount=0;
3 z  z" s! Q* l9 q. i) d* O7 oh=M;9 }! [1 F& B7 N0 T! V0 Q- s
printf("依次退出的猴子: \n");
0 a) t; o, A! W2 ^. ^while(count<M-1)
5 U  ]% V: {; ?- F: |{i=0;
. ^% {. K4 ]+ R8 z7 @0 t+ e8 Swhile(i!=3)/ I- J3 F3 c! j# G& f: f7 ^
{ h=link[h].nextp;! W3 U# g0 L+ k0 K
   if(link[h].number). Z6 x" v- }/ X% s
     i++;}. M, _0 q, x3 z- L$ K4 V; l
4 G  E+ S& G% w
printf("%4d",link[h].number);
6 ]& s  q$ g9 u  @link[h].number=0;0 a$ z* Y  h9 i& t( P. U) A" j
count++;
% U. N% t# Y6 b. s* N; W4 p}
9 _" b: @' y- t4 H  `6 R& s$ o$ |9 P4 a/ F! C6 T
printf("\n大王是:");
0 D: U1 ]% ^, u( B( A8 X  for(i=1;i<=M;i++)) P' O. A2 @2 Z; O3 w3 C4 f
  if(link[i].number)
. D2 ]+ p' H) P% O' U; u    printf("%3d\n",link[i].number);$ L) t8 y$ W# G2 z; x1 `

- ]1 R1 J, ~! m9 W) s, f2 L" }. b! Y$ |) s7 H7 |" e0 H
}
" T4 d) Q1 S& N& O$ [$ K; \/ R
第三种是普通方法for循环
1 I% O) s' w# ~
#include<stdio.h>
* M+ W7 @" X* p2 _void main()/ s& D1 z9 F  q
{ int i,k,m,n,num[50],q,*p;3 ~. R8 u7 a) c9 r! z' L& M( E
    clrscr();, |% Z) X: ]; X/ U9 A
   printf("input number of person: n=");
! h. X0 R' N/ Q    scanf("%d",&n);
( ?( d3 J0 @* g; t2 y5 L- Y$ }printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只# H! E4 u! a) n0 N
    scanf("%d",&q);+ b3 p  E1 ]! w# n1 j$ m" p& r
   p=num;# O; _7 r+ a5 S. y# K* ]# @8 L7 ~# f
  for(i=0;i<n;i++)
6 J" `  Y3 y$ m, D9 o$ A% J    *(p+i)=i+1;
! @6 l, s! m8 a/ r   i=0;
& G. h+ C& d' t8 |6 O: ~   k=0;# [" ~; P9 y% @; V
   m=0;
7 y/ B$ h7 b2 V  while(m<n-1)0 b8 R! B# P- o: B2 X
   {if(*(p+i)!=0) k++;; C+ D8 d7 d! O* Z
     if(k==q)
  B& x& @- u( M5 j5 P      { *(p+i)=0;
7 |9 J/ {; S. j        k=0;0 T' f( Z% }6 @1 c+ Q% N  |! G
        m++;
* \& s; p4 k2 c1 l( a      }
6 e! n" y) X. b  f+ ?: {% ^" `    i++;
  j$ J) y1 \, S1 y    if(i==n)i=0;: R  g# l% z- h) R! y
   }
' @' l( V& J! N& B; M# B  while(*p==0)p++;
1 H5 y6 E# G* [/ H    printf("The last one is NO:%d\n",*p);
: `' X: j( o) X; I     getch();
! F/ L8 x+ Q. `* S
3 v4 Z* [: m. C/ o' |/ x" m: k& `1 l}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;$ J, Z3 ~  I0 P
namespace 又费马达又费电! i; F9 e5 A- @+ p" r, i# K5 H
{
7 d4 |. N& Y1 f    class Program
# o# {1 s! @9 V. l    {
& }4 O/ v$ z  U8 x( H        static void Main(string[] args)
6 T  R- L5 K7 O. ?        {$ M. J8 W4 y% x- n- J( ?* B) i2 m$ K
            int m, n;1 K- L1 X/ b; I0 S: B
            Console.WriteLine("请输入数组长度");
! y! X' n. X7 K            m = int.Parse(Console.ReadLine());//m为数组的大小; Y& ^# ?0 {1 o' {
            Console.WriteLine("请输入要截取数字的大小");; u* [& }. i' ~, b( c
            n = int.Parse(Console.ReadLine());
; F: j$ X, e) |  d6 q) M) H            int [] numw=new int4 f$ X: N9 n2 a. K

" u* i4 S  i5 C9 K5 Q& Q0 s&shy;&shy;&shy;;
, h' I: ~# N3 H/ y            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数5 T! O# D+ B# v; d, g
            {+ Z+ v+ D  R8 o) P8 m1 p5 p
                numw[j - 1] = j;
2 K- b" ^8 S2 ~( n1 I  @            }
) }8 H! D3 T  E- p) e            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
1 [$ N) R8 I! h1 n, n6 p4 |- H& i' s            while (d != m - 1)3 L* w1 i) I1 e4 g4 D( B' U/ n! _' r
            {7 q/ D9 g, k) W) J  q) o+ X
                if (i == m && d != m - 1)
4 D  w+ ]4 h3 |6 R- t                {& k0 k# W9 ^, k) P  c! C( P
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
& L% [0 z2 s; g6 r& R$ X                    continue;
7 `6 H3 _$ }& L/ K# x                }5 J& b; p6 R6 F$ H
                else2 ?. }3 U# q/ ], S" ^6 G
                {; |; U* V6 B: j$ W! ~7 b: C7 H
                    if (numw[i] != 0)2 ~& P$ h$ d; j+ p
                    {& N- r+ a5 {: P8 K
                        i++;5 d; y' y, p& U0 G! n  z7 Q
                        k++;
$ N7 h' i" e1 a3 k4 o% A                        if (k == n)
" e" S9 D4 V/ A: [4 A7 L                        {8 E( e- h$ D9 b+ ?1 T* J! U. Q7 [
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
: Y4 N8 W7 s8 c0 L, V' D) z                            k = 0;
4 O2 H4 @- l1 w3 |1 s              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
. L; J5 h: U* t" z+ F                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
) z3 e, n  O. Q& p, O/ c) \                        }
' u$ M8 z+ o' y: ]  D  k9 z5 X                        else//输出暂时还没有改变数组元素的值
4 S) V5 X" q% x4 Y" `& _. R  |, D! s2 M+ S                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: x4 m$ e/ b/ X) [
                    }! G% k% J. v3 p1 W; x% j7 o
                    else) V! l9 o4 U  _9 Z8 {1 u2 ]
                        i++;//数组元素为0,直接跳过,不计数。。。
2 W- j) C/ t: w# x  ?  W" H* l: X                }
9 o- l. ^9 g" Y+ p' G ; K# }- u8 I& i9 n) e! E
3 n0 T5 p1 b3 P9 g, z% B  P9 y7 t8 [
            }//结束while循环# m; {. Z% {5 ?% S; q
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
" ~2 x3 i' S. e; x: X: E3 |           
6 I# ?' d& k1 q0 ^2 u# M) u( L- j                if (numw[i] != 0)
  `' H5 I# r7 F                    Console.WriteLine(numw[i]);1 I' p2 e% _8 F+ e- Y
           
8 y+ I1 J% i, A: B+ ^0 i            Console.ReadLine();
3 J$ T1 o. n. l* @5 h# D- F        }' ]: A" c6 g( Q1 U) H
    }
3 r- O% i% G( ?}
9 @6 `, v1 M8 P  K' R( V
小甲鱼最新课程 -> 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-6-21 05:49

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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