鱼C论坛

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

猴子问题

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

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

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

x
大家好!( O0 X6 v6 O- T
这几天我在忙着编一个问题,我用了一种方法编出来!4 \  X( O% t- M( ]; R
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
. L  h& ?1 l% v5 |- _2 ?注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
# V$ t8 C; u) F3 S( s) u
+ Z) Z( v& J  {7 Y4 G9 a
  d" }! q) c) h  `
                            题目
4 A( z3 [, X' X: R9 b7 ]山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
3 |& m3 h* ]2 U* _9 v; @0 \第一种方法:利用循环链表% x) p2 `3 k- a" D/ ~
#include<stdio.h>$ K3 ], Q2 t( i- a6 o
#include<malloc.h>) H4 A. l4 n% \6 i. v
#define M 8            //共有8只猴子
" Q& ?2 F+ h: c" v% j" v0 z#define N 3            //数到3只时退出第三只
+ V' P* Y0 K; `" G1 P6 _typedef struct monkey
" k4 u  h& D0 g3 P8 _' _! k3 V: ?{int number;
9 @; t8 M$ S( ^: S, pint flag;
8 @' c- x/ k0 X6 S# }struct monkey* next;
% Z3 z/ Y- W0 b( C- c}MONKEY;
. y3 c+ ~) W8 mmain()
2 n$ [8 q0 e: P* ?( c# f  l& V{ MONKEY *head=NULL,*p,*s;3 ?  g* Z7 x/ c# w; U+ N. p
  int i,sum=0,count=0;
8 L) ^# Z1 y/ q8 Q0 v& n  clrscr();              //清屏
' ]2 x$ @  V! ~9 V7 P  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
% [6 |0 d6 S* v4 @8 K& a: Y* e  p->number=1;p->flag=1;+ c& g  v0 R0 T2 h
  p->next=head;* w( {7 k8 r" X
  head=p;
; c0 C. [- j! p! V* h& @' r1 G  for(i=2;i<=M;i++)
' Q$ u3 `: ]1 P% m    { s=(MONKEY *)malloc(sizeof(MONKEY));% S& y# z: A& K* R
     s->number=i;s->flag=1;
  Z. \9 e: _4 }% ?     s->next=head;. n+ V/ Z" g& J- g. v" Q$ F0 ]* J# g
     p->next=s;p=p->next;: d( _- z+ o; D9 l$ T; [
    }+ r" W, H* [5 f1 T, G0 k8 R& s
    p=head;) K3 Q# t( k2 I; O# }8 a( T, d
   for(;;)% E2 N  g3 e6 ?) r# `( J
    {if(p->flag==1)
! S* A2 q7 x/ P       count++;) G. J+ L3 L' h+ b0 g: p
     if(count==N), E' {! E9 X& y) K( |
        {p->flag=0;
5 i  b2 o% Z6 g$ t; U" Q         count=0;7 r! q, {' X- x+ Y: f$ ~
         sum++;}
: X6 t/ f0 H( ~" H: N7 j     if(sum==M-1)5 Z9 c4 B  ?. k  I' E) T, B
        break;1 Y  c. E: B% s4 V: C
     p=p->next;
' w" A) D1 c& T+ Z4 ^4 Z% A    }9 Y1 H' B. Z# A* ~
    p=2 Y' Q, c: c" x" p
    head;
. X/ O% t6 w. R1 |) x5 v( G    for(i=1;i<=M;i++)
: w" Q1 H/ C$ ?9 f    { if(p->flag==1), s2 f7 H. w1 _. M* ?" I
        printf("\t%d",p->number);
) p7 g& I1 T. g+ w      p=p->next;1 _( W9 m5 C7 \) {! m4 A$ Y1 b
    }% n' e0 D6 e1 G/ S& C: f0 J
2 T  E* u) R2 P$ C  M

5 M/ q2 c; T; I4 |+ S2 H9 F0 y- S( R, a! i5 j6 k8 U  M
}
$ b% ~% }3 J. h3 n5 x
第二种方法:数组
' _1 q& _* W& k$ {2 H8 w+ p#include<stdio.h>
3 F; q' W) ?: O) m6 y9 ~2 ?  D& h#define M 84 b( [) h5 h: c( c# N8 }
struct monkey
0 o& N9 g, g: o' G2 ]# i{int number;
5 S4 p" x6 W3 l/ H* j8 eint nextp;& Y1 n) H: i* d4 K
}link[M+1];' ]1 h$ I" _$ q0 t( n
6 ^! [/ X: L( O9 _/ _& A
void main()
$ Q+ E6 h: n  `( x7 D. ]{int i,count,h;; _9 r: Y7 A1 U6 N' n6 F
for(i=1;i<=M;i++)
/ _4 c; |4 z) n" w{  if(i==M)
7 w# D% x+ T$ n+ {1 N* |" l$ ]   link[i].nextp=1;1 ?# a  Z% U5 ?$ W2 `6 G3 ~" S  Q
   else% l' q" E) m3 I: e0 \
   link[i].nextp=i+1;- Z0 n! O) |  O# N
  link[i].number=i;: V- Z/ w- _; T% J) {# K
}: j& K; e2 E' L  Z! v/ x
printf("\n");
7 l. W7 S0 Q5 O/ h& U# {count=0;# I. f8 Y/ u7 q" r4 y3 T/ n
h=M;
- U$ u! ]$ |7 W  K8 Sprintf("依次退出的猴子: \n");: A9 L# \! G' v
while(count<M-1)
' x% V* N: l) q& b  C6 n( t{i=0;
2 y) m) }) f2 v+ g% ywhile(i!=3)( ~% k* x  x3 J: D) e
{ h=link[h].nextp;
1 `+ r! C: O/ F; g* |   if(link[h].number)2 [6 \) H* B, D% o( b
     i++;}
% U, j; P8 ]( v6 }  d6 s# w0 ]& E3 ~2 h1 P' n/ O2 S+ x8 Y  b! e
printf("%4d",link[h].number);" B0 H: ^( N3 K$ u) Z2 c# ]
link[h].number=0;4 \% z5 p+ T3 a4 [
count++;6 e. ?. C* ]# [& N0 Q
}
: @3 P: E5 B: D) j& S  n# d& ^3 D, ?9 u) Z) j) E6 Y3 B
printf("\n大王是:");
* R8 Y, U9 W1 Q4 ~* w& X- U7 x  for(i=1;i<=M;i++)
( n3 K6 O; r1 x1 y  if(link[i].number)
7 w/ _( Y. v- G: s& A! }    printf("%3d\n",link[i].number);
  N( W# T+ f& ~" T3 F, D$ x, [4 O) N8 p& X* q" e6 n

/ m( P9 }/ _6 y( r" s. @}

+ k; Y7 s4 b+ m( H( ?第三种是普通方法for循环
& S5 X$ v3 [+ V% Y/ k4 b$ a/ x1 a
#include<stdio.h>
6 ?, O9 t; c' q6 svoid main()% r3 w) S) n5 d8 d- y% m
{ int i,k,m,n,num[50],q,*p;7 _0 E2 o' s6 S  U: x
    clrscr();+ q6 o; N4 v; w% F3 Q& u) y
   printf("input number of person: n=");
5 G- m1 G% G2 H( D3 H" ~    scanf("%d",&n);
* k% Y  j! j& ]0 [: Vprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
( D. v  A! l* w4 O! ]    scanf("%d",&q);1 L. e$ u2 \* Q4 O' I
   p=num;3 D* q$ C( P  G. E# h
  for(i=0;i<n;i++)
6 [  l: Z, z# H6 ^! F2 t    *(p+i)=i+1;
9 u" p  t: j! s( W$ e6 d   i=0;
0 n" ]/ b8 W6 z' Q/ b8 {, f4 ^% ?   k=0;3 ?9 ~, H5 M9 W6 ?( g0 i" k# D
   m=0;
) R* [; f1 J. U+ f  while(m<n-1)2 f  V+ v9 x: H$ D" H8 g% O) O
   {if(*(p+i)!=0) k++;
  q: o* X  x; }( x; I     if(k==q)& i8 Y7 c: j' h- f' j9 ^3 k
      { *(p+i)=0;
0 @" Y3 U' b, |; N        k=0;
- S- E8 k8 i( |8 s- k7 M        m++;3 N( W, j; o7 M0 d+ p; ]( ^
      }
7 V/ y- @9 g  U- A) c    i++;
! ?# W2 ], R" A' [2 l8 T    if(i==n)i=0;
& C+ v5 P3 y$ C- u3 t   }
) d, p* {" x' |) O- B: [  while(*p==0)p++;
: c4 I1 Q9 `7 S* |; P: ?    printf("The last one is NO:%d\n",*p);6 i7 Q  q( e" o; T0 k2 A* I/ [
     getch();
7 S6 ~- C4 O8 U3 z4 W6 }
, ?, q5 H6 |# ]. O2 |, P- V# Z}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
7 m/ e5 `( m; L2 x* tnamespace 又费马达又费电0 i! V3 u, L- u$ v- e
{
0 \1 f; T4 C' ]. @" p  A0 `    class Program/ C. r+ \  C# I3 K
    {4 G6 j& v! r$ Y& B, \
        static void Main(string[] args)& d. q/ T) r" a% `- f2 k
        {
: Y; v# O+ `/ T2 n/ t            int m, n;
  O  F3 D+ u9 }9 @  X/ A            Console.WriteLine("请输入数组长度");1 [! j( v# a6 e* N8 Q, |
            m = int.Parse(Console.ReadLine());//m为数组的大小3 G" M" U% K& S
            Console.WriteLine("请输入要截取数字的大小");
8 ^( Q* H; M: p; l7 L' {            n = int.Parse(Console.ReadLine());- c+ k& `% j7 ?$ Y4 F
            int [] numw=new int3 P! r, N% @6 }- R( d7 a: }5 z2 r3 U
. W6 o$ P1 s: _
&shy;&shy;&shy;;
6 F5 D7 M, G3 P            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数1 M3 g; l3 U. t
            {' \  V4 g& y# E
                numw[j - 1] = j;
  P+ p" F( J/ q1 a1 U            }+ z; D+ B; i) b6 K7 x' C
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
0 C+ s9 d* K0 B            while (d != m - 1)
) W" ~, x7 f9 ^- C4 `. m, K0 ?3 I            {1 J- a5 U+ S8 B* d
                if (i == m && d != m - 1)4 \' q% u$ n7 K! q0 \- v0 R7 R
                {% S. S- D, H$ }4 y( x; t
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
7 }, n/ a: c, O, G. Q                    continue;
! t  F6 b/ r& S" p( }                }& T: @9 @2 s5 ^1 Z0 H4 T. q! U
                else0 @: G7 P% f2 I) C& a& [( `( G& N
                {, S+ d& Y1 K" b. \/ U( V
                    if (numw[i] != 0), W3 A7 a+ h0 q; d4 \) O' y* l6 B" u
                    {4 o0 p$ u8 t$ z/ x
                        i++;  L$ Y( t  t; h$ n) }" C
                        k++;. B2 r: c6 |7 d( y, w8 I) B
                        if (k == n)# P: Q& z3 F6 b
                        {
# f& l+ I! C/ M5 i/ Y                            numw[i - 1] = 0;//把在n位置数组元素的值改变了1 w% O% f+ U( x3 U9 f1 Y; ^/ K
                            k = 0;
4 W& e# F/ S9 P4 F* q2 D              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小17 o% b" l" S# o0 q8 H  n. ?
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
/ g1 B4 k& o- Q" |, d                        }! \  `9 G5 v7 @  C6 V4 I
                        else//输出暂时还没有改变数组元素的值
; t: ]9 G8 E7 j  {3 q3 i% U0 d/ D                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
5 {6 ^1 Z6 ~% T8 c                    }6 C* A5 F. `3 r' R
                    else6 O$ \  I) D4 @  c5 X
                        i++;//数组元素为0,直接跳过,不计数。。。$ e/ Q% [/ Q1 V+ g9 F! ?1 K
                }1 A- W- @2 l0 \. r7 [5 t- Y

& b6 Z4 e5 @) I9 J7 W0 }0 N8 L& T8 O# C
            }//结束while循环& h- a+ }2 r$ U% B* j2 \$ [% n0 x1 `
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
- R0 t# H/ B) I/ a1 _3 E+ T7 R7 N           
" {1 d: I5 ?% J, ~                if (numw[i] != 0)$ v; N. x! C' H% S$ @
                    Console.WriteLine(numw[i]);! \& r9 m/ |3 u) q* |3 C
           
2 @% z# P1 V. V& v8 ]/ J            Console.ReadLine();
; l5 e$ n( c( B* |% h* u0 q        }
) e' ?. R9 _; Z+ y. G! n9 S: x    }, B! K9 p% P4 ?% H- X" K
}
9 h  `% B: m0 i# o/ ]8 A+ _
小甲鱼最新课程 -> 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-6-13 21:47

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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