鱼C论坛

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

猴子问题

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

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

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

x
大家好!; r  t2 ]: b8 g" Q" u, X
这几天我在忙着编一个问题,我用了一种方法编出来!
3 l! t0 C, c( e& C1 V但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!) y' I) ^, H9 E% \3 A
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 0 E2 s! z( R' y# f. D
0 S& n  A4 E- ]) t% n4 v

6 W4 h& g9 h6 J# r  N. f3 c2 K- l
                            题目0 J5 }6 r3 t& ]
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。. H( \: x; \$ f1 p/ p' t1 z
第一种方法:利用循环链表5 b: E, D9 d% G- M+ h0 L
#include<stdio.h>3 `3 j! z* G, \+ y
#include<malloc.h>
5 I: n( Y1 M: Y8 I- b( S* U. m8 O#define M 8            //共有8只猴子
9 w# C+ l3 h/ Z" A#define N 3            //数到3只时退出第三只
2 h- f8 Q# A$ Y# }typedef struct monkey
- v! B: h7 k, c6 W" [/ N( Z{int number;& M9 h# w  e4 p3 v; ^2 h1 P5 ?
int flag;+ T- ~2 D& H; T3 \
struct monkey* next;2 l) s  f$ z0 \. N
}MONKEY;9 f* m) T/ z5 W* T/ a0 o# I
main()
  n2 v( y7 G# ^. r. ^" _' l8 b{ MONKEY *head=NULL,*p,*s;. w. S1 `/ g, W/ a* b# f
  int i,sum=0,count=0;
! x" S8 r6 }3 J6 ^% S  clrscr();              //清屏; Z5 W" D/ x% l! c) H. _) i
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
* ^2 \' ~8 X. l: x) k7 r$ C  p->number=1;p->flag=1;0 w4 L5 Z- m; _- c( J( Z  ?7 \
  p->next=head;
: C' ^- v; o3 M( a: r) o" |1 q  head=p;
3 J% f& M" n- M. f( h  for(i=2;i<=M;i++)/ Q( C; n$ ]' v! `4 w, d0 Z
    { s=(MONKEY *)malloc(sizeof(MONKEY));) B  O$ L5 f7 Q/ }0 M8 J
     s->number=i;s->flag=1;
" ^4 |1 r8 g' h  Z8 k, k/ K& {     s->next=head;
1 j6 g' N, A6 i( @2 J- o     p->next=s;p=p->next;1 `4 O$ L2 k; u, C* J! b
    }
