鱼C论坛

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

猴子问题

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

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

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

x
大家好!
0 g* s1 A7 P. ~3 ~+ K% f这几天我在忙着编一个问题,我用了一种方法编出来!
- P: H+ z6 @- T% K4 t' S但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
5 J$ |7 o3 c1 E, i& d) X注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
" u8 d4 h' k3 Q' k+ O3 [4 `: @8 N% L' \8 h" d( j3 q' P+ Q( b

# ~9 [5 v- Q6 G7 D
                            题目
* l1 E0 h( O7 O  |山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
8 c& b; d5 n/ u$ Q. F+ K第一种方法:利用循环链表
2 d( i, N0 h: T% e#include<stdio.h>
3 ]+ T! Q  g& C0 S+ M- P#include<malloc.h>
9 U$ v5 Z8 K- b0 x2 N. [% j8 r#define M 8            //共有8只猴子' Z( x, S) v6 h) Z3 _
#define N 3            //数到3只时退出第三只
, q) f5 i9 @  T, g; ptypedef struct monkey2 g) z# J* a6 B" r
{int number;
3 n* K" K5 h1 A& X& m. w) D5 B  e2 [int flag;
8 S5 Q0 B: r/ C4 o+ Sstruct monkey* next;( k2 [; ?! s  y" ^3 T6 u1 N1 b
}MONKEY;3 g9 Y% p+ b& K" u$ W; c
main()
5 z8 h" T- a( S{ MONKEY *head=NULL,*p,*s;' d/ @+ p# j% j$ t3 I
  int i,sum=0,count=0;
% T2 x. o1 ~/ h/ f8 q  clrscr();              //清屏1 F+ _  X5 ]- U* E
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存( i. ]' t+ Q$ E1 R2 T/ V' O
  p->number=1;p->flag=1;
; J/ o5 P5 ^  U  p->next=head;
8 M: v3 b1 B" Q  head=p;
/ \2 e1 y8 R) [  for(i=2;i<=M;i++)
1 y# |8 Y5 |: i# e: v    { s=(MONKEY *)malloc(sizeof(MONKEY));) I- J; E" q. |; x& `, U
     s->number=i;s->flag=1;, i, v- f9 G7 {( D; \% e0 C
     s->next=head;
1 b; W8 v; k3 g% T     p->next=s;p=p->next;' \3 X8 k* a$ K! w! p- c& J4 v
    }4 g2 Z, X) z) m+ v2 g" \4 d8 m: ]
    p=head;/ x1 j, @5 _( M
   for(;;)0 N6 ]( K. C. j4 E9 ~& ]
    {if(p->flag==1)1 Q: n9 k3 H. z! i' ^& w$ M
       count++;
/ F; [9 i$ U$ O8 o+ \  J2 L     if(count==N)3 L, C6 G8 \' J" `- _7 b: l- m- R0 K
        {p->flag=0;
3 I  X0 y. }; ^( n8 Z! a         count=0;
0 D& u( ?0 {- J) v3 _& k         sum++;}
( P* x9 B) ~+ }. g) y# E/ Q' i     if(sum==M-1)+ N3 e/ K- B+ C; {4 f& m7 S" N
        break;
2 r& V  H2 ~+ J( g3 T3 D6 H. Z" t     p=p->next;3 B& b7 @% ]+ D) a9 J
    }, w+ E6 }$ l1 w& O6 g& l0 `+ \. X0 j
    p=
- k' l; y2 m2 o) v# I    head;
# Y" f: i7 B/ j# K9 h    for(i=1;i<=M;i++)
- o- S3 \  k9 z% M# I    { if(p->flag==1)) E) w4 p! Y# d5 W8 ]
        printf("\t%d",p->number);
! i% M9 }) v% t) ]# D8 _4 z' f      p=p->next;$ L; K' x: P6 Q& d* z
    }
( Z* F6 J! p5 \- ]: i# a
3 F& f' o# j! m* C/ H/ o% b2 F; X9 b9 f9 v) W+ C# D3 [) |* `

  [) w! a6 c2 R" q% p. q}

- i, b/ ?% }% F6 k$ j- s第二种方法:数组
4 I* j7 i; r2 q* F% D) t#include<stdio.h>
2 }( q! V; p3 p7 ]5 O% j#define M 89 \( U. w/ S9 P# [
struct monkey
, K. l9 j/ W+ b* O2 _{int number;
1 O& C: {  t$ r, \int nextp;2 W1 ^9 J0 t* w0 r
}link[M+1];
6 |  \: Q/ V/ }. i$ A. g
: o0 @' m$ Q' c, N" Rvoid main()
/ o; U8 y; H. O! V! P1 D5 {{int i,count,h;/ d+ f4 W  f% K2 R6 m8 q
for(i=1;i<=M;i++)
" K! W: u% k* v( W{  if(i==M)5 I4 S# c/ \' m! T8 U: E& b
   link[i].nextp=1;
8 g# h. P, ?% s% g   else
( [7 ^1 u7 I& M) F+ W6 c$ [   link[i].nextp=i+1;
! \; R; M  j( U7 k7 a  link[i].number=i;
% s+ K* O- y- Z8 H2 A}
& U. k: ]! o7 x. e/ Y$ d. o; Fprintf("\n");9 y( P! H: l+ M9 @: Z
count=0;
5 r8 J- ~" i1 ~3 S0 m0 X0 Bh=M;9 f7 k. t4 r5 n: h0 B: ?2 o
printf("依次退出的猴子: \n");
, _1 e8 Q& w. A2 wwhile(count<M-1)
! @0 ]) m2 ]0 q( ?0 [{i=0;% ?- B" W' J. |6 m! h
while(i!=3)
+ S$ }- c9 g$ f9 s4 l{ h=link[h].nextp;9 O* \2 a9 M4 k
   if(link[h].number)% A$ n3 U% d! k# Y$ |
     i++;}/ j) ?( y; j5 W1 e1 h% Y% J; d

0 Y7 Y8 k/ }6 ~; b+ {printf("%4d",link[h].number);
# V& c. o7 r" elink[h].number=0;% I: G0 |: d7 X+ p" J9 J
count++;
! y& A6 g9 c% m$ ^7 Q+ q}8 F8 e( M: R: [

: O) ]. U( I! Dprintf("\n大王是:");" w. F8 A& L- L  f! G9 k/ {+ u
  for(i=1;i<=M;i++)% L/ c; p6 R; m7 k
  if(link[i].number)
! S7 G. z$ Q' d% u' c# w; s' Q    printf("%3d\n",link[i].number);& ~5 c; r- S9 n& n) N# d% d
0 M. {7 Z! E& A- y& C2 r
8 E) Z: O6 ~) u. d
}

" D, Y4 u) X8 |: B第三种是普通方法for循环
" `4 `" @8 L, a5 \7 R7 m% o2 {
#include<stdio.h>
% {3 n4 m: |4 m/ v6 b- kvoid main(). T# R8 D& x  B8 E3 M- w
{ int i,k,m,n,num[50],q,*p;
5 i. M+ A* P% s) ^0 T    clrscr();2 P# f) t  U$ h% g# c5 b
   printf("input number of person: n=");9 r6 b: \' C. ^# U# Y9 Y. |
    scanf("%d",&n);' ]- i: t/ c9 V4 `+ a0 l, {' l
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只* S, d4 Q* p; ?' o3 ]) T! C
    scanf("%d",&q);
5 L! z& t0 f) d$ d9 n   p=num;
# S3 i* k0 H# m3 t. N  for(i=0;i<n;i++)
. K6 j- a; x- \9 R7 I( {: X    *(p+i)=i+1;  O3 g% a# o3 S1 G; H- l& m
   i=0;
2 E0 x% Y5 I$ q9 _   k=0;7 c+ U5 H7 r' }: S9 V
   m=0;; \& ?" C2 @3 [6 E1 X
  while(m<n-1)) J3 U9 b4 d* k1 B0 N5 g! C- y8 }' n
   {if(*(p+i)!=0) k++;$ T# y- P9 c$ E% R; N$ N, Z$ x) j
     if(k==q)
9 V* y, e% _( _      { *(p+i)=0;+ F. C: R5 ?8 z* ]$ p
        k=0;
6 f* o" a2 o% O        m++;  E/ T/ Z+ O3 t, \+ w: @
      }
; a& i' d& z! h/ [3 o  B- e    i++;
# C! p; O5 U) ]. x7 L    if(i==n)i=0;+ {+ y, w* {- }# N( j
   }- {' L( s% H2 N8 I5 z. A
  while(*p==0)p++;
' M8 ~7 p; I1 q! q/ {. Y    printf("The last one is NO:%d\n",*p);
" ^; j% Y& g/ c/ F2 e     getch();- f# f0 p  G1 s$ A3 D% e

! r/ M+ \% A/ A5 j( h}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;8 r6 o( H! \2 x) C
namespace 又费马达又费电" F9 O% S5 O3 M7 t9 @% n# @
{
$ j4 l- f* M& ~* C! E9 y9 a    class Program0 v3 q/ k5 g% s7 w7 ]2 V
    {
' N: B9 R: v. l3 Z; c9 g" U. G        static void Main(string[] args)6 H% `0 Q2 c9 m
        {9 |7 r! j) z5 N! N$ k6 R
            int m, n;0 @+ Z% j9 d  R* N" \
            Console.WriteLine("请输入数组长度");3 R6 r$ m# j4 {! V" ?9 R
            m = int.Parse(Console.ReadLine());//m为数组的大小
: i" k3 ]6 ?- ]$ u4 T8 N            Console.WriteLine("请输入要截取数字的大小");
( Q1 o9 r. v# g0 j# z1 t% {; A            n = int.Parse(Console.ReadLine());
* c4 c6 j9 R" K            int [] numw=new int) Q" f" j4 a* F% Y1 A

7 s& q9 e1 r) _' h9 v6 I- b&shy;&shy;&shy;;
9 p' K$ R7 i" j8 `2 k: _            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数4 k3 a0 R2 a- h3 l* z4 R
            {
; k) x. S! ?! C: k; X                numw[j - 1] = j;! m1 o: ^, {" O3 L& u: I
            }4 d' g) ?; _( u4 E
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
( s* e  T7 @+ Z8 W* x            while (d != m - 1)
2 R7 Y+ |/ ~1 p* ~6 m6 z            {3 h$ L/ i4 ?1 {. \8 d* I
                if (i == m && d != m - 1)
+ ?5 y9 M( s, H9 T2 ^                {' Y( P" S/ N) R, w2 u2 c: D, ?% W
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!: i& s2 j& m: b, w; ]5 k
                    continue;# n8 v( d: U/ N. G
                }  R0 O% k5 c# }0 a" M8 E1 F  B
                else
: f% E+ Z: ?9 Q                {
0 h) H0 Q/ d* l; R2 Q                    if (numw[i] != 0)0 D. b7 Y2 s- ^& l5 }) a  t
                    {
) O% H; N' k. W% N8 h0 B8 g                        i++;7 F' ?5 G  S2 a0 T! N( D5 O7 ^
                        k++;6 r9 P' _7 [5 U
                        if (k == n)) [* x  Z2 I6 T2 C; ?& @
                        {8 ^! B7 U( {3 p
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了; O, y* o; O, q$ J
                            k = 0;9 Z) @  |( w  q: K& L* V7 ~- n2 `: l
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1% v8 T$ e! `( u$ L6 u0 t
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);9 @$ Z3 m  G- Z( P2 C1 v
                        }+ A* T/ o2 a: c" q+ R
                        else//输出暂时还没有改变数组元素的值. R" {1 j, K+ T" p+ b$ m
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);) ~, G' K5 Y& r
                    }
  _1 J0 v/ b0 _) l                    else9 Q6 s* w% K/ v  G# E* W/ c* n) D
                        i++;//数组元素为0,直接跳过,不计数。。。
4 w- z# B) y! R* O$ i                }7 |: X# p3 X: e  s% u
4 k. S: d" G0 q/ v( `3 p

" |; e1 S, g. _+ J            }//结束while循环- O) N% L& A1 ^: o+ u7 A0 v$ L( H
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦+ f( r% b1 V5 d* q! d/ e
           
# ]  m% Z* P) s& C9 R) K% i                if (numw[i] != 0)6 R+ J7 H0 i0 g6 c
                    Console.WriteLine(numw[i]);
+ A8 l7 d( M& G2 ~2 ^           
. V, i7 q: y; Z- x( Q4 p' h            Console.ReadLine();! w; Z5 Y" x6 j
        }
: ?; r$ {& ]0 M: L) v$ W8 i    }
4 e: G" P6 d! V: ?, H}
. h* s4 V5 F4 C0 J8 m  d" \
小甲鱼最新课程 -> 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-3 12:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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