鱼C论坛

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

猴子问题

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

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

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

x
大家好!
6 L  B" D" Y4 U2 Q/ J5 {) j这几天我在忙着编一个问题,我用了一种方法编出来!
2 w8 _% s- @9 M* d( c/ i6 v8 X+ z但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
+ j0 E$ K6 x) B4 V: i% @9 i) T$ v注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
6 R/ G# q" L# \- P9 |; ^" q, X0 H2 P1 |/ ~. n/ y( ?5 B0 Z
; g1 @1 {8 e6 k
                            题目* R6 V. j+ }6 X4 N+ i
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。2 L) b0 z$ o; }
第一种方法:利用循环链表
# `0 O1 V5 [+ F! }. w8 j#include<stdio.h>- L* ^) v  Y9 m6 W- a" N
#include<malloc.h>
* \; h/ H# i1 l1 A7 }3 X4 v  Q4 L#define M 8            //共有8只猴子, H9 a9 N: w& P1 }
#define N 3            //数到3只时退出第三只/ n1 N6 {$ f' J  _. i2 v5 `' k
typedef struct monkey3 W& y8 ~+ v8 r4 K. l: Y
{int number;
6 ?! f, A/ k$ ~/ Z3 {% f" Y' Bint flag;
; u+ ~. ~0 \7 D* X- xstruct monkey* next;' T& r/ F9 `, P4 V4 Z9 ~- r
}MONKEY;  V5 E' e* p( y# H8 Q
main()
- ~  `  }' }% G  U{ MONKEY *head=NULL,*p,*s;' k" e. f8 w% g! d" ?
  int i,sum=0,count=0;$ u- N2 y) q2 `3 v( U
  clrscr();              //清屏
  j: ^. p* E1 f$ ]+ ?( U) b  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存% q; K3 L. h! e
  p->number=1;p->flag=1;' R* i8 w" ^' n( Y6 u& K
  p->next=head;& g: ]$ a, @6 f2 |  l
  head=p;9 ?* P& \7 U' |4 f
  for(i=2;i<=M;i++)
5 \7 {/ n' E/ R4 F7 J  o0 y# n    { s=(MONKEY *)malloc(sizeof(MONKEY));3 u0 \. _8 D' h% D* n
     s->number=i;s->flag=1;* ]& k$ {" V& P( j
     s->next=head;  T; x; R, w6 c( H
     p->next=s;p=p->next;2 e# J* A: L/ ?- m- F2 A* \/ q4 Z
    }3 S, N, E, I  F1 y" f* B% Y' [
    p=head;! x8 o4 w' ]' u1 [
   for(;;)
" N2 K- p! [, Z( U. s    {if(p->flag==1)
6 m6 U  d- T3 s* C( S& R       count++;1 w/ A) \9 f& l* f
     if(count==N)' S  G3 g  q/ C
        {p->flag=0;
: f; L7 g  d+ B. l         count=0;  C$ M& W3 n; h0 A
         sum++;}) J# l/ T, P# p* \# \3 F
     if(sum==M-1)& ~: W# t3 P# V# k
        break;% x* Y3 F$ X+ p" @" C
     p=p->next;
! g' c1 b- D' N    }  T+ p/ i& E  N6 j2 I
    p=) J* x/ r1 O; b; @% o
    head;
5 l' }4 C% N$ I7 Y1 C    for(i=1;i<=M;i++)4 c/ q% Y  F: {  G! g
    { if(p->flag==1)8 p/ v# s: O6 p# T" @, F3 l
        printf("\t%d",p->number);5 g" K& J8 ?6 d: K1 S1 h, `- g, t
      p=p->next;4 J) B/ N/ o* r! w9 Q
    }
, g5 D( g: B0 _9 B3 E; U' z7 c+ ?( U% b: l% Y& j" H( K

1 m' K3 L7 P+ v% L7 }( B0 j% y. |0 G' _$ n8 O9 b# S& l' t
}