+ D1 W( o  H% f  Z    p=head;/ S- q4 E' ~; Z' S
   for(;;)
' t7 W" L, R1 B: d" `* E  `/ i# J0 X    {if(p->flag==1)
7 R% J3 h- s4 D! p4 K7 b& Y' K+ u       count++;
" {: p  \* j6 P& b     if(count==N)  t( R7 ?8 F9 Q/ O# H' D$ g# Z
        {p->flag=0;
  ^( x3 M1 H2 M5 O, Y" B# z         count=0;
. U5 @! W1 n9 c8 V5 \4 i3 x         sum++;}
8 K8 }0 j9 I$ E9 A' \     if(sum==M-1)4 m4 v( Q7 Y0 x+ U# s
        break;
# g2 o6 g9 j/ w7 C* b. N     p=p->next;
' k; E& k* w# j+ T" r5 x! p    }
# g5 g* a( o) g' x    p=( b/ R8 E/ M- v/ h' a
    head;: g4 e( }7 F+ U0 m' C7 j/ |; l
    for(i=1;i<=M;i++)
2 ^/ ^( b' ~6 g- M: Q/ T    { if(p->flag==1)1 p. c, W3 z5 X; G/ ~1 @. n
        printf("\t%d",p->number);
' v$ `% K" |* H      p=p->next;
2 d: g0 V9 O6 i' {0 _    }
  `- M: v4 U8 R$ J; ~- b
$ k' t: b# a" C- Y! U. b; S2 K& s: y' ?% Q& P- x
  e' J: ^% y8 t. y/ f
}
/ \  [- U2 j; k$ h* q& \0 m
第二种方法:数组3 p+ {) ]5 h: S, _# L! p+ u
#include<stdio.h>
6 ?. U: E+ @9 U#define M 8. g3 B+ I: a7 i( x. E. U
struct monkey
$ ?9 x/ S& v* [6 c  n' W) A% m{int number;
8 l( H+ d( @) e. O. L1 oint nextp;: C! }% ?% Z8 D  @8 k  H% u8 \& n
}link[M+1];
5 `+ d; j: Z; j7 M7 H+ }  g5 p4 K/ ]5 H/ [
void main()8 i+ y# L( c& R6 Q2 v) N+ a" U/ y
{int i,count,h;2 |5 ]. ^& y+ Q$ w3 k' h
for(i=1;i<=M;i++)) x- e+ l' P! n4 D
{  if(i==M)+ o+ V1 c: ?$ a6 A1 U: G" o0 U
   link[i].nextp=1;
8 J- H; s( f. }; A. I" w   else: K  Y5 F3 }) X6 Y+ ~
   link[i].nextp=i+1;) E& A+ J* j: Y
  link[i].number=i;4 Q% S6 N  M. P) w! ^7 j
}
1 x0 z# e* P' K, O) Eprintf("\n");
7 R) i; G5 @' w# U8 u1 _! R: p' Wcount=0;, B6 Z* b! q* |
h=M;
, N% o% `6 y+ `& O) @printf("依次退出的猴子: \n");. Y0 H6 i. S. M/ o! l! H
while(count<M-1)7 P" @( \: M9 z0 z2 u7 }3 D
{i=0;4 t( }# B# M2 P! m& d  z9 I
while(i!=3)' A' Z% Y* _- P- @' O$ l
{ h=link[h].nextp;) `  ^" i  J; {3 [" ^1 m; t& p% Q# j3 c
   if(link[h].number)
. c/ s3 o; m& ?' r  W, x     i++;}
; [# [9 X* W+ P9 V' b
$ c- [4 F3 S& F# k5 fprintf("%4d",link[h].number);& p6 K, N# N$ _7 B0 V0 o
link[h].number=0;
  x" p. E% e& e4 n+ Rcount++;
+ B9 N, ~/ W# u6 B. M& }9 w}
7 a; q# K) b0 e) A
  ]6 ]0 [4 P7 R$ r5 H! M6 |1 ~printf("\n大王是:");1 s$ v" }2 \& _: n9 ?
  for(i=1;i<=M;i++)
* {% u( o2 n: O. g+ A1 t4 i  if(link[i].number)* N; t" s) Z! I' g1 j; C5 U& H
    printf("%3d\n",link[i].number);
7 M# Q% j8 p1 T) n2 Q4 ^% t" t3 }0 u7 u

: `1 t* B5 R' N" z+ F}
$ z1 `( h# R% i; m* Z) L- G* y
第三种是普通方法for循环

# _# q5 b# J; _#include<stdio.h>2 K7 C( q' L0 S
void main(): F7 H- N; C) N9 C+ Y5 ?' K2 u5 ^
{ int i,k,m,n,num[50],q,*p;
0 T7 E6 r6 a3 ^* P) q8 J. a' s    clrscr();
3 A+ f  c4 y$ _& i   printf("input number of person: n=");4 D% d4 i7 Z5 s8 b: _
    scanf("%d",&n);' u5 ?9 Y! @4 V6 |6 A' I: h
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
( @' p8 `5 l2 Y0 W0 C- K    scanf("%d",&q);9 P5 e; g, h: ?4 U( r) a
   p=num;
, @( c, J/ k& Z$ x  for(i=0;i<n;i++)
# H0 a; {# T2 R7 ^0 V% F    *(p+i)=i+1;
# N, Y' d1 q" J6 P" b4 W   i=0;3 `9 g, G6 d  L& I6 t: s# E: ^/ w0 S
   k=0;
) h. k2 A3 j8 y; G4 l   m=0;! ?: h: V/ p0 l! D
  while(m<n-1)
, g9 @/ z4 }) c$ B2 `   {if(*(p+i)!=0) k++;
7 u0 e: O( e. ]5 J( W- {' h; k     if(k==q)
6 e$ E/ y4 t; ?- ?4 e" m/ H      { *(p+i)=0;2 O! `2 u" E3 p$ B, p6 K
        k=0;
