鱼C论坛

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

猴子问题

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

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

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

x
大家好!( u( p1 h6 O. E# U" v" w
这几天我在忙着编一个问题,我用了一种方法编出来!
* Q" Y7 L2 X% I但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
# ?& s) }7 ]- [, V" N注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
% a" S' i  a% y. C( G& W. W' ^
: X2 P7 E" X0 ^
; C1 j7 q4 `& a9 J6 x$ x% z: Q
                            题目- I$ V* t+ t- x0 t
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。( \/ K2 |$ q# C9 R! P' c+ Q8 d
第一种方法:利用循环链表  d. ~5 s. S  v( T
#include<stdio.h>+ p$ ?' S* L4 x; d. `
#include<malloc.h>
. E8 d) i- v+ S4 H+ q& F#define M 8            //共有8只猴子  W% e# h0 e9 n& Y, a
#define N 3            //数到3只时退出第三只- N) w, L. y/ Q1 i( X  w
typedef struct monkey
8 Q; @* p3 d6 t+ m% X% Y{int number;
/ q' P& z) ?3 ]/ ?+ v: Q! K. oint flag;
3 ]$ r/ D. p/ x+ E3 \2 j  xstruct monkey* next;
' q  W& \% c0 Q% z3 y0 J) A# ]& t}MONKEY;4 Q7 `7 n# d; ]# {3 u
main()
- @& i9 |1 ^- d" P{ MONKEY *head=NULL,*p,*s;' J$ P$ o& n& w, p$ Q; g
  int i,sum=0,count=0;
6 W" M7 d' ?5 B& a7 C  clrscr();              //清屏+ y2 A- P+ g7 _' X
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存4 K8 Z* P* R* I
  p->number=1;p->flag=1;
7 N" {4 M' R# {5 h% |& X  p->next=head;. Y; `* q/ D% `4 D& k
  head=p;
. I+ C2 [1 |* j5 g4 X; ^. e* Z  for(i=2;i<=M;i++); R0 K) v/ N0 Q& I  E) C5 h
    { s=(MONKEY *)malloc(sizeof(MONKEY));( }. \# |& v+ D" w, s. m
     s->number=i;s->flag=1;
7 r" Z" A, J" f6 |     s->next=head;) o5 ~, Z  }: {" \; D5 a6 [
     p->next=s;p=p->next;; q  n( `$ S* y* m$ d6 }1 v6 o
    }/ E& [, [; V* Q
    p=head;
3 v6 ]$ v0 B6 f   for(;;)
' t* \2 x3 Z  y$ }$ t5 I4 G& A    {if(p->flag==1)
, [$ q6 K8 q$ t& ]; y. |* l# z       count++;. n) x( S; Q  L" ]0 A- i% |
     if(count==N)
# ~1 q9 @0 P& _( m; u7 e        {p->flag=0;
6 E* z+ H2 N& k8 y* `3 h         count=0;
, N$ C6 Y* a# V* g, G8 U         sum++;}9 o, i- Z: V; i8 y  G: f
     if(sum==M-1): |% i" x' D. _5 w* n
        break;
1 z5 u: }# \2 w& D; s1 ?# V     p=p->next;# }% G" A! o4 U% ^3 M& l
    }" ~% k, x, J9 O2 }9 M1 a/ \$ V+ M
    p=
4 i; ]) m! i7 A    head;
6 a4 Z: [# f' u4 }: J% m/ i; {    for(i=1;i<=M;i++)
' Q' c. a# v! U# M/ |    { if(p->flag==1)
5 h3 p0 k4 A' L3 {. h0 v; \7 G! G# x        printf("\t%d",p->number);
. r( M3 d2 H% l' E      p=p->next;
" j4 c3 m; z( o2 a$ ?. r. c7 A    }
5 Q5 ]. S& [- h: @7 x2 w
+ v  p- Y/ v( O/ X
& f) H$ z+ W$ F& M: c1 S) O+ @& C5 r
}

; I7 v5 n2 c; c0 p5 Z, F- m$ K7 ?. A第二种方法:数组
. \) [( G  J  Q- D#include<stdio.h>
9 R7 o" \' m" Z0 P4 g  W# U#define M 8
' M1 j, g& E% ~: D+ ^" Y6 Ustruct monkey
  h! J4 }2 }4 F. ^& s' V{int number;2 m+ m9 A6 A3 J- l" [