! s+ ^- i; M) `" Q! W$ P  s8 d" T第二种方法:数组
% t! i; ]& v0 S7 g#include<stdio.h>
+ c5 P/ Z# W6 l3 n$ s8 F( X#define M 8
* ]$ e" K' L- {& L2 ]struct monkey
$ P3 m( X; J* E: d9 N3 b{int number;
; P+ H( ~1 z) W8 S5 iint nextp;8 u6 ?( b& l8 ~+ H; y
}link[M+1];4 A9 p- a/ D/ i) B
+ D6 M2 ^/ I) K7 R
void main()
+ ?4 z# }" u5 J# w. T  q7 q) M' ~% w{int i,count,h;4 e6 L; k. Q( p6 N6 A5 C
for(i=1;i<=M;i++)) C7 o. _7 Y6 e# L, R; A8 y
{  if(i==M)
0 A7 }) s8 V2 Y: C9 J! l+ H9 s. o   link[i].nextp=1;
+ {. {, b+ ]) }. Y  G" P- a   else- q0 l! v4 ^) L$ Z. O: G
   link[i].nextp=i+1;( [* W* S$ `5 |
  link[i].number=i;/ s+ ~9 O+ I1 a. t; d5 Q
}
, G- r2 ^0 Y: g( L( c0 jprintf("\n");9 v. w* n8 ^$ |$ s# i& n- C0 @
count=0;  P0 u: \' ^- Y6 v$ ^
h=M;
, L4 Y" M5 o1 I/ L4 [$ Lprintf("依次退出的猴子: \n");
5 u; T0 L& J4 Lwhile(count<M-1)
4 m, ~, T2 r: h6 c+ u% v7 X{i=0;
! ]. a0 R' q  \3 y9 \while(i!=3)
& W3 D* @$ e4 F$ w3 m' M{ h=link[h].nextp;9 ?8 T4 ]7 z# x" ~* g. t' f- r. \: H
   if(link[h].number)0 Z/ \; |4 s, y6 p* z* M5 y
     i++;}( [( F- I" ~# G: B

6 s+ l. L- \2 c4 a# Jprintf("%4d",link[h].number);
, S. d8 n! B) I8 r  \- mlink[h].number=0;9 i: L& }( S, g, e
count++;% D4 O" P3 B7 L3 T1 f8 h% \. X
}
2 p8 n! `7 x4 }2 Z
4 B% k) A, c5 N1 cprintf("\n大王是:");
: W; T7 K: L2 M! }. V  for(i=1;i<=M;i++)
/ f4 I+ H1 W; G! [8 b3 {  if(link[i].number)
: m! x/ _$ n) a; q- M; l9 ?    printf("%3d\n",link[i].number);$ S3 [% U* P5 d8 {
+ q- C. z9 F/ s  Y( d2 V+ w
9 `) D6 b. r& J
}

! P3 A6 \; C! B; m) _( ~/ T2 ]4 [第三种是普通方法for循环

; s  W! ?  {) g4 Y#include<stdio.h>$ V9 _5 H4 r# {; R4 c( w& b. G
void main()5 T% t7 K# d; H! g" a. Z
{ int i,k,m,n,num[50],q,*p;2 q8 ]- b4 \( a8 h$ l. t
    clrscr();7 m8 y' E' }7 i% J* I0 H
   printf("input number of person: n=");" P9 g2 j; {: D" N/ n' [; K
    scanf("%d",&n);  n) w, Y. I% z0 i. x" k2 s
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
4 W) G9 U9 I1 u' S, j5 w  T    scanf("%d",&q);
  R4 O6 ^9 }1 X+ i4 R; h   p=num;! \/ d  @2 q% X4 e8 {
  for(i=0;i<n;i++)
* R9 b; k9 ~* l. L2 n3 L    *(p+i)=i+1;
/ G* I: I) S* }) I3 E   i=0;
$ a$ Y- N0 o* W+ U8 u   k=0;. I/ }/ [4 q/ ?6 `
   m=0;
4 ?9 c& W/ y% v" y  while(m<n-1)
9 x6 x- h9 u, h( X   {if(*(p+i)!=0) k++;
' q+ r1 g, i2 n# O0 s* d     if(k==q)
" o" L- }! U  c5 c- X7 ?      { *(p+i)=0;
) J2 N: y  T0 d" T" D        k=0;& I+ T! e  q9 y1 a$ U: B% j+ V6 q
        m++;/ e0 F- C" D2 ~  r
      }
5 {0 R* X: {; y* s( ^9 W- v3 A    i++;! @" s, q2 @  u# A% W
    if(i==n)i=0;
) E, g# U- v0 D- r   }
# P1 y: ]- E4 e) C; U2 a$ Y  while(*p==0)p++;. P; C/ `2 Z, r1 C/ _7 \, ~
    printf("The last one is NO:%d\n",*p);: x2 J% Z: t) |8 N7 ^2 x
     getch();
