鱼C论坛

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

猴子问题

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

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

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

x
大家好!
3 s" v0 r- R! i这几天我在忙着编一个问题,我用了一种方法编出来!4 P( [! U' N; D
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, P+ p+ y. c7 Q; t( d( W9 t8 A* ?  l0 o
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 N# W+ |7 G* g" K, e1 D4 k" O! V) C1 {2 n! o

8 F: k3 [1 B  P9 X4 u( j) f
                            题目/ y: b1 ~, O1 A9 W% v! V0 t8 X/ T: _
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
7 v8 k. x6 o1 c. y第一种方法:利用循环链表/ K5 `, ~5 M7 s; k- `* A6 H( ~
#include<stdio.h>* {- G+ U( ]- A1 L4 ^. s7 @
#include<malloc.h>% p' a8 V. x6 O0 \  R1 s
#define M 8            //共有8只猴子
( X0 U. X/ Q. @  ]: u: ^#define N 3            //数到3只时退出第三只! `! o' H/ n# k- Z$ y7 a1 H5 }
typedef struct monkey
1 i* _6 o3 u- o8 K3 g0 V! o" K% o{int number;7 m& `# X- b& d8 Z1 Z
int flag;1 P" j; T$ e) P; b, I
struct monkey* next;* S( d$ I3 \9 q# w( i
}MONKEY;
' B! y; b& u* L' x7 Imain()& d0 {  c; [" Q0 f
{ MONKEY *head=NULL,*p,*s;
. n& U' J5 w  C% ^1 r9 o6 ^  int i,sum=0,count=0;& A% B! Z* s* ^' u1 w
  clrscr();              //清屏5 k. s% [( O& t3 M7 W
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
7 E1 u/ h9 |  D  {/ f  p->number=1;p->flag=1;& i# C+ a! p# Y& {
  p->next=head;
3 w/ L- Q$ S% E( V# s  head=p;
5 w# z0 l; V1 u$ v$ P: i/ P) c  for(i=2;i<=M;i++)- N. o5 ^/ t( F
    { s=(MONKEY *)malloc(sizeof(MONKEY));- M3 Z" x  i; ]/ u& A1 V
     s->number=i;s->flag=1;' I# d, R7 v9 _
     s->next=head;
6 d6 v# ~3 f5 Q- P# O! g     p->next=s;p=p->next;
9 E; T+ F7 `6 \  W0 u5 D) [    }5 T4 P$ Z; i, u6 M& [
    p=head;
) z6 a  \5 k, g   for(;;)
; w/ i7 y6 d1 H3 H: L7 Y9 w    {if(p->flag==1)
6 R- [7 t7 I6 g8 f+ I+ f$ X       count++;+ g$ z4 K9 h$ w3 L4 X  r& I# w( _% ^3 V
     if(count==N)
7 A5 X2 j$ n# B- s* ~' o1 M        {p->flag=0;
7 V! X) E7 r1 F, I9 O% X. ?* W         count=0;
- ]% b* w* u5 W# _1 c$ @% x- z         sum++;}+ \" m, s2 ]. o3 w( j3 D& Z
     if(sum==M-1)
! e0 j3 a) ~; C        break;
* s( r( a/ n& I! s# P. M     p=p->next;
1 u0 m+ u0 w: O    }2 B! x6 H% [4 z4 Q" h, z0 e
    p=
& |  ~2 p) J9 w, o- n3 v( E    head;
7 T( M9 T: Y" @6 _' f) |8 @; {    for(i=1;i<=M;i++)
* L/ w$ E* _4 Z, E    { if(p->flag==1), x/ B5 v6 D  F2 a+ D$ T
        printf("\t%d",p->number);7 S$ U$ y( C  g0 p& O: J' f: J
      p=p->next;! u5 ^& }8 g. O; o6 H. H+ Y
    }
* a4 Z4 X8 {: S. X# f7 C8 O3 k7 O0 m8 N3 M
# W* r( B8 }8 D8 }

0 q, G7 e* ]& s( n8 \}
% O9 Q# r+ s0 A' ~6 }6 M; N7 m" }
第二种方法:数组
3 q4 w) i" }' c#include<stdio.h>
; a1 `4 W( S: _* H6 J" G#define M 84 e% z, V8 |6 M8 i/ V
struct monkey7 e2 E* A" c& G& j( r+ ^. ^
{int number;$ ]. T2 g. e  b7 v
int nextp;
0 I  N4 s  X& @* c7 A}link[M+1];% W9 t# d- {8 O" F
) Y, R! ?' z9 k7 q& K7 |" H1 V) k
void main()
0 g+ `; ^# r, p9 z) z2 w. _{int i,count,h;; N1 u& b8 Z" w* v) P
for(i=1;i<=M;i++). y' a* N/ c  u4 p
{  if(i==M)" Q# Z/ p2 Y$ V- ]9 g7 h" F* j
   link[i].nextp=1;
* ~' S' L; o8 |' G# A- G   else
4 H6 R$ L1 w4 _( z   link[i].nextp=i+1;6 b! F6 s) b( j- k* C; v
  link[i].number=i;
: }2 Y9 `. y) |; ?4 A  s}
: K" g$ m1 S% H, k$ S1 ^$ C3 c# Zprintf("\n");
: R) b/ `6 {; p& G; T3 C9 K) g& acount=0;4 v4 e4 r9 m3 G5 H
h=M;) I/ i6 U, M# f* V/ M3 ]
printf("依次退出的猴子: \n");
8 h2 p6 \+ W6 N* \- C# d' \& wwhile(count<M-1)4 ^% m0 C# C* Z" ]1 X
{i=0;3 @5 x. r  T8 M0 [! k
while(i!=3)  Q( x/ Y6 S3 d
{ h=link[h].nextp;
8 Y5 s1 t. E# y: P- r   if(link[h].number)! G' e1 U1 t- m2 v$ `2 l
     i++;}$ x7 d+ V! l/ x+ s* v- b* ^

, w; t% U3 D# B! qprintf("%4d",link[h].number);
) `( [7 C5 V: e6 Blink[h].number=0;& E: L+ U0 R. e5 |
count++;( x: B  N# P3 D8 m# E8 m
}! L! p0 h8 l% ]" T

& `9 q1 m( T) oprintf("\n大王是:");
# Z; b# E! ?: a5 x  for(i=1;i<=M;i++)
  _1 x1 B. f7 B  x  if(link[i].number)' q) O3 O7 j  n6 q$ I
    printf("%3d\n",link[i].number);
! v3 L" y5 a7 p, q$ N" q+ Q" O- M0 {; o
0 q# q* x) }. f' I! M1 Z
}
1 Z! J% t7 z; W7 N; J
第三种是普通方法for循环

0 S& x" }$ d% i' @6 E& {4 w#include<stdio.h>
/ i7 z3 F" Y' l2 b9 s$ E- s9 wvoid main()+ B  S. B5 J1 M* z" i, t
{ int i,k,m,n,num[50],q,*p;
' `7 g' u' c; |    clrscr();' R/ E  h( l! {: C
   printf("input number of person: n=");
" w, ~6 t& }* s& Y- ]    scanf("%d",&n);
9 K2 ^7 g& m% v& W7 q1 Zprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 a3 S5 j/ l8 r5 n$ f- r    scanf("%d",&q);; j$ X3 W2 G0 ~- l0 P1 {
   p=num;# O8 u; T6 Z: l4 ?$ `& h
  for(i=0;i<n;i++)5 U9 z" ?( P7 P) o) q$ Y
    *(p+i)=i+1;! E' u3 s8 N; {. E4 c' ?& g. \4 _
   i=0;
& @7 m! Q; A. ~5 U   k=0;( }/ O# h* d% F5 ^9 g  e% c* j  d
   m=0;7 I, t$ e; K, x- U) ]% |
  while(m<n-1); j7 K. @- P1 l6 I* g! R
   {if(*(p+i)!=0) k++;
5 `. q$ z& D% F, F3 _8 \/ T! K     if(k==q)
+ u4 {* v# A# ?3 t+ M1 _: C      { *(p+i)=0;& ]8 T" R6 X- D0 p. [
        k=0;5 F- G0 h1 a/ R% m2 T! d7 F: ~
        m++;- {- t1 o6 i4 \, r" m, j
      }
7 M5 i5 O: I( w7 L    i++;
; R  p) b! O. [    if(i==n)i=0;$ r. R& o+ f% }- O- R( G7 _
   }
1 |; y3 L$ Q0 ^& T# `6 |  while(*p==0)p++;
5 x% n- O: V( ^( g3 Y9 j* ?    printf("The last one is NO:%d\n",*p);
8 ]# y  k* Y8 ]. `* D" u7 N     getch();! K; s: q  L5 _+ X- Z* c3 i

" G% s/ K/ _( ^1 }% g: }$ n* J}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
6 c  y* [% q% |namespace 又费马达又费电
5 p# E1 {0 Y. A8 z- o{# [% T8 Q6 ?. S3 p. z; x
    class Program8 P* Y& ^4 P) Y' F" |8 Y0 Y
    {
- d8 z$ X7 H6 J0 f& K7 j        static void Main(string[] args)
' |1 e! U# g8 W- E0 X        {7 F1 k$ [! ~1 B* C
            int m, n;
/ R- p8 L3 g' b5 }            Console.WriteLine("请输入数组长度");
$ j4 [) R$ ?, H3 e/ C5 }            m = int.Parse(Console.ReadLine());//m为数组的大小2 n& N; j1 _+ M  I5 i5 C1 v2 G* W1 w
            Console.WriteLine("请输入要截取数字的大小");9 C. k9 ^- G/ S
            n = int.Parse(Console.ReadLine());
- h% K8 I* w) |            int [] numw=new int
9 Q+ m1 K( Y. v' E: w
, T& B5 [2 A2 D! b. E$ ?&shy;&shy;&shy;;
5 Y2 }: a9 W7 x( v, O5 v/ X            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
( K. ^' ^# \6 R* X& P            {5 G; I! i6 d5 c+ m
                numw[j - 1] = j;
6 a$ d) H. H& g: d- L            }
  t1 k$ W( K% b% u8 B- ^# K            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!* p9 V& c- x' ~* k: B
            while (d != m - 1)9 L! X) @4 n' A% p% g) c- V
            {/ A7 C9 _$ w$ T! J
                if (i == m && d != m - 1)' J0 k7 o" }, N, Z3 R, b$ W
                {
+ {( v3 C0 W! L! k8 n. t* `6 R                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!+ w$ d% Y! h, [! m, o
                    continue;2 j4 I) V2 R$ \& G0 w5 ]- F
                }
% [( O' I& M8 Q5 S                else5 A: S5 \: ]/ {7 p% A" w* P) l
                {8 {0 O! @3 ^, K- ]5 T
                    if (numw[i] != 0)3 ]0 `) m! Q! M: K+ G
                    {3 o1 R, v+ n  ~/ F& R: s
                        i++;4 A/ _: Q2 f6 l2 o5 C# j, l
                        k++;3 x; _! k( f! b4 R7 m, n
                        if (k == n)
6 I8 u3 q$ C+ A                        {
* g0 d5 q* i" B; h1 W) V                            numw[i - 1] = 0;//把在n位置数组元素的值改变了! J. V, d3 n! r: y: [: `
                            k = 0;/ l0 J$ K6 j) V
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小11 f& b: l; _& D: k
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
! V/ h0 n. @7 e! j$ J                        }
0 i. S. a' ~7 ~' M( @) f                        else//输出暂时还没有改变数组元素的值  X  x# d0 G9 D/ ^" N
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
7 i) K. P6 x( l                    }
8 n3 J  ]; p0 V( y0 e, ~. F5 j                    else
: E* m! X2 U  i0 h- C2 s' i                        i++;//数组元素为0,直接跳过,不计数。。。
9 j' x: G% v' y/ B0 x! v                }0 H  b1 J' l: m; D4 `) ~$ n( b

0 o% `6 A& m: h7 K0 a( z  x. k1 R; t. x5 F$ c/ n4 W9 `
            }//结束while循环. E  x, X* w( [; ~, ~
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
: ]& s; E9 R4 ]1 f; }8 Q" ^. L           
, m  h4 `- Y3 b* w6 ]9 i6 o0 v4 t9 v                if (numw[i] != 0)
: n+ p0 [2 z+ a5 D5 Q1 e, d                    Console.WriteLine(numw[i]);
; h9 s* [6 n1 J( r, r7 ~           7 `- x# m8 [$ L2 V! m6 S9 g
            Console.ReadLine();" _+ D. ~' S6 q# K9 ?: J
        }
4 b( g6 i# {6 Z6 `1 U) X    }
  A+ G. t! K6 Q- H2 k}
3 i! ~! t4 Q! R; Z0 G
想知道小甲鱼最近在做啥?请访问 -> 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:22

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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