int nextp;
; r5 [- O" [5 _6 L}link[M+1];
. K' A' C$ G9 s+ g9 x- o; p% i: [7 i) `8 X% h4 V
void main()
( b/ g8 B) [: U% Q9 z$ x{int i,count,h;% h8 Q: L0 N+ L4 V( N+ b
for(i=1;i<=M;i++)
9 F# q4 e4 w  `  s{  if(i==M)
. x- u& Z9 d4 e# h   link[i].nextp=1;) D" w, G8 _- _( K0 q" g( k
   else! z3 \% ?* E  k* {# U
   link[i].nextp=i+1;
3 r5 k4 E, f9 T9 c  link[i].number=i;) m5 y+ ?6 ?5 ?* a( y0 f- a  J2 j
}9 S! U* g! g" \% y  G3 [8 g' @
printf("\n");
  x9 \9 {- k, U3 {count=0;
3 b% N" ?7 z, S3 r, uh=M;
# V, V  `: o. gprintf("依次退出的猴子: \n");7 @. U; ?: M. _0 c: Q
while(count<M-1)! s. e5 \% }8 |5 e  L
{i=0;; m2 _- E, u7 q3 g' Q
while(i!=3), _. t$ S: ]  `# w0 x
{ h=link[h].nextp;: y* f! [) \' L7 X/ A" L) N
   if(link[h].number)
/ a" \1 t+ r6 J( B     i++;}) i. g8 a; r6 S( z- ?( T* Y

& r) A! \$ X" W0 D4 Iprintf("%4d",link[h].number);1 {4 l0 D; ^- |7 \
link[h].number=0;5 g2 }( d" j/ N$ n
count++;9 x" p' ~2 k$ P# F8 n( T
}
# W) O6 a' g* a! _  V7 {+ {( e( U8 ^9 p! _; p, r4 @, w3 Q2 q
printf("\n大王是:");
* U& {, A0 d$ F* f" h9 V4 f  for(i=1;i<=M;i++)/ A( C( Y7 }  p2 W0 s, E
  if(link[i].number)8 J- |8 I2 S# T. p5 G! Y3 _" _: Y
    printf("%3d\n",link[i].number);2 k" E, Y# U3 K

1 i- {) \* B4 B1 v9 q- m# n
( Z$ l" p7 G, a6 s/ f2 b! q}
" h/ ]; }. w, z8 f2 h4 b
第三种是普通方法for循环

5 G% s: }2 q' e! z#include<stdio.h>$ Z8 O& }# S1 v: y' q
void main()
" R* M9 v) b- T{ int i,k,m,n,num[50],q,*p;
5 Y  o# b2 X1 J: o4 M. M  G    clrscr();
# |9 K1 Z$ z' r3 u   printf("input number of person: n=");
! G/ b3 e2 w; Q. U4 E    scanf("%d",&n);
9 q6 b* R/ \" `* M8 b. @printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只1 t  J3 O4 R8 r, a0 \6 \9 g
    scanf("%d",&q);1 k9 ]: }8 K& z+ S1 G5 }& L
   p=num;
- N) i; n$ w; }# c' U) J4 L  for(i=0;i<n;i++), t0 E. a+ f3 l/ o
    *(p+i)=i+1;
& B# z# J3 N1 C" C$ ^8 H9 V# F   i=0;$ ]+ o$ P  A2 K! I) O* R5 T
   k=0;4 K6 R8 S/ J: Z/ p6 n
   m=0;
! o" A  ~% x! T  while(m<n-1)- d6 A6 a+ M. e# u- O1 M
   {if(*(p+i)!=0) k++;9 c* a& E$ A* }; _6 ?
     if(k==q)3 j9 I; e/ @3 P3 @+ w* c
      { *(p+i)=0;
: F: g- H3 R! }1 F3 |( m        k=0;9 C. P$ D& |" u5 c6 P
        m++;
" Y( e5 r- J& ?2 t- B; x  K      }& t, \- G8 t) i+ T
    i++;) D2 R8 H1 T/ s  p8 ^5 q
    if(i==n)i=0;
. m1 ?! @# l' O3 G   }
, N0 y' E+ v& R2 W' T  while(*p==0)p++;
5 a" \: |  b7 m. D    printf("The last one is NO:%d\n",*p);. n7 e& Z5 v  X  `- a! @
     getch();5 g# X1 c5 F1 q6 X  N