' X# _. T7 o% B: q+ `! p% p. y- u0 C  \1 G/ R5 H% `, F
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
; B! f2 X# M1 ]" j8 G# e2 [  Qnamespace 又费马达又费电( L! R- g. j. b7 e. I) ?
{
+ z) }# H  {& t3 j4 ?8 W    class Program" D- p3 h4 T* p4 _+ A, i5 ^+ g
    {6 A: m5 ]/ e$ Y3 O$ O  u9 v
        static void Main(string[] args)) ]2 _# M$ ?5 P- ?1 c5 p0 P' m/ A1 A
        {2 N! h% X/ b7 ^+ z* B
            int m, n;: k1 S+ v8 b& y" k' I1 l* Z
            Console.WriteLine("请输入数组长度");
9 h' B* Y" S% M" O8 h# ~            m = int.Parse(Console.ReadLine());//m为数组的大小
5 P3 j- K/ s+ H' G' v' N! L5 s            Console.WriteLine("请输入要截取数字的大小");
/ P( C- B/ r6 D* K# `+ @$ t! {            n = int.Parse(Console.ReadLine());( h3 z, d$ \4 `) i& I3 X7 `
            int [] numw=new int
4 [! k" k" q  F6 J6 M* T* f
, d2 k" i7 c* Y+ J" L( G$ b&shy;&shy;&shy;;
4 |: v+ m# N1 N* M# T' `            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数: z# s1 n5 _2 `; S8 B
            {
/ B2 o/ Y4 P" z6 z7 ~# U                numw[j - 1] = j;+ b5 @7 X: I( S6 G, W
            }# j, D/ ]% n# s+ {" C% @
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!; l$ Z  j+ M! m
            while (d != m - 1)
! H7 T1 G& w1 H# M% h9 _* p            {
, I$ c; k: I, Q. R% Q4 d9 u9 ?                if (i == m && d != m - 1)
. h7 e/ V2 V6 B1 m/ f" d                {6 m% d: X% |2 ?# _
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!% _# K# Z3 u7 ?: Q: H/ x/ K
                    continue;
% Q( p2 F. R# A5 Y                }
8 f" Y, M9 q: ~                else
. ~% X& M% q  E! [8 Z6 S                {
+ p( R' G- D9 d  \/ a                    if (numw[i] != 0)
2 A5 {; v! f, B" B4 w; j# S                    {
! N0 s; m: Z6 E7 C* V                        i++;
" r" K5 ]. W, i9 A# g; G                        k++;
2 r5 c3 M6 P# M                        if (k == n)* s5 M  }$ ]1 A" N# R8 y
                        {
) ?! a# C3 o. ^: y+ Q+ l8 r                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
+ X3 B* U% l7 ?/ w5 `9 q& L# P( s                            k = 0;+ @5 q3 q  ^" i# p' w' E$ f% G# l2 A
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
7 B) ~  w' C) y6 D( U8 A                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
. _. d7 r, i% L4 Y; G                        }
2 H, k% r* t5 L& L, |                        else//输出暂时还没有改变数组元素的值+ @% Z% N! c8 p4 C$ G
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
  ]8 \$ f% a1 S+ S% A. i                    }
" ^( g7 L! h3 t8 l: O                    else  t8 y' a8 m! t. U0 U: D; G. b8 w' N
                        i++;//数组元素为0,直接跳过,不计数。。。
. }7 x5 z+ q# R  r2 x                }
* Y* L6 w0 P) f2 w; t
' R7 y1 U% [" N  g3 u3 O$ \" C- G4 Q9 u( r  K1 g. E
            }//结束while循环' z- s* O  j: P- a. J/ w; s5 y
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦6 s  T$ x: T/ d
           
! P! e  g& }% `. G# ~                if (numw[i] != 0)& q$ e0 \0 z; W' B2 C
                    Console.WriteLine(numw[i]);
+ R& v6 R3 N0 X/ m           . o0 O) ]9 [# g6 ~3 ?6 Y6 V
            Console.ReadLine();
9 [( V' U( b) Q7 V3 l/ d2 B        }
( l! H# s: q3 b9 s- i! E7 \    }
7 _/ K1 Y/ w% Y) X0 Z$ U4 N}: I7 K( m+ o% J* C6 _! ]4 r6 \+ M
小甲鱼最新课程 -> 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, 2025-10-13 06:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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