鱼C论坛

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

猴子问题

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

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

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

x
大家好!
& ^$ x( k  E& o: l: X# z这几天我在忙着编一个问题,我用了一种方法编出来!
: j1 S# k, S! Q$ @但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!. U. l9 u9 R8 E  f& v
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
' \& e. t) U0 J6 I; u2 O6 Z
% m0 h% j. g2 t. y$ z$ g8 S" V! H! i! _5 N7 D0 H. I& M( l
                            题目
  z8 e9 F8 }8 n山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
0 |6 V* N) R# w0 B# y( i: d第一种方法:利用循环链表
2 `& w; h0 m" p+ N9 W#include<stdio.h>; c# O% A8 B/ h& y  a' R
#include<malloc.h>
* U+ U# \( s, M; O+ s+ p#define M 8            //共有8只猴子# s. Y- m( |. T
#define N 3            //数到3只时退出第三只$ k$ Z. T3 e8 A5 Z; T4 N9 q1 S
typedef struct monkey
9 \1 l- E/ {  ^) ?3 m7 G{int number;
# m0 x! P1 F6 m; E, d# `: ^* bint flag;
% V: G6 c, M$ a# T& Istruct monkey* next;5 F, t' A* d0 Q3 C/ D
}MONKEY;
% X" I) z6 E- K+ u! n. s4 [main()/ ?& j0 [/ ]% `+ l
{ MONKEY *head=NULL,*p,*s;; [$ I  J3 w+ Q6 h* Q
  int i,sum=0,count=0;2 ^. g) S, H* L2 _( I$ V
  clrscr();              //清屏' _+ q& A$ L, C; {" S- ?. P: p
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存8 g6 r0 ?& t5 r4 \# A" N: M0 w( ?
  p->number=1;p->flag=1;9 k  M4 ~5 U# L4 B! t8 g
  p->next=head;
% O! c3 w2 H' u2 g" V! q6 B6 F% E6 F  head=p;
  s3 ?* @9 C& M  K, V+ X: o) p  for(i=2;i<=M;i++)
" Z0 u2 y2 m1 Z1 v1 I* c    { s=(MONKEY *)malloc(sizeof(MONKEY));! w# k+ L! N- ?% o, D4 T0 H
     s->number=i;s->flag=1;
3 v$ z* K' v# L  }: d0 Z0 v- W5 e. C     s->next=head;' _9 x* ]1 s8 m, m5 y3 j
     p->next=s;p=p->next;7 C2 V' i9 }. U* o' I5 ~4 I$ I  o
    }' T5 R0 t& t9 r' H
    p=head;