: ]& C" e- e% C& O+ x& d
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;1 n4 U/ B0 F, P) B) v9 v
namespace 又费马达又费电9 i/ x+ O7 {. Y1 Q. G8 z8 ~
{
8 Y+ T! `  ~0 r, n( {  k    class Program
5 j4 \$ \* Q5 P0 h& p8 }    {
+ n) E6 C0 K- T/ }/ y7 c* @        static void Main(string[] args)
7 Q- a1 D+ y( o+ W  a% r        {
# o( E0 r9 C  y% s4 \; ]2 t            int m, n;
, T( Z/ w# O2 b8 K5 A            Console.WriteLine("请输入数组长度");
+ ]1 Z1 J$ ?1 i) v            m = int.Parse(Console.ReadLine());//m为数组的大小) U7 [/ w6 h4 P0 Z1 t+ a+ \
            Console.WriteLine("请输入要截取数字的大小");
* }& E& H) V9 ]! t  h, ^            n = int.Parse(Console.ReadLine());$ J! D6 t9 {6 w+ _. m& p
            int [] numw=new int
$ D# G9 Z' _8 q0 r9 s  E7 [
: ?4 S5 \# a: W&shy;&shy;&shy;;& \4 _5 B( b* j, y& m8 V
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
( Y# X' E7 V. u: V2 b            {. o1 J" P9 E4 T( E: Q7 N
                numw[j - 1] = j;1 b# E, ?% W: F, z, q% i( I
            }, U7 y( Z9 S- j& ^
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!  @( ~+ O. j  u/ t! M+ q
            while (d != m - 1)
& R- k* R/ A& r3 D2 z3 ]            {6 t& n2 p( W, C
                if (i == m && d != m - 1)
) d- w$ S/ ]9 C" v4 K' s# ?                {2 H# j+ W! C8 \1 B- m7 V' Q
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
% x" L/ Q% f9 S0 O" e                    continue;$ y0 K9 d) I; f
                }4 L" V( |0 o0 A. f
                else
0 B4 e  ]+ |; Q, U* s0 t8 e0 U                {
; A" @/ [5 B5 f% @5 u                    if (numw[i] != 0); Z! N1 A+ D) S
                    {! ]  I1 n' `* z7 L* j+ z- X) {2 ]- d
                        i++;) Q4 r9 ~- T5 B9 A1 y
                        k++;, C9 o2 Z3 L/ q, ?3 E
                        if (k == n)
) ~* X1 Z+ D- [* L2 i' d* @                        {: S2 v8 C, U+ Q8 w3 H4 Q
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了( T5 F& {& x7 g/ z
                            k = 0;
" }( z! P! W7 c8 u+ z. y* `              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
0 i, J- T+ m; Z2 L8 \  \) o                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, L, ~' j+ S! V4 c4 T9 v# @                        }
& e* m) u5 r9 J! K1 N4 z% v. _+ ~2 y/ b                        else//输出暂时还没有改变数组元素的值# h9 V7 H$ X# i+ d
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
0 L: D: i# ~& ~$ U                    }
1 C0 n2 G$ I* s& z9 n" S8 Z9 O4 j# U                    else% ?8 d; u9 ?4 o% l! [9 W6 _
                        i++;//数组元素为0,直接跳过,不计数。。。
( Q. b0 _$ ]* E) Z1 V4 e. U* a$ ]                }
8 }  y/ y) n( D- p6 |8 V7 M: B% @ 2 m1 d, A6 D# q. |4 D

3 l2 d- c3 Q) s+ r/ e5 |; S" E3 F# u            }//结束while循环
% T& R9 s( a# }            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦3 V2 r/ t" R: x" K* |. r
           
* }8 m5 I  U1 C+ E* W9 W3 @- x7 v9 d                if (numw[i] != 0)
3 x2 [' Z7 Y4 t: ^  }3 T* D                    Console.WriteLine(numw[i]);
8 l! N: I+ ^( B! W( x8 ]1 I           ' T' t7 }6 A7 c% G" R+ V! Q
            Console.ReadLine();
+ w9 }5 d- j& M) `! b        }
8 Y2 g, W8 y6 i0 C5 j% R    }8 m% x, x& Q, H6 @5 k' y( Y
}
8 i7 }0 h- @' l. L! S- c
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-2-19 06:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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