鱼C论坛

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

猴子问题

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

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

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

x
大家好!* `0 R. A! E# Y- ?
这几天我在忙着编一个问题,我用了一种方法编出来!6 |: Q* [, y1 H# `. E' Y& X0 _( p
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!! {3 I$ T9 |4 o: m* g
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ' q# a6 t% A/ \3 S& A/ Y; j

1 ~' x1 x+ w9 I; Y7 k8 f" M6 |, ~. n2 p) ?6 @
                            题目. e9 |) M2 i; n3 Q4 n! f6 n1 g3 F7 Q
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。7 J& E* ~0 Y7 ^! s* e- b
第一种方法:利用循环链表+ T4 D" [- \" r7 C' z# a
#include<stdio.h>
# k$ S9 G4 ?5 [$ f5 \#include<malloc.h>
7 `5 v) z5 o6 S9 ~; c. h#define M 8            //共有8只猴子; T3 s& o+ N& y1 P! J
#define N 3            //数到3只时退出第三只
( |$ V9 Y& A$ D& Ltypedef struct monkey0 s! S1 C" o$ }+ }, G7 e/ U$ P! u
{int number;
# ~/ _& F/ M) q. pint flag;
9 O! N) v+ N, Z4 s- Sstruct monkey* next;9 Z+ p, Y+ P. L2 a
}MONKEY;
+ `6 n& ^9 c$ m/ \8 Y- r3 f% F7 ?  Omain()
$ V5 P) X, M0 B' m( i3 S{ MONKEY *head=NULL,*p,*s;5 G1 m  ~9 z7 Y6 V- f, V* }( u
  int i,sum=0,count=0;+ r( L9 |% |7 U" j1 p1 \
  clrscr();              //清屏# v5 @/ g% V  S2 C2 C% W# \7 K( I
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存. w2 z' U9 m& q0 B! g9 M/ C
  p->number=1;p->flag=1;2 _& l4 i% y$ Z! Q
  p->next=head;
8 A( T4 K/ Y! n' `; q! q  head=p;, J" c' p2 ?0 V. l$ k! s
  for(i=2;i<=M;i++)
: o# ]4 T! I, V$ v  X( L( j; c    { s=(MONKEY *)malloc(sizeof(MONKEY));8 K  e4 m- H% n+ ^. d8 p2 s; ]/ M
     s->number=i;s->flag=1;$ v& o0 G2 v8 Z* K8 d' W
     s->next=head;$ O5 E# ~: R7 j: g0 Y0 b
     p->next=s;p=p->next;* U; _% [# B4 O( `8 f
    }# }  \1 k. ~( O0 E- `; `! B% b
    p=head;" M+ t6 H2 {- V' Q# K
   for(;;)
0 \! N) H# G/ Q: ~" D  Z. G    {if(p->flag==1)6 p# d, C9 r" C' G2 [$ N5 `. m( t
       count++;
6 o' y9 h. O0 s1 b$ A     if(count==N)
. H8 @) ]( y  G6 m! D! {        {p->flag=0;& G5 Q) ~) c- j5 z# u
         count=0;. ^' \6 v! H& y9 E
         sum++;}
) s' n% ]) X4 H. ]* j4 Q     if(sum==M-1)
' W+ J. Z% |6 P+ W        break;
2 V" {" @4 \- ~3 G8 O+ p5 b     p=p->next;" F& r( I, R; |- l& U
    }
3 {' ^/ x9 ~( a1 W( K    p=8 {% _5 U* B. h3 c
    head;
/ C# [1 K: C- [0 z) q    for(i=1;i<=M;i++)
2 Q6 F) h; U; p1 }& T$ R" Z    { if(p->flag==1)
+ X) v6 J  r8 s: ^        printf("\t%d",p->number);+ B& E& Q" D* |
      p=p->next;
  ?* ]& G, ^% P9 ?* @    }
" F, O1 f3 w2 A. z  B3 ^0 {; E2 @
4 j9 C$ f& t# |- @: n# p! x% Z$ }7 }) U( M
9 Y3 l* A7 X1 h( U) j
}

