鱼C论坛

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

猴子问题

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

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

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

x
大家好!" j# f0 f& Y' h# V) ^/ P( A) h
这几天我在忙着编一个问题,我用了一种方法编出来!
9 s7 D4 H6 S, f. V但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!. a/ h& w: B- Q7 p2 T, h5 ^9 c  }
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ( T3 v) K$ ?" T+ Z' w. z! w
( e; R' b4 n( z7 v  M* |1 r: b

+ e0 G" h. w7 s$ k& X* B0 j/ {  ^
                            题目
  N7 _) r. K7 C' g% s山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。  ]- y- H7 d5 w7 f5 ?% t
第一种方法:利用循环链表' i) B* ^& c; Y
#include<stdio.h>0 r; m1 G  f% ~9 @+ i
#include<malloc.h>. S- M0 s  T# m( O$ u+ l: f
#define M 8            //共有8只猴子5 m* s2 t/ P% n# t. {
#define N 3            //数到3只时退出第三只
$ y: ?4 N% H( X6 t. j7 Dtypedef struct monkey
: r. i: G1 I0 ?7 q{int number;
' O& n2 p2 _# i/ N6 N  Q* O: P! rint flag;
2 X4 b+ ?% w* p( F6 Jstruct monkey* next;
* v0 I$ }7 F) Y- @- a}MONKEY;. `  D9 p  O* _! o3 L- E, N3 ~
main()
! ?' Q$ L9 o  j, Y2 G{ MONKEY *head=NULL,*p,*s;
+ Q& I# Z) m3 Z- n# l  int i,sum=0,count=0;
: q6 V1 x  F/ y% U0 D  clrscr();              //清屏
6 ~& d* A, n* H+ n  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
. z* R; z, F0 Y4 R+ ^  p->number=1;p->flag=1;
7 A& F+ t3 Y2 f* ?  p->next=head;
$ O6 f7 ~# m0 H8 K! F; F1 G: }  head=p;
3 Z/ y8 c/ a* P2 S: s4 W# t  for(i=2;i<=M;i++)
  p: O: T% u5 a& V) z- ]    { s=(MONKEY *)malloc(sizeof(MONKEY));2 R4 Z! g* K$ \! L$ u# k
     s->number=i;s->flag=1;( Z. }. X, ]: w# V$ b8 \) h/ T
     s->next=head;  y( q" b5 r0 y. p
     p->next=s;p=p->next;
3 j5 ~. t/ f$ i4 S' ?' [    }* S% C* ^8 I4 p8 I
    p=head;& U: r( O7 l) D. ?) Y( h$ M; u7 X
   for(;;). T- w: w2 `+ h# a" F+ W/ j% C& h3 j
    {if(p->flag==1)
8 ?- z6 t4 I3 \) G- }; _       count++;
  R( R1 i( a3 g: f  R0 |4 Z% r( ?     if(count==N)8 \' O2 \, i( x* o2 ?
        {p->flag=0;
+ o' _: {6 {8 g& |: \! ^4 z         count=0;
8 _. O1 N+ q% u2 Y/ b$ x         sum++;}
# C, |( s& {+ P0 [$ k# H     if(sum==M-1)
9 o& ^) U$ x$ g7 A7 x8 H! U        break;) \6 P) a4 f- V% b9 w
     p=p->next;
