鱼C论坛

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

猴子问题

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

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

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

x
大家好!/ k# A4 u2 f4 K' J; ~
这几天我在忙着编一个问题,我用了一种方法编出来!9 }! X/ q% l0 a: k% Z5 e, i
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!: _$ A6 V! }+ U2 l& K8 E( O
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 $ y. T" ?+ N! r1 r5 w

8 c7 e0 m1 B, }* p& x
, G1 n' e7 P% Z
                            题目
  `" i2 x$ p8 O2 G& h山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。9 F7 p7 j  R, c
第一种方法:利用循环链表. P0 M$ J: ^) F  _
#include<stdio.h>
/ f- }) J0 J* f& H6 ]5 r#include<malloc.h>4 z) k3 G5 _) a$ K' X( H0 p% E
#define M 8            //共有8只猴子4 ^& j8 P4 I: t1 I  z% T
#define N 3            //数到3只时退出第三只; b; v2 x( q. [7 @& Q  p
typedef struct monkey
# N4 ~, N2 c3 X; ]: y{int number;
: \, K2 e* ]' x3 R1 qint flag;
  X% X8 s: Z( T5 u- b# `' V" ~4 Fstruct monkey* next;2 M# F1 Z+ c0 g  S4 }
}MONKEY;& p% `2 F9 K( S$ d7 Q
main()
# w, A! a" Z& F- b+ |  U8 t6 m, X{ MONKEY *head=NULL,*p,*s;' T3 m' N4 j# e/ f/ ?. |1 B
  int i,sum=0,count=0;& E3 i6 x1 M( y3 X4 f  T
  clrscr();              //清屏; C( S$ Q8 B! W) X1 {7 Z
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存8 o" t& G5 U/ u
  p->number=1;p->flag=1;* @0 }+ {9 Q  D. [+ h( d
  p->next=head;
) Z! J0 ?9 d: U8 a/ c' G  head=p;* v6 M5 G+ L( d& g& W* M3 \/ R) t
  for(i=2;i<=M;i++)9 N2 z! x- Q- ^4 g' w: M. }
    { s=(MONKEY *)malloc(sizeof(MONKEY));
9 B: `9 a3 }. u" b: j$ C     s->number=i;s->flag=1;1 H6 _$ A6 h( m! e; Y: E
     s->next=head;/ P: W; T" e7 l% k* u
     p->next=s;p=p->next;
& e; r% h, v& [. `. M    }: @$ h0 C+ _4 Y
    p=head;- c2 i1 T4 s4 \/ y: W. F! {
   for(;;)
: z) R" L$ Z2 [8 t! h7 n2 w4 {    {if(p->flag==1)
, O  P* G- p3 ?8 E7 _8 J       count++;; R9 f7 t8 e; F5 T  b; ~
     if(count==N)0 w/ c6 ^& E- l' B) d/ q
        {p->flag=0;* D2 [2 f5 A, V# c" }" `3 |9 g
         count=0;
/ U; f) m, G" @         sum++;}
& j+ k: Z& Z' o4 C% [. c# b; n9 r& A     if(sum==M-1); d3 A6 p! a) A+ y5 S! {% X  v
        break;! B9 Z% G# L$ d# m6 j
     p=p->next;
