鱼C论坛

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

猴子问题

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

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

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

x
大家好!& C. }  M) g( ~' z
这几天我在忙着编一个问题,我用了一种方法编出来!0 z/ j, b2 @  q( {# J
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ C. N3 U' W) D% ^  j' j% a
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
; E$ Y3 h! @! ?/ K* }4 s* a* m$ ]9 y; }1 ~4 l: k

* [8 H% J1 o; t' q9 Q6 S
                            题目
+ K6 S+ Z, X  i! A& y( R; _山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
  G' f1 S" ~- I) e4 ?第一种方法:利用循环链表6 V* J! ^/ f+ a% M$ q/ O
#include<stdio.h>
) V" _6 _5 r' E- `#include<malloc.h>
$ o2 @( _, W) j#define M 8            //共有8只猴子
- a6 W1 n! m- [$ {" M#define N 3            //数到3只时退出第三只) N9 z: n. x: f! k, P* |
typedef struct monkey
- B2 ]1 v$ m: L{int number;% h. b- h' \) \7 ?# m  y6 D
int flag;
4 W1 O: x$ ~( N# v+ D2 }struct monkey* next;: I- @' D6 G4 Y0 X
}MONKEY;8 b- N1 ?3 l2 f4 `" z
main()% g2 C  j; {: S3 V' S
{ MONKEY *head=NULL,*p,*s;$ W* i- O6 |8 \, j* s* k' G% b6 C
  int i,sum=0,count=0;$ _" P3 o$ d6 T1 C8 b( _
  clrscr();              //清屏6 ], t6 H0 y  e: J  R
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
" \" F/ Y0 ~' V# f  p->number=1;p->flag=1;# z' H: D2 Z% ~  b
  p->next=head;/ f9 m7 V2 r8 T' V( z. G: ~* J$ W
  head=p;
* n7 U* e: W; s. g: x  for(i=2;i<=M;i++)- j2 U8 y) J$ g) L. W% D
    { s=(MONKEY *)malloc(sizeof(MONKEY));" Z$ V& K! K4 \. I1 r8 S3 q$ S
     s->number=i;s->flag=1;# J/ q) c; z0 C% L
     s->next=head;) m( c! U" x$ m/ [) l
     p->next=s;p=p->next;
$ i8 s% [4 l9 ~3 z6 z+ U8 b# ~    }1 X' r9 s' R, t. y
    p=head;4 w& s& j8 t" s
   for(;;)
9 E$ P8 e4 ^; U    {if(p->flag==1)' u7 I& |- Q. t2 @0 @2 F9 q
       count++;
4 @. q8 C$ W- P$ X! K" _     if(count==N)
+ e% `! y( `8 z- E. ^  b        {p->flag=0;
7 I2 C+ C' W. x: V: h( @         count=0;
* X  w5 n# w0 b" u9 h         sum++;}
$ N/ J$ X5 u/ L0 \; P     if(sum==M-1)
" x0 f% `9 D2 n1 v4 D        break;' W/ J- l* h# y. T3 j0 @4 j
     p=p->next;
( M+ ^# ~3 s( y% f    }% {7 u9 l9 a; w# {/ h
    p=
5 K4 T; m: G+ h  l6 O6 H6 N    head;) G; o0 x/ I% u; X6 I$ a
    for(i=1;i<=M;i++)+ c2 T, d! f% `& l
    { if(p->flag==1)
  j" a  }- @" c# n        printf("\t%d",p->number);; O" {; p" w( S6 K% P- |: i
      p=p->next;3 ^: j1 S" x; B7 F0 S# N
    }
: }, ]: C; ^9 ?! ^! A) v8 {3 Z1 N
: b3 {8 p5 C* a/ f% |( Z5 p7 A5 O6 U9 e/ V
8 P. u$ q2 ]1 B
}
5 A* f2 l1 B, l3 U5 `4 w( _9 l9 T
第二种方法:数组6 ?- v! z+ D' f  U; |2 a3 n2 L8 Y- V4 p
#include<stdio.h>. _: k$ x* O, V7 C
#define M 87 X8 R0 E( n' _& W
struct monkey
3 p8 G( a( o" t1 i. e3 [{int number;
# V& e3 S- K  m) Zint nextp;: w' ~! M9 B9 g1 _$ s) Z
}link[M+1];
- y4 `2 [, ?! g/ U1 |8 [1 J) o. x4 w, [3 c3 O' j7 k6 r
void main()5 ~1 r- A  B. _8 ]
{int i,count,h;. J2 W: I- F3 q& E. S9 x
for(i=1;i<=M;i++)6 o/ M  m3 g0 Q1 H: }
{  if(i==M)2 b9 l: _) {0 b' V/ t
   link[i].nextp=1;+ {+ w6 X" Q6 D; O
   else$ t9 @( ^8 E% p2 X* C! s$ V+ r" x
   link[i].nextp=i+1;
+ z  c9 a6 b* _6 k3 F1 Y2 m  link[i].number=i;
) \, e; ~4 T* {' A4 c! k! B}5 ~& Q0 [: B% s; b) i' y: V
printf("\n");
4 k. d$ q, a: Q2 v, `3 ~+ V( ecount=0;6 d; H. q% Y8 W& C# w
h=M;  l: X, S7 i  f) W$ H- W% I5 v
printf("依次退出的猴子: \n");
: R5 \" y* o4 f: l2 }: nwhile(count<M-1)$ a$ d2 Q4 V2 a, F. n8 U
{i=0;% r5 A% @2 `: U# C0 G9 F1 L! p2 U
while(i!=3)
0 {+ L+ z% [6 B& Q, M: f{ h=link[h].nextp;
4 `2 [# k* Q2 l( g7 O8 o   if(link[h].number)
$ m% c& W5 V, f/ r/ N. }/ p, \     i++;}/ s! p8 F2 `3 m) X0 A

  I7 B3 J% p* R1 V! ?3 zprintf("%4d",link[h].number);. L( J6 r" _$ _5 I) u' E
link[h].number=0;
5 S; D& Q& {8 ~$ Ncount++;
9 E# W9 J3 B7 Z/ ^, D- a: ^! y9 b8 R}
! w' Q6 D9 u2 x
+ r0 F9 d# j4 Eprintf("\n大王是:");8 Z) i$ W  @# w" k7 {
  for(i=1;i<=M;i++)
2 Q2 @( F0 `% x3 r' h9 C/ J  if(link[i].number), D( l+ \& Q- W7 S
    printf("%3d\n",link[i].number);
! S; F0 ?( t. o9 A4 S; G' W3 E- u/ J8 U6 |2 b# n- f
2 j( y# _- H. ?$ i2 Q# `
}

( ]# w- ^( M* s' g; I, v7 Q5 x第三种是普通方法for循环

3 N# ?2 K3 e. }' P/ X( @( t0 A#include<stdio.h>  M. p: b# ]' T' b' e
void main(), B0 j: R0 m6 X9 _" j6 H
{ int i,k,m,n,num[50],q,*p;
, v. U2 u7 p7 S9 z* Y    clrscr();$ J. v4 ^. O/ r8 m
   printf("input number of person: n=");
5 c' S+ J* t$ ?2 z  f  `$ E    scanf("%d",&n);% a6 E' V2 P, M
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只) j+ n1 n' K" w2 m
    scanf("%d",&q);
# X" `$ u, k3 `/ k& y+ s   p=num;
" Q3 `/ z5 G% T  for(i=0;i<n;i++)
+ {+ X- Q7 N7 p$ X7 a    *(p+i)=i+1;8 X% q$ S9 x8 j' R% c
   i=0;  z+ N! W3 e  `9 W# S- v9 r
   k=0;
9 t! e+ K  H0 K" f! h# m+ z   m=0;
, C! d" _9 H7 ]3 r8 p; v. V4 O  while(m<n-1)
4 L6 ?! t+ a6 K0 a. e' U$ |7 L( [   {if(*(p+i)!=0) k++;
( _5 P  b7 x6 D2 ?     if(k==q)9 D" G' O6 Z( X
      { *(p+i)=0;
2 F, N* T+ |; X: ^1 q        k=0;
! c; a1 Y2 B& B" Q        m++;7 j& c2 D& V# }( A2 X3 y
      }7 s( J3 |1 I9 B- m- U
    i++;1 v# `9 K, ?9 H8 M3 L' K1 S- p
    if(i==n)i=0;
4 Z" @5 y1 W6 Q   }
2 q: Q3 h. H5 s# V, O2 a$ p) G2 d  while(*p==0)p++;
9 g2 X2 q% N& N8 _    printf("The last one is NO:%d\n",*p);
& o" A5 D0 G) O6 E9 ^     getch();# c. w0 V3 u  |8 t

6 ~& u6 T! z3 }. Y) M& D}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
" R% h8 P, f- J4 b+ O- Jnamespace 又费马达又费电1 |1 ^% \2 n& S
{8 {! ?) G$ h" n; L) N, p  }7 y- _
    class Program
, e( u% s0 {% l: i5 b/ t' Y    {/ g% H$ q9 A7 z4 J
        static void Main(string[] args)" K8 R7 c) q" E2 z0 Q* \; R7 e' A
        {8 U' U6 V$ l3 W+ H2 N3 K
            int m, n;
& t4 M# }; o6 z, i            Console.WriteLine("请输入数组长度");3 N6 X' L: F3 i2 a- s# H4 [  `4 u
            m = int.Parse(Console.ReadLine());//m为数组的大小
- _. Y9 {) V! X            Console.WriteLine("请输入要截取数字的大小");
  s; g4 x2 d7 f. p8 d1 o1 r2 F8 x            n = int.Parse(Console.ReadLine());
6 c, L/ f# m+ n+ n, ?            int [] numw=new int0 _% z( Q4 |' a) T- k. g, U

) E5 x) b% K# y2 j7 B+ c&shy;&shy;&shy;;: G( k$ ?, q8 K3 |6 D" ]) n
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数2 C" h3 [- k; d5 i  u
            {
$ B: T' Q' \: U8 ~$ F                numw[j - 1] = j;, ~6 _, _) L$ H5 W. F
            }
9 i- d% ~9 \2 d% w  F            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!; Q' w( r& d( Q* V+ w
            while (d != m - 1)
/ K2 l, o: v2 M6 B  E+ f# N7 [+ y4 [" |            {
+ `1 n1 t  b/ }6 i* D; K                if (i == m && d != m - 1)6 M! l# w$ e& r% h
                {
0 M3 ?$ W1 m7 X+ B+ e                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
' A) J/ D) e9 L0 ?2 a4 }                    continue;
0 }5 @6 C9 G' Z                }
9 Z3 a+ ~( C& H- p! C0 t                else
8 n( {! y  s) B. d5 |& F6 [( f                {# |2 }1 x% p9 \7 ~; R
                    if (numw[i] != 0)
! M: z8 T* F' G                    {
" x  W  v5 {* p$ _                        i++;
+ z' Y* O, t9 X                        k++;9 t" T% \% L6 m# _1 M! J
                        if (k == n)0 b( H5 @$ x& E$ Y
                        {
- R4 y# y1 }% ^% p! x                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
3 b% Y* M$ L( d( Y' `                            k = 0;
3 k5 {- X# ?2 Y              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
" ?1 T' m: {0 g4 F  F% m; M                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
: [% a# s4 ^) P& l/ ]                        }- h0 }; K. }1 j" S4 X4 p+ X
                        else//输出暂时还没有改变数组元素的值
& {0 i0 s( O; ]4 b# H                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
) j% ?5 e. v6 \- J                    }0 J2 x+ W! {. A+ l! ^
                    else1 r- D4 _$ ]( b6 ~
                        i++;//数组元素为0,直接跳过,不计数。。。  C( t! X; f  t- @' s) \: @
                }! G7 c' t; {! Q* o$ T/ Y. y

$ r6 D" c# q6 S+ A. N0 \, f9 q) p8 p: ?; D" K# ~2 R
            }//结束while循环
/ M( J: x+ U4 H; Q6 p2 ]' t            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦0 ]! x4 C% X. ^1 U
           
4 Q8 V2 Z: j, v& s* T0 K  F. z                if (numw[i] != 0)
4 y- x' T# q, m1 s                    Console.WriteLine(numw[i]);
! b) y! i% U1 F4 ~7 {; s           
6 c5 b1 _8 n7 j            Console.ReadLine();5 c( m2 T4 `. K
        }
2 C7 k7 o6 |7 c) Z    }
6 P- }- o$ `2 q3 Z6 u# A}( b1 J* z; `! U/ `: M4 a1 s
小甲鱼最新课程 -> 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-5-31 15:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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