5 ]( i" Z2 V* \) r, |+ c! l        m++;
: U3 C$ A. D# ?% t      }
& {# T6 L0 P  H+ m0 y1 q    i++;; |) F/ J- l# h. k4 e: S: q( T
    if(i==n)i=0;
; V$ _7 ]/ P+ q9 s   }
, i. K3 E4 L# L. s  while(*p==0)p++;
9 C. X  R# c; c    printf("The last one is NO:%d\n",*p);3 P0 f* A: [; {$ f
     getch();
( _6 R6 m) t0 x0 I+ a" `" x+ o
! I! o1 z; }. q3 U! W}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;2 h! l2 d) @& H! k5 L
namespace 又费马达又费电
. b; y4 ~# t. T0 w5 u+ O{
" m; Z* }4 Z8 M* c    class Program
2 s3 y+ T1 V- U7 d    {. H- M6 w/ a; C" v! f
        static void Main(string[] args)9 ^! ~: ?9 P3 t* Z# v; {, C* R
        {
0 j' s4 m0 o5 p7 q, O0 h* v* \; ^( O/ d            int m, n;) b; X* j( z5 X& q
            Console.WriteLine("请输入数组长度");
4 b9 n2 i  D8 N            m = int.Parse(Console.ReadLine());//m为数组的大小, {( r) Q+ Y3 t/ Y" C' E; p3 R9 |
            Console.WriteLine("请输入要截取数字的大小");
1 L* I/ S! M# {  ?            n = int.Parse(Console.ReadLine());: }# X4 Z9 `& ]& v8 ~! E
            int [] numw=new int
+ a' u- s9 T- _$ ]4 C, k- n/ U4 B" Z: j
&shy;&shy;&shy;;: L: t/ V% A1 B) v# ^0 j7 z' @1 X
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数% n3 s4 D3 G* ~9 `3 U) J# w# ?
            {
9 G* m( y8 S# k' [, Z: r* w                numw[j - 1] = j;
- W: ]. W. I* D  r            }1 s* b* h& K1 Z! X
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
; @+ M) G7 F2 C8 M            while (d != m - 1)
# o- F9 i' i& V: d; E            {+ f; |$ v2 J9 S. Q" J2 h5 n7 Z
                if (i == m && d != m - 1)
0 @8 x% X/ v5 ]3 n                {9 M% c) _! C+ E6 W
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!7 ^) v( ?6 c4 _8 ?, b4 _% m
                    continue;/ p8 a. b% R5 U/ J) q2 g  ^' P
                }9 d" V# e- e9 e/ \- ?& r
                else' ~# Q- Q# q. I) u; Y/ x; P
                {
. \; n1 v0 p! J8 W) b+ C" L; x                    if (numw[i] != 0)
% k5 N" M% u2 E' k" g; l                    {
0 Z, o7 E  U+ G' w                        i++;* W. e1 k7 ?: Q  e, g4 q
                        k++;. U5 G" ~/ h3 C0 V
                        if (k == n), g6 d3 f4 k" g4 c+ v' n
                        {/ ^* `6 X& h! R8 H9 x0 r
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了5 N. H$ u! c1 Y( B+ Y
                            k = 0;0 W/ F: T( d+ c! f' ^. F: Q
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小16 p) n$ l/ @6 u
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);; {& \: r& {! ?$ b! @
                        }' s% k) K3 K: O( }9 |, f
                        else//输出暂时还没有改变数组元素的值" e6 O5 l* b* M- y: Z
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* x+ q! a, f; O( O
                    }4 b7 t+ y$ R% T- T! |
                    else
! O* M1 O* g3 h% d+ k. Q5 m                        i++;//数组元素为0,直接跳过,不计数。。。
3 V* `/ B7 g* w5 P: q0 m                }
. b' F3 I) }0 m9 u; M ; u3 q3 Q% q4 c, M6 y* z) I

$ y8 P  _1 X9 E; m            }//结束while循环/ r) w0 K! J9 b: Z8 c  G
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦7 v3 o- y+ s$ Z3 z
           
) R/ H5 c  O* q* A3 h                if (numw[i] != 0)
9 {8 O% h; V$ [2 l                    Console.WriteLine(numw[i]);
) A0 r3 ^5 u7 O) a# V" E* H+ ^( @           
" J0 k# r% Q4 C  a            Console.ReadLine();
, C6 {+ R0 T3 x2 Q        }1 Q; D' ~6 _+ a
    }" _4 l6 r/ V" A% M- l
}, U# C8 X" [# a' u  f6 ?' \' G! Z6 |  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, 2026-7-4 07:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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