0 g: j' Z1 I4 u    }$ q6 Z( O5 P+ l9 ^5 j% e' ?4 Z
    p=
) x2 N8 F0 [. G3 C8 N4 |9 B; F6 F1 m    head;& F/ h% v0 a3 J; y$ |
    for(i=1;i<=M;i++)/ S. t! s+ m( P7 y
    { if(p->flag==1)
9 A5 W( A' M5 u/ Z8 I        printf("\t%d",p->number);
0 x" K( }5 D, C; o2 D      p=p->next;, a4 [- u- X8 C/ d8 k
    }7 D6 i* S4 G! ?8 P9 }2 X' Q* [/ c

  z9 ~$ \& f! P- A6 K* R/ m2 s- A7 v" ~9 ]4 \+ a, G& ~# o2 X

( k  s% h. L5 I) |}

7 _! ^8 e( a! T% H第二种方法:数组/ r4 P- m4 w+ \% z5 ~
#include<stdio.h>. h3 ?' ^. ~2 i- c9 P4 d
#define M 8
* ~6 L% x+ B, Q2 d( k4 Dstruct monkey: k# p1 x, F9 U& _+ T# Y
{int number;
- b; T7 }% s( ?int nextp;. X, d7 [6 Q  ?3 A
}link[M+1];) x6 z: ^- X" w, \& ~2 }

7 L6 g) D7 @6 p+ a/ Jvoid main()/ q8 V6 t9 w$ o
{int i,count,h;
3 S1 i/ B0 @2 F/ Cfor(i=1;i<=M;i++)# P. W  j2 A% H$ Q2 b! l: f7 O& ?
{  if(i==M): }. |. ?# u" Y2 k8 z8 y2 e0 ^( B
   link[i].nextp=1;; N/ _0 ]- B. J/ z' R/ ~
   else
# G* T" U& _$ g# u& J   link[i].nextp=i+1;( V/ ]7 j' O5 L& h" g, I
  link[i].number=i;
  c. @' y1 V4 T6 e! V7 t' {. H}
: ~4 n3 j5 }- hprintf("\n");  @$ {( s$ a7 t; I8 z
count=0;) T8 V6 s: ]! r: Q/ M7 F
h=M;9 M2 w9 [9 t- F+ L% ]
printf("依次退出的猴子: \n");: e4 B! G( v4 N  g! G8 F
while(count<M-1)
0 P! h2 U. p$ J, b% f{i=0;; y' ^. p+ W+ r: g! ~! u1 ~
while(i!=3)
" q0 R' Z1 ]. p4 |{ h=link[h].nextp;( k0 b4 }& q, n/ _5 S: s
   if(link[h].number)
( T! D# j" B; O; c3 |     i++;}9 l6 x) d) [5 a: _* z! m% ?& V
5 @6 B8 w5 O! c$ b0 f# w! C
printf("%4d",link[h].number);
! r& l, k; E8 i' E  k  Y9 ]4 ?link[h].number=0;
, }" b) J  U2 q1 \* \) ccount++;
  w# U9 w2 a% F( C' ~6 X8 s}0 X0 E& v8 R2 |. s, {- H

6 `) d4 G; s9 x6 a4 I/ Yprintf("\n大王是:");) k+ g2 O3 P  K' Q
  for(i=1;i<=M;i++)
- \8 U- \* M/ \4 g, l' _1 m3 d  if(link[i].number)
: W, M. h# j- U    printf("%3d\n",link[i].number);! m( o& n; {. t3 ?" H" i9 U( i

- N7 T+ S$ z% A+ D
1 F$ T" J* y" M8 P( R& j6 E}

. g4 }! ~' P  F( x; l4 P$ x第三种是普通方法for循环

0 k" Q( p( c* n  [  M4 ]! w% Y#include<stdio.h>4 t2 Z6 O5 I: C$ ^
void main()% k( ]7 d! {9 t" }1 F% M
{ int i,k,m,n,num[50],q,*p;& p2 r: {- A; D: _  h. n9 O
    clrscr();2 T" |! q: D9 H0 m8 A% p
   printf("input number of person: n=");# v9 v& d& S5 {8 _% b4 C. Z
    scanf("%d",&n);
2 {) J( U0 \2 n7 K% U0 ^$ Aprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
, C6 U, b" u/ F5 t    scanf("%d",&q);) p( f( V8 y3 H4 z- M
   p=num;+ N6 k* X% t# w2 H) ^
  for(i=0;i<n;i++)% R& q+ E2 R6 f: W1 m" |0 j/ r& }
    *(p+i)=i+1;
. U  Q2 s" k7 b- K; q( ^   i=0;0 ~. k6 F. z) s1 v# {- @3 k
   k=0;
# R) X& c3 r/ K; h   m=0;
+ _1 E( ^1 s, F% K" w. p  while(m<n-1)' o. y. _# u- |  \, @- e, B
   {if(*(p+i)!=0) k++;! c1 f1 `$ ?$ l. N  Z  n
     if(k==q)+ j& K2 y, q7 J$ K! `$ c: E# y) R
      { *(p+i)=0;1 _( r7 u- |% |& N8 l
        k=0;8 o6 S# e- f( j
        m++;
9 q8 b, B& _9 H: c" M5 N% c1 h      }1 F; K% }& R- B% k# d
    i++;
- i, u& V: O  T' k; Y7 G8 E3 x+ O4 S    if(i==n)i=0;5 R7 h2 \2 ]" t
   }+ }* _* Y: l# z% d6 y) d7 G
  while(*p==0)p++;; ~+ c( s7 A8 E. O0 u; [# y
    printf("The last one is NO:%d\n",*p);
% S0 ~6 ^& H) S2 e5 Z. V+ h     getch();0 d, |) S) F- t9 U+ {+ ?  g/ _

& i* u0 x' n# J- c: n' F. k* A}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
3 b* v: ?! R' P  A5 ^5 Tnamespace 又费马达又费电
/ H; c; M1 Q3 s; f{
7 P# w- a5 F& B9 _& W: h! K2 M" i    class Program! C! V8 J" c! y- U1 k$ d) h
    {( u. _" v. I: b" L
        static void Main(string[] args)
7 L) ]! q* a0 R# b( S- ?  J# }        {2 |+ d9 h- j) W1 S2 a
            int m, n;( u" Q# j9 B- n! [
            Console.WriteLine("请输入数组长度");) C- f: e" Y; _1 K' I1 h, y$ e
            m = int.Parse(Console.ReadLine());//m为数组的大小7 e0 Q: P8 Z" |' O& w
            Console.WriteLine("请输入要截取数字的大小");
0 H  T% b; c$ N1 j: i( T* x            n = int.Parse(Console.ReadLine());& q  v" d* p& _" h  J8 s( u* C
            int [] numw=new int0 I( _) ?3 D0 O. }

& q3 D7 @6 G  c% d7 `8 F5 W&shy;&shy;&shy;;3 d( l& u# _! O' d6 Z! H1 d, r2 C
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
0 M. ^/ y+ r* C            {
# [& e4 i' t7 \, ^0 [                numw[j - 1] = j;) a. g7 `" v% I0 M  c0 b7 `% _
            }0 ^/ M, n$ [. c" Q0 S
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
. Y  S, A2 L' l% l; L1 B$ @& D            while (d != m - 1)
' R# o/ w$ [7 o3 z# g- M. h            {- H* K& ^, J; i# f4 ?
                if (i == m && d != m - 1)
, h* t  d( ^8 E, L5 r" S: Z                {
5 I5 A2 L) a7 i* K/ s                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
" i. y1 k% l9 P& O/ W8 s                    continue;
: H8 c2 x+ B+ q9 ~; p4 M- e                }
' S" m. I9 d2 w, l% m! L" ?                else
" J: _- Q) F: j9 Q; r! ]- U6 [                {, f6 @' p* |+ f6 P& e# K( g# o" K8 w
                    if (numw[i] != 0)
* }. U; z. R/ I! k! h- K                    {
+ V! b7 k5 h: B5 A                        i++;
# I  C2 F' z/ E# j* {                        k++;9 Z- \! ^# f) i6 f: [6 Y6 Y
                        if (k == n)2 ~) Z) W/ Y0 _' x5 ^' C
                        {
. n/ A3 K+ j) P$ c3 c7 E                            numw[i - 1] = 0;//把在n位置数组元素的值改变了; D& e: Z+ ^+ U3 T. O
                            k = 0;
& B0 W. Q) l; l1 r; x              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小12 \! x( R4 b6 D3 Z( }1 K
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);( x- t" C( D7 p( s( H
                        }  z' }0 `. n- H
                        else//输出暂时还没有改变数组元素的值
2 V; L. I- B; L" b3 e3 q                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
1 o+ ~' H- y. D4 V# e                    }1 O. g" T- D0 K8 n+ Q
                    else
6 Z8 U6 q, ^( u5 L                        i++;//数组元素为0,直接跳过,不计数。。。) |! m* v$ \( W
                }0 ?0 N0 y7 U" H

; J6 Z4 [- ~, Q9 q! b8 v. R; }6 v- U6 E2 a+ }& @+ |' G- u0 k4 n
            }//结束while循环( A) ]# C8 ~* {0 e" w. V9 Q5 X
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
3 }3 f$ l& c  H/ H& a6 W( E5 S           5 \+ @( w+ Q; c
                if (numw[i] != 0)/ w4 ^# W2 i; g& b; n! ^- W+ ^
                    Console.WriteLine(numw[i]);6 C+ h/ l* r, b' l& r
           
. y1 b& \3 t- Q" W0 v            Console.ReadLine();
2 j0 v5 I2 B( @9 J        }) z9 L9 J% F0 w- R5 N# b0 n
    }
* m9 b  {* f1 N}
* W/ o& u0 ^+ G' A% X, A  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, 2026-1-14 18:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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