鱼C论坛

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

猴子问题

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

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

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

x
大家好!
  B% p. V! r. B+ e8 I4 U这几天我在忙着编一个问题,我用了一种方法编出来!1 i1 E0 R0 W, S4 |1 N! u. \$ M
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
2 w" S: z! t6 r% G+ f注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 3 g! S4 Z3 R7 A2 ]- Z  W

* C) b  y" Z3 X( ~; L/ f  E9 O1 C% q, h6 I5 s5 z% N+ L
                            题目
9 r  M; ]& D* A山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。. I; r) v1 P0 d  p8 J/ B7 l' K& l
第一种方法:利用循环链表
# i1 B7 q" l  q9 Q#include<stdio.h>
& O- ^0 p9 K; e  e7 W& ^0 X  I% E: X#include<malloc.h># T2 u! A, t( l- |" b/ t5 _
#define M 8            //共有8只猴子
+ Z) Z3 b* Z0 G3 n5 e#define N 3            //数到3只时退出第三只
# @, f$ d9 }/ ?/ \2 k  i- Ptypedef struct monkey
' n8 j) n7 S2 @, j4 r{int number;
8 l+ F' g+ a8 {( Y' vint flag;: A) b) Z) Y% |( @! d* J; p
struct monkey* next;1 F  z! M$ i6 ]( ]* N, Y" M; P
}MONKEY;8 D* ?  \4 c5 j" |" `& d
main()( U* d1 Z0 P7 f" E# ?
{ MONKEY *head=NULL,*p,*s;" e5 |2 s+ o$ [0 T' l
  int i,sum=0,count=0;; G# Q( \8 H1 M- V4 {* x( D
  clrscr();              //清屏" O, k3 c6 J: Q, Z( B8 L
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
" k, x0 F. ]4 b7 A& c  p->number=1;p->flag=1;0 B. v, O4 G: h0 Z* |2 x) o
  p->next=head;* d: p2 Q1 O  r) q: n% N; W- w* ?
  head=p;
* Z% Z! O- A( H& ?! p5 Q  for(i=2;i<=M;i++)
+ t' l+ U+ Y5 V6 s, n    { s=(MONKEY *)malloc(sizeof(MONKEY));) t9 I* E- x2 M, _
     s->number=i;s->flag=1;3 B+ r1 m& H+ @# R! Y5 i9 r+ i
     s->next=head;: U2 O0 @0 F* j) O& j2 D, Z3 }
     p->next=s;p=p->next;; j4 {. x* Y: W. F& e  b
    }' O) w- M: _/ k( P
    p=head;2 X" f4 L( P) u2 y9 k! p0 x
   for(;;)( P9 v; f6 D9 j" W
    {if(p->flag==1)5 W& i7 Q; _; ^5 X) Z
       count++;6 I) n9 O5 z- ~+ [, `5 o% t
     if(count==N)
4 F$ D, Z- N: T; K4 G        {p->flag=0;2 w" o' r0 a' b% C
         count=0;" S# L6 Q0 E" t9 s. H
         sum++;}
