鱼C论坛

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

猴子问题

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

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

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

x
大家好!, J2 f3 e" `: r& x  M/ [
这几天我在忙着编一个问题,我用了一种方法编出来!$ z; C' s; l5 w$ a- f3 `1 E$ t
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
* {1 @( n" J! l: `" ^) ^注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
! @, h% r% [8 M6 A+ P: R) ]0 Z$ u

) k9 @' o$ ]6 n, U
                            题目  C2 z  \* W9 X
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。! M9 |* W& P; T4 r7 ~) o! i
第一种方法:利用循环链表+ M! W% u" D, V/ C) l3 I
#include<stdio.h>
: h, J% L; E- W#include<malloc.h>
3 T. c' W7 t% D, w& Z$ ~#define M 8            //共有8只猴子
  q- N# }( _4 h: Y% M9 `4 W#define N 3            //数到3只时退出第三只
5 U( q& @2 _% t' d( l4 Q9 Itypedef struct monkey
& s4 d* w+ S* l# x. v* d{int number;
) B. [0 l! W1 m4 ?. W; b( h% jint flag;
0 x$ ~- ?8 U, `0 [0 u  ]* Kstruct monkey* next;
) f: B; X* L' l. ^}MONKEY;0 G: O* \+ S' u" @8 A
main()& ~! G3 m2 p3 }2 K* l0 `
{ MONKEY *head=NULL,*p,*s;5 m4 W& J8 K2 H7 t  f0 w8 E9 Y
  int i,sum=0,count=0;
( }( _; q( s. s& I0 c  clrscr();              //清屏
1 R1 U8 r/ a/ r: l  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存& i$ Y+ I6 W+ [, t4 V" L: C- B
  p->number=1;p->flag=1;% O0 P% [1 F, D2 t
  p->next=head;% q4 S: a$ y2 l" o# q1 M
  head=p;
  M5 I8 T* A  W, g% ?  for(i=2;i<=M;i++)( X* o& U' W4 M6 ^' i: {
    { s=(MONKEY *)malloc(sizeof(MONKEY));
  h6 ]$ j+ ]8 L     s->number=i;s->flag=1;
. p4 l- K( f3 n0 ]) n! e     s->next=head;
0 R* w+ x6 J/ l* ?" M     p->next=s;p=p->next;7 a4 |; f( L/ k" \3 [, E
    }' Q4 X7 K; ^6 b3 o$ `
    p=head;
. q+ H2 E- w2 B8 @; k; h   for(;;)( W! `/ W3 |' K/ c  y
    {if(p->flag==1)
9 y* j. J% o0 B4 U9 V( p+ t) k       count++;
/ r7 p7 _9 _- S     if(count==N)- V1 K  ~8 d3 q9 a. w, S) V: j6 D
        {p->flag=0;
+ D. B7 l; D9 w         count=0;2 u6 u4 a2 O7 P* [6 b" m
         sum++;}
7 |& j8 X3 W8 L$ R     if(sum==M-1)
. {- ]" _0 ]  e+ _( ]/ U0 ~3 X        break;$ m, H- X2 {) A2 r
     p=p->next;
: D' J2 I* }1 x- J9 i2 k4 x7 }5 b    }9 x' |8 ?. n$ j
    p=
% h9 A, q3 A* N  J    head;
8 F: _7 I# L: k8 X6 N, Q! W% h    for(i=1;i<=M;i++)
9 g7 Z  |4 _6 o9 B    { if(p->flag==1)3 q2 `! C/ a8 N  @1 W5 F) q: N
        printf("\t%d",p->number);
1 M: y; z/ n" P/ V      p=p->next;5 R2 p! h7 o& i! P! N+ {9 E, q/ M
    }) M8 A" _: T6 N/ x2 R% Z: ~  q: Y
. R- p$ M! J- D" W$ m, T! h" J
0 v) T  _  I' x# W8 g- _

4 t- ~3 G4 d$ C& [/ w* s}

2 G9 j3 G' E! z) @+ |第二种方法:数组
1 I2 M1 t) w! J#include<stdio.h>0 g% T- V! j# O4 k7 n- c
#define M 88 q) |; C2 Y4 \% e. b' j. X
struct monkey
/ q/ h  E6 M; S1 a, n/ Z$ f0 \/ v{int number;
8 K! p7 @. U7 D& W. K. eint nextp;
* ?& [; ?5 T9 k3 o" b; {2 u}link[M+1];
- F. C  T+ @3 {
8 s! d' I* E0 a6 Mvoid main()
0 B  O3 G( o4 v7 x, g; ^% s8 t" b; ~{int i,count,h;' o, p  P: M. V7 h- O( b2 o8 \
for(i=1;i<=M;i++)% c8 [3 ]' ?, }3 u5 ]
{  if(i==M). G- M$ z& q! b0 K4 S) {
   link[i].nextp=1;/ ]) K; T! ?! d5 e( T  g
   else0 A4 Z  A, G( @+ n! G
   link[i].nextp=i+1;
( Y% e! U. o( x  link[i].number=i;5 v" u: Z% R% Q9 I  y3 I
}
% u' b; `4 m9 Y* |( o. ]printf("\n");
% h. e  c4 D" P6 n- g0 f/ _count=0;
; u' H* X0 O4 ~* H% G/ Ah=M;1 C% M5 N) Z% i4 W
printf("依次退出的猴子: \n");$ @, E" l; W) W' _& u4 u8 f. Y; b
while(count<M-1)# ^* o* {! l: s) w
{i=0;1 F. n9 j7 \3 U2 C3 z" r* t6 g& @
while(i!=3)( ?1 V7 F. o' D$ W0 Y% S4 a2 @7 ]
{ h=link[h].nextp;. C# ^" a  V& x7 p4 g
   if(link[h].number)
6 a: T8 B# r' B6 `     i++;}3 y+ G9 X+ `9 Z# x6 x/ R

. k8 ?0 c0 w9 @- e7 i3 Hprintf("%4d",link[h].number);* I  A* ?) ^+ U; Z4 y  F/ S4 f
link[h].number=0;
. }3 M7 Y0 g; g, q3 [+ `# G( Bcount++;
1 j/ C+ C8 t6 m9 e( i}
4 C' g* ^' @# u$ a) _: T! P& }9 h$ |% v0 i# o
printf("\n大王是:");4 ?4 J+ H# o' i$ C* e; _
  for(i=1;i<=M;i++)9 t5 }& ~7 ?9 G$ |
  if(link[i].number)0 N6 k/ C$ a4 q: Y" j8 R
    printf("%3d\n",link[i].number);" `7 O+ S$ u$ B. @7 `; E
7 T+ S4 K+ E/ v! e

, ?' c9 s  _: L( T8 i3 P}

! o8 S, s* x, z' k第三种是普通方法for循环

( s+ i& g, U6 @3 ^- {% X# k% g#include<stdio.h>
9 s  ?- Q( m; X# `void main()) a. E0 ]% T" d  z/ E# X7 j$ Y  n
{ int i,k,m,n,num[50],q,*p;
" z( v: v( h" E. Y2 g9 S" U5 d    clrscr();  S* u3 `- H. j! d7 A" K
   printf("input number of person: n=");  A- s  `1 N" |- `) T  j
    scanf("%d",&n);# w0 e$ o4 t4 U( u
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只% w8 X( K; s) l) g
    scanf("%d",&q);
& q2 T# `. j) T* N   p=num;
  ]5 W7 i# p% q' b8 t( W2 w8 V5 b  for(i=0;i<n;i++)
9 D' T6 O) i/ [& }. ?8 Z    *(p+i)=i+1;
) ]% {2 |% T$ G1 b6 ^' J# q7 W$ X   i=0;+ q0 Y* `  {: L: s  G4 d7 d, d( C3 M7 Z
   k=0;7 S$ Q# H# g5 o7 B
   m=0;1 @# A) N9 r% R6 [
  while(m<n-1)
3 \1 |8 r. Z$ p   {if(*(p+i)!=0) k++;
+ r# E4 i: i8 h     if(k==q)
: \! H  G( P) P3 Q! v      { *(p+i)=0;
5 k) M8 ^  G3 A        k=0;
1 s+ q, E( N8 J& Z3 d( p        m++;- Y/ w. Q) P( e6 c9 z
      }0 p0 u# i+ q9 G& S: B0 l
    i++;
( N0 Q5 d) q* n& \# T, c* S    if(i==n)i=0;5 R( H. A. a% ^$ o8 F
   }
0 s' q7 j7 r8 S) P: s  while(*p==0)p++;
& p& [* g' J: _& |; x! k    printf("The last one is NO:%d\n",*p);
! M/ P3 T: o- X5 r& @     getch();& w& f) p2 K, D! Z. f; w
* G$ ~$ Z- V7 X" T8 ^# Y
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
6 V( W2 u+ U; tnamespace 又费马达又费电
5 ?$ X9 n& }, d* Q2 Y" S{0 P$ F. H* G( s& `+ B; g
    class Program+ d: I( W! o3 Y/ P  _" K
    {
3 t! P6 c8 O: N  F2 K        static void Main(string[] args)$ q( v9 v0 t7 ]0 e1 I: @: G
        {, V+ \% v' \1 f! U! `7 E8 H
            int m, n;- _+ T* g8 x, |- M
            Console.WriteLine("请输入数组长度");
7 D" ?) u" M/ }! W- R+ B2 l( s            m = int.Parse(Console.ReadLine());//m为数组的大小
# y8 S" \' a4 @            Console.WriteLine("请输入要截取数字的大小");
& U' ^% q) T8 y" r; @6 @' v            n = int.Parse(Console.ReadLine());" h' @; X# h! @( C
            int [] numw=new int- v' W  e. j1 Z' B" r: K3 O
. T! f- ^7 f# C
&shy;&shy;&shy;;
! [! i7 H: K$ N8 F2 C& e            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
3 f& f4 q3 \- g0 o            {
( `) ~: X6 }/ T& \                numw[j - 1] = j;7 b9 ^  F! j" g* h
            }
# }1 c) \- E  I  t% I            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
, ]0 d  Q+ A0 Q3 D5 ]# k$ H            while (d != m - 1)
) g& m0 V8 R) u9 d            {
8 {' C& O6 q" L8 ?& i* N  e! A  D                if (i == m && d != m - 1)0 R& [% K0 j# C- p4 d2 ]; m8 j
                {
$ f# N, E6 _. S: k* V' E! X                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!' r! H2 z' N- K- ]
                    continue;
2 n1 T2 U1 P. {. a                }
+ N8 o" \( _/ h0 j; {6 b4 J                else
5 h7 r# M5 [1 w; c# @# n2 ~                {, g% m4 s; V3 a: G4 I. H* ?3 R
                    if (numw[i] != 0)
, [# m# Y' x! D/ B3 u$ z" u7 T                    {2 W4 ]4 M) S9 e+ c7 @$ l+ s
                        i++;$ s' S9 b/ o3 \- x
                        k++;
. s8 p: [) K9 q4 w; @                        if (k == n)) {. P8 j2 p% L/ S/ d6 p
                        {
) ]+ A7 z" w: T" M4 n                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
) ]0 W. O9 c5 D                            k = 0;
5 }: x( ?) l* A. Z( h              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1" @" U' Y8 N2 E0 P3 q7 [) v
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
' a/ |! V8 N3 X$ l; o                        }
. H: M- o/ `# K6 {8 _                        else//输出暂时还没有改变数组元素的值6 r8 c' q5 y. Y3 U) t
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
# P# _/ f; Z: b% Z9 s- w# m                    }
$ A; U# F1 o3 V6 L7 @) F                    else
( ]! j# N( L  d: L                        i++;//数组元素为0,直接跳过,不计数。。。4 c- ?8 v8 x6 S2 B! ~' ^
                }
' t" @; O! a9 n5 `8 f+ o
1 p; u6 h: `; {7 ?7 _
' s' \6 t+ t% `' {8 |            }//结束while循环% C3 H+ m; V3 G: T7 B
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦, F* [6 E. L) X; I/ ~+ l
           
# }$ ]) K# f3 j0 O1 u# G                if (numw[i] != 0)
" V( @) o: R: I! N6 L  a                    Console.WriteLine(numw[i]);. V! {; Q, U7 C' |8 t. O
           
7 I) }+ q. V+ a  j2 K6 W9 w1 P            Console.ReadLine();
- D& g' P: @6 \& _4 x: w1 {0 {        }
! V. _# i* G, A$ a    }3 d8 Z" O: s4 o9 T8 B3 s, B
}, A2 q- h$ f* X: M
小甲鱼最新课程 -> 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-23 00:39

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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