/ q$ I- |% F9 W( U3 ~0 V% Q) m! e    }. B5 E. _( f- L& `, ?
    p=
* ]+ [0 [+ M- I    head;* _0 O2 F3 O% h
    for(i=1;i<=M;i++)
# o5 {3 [" @/ Q; H& N# {0 R$ E    { if(p->flag==1)
. Y- a6 T% g- k, i& Y        printf("\t%d",p->number);( W, c+ n3 w3 x/ w3 Z
      p=p->next;
& W$ z2 A) p% k4 x  z8 i' }# b9 Z: }    }
8 [/ Y- y5 [3 h" X( u
9 p/ }/ a# T: e# ^. E  A6 a7 C5 v: ^6 T! H# ~$ K

/ O" R! n0 o* w5 T6 Q}
/ b* E; T. E" c7 |3 \) j
第二种方法:数组
% i' U: t4 j0 w, _#include<stdio.h>$ b, D% f+ _3 p  n# Y
#define M 8
! N+ j) g$ U/ p3 j( ?$ Y4 Rstruct monkey2 L( G7 k' P" D0 w% m
{int number;
. `( ^2 |* J+ s; [% m3 Q' Pint nextp;/ Q$ t% t+ S# K
}link[M+1];6 E$ f" ^9 L4 ^2 q' T! H# m

; t# p5 w/ K3 l# h' lvoid main()  C; `% h! k1 S3 L" m  P
{int i,count,h;
. ]! |+ i" O! {& lfor(i=1;i<=M;i++)/ [! @& v% f1 m. t$ {7 x
{  if(i==M)) S, J) u2 r$ U! [  g
   link[i].nextp=1;
! ~: w. L% }3 V" f' r  n   else4 Z% S& |' f$ T2 k5 \  |+ W
   link[i].nextp=i+1;
2 ]% Y" B" h7 q1 S) D$ s  link[i].number=i;4 R( ~5 l# d& F- K- _, G6 F
}4 J' E! d' p% n0 F' C
printf("\n");  O# C& `. l, }- m( q8 ]* ?: n
count=0;
# u8 `2 `2 ^( Nh=M;% a9 c: \. y! b2 J$ {1 D# P
printf("依次退出的猴子: \n");
" u2 @0 M& y  M7 y$ Bwhile(count<M-1)
0 z8 J, s0 k$ P: l$ G{i=0;; H: u, v3 n1 e6 d2 i2 ]
while(i!=3)4 |: s2 G* j8 x- {  D
{ h=link[h].nextp;: s) j8 b8 P7 k8 |1 S% |$ p
   if(link[h].number)# H9 |( x5 i. X
     i++;}8 Y9 K# B, A8 H5 V

% f" O+ R9 R7 Eprintf("%4d",link[h].number);; {5 b/ Q1 ~9 u$ U6 }( a5 W
link[h].number=0;1 s- D' D, R& y" t- z' d
count++;6 V/ q, {, ?5 @3 @5 D
}
* e+ i2 b+ J; h) J, K% u0 I! v) P8 @* I, e- z
printf("\n大王是:");3 x9 w' k/ j4 W* Q! m% c2 A4 G
  for(i=1;i<=M;i++)
9 U  D" v4 K- B" a1 R$ H9 c7 s  if(link[i].number)
; s9 l6 t# d  Q; v' G    printf("%3d\n",link[i].number);2 L0 a6 ]! a( I

/ X* r4 x, P4 H+ I  ]' Q6 `$ a: q8 W( L0 r6 w- t! B* X7 h9 |
}

; Y) n1 B- D; s第三种是普通方法for循环

