鱼C论坛

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

猴子问题

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

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

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

x
大家好!
& \& N( C1 d8 j6 X这几天我在忙着编一个问题,我用了一种方法编出来!
- t+ X2 Y1 e2 ^5 R" `但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
& v; \# q( s+ `: E; b3 ~. r+ l注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
3 N4 T, `4 M; U6 e4 l$ Y0 B7 z8 d
- ]- ?% p$ ?1 G; k
: d9 `4 J! H4 q
                            题目$ N( G( [6 ^7 b0 }8 _
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
. Z$ v7 c3 H' ]3 O, r" f/ R第一种方法:利用循环链表! L+ [5 ?  d* ?$ O
#include<stdio.h>0 H- r7 G0 n( l% X
#include<malloc.h>3 n4 n8 I9 _2 T4 T* h4 s9 f& h
#define M 8            //共有8只猴子, A& l. ?1 U+ r6 N
#define N 3            //数到3只时退出第三只2 b: {  ?  {: v4 F
typedef struct monkey5 u6 d- I( d% v1 ]# d
{int number;
% F& u. @* V6 p% \( t$ ?! Oint flag;
4 X* \, }$ b* f# Wstruct monkey* next;
/ o2 n/ B" F) Y# A) I8 x}MONKEY;& I5 D& L, w' {$ f5 w: w* f
main()& R: U3 z1 T; \9 q8 ]! @
{ MONKEY *head=NULL,*p,*s;
& y- ?, `: Z1 Q# }( d/ O  int i,sum=0,count=0;
' d- c- Q4 G& i( f" Z% e- V  clrscr();              //清屏& ]' g' R2 m% R
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
6 T' V% ~5 b8 m$ n8 E# F# z* {- r  p->number=1;p->flag=1;6 }9 f; A( E' g) |* A' M
  p->next=head;! X" j6 ~  I' {/ y' z% u* v: P0 [
  head=p;
) a  E  S" e( [5 Z  y  for(i=2;i<=M;i++)9 ?( z$ ?) ]; h( Z8 ~
    { s=(MONKEY *)malloc(sizeof(MONKEY));1 t  Q2 v. l! U9 U( |& z* A
     s->number=i;s->flag=1;
7 i  v+ f( ~8 e' `     s->next=head;, l+ }; L; L7 b. t2 g  E/ `
     p->next=s;p=p->next;0 M# ?, d0 }7 j* u. @5 @" {
    }
# x$ o, B1 f- U3 Y3 Q) \; {$ ^    p=head;1 O. \/ F9 e. k( j
   for(;;)
, J1 [5 V- F' F# o    {if(p->flag==1)) k5 K/ U' b* m5 X
       count++;* y8 x3 c+ E( |$ L
     if(count==N); K1 L4 j+ p, [4 K3 ]
        {p->flag=0;  q$ s. _3 s) W: l; P6 M
         count=0;( Y* g3 O" Q8 t; F5 ?5 R
         sum++;}
* ?3 l$ \6 R) ^7 N     if(sum==M-1)
8 R( X0 j' \+ k3 |! h  u+ v% G+ F        break;+ f: u" Z: G" d8 U9 U
     p=p->next;4 E7 F+ L/ ]# b( c& M1 ]
    }
- \* S( Z; k+ b4 F1 F( ~    p=$ e& y& K3 y8 S2 e) C4 ^" g" i# f
    head;3 J  ^" y+ ~1 p% f& o6 ^
    for(i=1;i<=M;i++)- I* `6 w! ]: p8 D
    { if(p->flag==1)
1 g6 x& e, V8 R) C' E2 u( p' Q        printf("\t%d",p->number);
% G( N; }. `4 q& @$ @5 D, F      p=p->next;; |- W+ Q! A: a: h1 H- D( }+ F
    }! S/ |. k0 y1 d! T7 R7 m1 h+ I

. X- j9 y) w5 ]- O+ ]" X8 e
% Y& R6 L8 F* H) V0 {4 H% g6 k) h& d4 v9 C; R
}
& d" F6 F5 l5 @: ?$ G: x/ ]& p- l
第二种方法:数组, Q; a( c0 l) r
#include<stdio.h>; ]! i2 Y  y! ]# h
#define M 85 G) t3 q+ {% Y1 G
struct monkey8 s  I/ K/ y4 Y! |
{int number;0 T6 {6 j& {! [( J
int nextp;4 y9 V/ f: {! H
}link[M+1];
6 \. S5 X4 z+ K! h# A. O$ `8 [
  \4 @8 ?. V8 ], Xvoid main()5 z3 {) H$ v8 b- ?( o3 o9 N7 ?2 Z! g
{int i,count,h;0 t3 _1 \+ R3 j! A
for(i=1;i<=M;i++)5 `" D& E- ?6 f# n* z, y
{  if(i==M)/ u2 S% u" V; d7 L4 _3 s8 |
   link[i].nextp=1;) C. z5 z; N% T7 x$ a' ~
   else
& u2 Z9 p3 c: N9 l   link[i].nextp=i+1;4 C# E. e& [$ B
  link[i].number=i;
" i6 E& F6 N6 ^% H* S}
& R8 ]  p0 j# N+ y/ Jprintf("\n");
) a* O! s( b' Vcount=0;
! m8 k* E7 c2 [' u' h+ E4 F6 z! i1 }h=M;& @; E3 Z: \: c# a, d& i+ E5 D
printf("依次退出的猴子: \n");
; X3 n1 s% P- c% d) S- @5 uwhile(count<M-1)
& l; Q2 u2 [8 F  l) d{i=0;
9 J$ `  d( q& b: Y* Awhile(i!=3)/ Z# C' k* {/ g. @$ h
{ h=link[h].nextp;
8 b: A  n9 @$ U4 p   if(link[h].number)+ i0 \: q6 w( m+ A+ n# f2 n) U
     i++;}
% j7 H; g3 t! O) m2 b- `1 B$ Q& d
2 s( R. _: K- t  A" |0 c: o' o7 wprintf("%4d",link[h].number);$ \$ b1 {& k' l9 J5 Q. e
link[h].number=0;
1 l  a* A) ^. p" n0 J4 G1 |& G/ zcount++;% Z% M! a3 ~5 F5 L. B# `
}
+ G& ~2 Q# v& M4 r' F2 H# u7 E, H! i% m4 K- E8 K& Q
printf("\n大王是:");; R: ?/ h/ S. o; C7 M1 \+ _
  for(i=1;i<=M;i++)
" @0 e+ V4 O1 ^5 a0 c0 G  if(link[i].number)& ?" r1 p- j3 B
    printf("%3d\n",link[i].number);8 Y, X/ o# k. b$ O% ?% k6 V; a

$ p; b* f  x" Q' q
. m% q4 ?2 ~% l, r8 c# D' B}
& [& A5 W& {2 S( I% \* s
第三种是普通方法for循环

' _! A( E- Z# V+ q#include<stdio.h>9 J: V- `* L: V% @9 o4 y! n/ Q$ ~, I
void main()+ H6 _+ P9 @2 G4 U. b6 ^3 ?! Y8 n
{ int i,k,m,n,num[50],q,*p;
9 ?; y( A) J3 V9 V9 a8 e    clrscr();. @3 G6 A' P5 M+ d" S
   printf("input number of person: n=");0 f  ^. H7 F- ?: M3 y
    scanf("%d",&n);
- z. d; v6 B8 Cprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
4 H: A' ], h3 h    scanf("%d",&q);* V* }) a4 ?3 {1 p# @; M
   p=num;
; S! C$ g: f. N, H$ L: o( x  for(i=0;i<n;i++)
  j$ v, M0 x' \; L    *(p+i)=i+1;
: |# @( N* |6 [( G   i=0;
- p5 Y7 l% L$ S& I7 N   k=0;
! w- K" R; P+ |8 ?" j   m=0;* Z- u$ N+ v7 p- i  v
  while(m<n-1)
" ^. z1 B3 n% }   {if(*(p+i)!=0) k++;5 C- y( N8 ]/ m  h0 c
     if(k==q)2 Z: `5 Q6 O; K, M# M# c; }
      { *(p+i)=0;; M4 @: ^3 |' T2 W/ L. S; b
        k=0;
. N& u9 P$ R- ~4 l9 x8 c        m++;: _7 r5 `: t) W/ Y
      }
* _+ a' s% N- C  d    i++;; G) c1 s5 h6 C; x0 J" d4 S
    if(i==n)i=0;
8 H) G! Z0 L. N+ M6 v! E- M   }" g( O; O+ e1 ?* s
  while(*p==0)p++;
: a8 V* n" j0 E  N7 o5 I9 b    printf("The last one is NO:%d\n",*p);
8 l7 F% d! M5 j5 K0 s     getch();
  J  g' J6 Z6 S; [) ]5 v
6 r  t& D1 {+ V* ]  H  Y& W}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
7 B; o& x4 E2 ^3 Anamespace 又费马达又费电& @1 i8 B4 e' V. k* g' k
{9 P4 O! b6 ?+ |) M
    class Program$ T4 U8 A) U( s: l( P$ m& l( T
    {
1 P, ~3 Z1 g" k; a$ |        static void Main(string[] args)+ h1 y- F( {' H  _
        {
8 Q3 C; R( z' r5 M( \5 N  H+ H            int m, n;
& }/ ^& S$ _% f2 D: j4 A            Console.WriteLine("请输入数组长度");
) W6 ~+ U' c2 |7 d% }% f. K            m = int.Parse(Console.ReadLine());//m为数组的大小  o9 G* B* Z7 i2 T
            Console.WriteLine("请输入要截取数字的大小");' V  d3 K# D  E, y
            n = int.Parse(Console.ReadLine());9 ]( F+ }3 l& m* X; Q& e: \, F
            int [] numw=new int
: }3 h6 K: B. E; P6 R) [" Q3 O# Y) Z. l7 M9 g* c. h+ B7 r, B
&shy;&shy;&shy;;+ r7 Y9 r- h2 }( m, P8 f5 @  f
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
& T5 `8 }1 t% h7 H. w/ Y            {" B8 |7 C/ M3 P- w: x2 m% ?4 r1 E
                numw[j - 1] = j;
7 I+ V" B. @& W/ Q5 ~& x! @            }
4 v7 N& C7 Y0 @9 f6 v            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
0 e& _. G  d! e8 s& M$ i% s            while (d != m - 1)5 w8 v, f: ^8 [9 `. W3 C( O& `5 F8 U
            {) ?3 n- k. F0 v! i/ x
                if (i == m && d != m - 1)2 m9 L$ v, F  N( t
                {
3 X1 w2 U. O5 U4 w7 h: m$ [                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!- ]3 }6 k- z9 U. G) `1 B+ O
                    continue;
3 v7 S2 f+ A4 @3 H                }. W7 K0 c4 R, c5 u0 g! p0 F0 |
                else& _9 f7 O9 f# Q" @7 a
                {
9 g3 O1 h0 v1 y0 |+ G5 t1 K0 ], ?                    if (numw[i] != 0)7 T) M9 E- ^& I# ^& P
                    {
# L* j. E! \, Z8 x9 T; U! G. `& L                        i++;
5 E. S7 g4 B0 J# n                        k++;
( b3 B  r" L/ ]                        if (k == n): E, @' g" P! y$ f/ ~3 a3 L
                        {
9 @% c; m( I3 V) {. w                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
$ j9 b- z. a# I3 \                            k = 0;0 Z: Q2 L( l/ n" H. @) `5 M2 `0 O
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1+ ?1 Z* x' d1 y/ O8 v* F- t; y
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
& y7 R" B* _5 _! p3 q* h                        }
+ l  A" ~* {' M6 n                        else//输出暂时还没有改变数组元素的值, w5 c. b) w, n& _9 Z+ }
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 z8 t% I9 R: L* Z                    }
% Z2 a. |8 r4 B7 E5 \8 z: R- \                    else
" j4 u: W5 r7 u" h0 i3 `                        i++;//数组元素为0,直接跳过,不计数。。。, T- T3 K7 a) s0 P$ ?* r( J
                }) \) t5 I& O. r# d: u

& i; u6 F, L- c4 d8 Y3 b) \0 h* k  D7 J: X: f
            }//结束while循环
, v) |( @9 }' m* S/ L; O            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦6 _* l7 K# g. N- p
           , M& I2 a- U) M( X# ]( m& x6 T
                if (numw[i] != 0)* L: \% h2 D0 z- D* D/ ]
                    Console.WriteLine(numw[i]);, g# I7 Z# F- i" w5 C% \! d
           
5 M2 J* p/ J% ~4 _" ?! n            Console.ReadLine();0 Z- o9 l4 ?5 w* w; Q6 b! T
        }/ H. F+ ~1 [3 b" _' G
    }; P: E& Y6 Y1 q
}
, }% k& H7 e5 q/ F9 q7 W. k& ^. q" N
小甲鱼最新课程 -> 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-1 05:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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