$ V* y: q8 I4 c- `& k/ D3 Q     if(sum==M-1)
6 g: H+ c" g9 I        break;
5 \0 N; @2 ~0 Q# y3 w     p=p->next;8 R9 B8 {+ L& v6 @- r$ V- L
    }
2 o' D/ m) u# u! S) R    p=/ o8 p, r$ _& X0 M
    head;! Q) N0 l6 D* |% M
    for(i=1;i<=M;i++)
) |! Z$ J4 J0 K    { if(p->flag==1)3 h& x0 K& r$ @+ U$ X6 J0 w) K; [. m
        printf("\t%d",p->number);
$ D, @, f: Q$ A" x0 y3 w1 i      p=p->next;& J4 H7 \3 |: U/ {4 {5 Z% n7 x% a
    }7 z, P/ q; b" w. H3 K$ X) N

7 e/ k8 L7 {! b+ K# B! y
* e2 H! R0 p6 Y  V! k) l4 O1 V% x3 y) k- s; Y: O5 [3 p* [- E# u
}

& w  v( P( n" Y  N, @5 @; z第二种方法:数组% V' A# P3 {/ c: h. M$ Q! M( _" b3 R
#include<stdio.h>! O8 ], y% q- E! l0 Y
#define M 81 a: J$ a' V7 F0 e* q8 ?. ~5 n, m
struct monkey0 ?. \5 O5 R8 g1 l$ M
{int number;0 \5 c, l0 \6 `- j% V
int nextp;( q$ u7 a9 H( A
}link[M+1];: R2 N& s7 o# ?$ U
. l( s" D) s$ n  \
void main()2 y) f  |! R  w6 J( W/ J& D3 H( }8 j6 Q/ F
{int i,count,h;
4 i& k1 A/ l% _7 Ffor(i=1;i<=M;i++)
: s, x$ N0 t, A: d! A5 J; S( t{  if(i==M)+ t2 l. m6 D/ ~
   link[i].nextp=1;' d% t( U& t- {) U& `( t% a; N
   else
% o. }. E6 V0 w: r/ N   link[i].nextp=i+1;
$ y/ ]( C4 P& V; T2 U% G8 Y. Y  link[i].number=i;
! V, ]; C2 _: `; X' D) E}
  `! f) Q0 T  D4 e! F6 ~! Pprintf("\n");+ R$ A1 i; |  M" [
count=0;( c* }7 K1 l! L5 V) e
h=M;
, \  [6 F% F6 b: |7 ^printf("依次退出的猴子: \n");2 f6 |) C! g( k% `6 ?
while(count<M-1)' o1 j: i' a  I. W% {1 [
{i=0;) `6 ~- L) ~& i, d) }: ^( R1 [
while(i!=3)" i* c; V4 S! d5 J4 o
{ h=link[h].nextp;8 p$ L! I2 R% M6 N2 n) k. G
   if(link[h].number)3 U& N6 }; d! }) @. }& `
     i++;}
0 l4 F" t& Z$ t  k6 s' w; A
; l) v( i8 I0 z' Hprintf("%4d",link[h].number);9 d* a6 J/ G) M" u* ?
link[h].number=0;' U/ b- N2 `) N9 m' i" X
count++;0 Q/ D0 h/ q  ]" Z& ?7 v4 p( F, C
}
( I/ x3 x. _: p7 p8 I/ A* z7 B& y+ S$ }4 y8 j1 {
printf("\n大王是:");5 B& w9 z: H# r
  for(i=1;i<=M;i++)" k7 r0 |# j* c5 G. G. s# i
  if(link[i].number)% K, B' F8 K. B9 ]' K0 _* b6 a
    printf("%3d\n",link[i].number);8 v' E4 D1 y  m$ ]# B5 i; R

2 ^2 H0 M9 L' l' O
) c4 ?4 {& F; T3 n$ A4 ]+ F% i}