( \+ `- \$ J: }! L#include<stdio.h>4 }% @% s+ h, d3 j8 d" Q+ l. b
void main()) g3 e3 H$ u% a7 C5 k
{ int i,k,m,n,num[50],q,*p;( k, f& l- P* J5 k4 t. o! b, ~
    clrscr();3 t- x, G$ w, |8 W
   printf("input number of person: n=");
% V$ u8 d0 K% k; Q$ |; ]+ g- G    scanf("%d",&n);- j5 b$ |( H& c/ L9 P2 x; V
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只) v# [2 `5 X1 c0 d
    scanf("%d",&q);
# U2 o0 G6 z& [0 f* r   p=num;" g+ W# c- ?* i
  for(i=0;i<n;i++)9 j& E8 U( `* s8 H" n3 d8 D6 `$ l
    *(p+i)=i+1;3 g  W, ?! w4 a2 ^
   i=0;6 l) ]9 v' `$ T( P
   k=0;; B" D: D+ R4 x
   m=0;; [+ J/ d8 c1 \4 q4 P; `
  while(m<n-1)! k, x( d' y9 ?; X7 K
   {if(*(p+i)!=0) k++;
3 f3 ?, Z% g% S$ @5 m& b  ~     if(k==q)
4 T0 x. A& g3 G: v0 b      { *(p+i)=0;# P" }& B$ n6 |4 {7 J
        k=0;
2 d9 {$ @0 n5 a        m++;
3 u) d  X" m, Y' e2 A      }8 _+ _; C7 H; n* s. ]8 Y+ H" s
    i++;
$ U/ m2 ]0 L  G8 u; C    if(i==n)i=0;
/ H/ W0 ?& J. f' V' o7 o/ w; G   }$ M; A* w5 W! R! m1 L5 ]6 {% Z
  while(*p==0)p++;
7 |- B( z2 {% b3 o( s' [# k" T% M    printf("The last one is NO:%d\n",*p);
: p! L5 ?# V6 e6 \" e% [! A     getch();% r) U# @3 A; G3 f. j. d

6 O; d/ H6 p0 A$ F}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
3 {, D5 L! i9 T5 _! Z+ wnamespace 又费马达又费电' A; ~4 m0 F4 Y3 [7 C  z
{
% O1 Y- I1 n+ ?# x6 ^2 m( o$ w    class Program
; V! C- q* l+ L. C, @6 e5 ?$ U    {& M7 H9 ~! f: G& Z  z
        static void Main(string[] args)! ~$ E# v' j( n1 u4 N0 B0 D
        {
  @2 V  ?4 A# h7 g" ~            int m, n;6 }. j* k+ d& v: G0 N
            Console.WriteLine("请输入数组长度");2 L8 X: l# ]# P& c4 V1 t' W
            m = int.Parse(Console.ReadLine());//m为数组的大小
( l: v  G, B3 V/ g+ H( N; B            Console.WriteLine("请输入要截取数字的大小");2 P+ W3 D  o$ c5 c) ^
            n = int.Parse(Console.ReadLine());+ U, [( R4 E: B& B" }4 I8 l
            int [] numw=new int; l1 R! J$ t' L6 T7 [8 U* @$ Z
* L8 w( o( D; A' e  F/ k
&shy;&shy;&shy;;
; `- u* A' a* B. B+ z7 _1 c* r4 l            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
) A' m  v* K3 g" ?7 ?, V            {
1 c# b: J$ _3 i                numw[j - 1] = j;
. |: P, {% E1 ~& J. M( d% t            }
+ G7 I- {: L+ [! w/ O            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
& f4 s! `( H' W6 N9 l0 C1 h            while (d != m - 1)
9 S- z  a" P/ K: J4 x            {0 k' X. y. Z& w3 e
                if (i == m && d != m - 1)
  r$ N4 a8 P9 v+ Q( o; \6 N                {6 J  K. _6 i) v* ?1 O" O
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!& @. T8 e+ t) T8 S9 d! u' n
                    continue;; S7 U# L' x0 M+ A
                }
9 }7 Z7 e3 k5 S2 E9 d3 R, G3 H' S                else
5 l$ G" a+ R6 [- `) ?4 K" S9 L6 N; M                {
& a1 Q6 B4 p# e, E0 u1 S8 |                    if (numw[i] != 0)
% j+ b( U- J; {+ s$ O                    {! `5 W  j. u* f
                        i++;
. `! A' E' c0 C5 q3 Z                        k++;: m0 P9 k1 n  _9 V: T2 I; ~
                        if (k == n)  Y% D' C; T& ?, c
                        {
- P1 |) K$ T7 u! k                            numw[i - 1] = 0;//把在n位置数组元素的值改变了- A3 \( h' u+ ]9 x9 s! k
                            k = 0;0 T0 D6 |- ]( y7 q+ T$ _7 a
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1$ J! P7 O  Q3 F, T  I( L
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);# |: @7 d# a3 f) J
                        }, ?% u9 N2 `6 U3 l# t2 g5 Z
                        else//输出暂时还没有改变数组元素的值
% w8 @  A& `9 k& l9 T, n- r                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);9 v9 h8 U0 c4 j# {' @' C
                    }
0 Y0 U7 _+ p7 x+ ?3 b( l# v                    else; I! E2 z+ M$ S8 U; `. z
                        i++;//数组元素为0,直接跳过,不计数。。。
7 `5 @. L/ n3 {0 Z                }$ T1 z) j. ]( `; U& o* p
0 h. P6 z, k* I

0 R. K( X1 D6 m) k/ S, q            }//结束while循环0 I% z" s! N! _6 v. H
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
6 A; f0 x+ N. n! g" }, q           & K( N- k  N0 m
                if (numw[i] != 0); C( r1 Z5 y) a6 Q/ x5 c8 R
                    Console.WriteLine(numw[i]);
# E  c8 t4 }$ d, g% K           1 B4 i" y# g" m
            Console.ReadLine();
: M- U: q( u) o        }3 K" I" X- V3 H- |1 A! W- t- }
    }
1 m. O2 I4 Y. Z+ v2 G8 x}
/ n* g% y/ H7 j2 v# N8 I
小甲鱼最新课程 -> 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-21 13:32

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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