鱼C论坛

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

猴子问题

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

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

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

x
大家好!  Y7 l. x' o( o% {0 z1 Q7 I* q
这几天我在忙着编一个问题,我用了一种方法编出来!, F' v7 F1 N' E! k" @
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
! P: x+ `7 s, G, ~注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
# n2 i! q, _5 h4 ?+ {) p1 Y4 y0 Q. E  P( e3 J6 W2 {* `6 K4 n0 i

/ @; M. x& o! Y
                            题目6 s# r3 @2 Q* F$ Q( k6 Q
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
" S6 q' K2 \! R; i1 p第一种方法:利用循环链表
9 X, U& t" d9 B) q% f5 C/ [#include<stdio.h>5 I8 @( s  r9 E2 V4 h! g
#include<malloc.h>
. s3 f- R3 y; s( @( M#define M 8            //共有8只猴子
2 G0 I6 o3 [# W#define N 3            //数到3只时退出第三只! j& z2 R: T% Q1 c# Z0 \: \# j
typedef struct monkey
) Y: ^2 ^8 ~: Q; k/ L. Q5 P{int number;
: z+ m( x: s4 J& Wint flag;
6 s! @; U6 t' P/ I! Xstruct monkey* next;
8 m! \: `2 a+ _; Y}MONKEY;
. B/ v9 i7 C- y. }9 k8 ~# Jmain()) k! h) ]: E. z8 j8 R  w1 K- j, v3 P
{ MONKEY *head=NULL,*p,*s;
. g5 U1 O1 K3 H- R9 X  int i,sum=0,count=0;9 r0 p/ w8 N8 ^$ [  @4 a: c7 M; e0 v" l
  clrscr();              //清屏8 `: s) H* x1 G' T, c
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存( Q* |' \# Q  D! U$ f+ n
  p->number=1;p->flag=1;
; T% E$ \/ `) v& r7 O( Z1 K  p->next=head;' e& A) b7 l0 Z6 ?: j
  head=p;
6 B* \0 {& {7 y. i2 q' f; V  for(i=2;i<=M;i++)" g2 \3 N4 }, B9 L, p" u
    { s=(MONKEY *)malloc(sizeof(MONKEY));* R) s1 S1 n8 Z: H6 `, n
     s->number=i;s->flag=1;" U8 V/ F5 ~! H3 P
     s->next=head;
& e( I; T$ p3 {7 X6 |     p->next=s;p=p->next;
8 w, k: Z! K9 m8 n7 l- D    }9 c2 Z. ?3 S- _
    p=head;8 Z7 o4 V; X9 x7 V2 h0 f2 y
   for(;;)
9 |1 m7 |! \/ a    {if(p->flag==1)
  L$ z: ^$ `* M3 I5 @# G       count++;2 I! k' c6 Y' Q/ A" `1 o  ]$ C
     if(count==N)
- Q  `4 p0 W7 {: y, ?& g2 t        {p->flag=0;/ M# C; q2 m6 c2 \. n. |
         count=0;/ k% K/ Y( f9 G6 b6 k2 y
         sum++;}
7 F; X, v1 n2 \4 s     if(sum==M-1); e2 y- p4 @+ _+ N6 `
        break;6 t3 s5 P4 X( j
     p=p->next;
1 X4 a+ _( d8 y( Z6 \* w    }
7 p) a" z. q' F0 s' o7 |& C8 t$ A    p=
+ n" y7 c' j' O" F# n    head;/ z* N- E& e: a5 W6 C
    for(i=1;i<=M;i++)
% M4 p+ [- ?, T5 i/ F8 r    { if(p->flag==1)5 d3 K, P- Z) C% j0 _0 `
        printf("\t%d",p->number);
" {2 C0 \: |- C9 \' |6 g9 S      p=p->next;
0 @  @7 d8 U4 J: u/ ]7 k    }
* K3 z. D6 a) e% l) D
, y8 [: ]9 H- \8 J  |% {) z$ R# B" F5 Q2 M- f, T
, M" U" r  j* @6 A
}

' @0 P8 G7 q, b' o- D$ y2 T: Z( N% t第二种方法:数组+ t8 ?' k% z4 n! O
#include<stdio.h>7 _; Y: d# j0 m
#define M 8
# r( b8 q7 M# |7 Fstruct monkey/ h, n6 T0 F" \
{int number;
9 L+ z3 {; t, F- W- Fint nextp;. Q, [8 H8 V. M, V& H. k* _' V0 V
}link[M+1];
/ |+ m) z2 d. \" p
1 X* C# d3 d3 cvoid main()6 n" D& j1 ?4 p. H6 V  o! h8 T3 [
{int i,count,h;4 @; t2 K7 D. }
for(i=1;i<=M;i++)
9 x9 X  p, w4 I6 c3 S5 ~! y- ]{  if(i==M)* J7 n% j( M+ J4 y9 e6 j
   link[i].nextp=1;
: V& i( K! [5 M8 H/ }0 `   else
9 a5 b7 P& _& s: S. k0 W5 ^   link[i].nextp=i+1;
5 V3 l6 N: D: Z1 {- K0 G) M  link[i].number=i;% G9 y* t& `/ J& r( \4 f9 ~
}
+ x, |/ g+ m7 K- }8 Aprintf("\n");
, e# v. b/ o) k% pcount=0;
6 ^( L! f2 n2 r  X, E8 U$ B( sh=M;& l* o3 O' e" ~7 ~
printf("依次退出的猴子: \n");
! Z& Y9 y6 m, E& i. F; M# Q+ qwhile(count<M-1)
, ]  g. i1 {# w; T, Z# Q5 q" w  F{i=0;0 N2 K  B- q& N
while(i!=3)$ b5 V( \0 R7 @/ F
{ h=link[h].nextp;+ J* h5 y" W( m, p0 [" h4 z" G, N
   if(link[h].number)
5 E" E9 Q  [( G( _4 [  m     i++;}! X( B/ s' ^, `" Z, R
- Z% N' j. J0 z) s1 u" d) z
printf("%4d",link[h].number);
' F% \+ S% R" _% j; u5 Hlink[h].number=0;
8 Q: H1 [) Y+ W0 Mcount++;
7 u# _! U" M( F$ O. W, v}5 X% `* R8 C5 c, }* W
3 V/ a* w3 o& B6 z# g
printf("\n大王是:");
* W0 K8 j+ n7 k) \  for(i=1;i<=M;i++)
0 l' W! s7 q( O# U3 t/ M' P  if(link[i].number)
& A# L( U0 M% L8 g! r    printf("%3d\n",link[i].number);
+ o+ X8 x' J3 D, h; v. t$ T0 f' {0 Y6 s( C! p4 o0 M- ^
$ L9 s. e, H' t
}
  x$ W% M1 W5 D) n9 B) ]! R
第三种是普通方法for循环

$ Y6 C6 ~6 z2 P  j" }7 V#include<stdio.h>5 b5 ]  K7 D1 y" S' s' }
void main()
; Y6 b$ _- V* Q9 ^$ P{ int i,k,m,n,num[50],q,*p;
4 Z" E" H5 h+ G" b% o$ u8 A    clrscr();/ n" J6 n. q3 h4 }, E. o' e, p
   printf("input number of person: n=");# {/ p9 E/ P; Q! K
    scanf("%d",&n);
5 P- n6 q8 ]+ R8 Q0 Tprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只# z  X2 y" G  U7 E: q
    scanf("%d",&q);
! t& r2 g; K8 X# ?, e   p=num;/ W6 Z; \# j* E* J6 L& |
  for(i=0;i<n;i++)# |) x7 g7 V* y  F, n! d
    *(p+i)=i+1;
$ |% f2 D  P; y( t3 h: }  d, {, h   i=0;3 r6 I6 \1 X) H$ x  E+ H4 ?
   k=0;
6 X6 W' C& [8 Q9 f   m=0;+ Z+ Q. x4 O) S% O
  while(m<n-1)  Q+ ^2 J# s. o
   {if(*(p+i)!=0) k++;
$ c0 @; J0 d' y3 Y9 y$ o9 o     if(k==q)& G# A! o" ~0 M, o
      { *(p+i)=0;
/ i3 i' R$ h2 O/ p( [        k=0;6 {( H- o6 Y% `4 \- x5 m# {  |
        m++;
1 W' i+ [. @. C2 A4 W      }! W9 @. `8 m% C: \' W$ ^, [
    i++;5 L  z; A9 ^3 J; P: g" S3 h4 L
    if(i==n)i=0;
4 h( ~7 s& A( U1 I0 O4 _   }- W1 U  y1 @. ^4 G
  while(*p==0)p++;
: D7 J, {( _0 y5 ^! P    printf("The last one is NO:%d\n",*p);* d6 e# v' ^2 m* P/ P8 z) u& r* j
     getch();! k' O0 G5 A/ m, j

1 Z1 h* F* ~+ R: R/ @}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
4 T: \2 k: a, `  a" c3 m4 j7 qnamespace 又费马达又费电
; O# t( i& Q: H7 o$ ~{% b6 @9 U5 p6 X, S- F' M- ~
    class Program
- X9 _2 E+ `4 x$ i: X    {# o; T4 J( d' j. O  {3 \. l
        static void Main(string[] args)
, o! w7 |* ?+ \8 |( E( y7 P        {. W, l7 N% k9 f+ }& }" a
            int m, n;; E( {/ z; q9 V# H  @+ {- k5 k! |
            Console.WriteLine("请输入数组长度");! M# I# x. H8 K/ B# u) Z
            m = int.Parse(Console.ReadLine());//m为数组的大小
0 Q) L/ I$ m! f4 `! ~            Console.WriteLine("请输入要截取数字的大小");
5 Z/ p) G, A; G" ]' p1 I+ O. Z7 E) O            n = int.Parse(Console.ReadLine());# ]+ z1 u8 \4 F* _8 s* a7 ~
            int [] numw=new int
& q8 v0 `3 o# L  q" z) o, R$ m" c3 F1 s6 a2 V6 u
&shy;&shy;&shy;;/ l" f' o' c6 i- j& `
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
6 @1 s2 s2 u5 q! M" B9 h            {: z+ D! n; ]8 z( p
                numw[j - 1] = j;: q: d! W% E* D
            }9 |  D! o! Y/ t+ X5 Z
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!9 p# H6 s, V/ [
            while (d != m - 1)
% D' `" b6 P; \            {
+ `! c+ G! i4 Z- `                if (i == m && d != m - 1)
1 f: n2 ?% \9 f; u* I& l3 R                {
, @2 O5 {9 T0 |2 [' ^/ A                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!$ s( I3 T  v" V4 X: G/ s- D$ y
                    continue;7 i% a/ q. T- r/ y
                }
  {0 U$ b1 S. Y                else8 }& j, ?" @) {
                {6 }3 }5 r- @. u- Z
                    if (numw[i] != 0)
" @8 x1 h$ G/ i7 h                    {( B( C5 B* {; ?  \! X
                        i++;
6 G: a+ h  }& m                        k++;$ P. M5 r( J( D# l% U& b" Z  T7 `
                        if (k == n)
4 j/ W. N$ d& w                        {' |  T% W3 t, v6 b% l8 n
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
. |. ]3 I& X! E, b3 i5 T                            k = 0;. g; C: |; V/ ^( W# b
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小11 J: w  a" b3 D- r6 f5 S
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);6 R# z; S" t" A3 E! ], E, B
                        }! P4 B8 ]5 M7 \, P8 L
                        else//输出暂时还没有改变数组元素的值
) v; z& X8 X$ n  w                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
& f. ]6 B  E; K" {1 W                    }
- Y" r! c: g! M1 {                    else+ ]& N* y# j7 j' b2 Z3 T( g
                        i++;//数组元素为0,直接跳过,不计数。。。
; |& |, Y! i9 \1 d/ P8 v3 k! e                }0 G2 S, {. C' x5 n! f
+ y4 k# |2 U0 S* q' M8 H5 a) w

9 d1 ?) ?* X8 K) n            }//结束while循环' J" e% r. j7 Q' u. W. m* X
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦! k0 Z7 B. [$ F! e5 V* `: n
           
! y7 @/ i7 w# Z) }# m/ K' g' h                if (numw[i] != 0)
# k) H" W3 R2 R2 z  k3 ~+ r                    Console.WriteLine(numw[i]);
# {/ l; T% m: B2 Q  Y           
' {# m, s# r& e$ G            Console.ReadLine();. U6 g/ t* U3 c& L( j% ^
        }
7 Y; O6 \2 _- D' v: j    }
/ i) g# [* E3 P8 C* L- F}
: ~. A- K! H- k' G8 M" C! K% o2 X
小甲鱼最新课程 -> 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-10 17:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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