( F+ b8 r- P% f; y/ i8 X4 i( W: o第三种是普通方法for循环

" f) c- `* n5 G! K% p#include<stdio.h>7 f/ T* |  O4 G: k
void main()
- J2 d; N) L/ U& N) y( T{ int i,k,m,n,num[50],q,*p;
1 r2 C% M3 G8 u& _7 `8 _# z    clrscr();6 N( G. u! p$ c# f$ V
   printf("input number of person: n=");+ Z* H) Y$ F: q% m
    scanf("%d",&n);  @( @1 z$ y8 Z. r
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只  a% n$ T/ X# Q! H5 }7 N2 u3 T& S
    scanf("%d",&q);
" j0 Q8 }" O; ~9 K4 P) P   p=num;
& H, a; Z8 s! e% [) R  for(i=0;i<n;i++)- G7 O4 G! M" c8 _
    *(p+i)=i+1;2 J% A. R2 ~1 Z7 A! c4 g$ {1 X
   i=0;5 ?: f& T' M: M3 g( u; ~
   k=0;
  M: e6 u2 ~3 N1 i8 D   m=0;
5 m4 Z. L& G0 f, z  while(m<n-1)" y, c8 s4 ^5 q1 d3 o
   {if(*(p+i)!=0) k++;' L1 D6 V* G2 l6 T" K( k
     if(k==q). A  P% e' Q# J- z9 M, ~; `( }
      { *(p+i)=0;( B6 S6 a7 k# G( l
        k=0;
; a4 @' L" e! l; b8 ^        m++;  A0 Z$ J) n- m" k. \
      }3 C8 _7 W$ K) Y
    i++;
2 P1 Z# F  E2 ]; ]    if(i==n)i=0;& ]2 m! {) i5 p
   }
6 ?) o3 T6 I0 R. ^) K" X6 A  while(*p==0)p++;
/ I& `9 ]6 L% ~2 u- q( U) {4 l7 Y    printf("The last one is NO:%d\n",*p);
. W1 {) V2 n/ a2 e: P     getch();
& R$ n$ i0 V* p0 _+ y* g7 t( r0 }) I5 l0 p" n
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;* h" h7 i( v9 c% o
namespace 又费马达又费电0 q1 U7 R4 z: R  d8 b
{
" k/ u: f( Q) d" D2 s: w/ ]" m    class Program
5 B" f2 u* \. V% u# o    {( W  P5 Q) c- \9 s# X+ ]9 B
        static void Main(string[] args)
5 ^% Q! r: Y' Y6 d* A        {% J+ X: g, K% N' Q! a
            int m, n;7 i  X: S* @3 ]
            Console.WriteLine("请输入数组长度");, }, P. g5 E& n; e
            m = int.Parse(Console.ReadLine());//m为数组的大小
, C7 x% Z% r$ W$ K! Q) u" l            Console.WriteLine("请输入要截取数字的大小");
6 P6 G. C" Z& L$ l; y( f            n = int.Parse(Console.ReadLine());
. z! V1 u3 ^. W' q6 i* U4 ?( u            int [] numw=new int
7 B) h4 s2 Y% g/ V! E9 }2 C2 F
# [* m1 X2 @& t- v&shy;&shy;&shy;;
3 ?3 X- x* P- ?3 F* D$ A            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
! _, `9 G6 Y2 c            {
( O- @6 o1 v- ]5 Y6 b9 o8 s: [                numw[j - 1] = j;8 F0 ?. s& W6 i/ R3 k9 ~9 U5 h
            }: j& `6 D" _) @+ c
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
: x% s# _* U) L" Y0 p, O  m' i            while (d != m - 1)
" ~8 r- [6 T/ V8 t# d            {# ]/ ^1 ~( P" n1 H: F. [
                if (i == m && d != m - 1)4 W% }/ f* B$ f: O6 G( Q
                {2 q9 L  t0 c$ k5 {" A+ r
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
# s; Y# \# o# y" A, I8 V                    continue;& b/ v! i5 I2 M( w1 Z4 K' ?- w
                }
* }5 Q3 t7 a9 f- @; u% j2 |                else" B& o" P1 |* `; L  y9 ^( N
                {
9 E% W) D3 t8 A( S  S6 Y- C: P                    if (numw[i] != 0)- G( ^  I9 ~: s0 h, e
                    {
9 F  w  F. v7 u; q# r                        i++;
1 f& ?- F- I7 ?; E) V. R7 F( N2 M2 A                        k++;
/ N( D. A- A/ p; P$ h                        if (k == n)7 N" `8 g, n: Q5 b6 C) P# O
                        {7 G( E; u! _2 p7 ]0 f/ w
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
/ j. R) r/ L3 Q                            k = 0;2 ~" |; e0 K9 M7 j& {, p& `! ?
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1  [. ?- f4 ^+ x) X! X
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);) k- y2 b, R9 L) x- K
                        }; K2 |4 }! o3 T: P% l3 p! A6 K) i: g
                        else//输出暂时还没有改变数组元素的值
3 Z3 ^  q; |# a$ P. G) t  Z; U+ {                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
6 m; M# Y1 s" P+ C0 W                    }
1 \  N4 {8 ]% L1 p' F                    else
4 g! n7 C& y/ R6 i4 g' m, Y  r8 i8 T                        i++;//数组元素为0,直接跳过,不计数。。。
4 F8 _7 T6 G; Y' b                }5 `/ a) }, c+ F5 K$ A; S2 }
: P/ z4 E) _+ x0 x' B. ?0 B2 j2 |3 R
$ r) {" b  V% ]
            }//结束while循环
5 ]6 u7 g6 }) q+ e4 x. u( K% w            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
. F9 y+ i: }. j. ?$ k* ^8 J- G           
8 P" s5 i  F5 h& H                if (numw[i] != 0)
/ s- H: e4 C& Q                    Console.WriteLine(numw[i]);* w+ [$ p. n! k$ o* `! I
           
& ~3 k. U8 K. c9 |  Z# a            Console.ReadLine();, K4 A, W9 D2 i3 ]7 c! }. ?
        }- M& b2 A5 C: u
    }
8 F. E' f: H! L5 _' Y" V}; h7 A& T, H/ w. y
小甲鱼最新课程 -> 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-2-22 10:22

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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