" Q0 @  R: z- P! v9 b   for(;;)
- @# P/ _  N: U9 b. I    {if(p->flag==1)
: `( w* G% f1 v3 L4 c       count++;
5 c0 K# e% {; a1 l     if(count==N)' i+ u2 A" h; J6 G6 j; W
        {p->flag=0;, _4 M: |) q  O) B
         count=0;
' W7 N# ?) C& j9 z+ |6 k         sum++;}9 v0 s- z4 U! t; l) S( Q
     if(sum==M-1)$ U& T0 E4 H* K- y/ Y+ ?0 R! p$ s
        break;
  J: U$ V6 q  ], J* B     p=p->next;/ b! f  \2 J# d% ]0 ^  r0 g% H
    }% o: q) T. w& }' Y. c( J
    p=: C. J& t- g$ B: z. P
    head;3 H0 \4 d# d$ T7 f$ e3 l7 o  g
    for(i=1;i<=M;i++)- B0 h$ A+ n4 k
    { if(p->flag==1)) p1 \6 Q, l1 z7 `% ^. V2 K: {  I
        printf("\t%d",p->number);' ]! U4 n3 }- i. ~' R
      p=p->next;
+ Q- m! H5 q7 w# ~    }8 e% ^0 ^) q; ~' n
7 d; Y6 X( Q# m1 b* z

1 R- j3 h! i/ Z$ N9 h6 ]( [: a7 U, Z, s9 m# a
}
3 D- L' w# M" z: U/ {, K6 J
第二种方法:数组
$ m# s9 I$ {/ y& O& K& t#include<stdio.h>4 c6 [* O% }/ |2 V
#define M 83 r  m$ n6 g4 @  n& x& c
struct monkey
6 I/ @5 H3 v/ \{int number;$ O, V" a% h9 J& E* M, t
int nextp;
- [, `5 }3 ?2 K* K}link[M+1];' d7 {" L' M' f6 |

" D- i7 z+ H) P1 E9 `void main()/ R7 L6 T0 O* D) ?/ d2 R% G
{int i,count,h;
9 n9 V+ D  v" V% a: L* q+ J' Cfor(i=1;i<=M;i++)  G3 T6 Q' g; E: Y9 S  g
{  if(i==M)
' p+ l) |3 e  v4 B( m% \- h   link[i].nextp=1;
2 g: j9 ?1 U& a9 F) b( m% _   else
: @7 ?9 C* e" f   link[i].nextp=i+1;
" n  O9 ]3 U# e  link[i].number=i;0 A; n  L6 W0 K
}
* u! y# q+ \) q8 Q3 tprintf("\n");
) I' K5 }. p+ pcount=0;
" [, r# O9 [$ E/ m9 o% K& O! Nh=M;
# D# P' ~. U5 B! v8 k# nprintf("依次退出的猴子: \n");
! N: w5 \1 Q' Jwhile(count<M-1)
+ c5 g2 K8 G; f" d4 n{i=0;5 A" @, v  ?' ~( u3 C0 D
while(i!=3)
. r* x2 Z) m8 h1 t6 R{ h=link[h].nextp;
& W: J) w1 }2 M5 [+ s  x   if(link[h].number)
) u( G6 g& u) s3 V$ [     i++;}9 _* m5 S, s- x" Y9 w$ C

, p' R  h2 }3 Q- ~+ g* _printf("%4d",link[h].number);# h0 w9 W+ f% `3 Q8 @
link[h].number=0;
: r& H- h3 S6 I# K9 D/ @' Jcount++;' S+ V+ m& U( r  a+ V, h
}
1 G  Z; t7 l3 {2 L7 s0 U* O9 J( d/ g* `( y7 p% c
printf("\n大王是:");* [* [! ]3 t2 \% w" ?: t
  for(i=1;i<=M;i++)" E4 x. e1 n6 Z! ?" B3 }
  if(link[i].number)# O& `9 R: m% a% g! P) ?
    printf("%3d\n",link[i].number);
& l1 W0 d9 A* l  C" f7 M( T) @, U" W8 k6 v/ B
" U- g5 l$ o2 e; y) }
}
, G$ E! `/ y) M4 h& D4 a" I2 I/ J+ {
第三种是普通方法for循环

$ x& p( M& b6 Q- x' w- X) _#include<stdio.h>
6 ]) J: {: O! Wvoid main()
  }0 Z8 F* I2 f0 ^9 ], A! X{ int i,k,m,n,num[50],q,*p;
& l$ x! q" W$ B7 G2 j3 Y    clrscr();# k7 h' ?4 q- r5 Z* ]0 s
   printf("input number of person: n=");) \6 q4 s& g8 g3 R0 N/ u
    scanf("%d",&n);- g, {, E. |* L9 n' F" k9 s
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
* y, a/ a' D1 m# f    scanf("%d",&q);
: U- O7 n$ F5 S! ~   p=num;4 K, _1 q; n4 l
  for(i=0;i<n;i++), }6 b! y' `/ K# l) L$ Q3 \
    *(p+i)=i+1;+ q8 f5 B8 ^, u/ h: q  W
   i=0;2 ]" j0 ~/ N4 `- t' o
   k=0;& N7 \6 _; R# U5 v
   m=0;  v% U% x9 ]' y2 J
  while(m<n-1)5 r. r! A$ j( e8 ?  c' I$ ~$ L$ S
   {if(*(p+i)!=0) k++;/ q# [" Y* }# q4 l: x& o; @
     if(k==q)+ t) Y+ C7 ~: f, c4 }" |5 a
      { *(p+i)=0;
% h8 q0 l- S9 H1 s5 r1 j        k=0;
. v2 R8 v, g; w        m++;
$ F6 {: u+ _6 J9 x      }0 T8 M# ~$ Q6 T+ @% X3 F, f
    i++;, Q2 O* V3 a/ t% {
    if(i==n)i=0;5 S- |* v( ~1 U1 C/ ]; f5 \! `
   }4 o$ x9 }) }: t" E) }' G: O: U
  while(*p==0)p++;
: S. q/ B6 q1 I' l- i' c8 i    printf("The last one is NO:%d\n",*p);: Q, _8 r8 o1 h; v6 H
     getch();
; \9 A  F* o; G% P, Z3 H2 \# h% m) q4 K" P7 ]6 u9 \
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;- e+ O8 S( a: }. N3 K
namespace 又费马达又费电
" n( s( X2 C8 Z{8 M' Y* b$ u$ i# p" [" U* F9 h
    class Program$ `: a, f8 g- e6 E4 o2 Y
    {# z/ f) @! O' i7 x; u( i
        static void Main(string[] args)3 J: U: k' i* {8 v
        {
' s) }9 h3 D+ @3 \# d  Q; C* h            int m, n;% j2 e( N4 x% S  a4 ^
            Console.WriteLine("请输入数组长度");
0 F- Q& z8 N8 l4 E! H: p8 i' ^& a, D            m = int.Parse(Console.ReadLine());//m为数组的大小9 S/ m7 O5 |7 S" q. |" U; E1 P
            Console.WriteLine("请输入要截取数字的大小");6 k' X  ~. B: Q: d8 q* K
            n = int.Parse(Console.ReadLine());4 q2 g" m- i% G: i% I
            int [] numw=new int" Q% a9 ~! G1 W+ p. b

! v, o  {, G: m5 O/ \: J. Y  `4 i$ R&shy;&shy;&shy;;
$ D, J" s, s' l9 M* t4 `            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
, I( k+ M' X' ]2 o" G5 E  d# U            {5 Z0 c1 m  d+ s1 D
                numw[j - 1] = j;( \& C+ ]5 y0 s' ~# j9 l3 G0 n
            }
9 G. H! T5 ]' d            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
/ ~, m, C; |9 P8 i% C            while (d != m - 1)0 m. d9 H0 W: q* H
            {! |% r! Z4 C$ z2 y) L, l
                if (i == m && d != m - 1)
' @! J+ M7 F1 ?2 o9 B6 `                {
* Z. b! z2 C7 K: |/ o                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
: p0 M; h+ X+ |& G) d                    continue;
- P0 d" y. I9 y                }
, E6 O* L. M# V& a6 f% C: Q7 L                else
/ M: e6 z$ E' ~  J                {) B3 |" _9 G6 P& s9 V
                    if (numw[i] != 0)) O* b# g  C5 k9 \8 k
                    {3 L/ [, A) S) H: R
                        i++;$ [9 L( R3 X9 ]* t
                        k++;
1 D( I$ S! ^' P5 q  J# m4 \9 E                        if (k == n), U! _5 M+ s* Q0 S8 U. J2 `
                        {
- x0 D4 K1 F! U/ o3 M                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
# [  s1 t. }/ r. z4 q  ]$ p& f+ H                            k = 0;
# v# L1 k* n& [+ y4 j" k              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
, t( ^/ z' s( E" L                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);$ _( Q" }: t8 C2 r0 B4 s  {
                        }* w$ ~$ @$ H+ N- D+ }% W8 h
                        else//输出暂时还没有改变数组元素的值
) v5 v8 W+ N0 ?/ x2 g, \' t                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);1 V9 ]+ Y2 H) w' Y9 P
                    }
# l" O& x+ F' k- J7 m1 ~- M( T$ u                    else
2 c  i, B" f$ S2 u+ \) s; ~0 B                        i++;//数组元素为0,直接跳过,不计数。。。
# D  {8 F$ F) |7 q5 {" t: _5 M' d                }
) ~* _- g7 ?$ B
3 e& c) s% S% Q) {. C  C
( {$ l- t1 I: F' F9 r* R! N: c  d0 ]& t            }//结束while循环- Y9 w, f  i/ F7 b# B
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦0 G1 \/ M" a0 X# M
           
1 }4 Q- |4 c( ~% r$ P. s                if (numw[i] != 0)
7 C0 A# y# F5 y# v: l6 {, B) }                    Console.WriteLine(numw[i]);6 f; A/ c, H* y" x( x
           
6 R9 O' y6 i0 ~/ r' S            Console.ReadLine();
+ F- X/ k$ O# N- H- b        }
5 I. t! ^: p, E$ E    }
3 A) B; O6 m! T; {# b2 H}
6 G5 T% h$ t9 h) I! V+ L6 u* _
小甲鱼最新课程 -> 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-3-11 04:08

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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