, B9 d5 X: g# {$ ^5 p第二种方法:数组  `" ~$ Q% U" U" `6 a- S
#include<stdio.h>2 r7 u4 T5 y* `8 [
#define M 8
8 r3 s  |. A4 ~3 }" \! p7 jstruct monkey$ _$ ^' M3 ?  M% T& o6 X; _
{int number;
5 f& b/ p1 P5 ~7 u8 W! r  cint nextp;
1 v! l) u) R5 u* f}link[M+1];1 D* Q9 t' s0 c/ |% G4 ~
9 ~7 I, c- A7 t: e- P& D
void main()) h& ]! E+ {7 C6 _
{int i,count,h;3 |: }+ @; A) r' T
for(i=1;i<=M;i++)
' R( L, {& W* Z, e{  if(i==M)
: h8 I2 Z- [9 X& _7 R( t   link[i].nextp=1;5 }# A- b/ V) h
   else. v5 x5 R# K( m- F" \+ q$ y/ g
   link[i].nextp=i+1;1 M8 C, O  A% N4 j% _) M6 }
  link[i].number=i;
' C0 r; N: s  j+ A$ h+ A" x. m, \}
4 e' S/ g' y2 L/ E- V- tprintf("\n");
, @2 L) j' I4 c$ Mcount=0;  V- M& O7 P6 o' k" {
h=M;/ c5 d1 w' u; ~# q; z% v# {
printf("依次退出的猴子: \n");7 N  M  [5 B( Q% L  Q$ D; ?
while(count<M-1)  E/ b! Q, l* Z
{i=0;( ^4 J' Y5 s+ [: [. ?  O
while(i!=3)7 R% y$ ?3 z' Y6 `: `
{ h=link[h].nextp;
- q" F, H4 D, |, d$ `3 ^   if(link[h].number)
% V6 h- M% g+ f  m' X     i++;}
) M) _* T0 O6 t7 `$ K4 S3 b: ]! k( X" c
printf("%4d",link[h].number);. P2 f1 E% d0 M% d3 c
link[h].number=0;, @, C" ~. T: P' C* t
count++;$ Y$ q7 J4 \6 d  \
}6 u" I7 U4 k8 S" G/ N3 b5 q4 S

$ f' F6 N2 Y, G# a6 b% Z% C: `# nprintf("\n大王是:");
% H; w" i# A; U6 b- i! C  for(i=1;i<=M;i++)
/ f6 q' g: m) q" M! t3 n  if(link[i].number)/ l0 f; S% _* e6 Y8 g: G( }
    printf("%3d\n",link[i].number);
8 C: R% s6 Y. @; {3 B2 \8 U+ r4 J9 I9 l0 ~# u

  Y( t% q' d2 K5 k  U, T$ M3 c}
- q4 N0 x" B! C7 V. U
第三种是普通方法for循环
9 Z! J, o% R6 e- x! P  Q$ D
#include<stdio.h>
, M# i" n0 j: k0 `. B. p$ Mvoid main()! Q( {8 q% b% U) E
{ int i,k,m,n,num[50],q,*p;
3 P8 b& a/ S% w' Z0 o5 Y- v    clrscr();# R. r# s* G$ O2 \
   printf("input number of person: n=");% T; ?8 p9 N% ?' y1 a/ V! n
    scanf("%d",&n);% V; _- t! T5 H
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只) t6 s# h- G$ R. i) q$ _
    scanf("%d",&q);
) Y$ B/ Q. _  Y6 Y9 l: D4 i   p=num;
1 y. ]1 S9 ?( v% }1 R5 e1 T9 F  for(i=0;i<n;i++)
3 S% ^& f- v. m5 G    *(p+i)=i+1;
: \* o6 _& `* H   i=0;5 Z) X, F: H" B
   k=0;6 j- j6 _0 Q/ X; G
   m=0;
! R" q3 E0 d- Q( e6 T& j- D9 R% B  while(m<n-1)
/ b7 U. V) n1 x0 |   {if(*(p+i)!=0) k++;( N  h: T; A. d' C# c
     if(k==q)
4 k% y. r; p2 L" ~      { *(p+i)=0;) Y! P6 F/ V$ s9 s% L: i+ q- i
        k=0;
- i5 s1 m& F+ U( t: Z. J& w3 k        m++;
7 W5 G5 [* p) a3 j0 f8 _      }
  o+ H8 V9 m& x: i6 n8 Y2 ]3 n    i++;9 U' E: v: e; p/ g' e( {6 K
    if(i==n)i=0;- U- y/ t8 j9 F2 I
   }
  j6 |% c8 V5 C+ f  while(*p==0)p++;
% {" V" ~. b$ D+ @" @: `* d    printf("The last one is NO:%d\n",*p);5 O' D6 s; A9 O3 D" C. Q: {' [9 d
     getch();
8 L# M" m: C6 q8 i3 \; @8 x$ `' L# y7 ]# V* n
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
2 o' i5 d$ R9 q$ ]7 L$ m; {namespace 又费马达又费电
( [  @) c( g8 [9 K, c0 i( W  {( [{: p: ?0 c+ l. V
    class Program. ^5 g4 b/ ?" H/ w; Q4 V
    {, {  k' k9 m% G
        static void Main(string[] args)
) [) O8 V7 [3 h        {/ N' ?" z1 {; Z% c: I# j+ @5 H8 |/ G
            int m, n;9 y; ?( s# I% G- p% E
            Console.WriteLine("请输入数组长度");
, J7 \9 l/ f& H" g' a) I. f! G1 n7 F6 z            m = int.Parse(Console.ReadLine());//m为数组的大小# \3 }& t+ O! d4 p
            Console.WriteLine("请输入要截取数字的大小");
+ P, L" W# D* B- J            n = int.Parse(Console.ReadLine());* E, U' u5 W* r& R
            int [] numw=new int( \3 J8 ^+ b. y: J7 t- D" V

* N0 d! R. _6 w2 c7 |& B&shy;&shy;&shy;;9 o7 V+ w8 L9 `) T0 Y% D
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
% n1 b% z8 Z2 q+ @            {% M7 n! u, f8 w' M# p7 W9 d
                numw[j - 1] = j;
* h! f/ h% v* v* f- i) X            }
3 r; p3 R: p) |1 ]& }            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
0 v" f1 h$ J* t) _# f# a. G- n6 v            while (d != m - 1)
, k! ?( ^; I" f7 b6 R            {# S, Q0 e9 c; N
                if (i == m && d != m - 1)6 o$ q  O% M& a. k
                {- c: Y8 F3 }' i, B1 L
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
) o$ a( h' q1 t                    continue;0 a$ }2 V7 K$ Y$ e1 {; z
                }
/ I+ Q! P  Z. H2 F2 v3 _                else5 r: _- @" ]/ z9 a1 o7 f# E# a
                {
; n' O4 z+ i: Y+ P% o                    if (numw[i] != 0), V) x& \6 v' |3 f" y
                    {$ {* X( h3 Z: s) J' R; [# ]" V
                        i++;
" ]3 C! W+ H0 P0 w                        k++;" M# v3 s& M# l) F/ ^' m' ]4 W' ]: ~/ s
                        if (k == n): J, O7 E4 X9 R, o9 f& W' {
                        {
: w, O% u$ }; K. Z                            numw[i - 1] = 0;//把在n位置数组元素的值改变了* g& V" Y7 I( }& A- [" }
                            k = 0;/ r. y3 ~" \5 Q7 j8 l; p
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1* S! S+ l- g$ T0 L. v
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* R6 O/ L- g$ p8 [  w$ K$ D& u0 |9 G
                        }
. O+ ~. ^) I* ]+ w                        else//输出暂时还没有改变数组元素的值6 P: u4 G5 w# v+ [
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
: v! n; E$ m" G( G) V8 S                    }0 |6 i# d  l  R2 O+ u# c0 Q: Q
                    else4 l$ R/ l+ r% G' H) _* _7 z2 E0 c
                        i++;//数组元素为0,直接跳过,不计数。。。
: l, i& N4 A/ ^1 V! C; U                }  d+ d* k  e5 [0 j; o+ ]# k
; L7 M4 K3 S+ j) E  x3 y/ |2 `$ L
) G. u" C- w( b/ R9 s
            }//结束while循环
7 T! ?( S5 |: [/ |            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
0 }5 J5 z! m8 y$ A% o, B. d# ^           % `3 y8 V) [2 o9 u
                if (numw[i] != 0)$ F, m( @! y9 i' h- z* m# d0 h
                    Console.WriteLine(numw[i]);* V9 q. t' u9 C, h6 h' ^
           
5 j* G  J* E' U& U            Console.ReadLine();
  s5 T; v$ K6 a$ w; A# M8 U+ w        }8 T. o+ c) H2 y/ H% Z( i; N  S
    }1 M7 \8 q8 e8 v7 x) s1 o$ y
}
! G6 i$ I/ t2 _
小甲鱼最新课程 -> 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-1-18 13:17

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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