鱼C论坛

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

猴子问题

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

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

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

x
大家好!
( L5 p  _* |+ W# o6 F% I- G这几天我在忙着编一个问题,我用了一种方法编出来!
( H% d4 ]! F2 |8 L但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
0 v4 k' @. G' r) q6 x$ t注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 5 R8 W! x+ v; f! I. ?7 A' P% g

* a. P8 ?  t. ?/ i, t2 ~9 y
2 u' ~: b$ K8 w, ?7 D
                            题目
# z& L2 S! j# C% M6 C山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
! M( L! O1 }8 G7 P2 ^- c第一种方法:利用循环链表
& m4 z: i. r2 X9 t! E( b#include<stdio.h>" N0 T) k6 z$ R; F
#include<malloc.h>
! C4 v; G3 \3 i  @1 b: O5 {#define M 8            //共有8只猴子/ S! s  K+ ]. }
#define N 3            //数到3只时退出第三只
. _# \% W3 ]% T4 B$ s; v8 h1 Qtypedef struct monkey
: t- r% e7 j1 F7 l7 _9 p$ {8 \{int number;
& J4 G1 f) b2 |$ e: Z1 \1 p5 Z! Gint flag;
$ b; P- g$ Y5 E( v9 `4 wstruct monkey* next;
7 j+ @# d  R4 z$ {; P}MONKEY;+ Q/ n) ^+ i2 r( F
main()
; r% ?8 Z& F4 D& Z{ MONKEY *head=NULL,*p,*s;
& j- O+ D+ p+ ^+ q! H  int i,sum=0,count=0;7 J8 f. e6 M1 j" j0 R: D8 V% [. {
  clrscr();              //清屏
& P3 e; C; G" D  P1 @  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存% C. [8 j9 X0 ?' r& w
  p->number=1;p->flag=1;! m' |7 ~* G( R% E  y8 `
  p->next=head;
+ P: }0 j  S3 R# f. {  @  head=p;
2 R8 V: n- j# g$ |  for(i=2;i<=M;i++)
# J3 M& g2 v2 i2 z8 x1 A+ K/ t: a    { s=(MONKEY *)malloc(sizeof(MONKEY));
0 J5 x# B6 ~# ~$ n3 u! o0 B( x     s->number=i;s->flag=1;
. u- ~1 r) d: I/ [     s->next=head;% h6 V9 z4 r5 X7 ^, f( }6 R
     p->next=s;p=p->next;
1 t6 M5 s6 H& H( B6 ~* R, v    }
: A7 ^( i8 O% _3 T; {) M8 K2 p: ~- f    p=head;
# j/ S/ a6 h+ l   for(;;)
. J" U: K6 q; c3 G7 J' T8 x    {if(p->flag==1)
! `. q6 T9 G  y7 [       count++;
4 e9 g9 M$ C- |  t     if(count==N): [0 D5 q6 s7 J& B
        {p->flag=0;8 z; Y0 {  Q& y$ z
         count=0;# k' J+ V" K% ?8 V
         sum++;}' ?+ m# W# o, I+ k. B4 b1 x% F
     if(sum==M-1)8 G8 j1 C! x& q& H: R" ~
        break;
# N4 ]/ b& [, Q$ l* T     p=p->next;& b  ?, ~7 L8 L9 p4 J6 t
    }3 W' _6 r8 c4 |: [& s
    p=- Y) {) ?8 B9 d1 i8 Y: t
    head;
3 J) b6 j: T" B& f0 Y, P  q    for(i=1;i<=M;i++)* S7 V% \0 ]# C% B4 a8 K9 y9 w
    { if(p->flag==1)! p% S, s1 M  e5 h! w( c& h* J
        printf("\t%d",p->number);$ r, x; k4 j6 U( g  G; P5 E! Y7 t8 e
      p=p->next;' e  U3 E7 l4 p! u
    }
: n9 T+ t9 K% I- d/ c$ s8 I! g6 G0 R* ^0 q: p. q0 F7 x$ }
7 Y# S- ^7 }, K4 k

" z. X/ U3 p# y% W- q4 A1 g}
6 v; D6 s* j# r& [# r) h
第二种方法:数组) w7 b! l* t" T4 ]8 R& I
#include<stdio.h>
  O8 H% ~, @) @/ S% O/ P#define M 8
! N: [2 z6 E) A0 C( Bstruct monkey
: W8 R4 l$ }/ H" C{int number;4 ?) H4 y" k& A; W
int nextp;
& `6 H) i; T" ]3 D; V}link[M+1];& q) Z/ y# ^. R2 N7 H
4 H8 ?7 \# q5 v' V
void main()
4 [3 F% h' O) H* M{int i,count,h;
/ e2 Y0 z" m6 g) ufor(i=1;i<=M;i++)+ B& M% I- w* t7 b- O( m
{  if(i==M)
& t9 n) _! H! W. A   link[i].nextp=1;
  {' Z6 x6 K, l9 z5 i   else
$ ?. I3 c  C8 i. S" i   link[i].nextp=i+1;, e9 t' O7 C: D5 @5 Z. C
  link[i].number=i;
0 C9 K, X% A, ]* k}0 M" r7 R3 a7 B. `" U
printf("\n");
% @3 V# W9 C+ B3 Gcount=0;( g  U# R, l: x3 Q5 `6 p, x
h=M;5 ]8 u; x  G1 d+ Z# o. k8 a
printf("依次退出的猴子: \n");% e: c! @/ |8 `0 T* m5 [9 ?6 R
while(count<M-1): |4 ^3 s2 \) ~
{i=0;
$ X6 _% |$ r5 G/ Xwhile(i!=3)
1 {! t1 H# N% g{ h=link[h].nextp;
- r! L6 S5 i2 {* ?9 m   if(link[h].number)
" p4 ^' g% J1 s! N     i++;}
# E- E# o0 X) w3 Z
# _' ^8 A% G9 \; b$ bprintf("%4d",link[h].number);
) g( j* V5 K) S( m3 l& F0 rlink[h].number=0;
+ D' V# N: u6 zcount++;; l7 w0 V, l' u% h% t
}4 u8 R/ P: h; W4 [6 ?

1 g6 C% k! ~* K* U& b" d9 yprintf("\n大王是:");# O9 M( L0 D5 Z: r4 A- \: ]
  for(i=1;i<=M;i++). l1 C1 [) l& y0 F6 F, H- I
  if(link[i].number)
; U6 Q- t9 d2 X* L) y    printf("%3d\n",link[i].number);. p/ z+ Z. _/ L" L
, P' \# F3 b9 Y# j. y5 y1 m& z

0 r- l2 l: D9 h$ H/ G2 P}

  K" [" k2 D8 f& t. n/ T第三种是普通方法for循环
  D! [5 M5 r1 p+ z* L: i& ?
#include<stdio.h>$ J  E4 [1 o1 J, ^) b1 ?
void main()$ @0 O! r/ M+ M% b8 A
{ int i,k,m,n,num[50],q,*p;, ?& C5 i5 T( D7 \5 s  A
    clrscr();# n& ?6 }0 p9 u9 E4 ]7 y5 F$ V% |
   printf("input number of person: n=");% K; q+ G& v' w. T
    scanf("%d",&n);$ T- o! \6 C4 h% h
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
' ~& L8 L. w0 _3 s$ J2 p- ]% p* r    scanf("%d",&q);
; c+ ?6 \/ D8 ]. k   p=num;' f  {. `3 x% {' z! I% P
  for(i=0;i<n;i++)
- \0 x! ^/ b0 d: Z    *(p+i)=i+1;& n$ X, |4 L# K) m2 |+ f
   i=0;0 `, y. r% T  E/ S( E& w
   k=0;* G2 {5 F6 S9 z
   m=0;4 e% C' `+ A% }: J, i4 n' _
  while(m<n-1)
+ w# ^* k! u1 n   {if(*(p+i)!=0) k++;! i2 y3 y* S$ I( l8 z
     if(k==q)
* C1 n; P* ]# D      { *(p+i)=0;0 [9 o9 k# n( ~& H# S/ g
        k=0;5 y4 q& o: R& S; e8 A
        m++;7 Y+ w0 x! \4 V  H3 i7 u
      }2 F, e. v$ l% e( l! `/ c% n# V
    i++;
  [2 V2 n- U# c) O    if(i==n)i=0;
  X/ {- w, Q) w" V  U2 z+ K   }
6 d! x9 w: o9 u  N$ ~4 S9 g# w+ r+ [  while(*p==0)p++;& P; S; i3 p1 D* d) }5 Z) I1 p
    printf("The last one is NO:%d\n",*p);
2 S$ S% c2 E( y7 f6 H, v     getch();
* G/ q" s, u/ D! Q& @2 H* A0 m8 ?# m9 ]! \( t1 G" e
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;8 Z' g- {# g1 ]6 N
namespace 又费马达又费电+ z" O0 `  ~) b$ t
{9 {9 ^( ^! e2 g8 d: p4 D) n! L& A
    class Program# f6 D4 v) J4 h2 }/ H! \+ k# w
    {
! f7 I1 o$ s( G: C% `        static void Main(string[] args), m; `& n$ x* x* G6 k
        {9 M# o% w& [6 v9 y3 A7 B
            int m, n;
7 Y3 n4 ~# E/ c( k( K8 k7 r' G* L            Console.WriteLine("请输入数组长度");
, O+ O. z5 O6 o0 }4 ?, `; G8 H) @5 t            m = int.Parse(Console.ReadLine());//m为数组的大小+ @+ E: i; _; K0 o
            Console.WriteLine("请输入要截取数字的大小");1 }' Y# Q; O8 c% G' G
            n = int.Parse(Console.ReadLine());
9 z8 W3 l" e  a  u8 ~0 F4 y            int [] numw=new int
) ^$ ?& [) ^7 V& Z0 j- j% U0 w) q, O
&shy;&shy;&shy;;* u& Q/ m- z9 V7 V
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数; A% Q1 D7 v6 [. J9 [
            {
! d/ f* L" k) y                numw[j - 1] = j;: Z& \. O% c* Y
            }+ m3 E* n  k$ A9 c2 A8 Q  t) Y
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!5 _% {- Y+ h' s. L* s- G( h- Q
            while (d != m - 1)2 Z6 N8 Y, g( a$ p3 C7 x4 B
            {
& b$ D& j' Y% A6 B: @                if (i == m && d != m - 1): n  ~; Y/ _" u+ |9 I+ C, y% K
                {
- B, G, d  k; J& \                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!! z  _2 c. z$ r7 Q4 G7 ?8 `1 z1 J
                    continue;
6 ?+ M6 L( x2 w2 d0 ?: {, P                }4 X2 z( k  y: p7 ^& c
                else
* m+ I0 Q$ b) g+ i                {9 E4 i, [+ X5 P6 t  q5 `
                    if (numw[i] != 0)
) |, A* L7 e8 |+ L& `                    {3 L' [$ ?( y0 |& J: [/ m
                        i++;# T: n9 G; |: C6 x! ]0 n4 y5 e
                        k++;/ J4 V  o; ]6 j* w+ [
                        if (k == n)
" K; K% u; `* I; r7 F2 [                        {5 P3 q+ n0 Z4 L3 j: Y. N) g
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
" a4 `0 V) V! M, a                            k = 0;
! p2 C2 D5 H2 v              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小11 N2 z' x3 z4 c8 f* S9 ^
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
- S$ j! `) x  r2 T5 G                        }2 ^  f) ]8 |1 |' \% Y# D$ E
                        else//输出暂时还没有改变数组元素的值0 S, a& H- t4 {! ~
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 m* C5 z5 `1 W0 k" c% d* F5 M
                    }# R. G( U' Z$ E
                    else7 N% b/ G0 b; s7 D- d
                        i++;//数组元素为0,直接跳过,不计数。。。' _8 \7 |! m( r' u8 F( W
                }5 A, p. s1 |6 q
) e1 C1 ~1 w  Q; I
, @; c7 n" w6 u; J( H0 j. Q: r
            }//结束while循环* _: z1 `4 v! v3 R; {* M
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦6 r0 ]/ q- [1 k, p) E0 S& z
           2 E& \* O. @6 m( O. ]5 j
                if (numw[i] != 0)$ c+ i2 f% O" |, J, A) A
                    Console.WriteLine(numw[i]);
' m1 Z; P5 Q) _* t( r) L! N& S           " G% B1 L3 x1 ?! m& e0 k* ]% t# M9 K4 C+ h
            Console.ReadLine();
+ I$ k5 ?, w! d# {        }
. x" y3 o9 V* [3 l4 }: C    }
7 b. b. ?( g3 f8 o- q/ ]6 `. V}9 _( j. z: G- J2 T+ k
小甲鱼最新课程 -> 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-4-25 05:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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