鱼C论坛

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

猴子问题

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

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

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

x
大家好!
' b2 Y! u+ n. [1 W% s这几天我在忙着编一个问题,我用了一种方法编出来!, P$ m  f( G" P% Z
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ J1 s! t% |* S5 z8 V# n
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
6 v" e$ a1 q2 Z
. f% C5 h; H5 g& ^) \
# D% u0 C* K4 V, I$ [2 O
                            题目6 i6 I9 Z9 l# K3 Y; t2 M3 b
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。' g, i# ?9 E) f7 |, N8 |$ m
第一种方法:利用循环链表' n  T# W7 y! b  }! I* f
#include<stdio.h>
, Y* J0 F8 Y& d  P6 f% c#include<malloc.h>1 s3 C" E. O" g
#define M 8            //共有8只猴子) h# W; A# b/ Q/ t
#define N 3            //数到3只时退出第三只: D& U  v5 K4 ]! K
typedef struct monkey1 Q- g4 U$ M9 e1 d2 R# R' e
{int number;: E/ S5 f. Z! z! n; v- O( c
int flag;# V! e: y2 a9 j: m- [
struct monkey* next;+ I: E5 P$ z! a+ H- |
}MONKEY;6 F, d0 k% a& Q3 d) i5 I5 E
main()
  h! _9 ]+ M0 Y& O. G$ d{ MONKEY *head=NULL,*p,*s;+ H6 z, b' L4 [3 k
  int i,sum=0,count=0;& k, t; z! @6 a5 \
  clrscr();              //清屏' k' M" _% `" O3 e* h5 P! N+ \
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
' z9 G; Q5 Y- e  p->number=1;p->flag=1;
4 N# p/ c) V' N; [6 o6 `  p->next=head;. W% {  {5 M( X9 M" I3 M6 t8 j4 W2 Y
  head=p;+ R6 q* A( g  H! L
  for(i=2;i<=M;i++)8 v5 ], l8 v! [. g0 P: _' Y+ T3 P
    { s=(MONKEY *)malloc(sizeof(MONKEY));. q9 u/ ]+ \* r
     s->number=i;s->flag=1;
" U2 H8 q$ Y$ E) a5 V  {     s->next=head;
: Q7 I. G& p  x     p->next=s;p=p->next;
1 J) G7 b+ t  [% N& |$ q. W$ J    }
/ P  X+ G' g1 e    p=head;- e! T) P  _# ^% P9 T
   for(;;)7 ^! E8 Z1 V- u) F# O
    {if(p->flag==1)
6 }4 ^' {8 @3 w- `2 }! W: {       count++;6 U  t5 j! j6 |9 |8 t
     if(count==N)
! g% }2 G+ s$ T1 F7 m: k        {p->flag=0;
* h+ V; J+ s% G! Q2 u2 ]         count=0;0 [. K' B0 ~) f4 p* A
         sum++;}- n2 ^+ h; i- U2 y# i4 Y
     if(sum==M-1)
  U" Z, I* T& G! p        break;" i, m" t. r9 F* q4 K
     p=p->next;
( k* j, \5 k0 t$ Y1 J    }
+ Q' H: P8 }$ P, V( i7 q    p=6 f) R0 f# l7 t( O) P+ d
    head;
) [3 U  l. q/ e0 ^' ]    for(i=1;i<=M;i++)3 l( u) A: L$ d( T
    { if(p->flag==1)
. q4 [) q) b4 t0 T0 ]  G7 h        printf("\t%d",p->number);
5 V- b7 E4 ^+ Y6 m* F      p=p->next;/ }! e* y" g9 K8 K* Y4 f
    }
$ `! Q: \& ]! D
, O, j: S8 p8 t" W$ B1 p! O2 V+ ^6 Y
) b* r9 V% `( j: m4 \0 G
) H  x& @+ ]0 u  K0 C1 F1 C3 z; p}
* F7 V  M! v. M; F; o0 @4 W
第二种方法:数组8 c; V. Z# I9 o% Y3 r
#include<stdio.h>
$ h) r* g) e' e- Y- h( N$ R#define M 8/ N, f6 `' O, |
struct monkey/ V  e+ }, V' A0 v% L' y9 s
{int number;/ o/ @- }: N2 ^3 r$ {
int nextp;
2 s! Q2 f- \& c0 D}link[M+1];: r5 u( a! W& |2 P+ h( w
( C  K  `* p# U  u1 `' `' K
void main()" f: i) q/ ^% `- S' {7 a' K
{int i,count,h;
5 n, e5 s/ V& W7 ~2 b1 V* K9 Jfor(i=1;i<=M;i++)( J$ U7 H5 Y7 L% K* f+ c3 X  v
{  if(i==M). {/ E& I. x" Y6 d4 E/ r
   link[i].nextp=1;
7 S! u6 O6 o) H8 X/ M   else8 `  h) M" x! R* k& e. f* D0 V
   link[i].nextp=i+1;  p- P3 K0 Q% Q" k7 h
  link[i].number=i;
* C- ^1 \! F2 v+ E$ \6 N; J}
* i7 Q  C- B1 P- L: E! s6 Fprintf("\n");9 |' X( J* s0 d5 X2 o, l9 p
count=0;, ?" k! U, Y+ y8 T
h=M;. Q( J2 v1 ^( g- t* J8 e
printf("依次退出的猴子: \n");
4 ^4 h6 l- u: G$ g6 gwhile(count<M-1), N! C$ y6 @4 y+ P
{i=0;3 O6 [3 F. H" T+ @
while(i!=3)
# I' G$ e$ U0 [: G6 k{ h=link[h].nextp;1 }9 e/ V( u  m! u- I% ]) F
   if(link[h].number)0 D8 J9 n" {6 P
     i++;}
/ B; }' ~+ v$ m- V4 \7 y7 O+ t8 Z5 W( _6 s
printf("%4d",link[h].number);
/ N3 ]7 @6 x$ \2 Y/ y4 ylink[h].number=0;8 q+ z/ U+ h# r% e! b9 ^
count++;% o! ?3 w4 [7 B* a* u2 U1 H8 s* W
}, o  p" h$ W0 k( S$ q* A' l
' g. j1 x  ~0 R0 I4 a! i9 @4 D
printf("\n大王是:");. d' p. k& r, v  u/ A4 v
  for(i=1;i<=M;i++)" h& P! A4 K8 b$ N, i
  if(link[i].number)
" J9 F& y1 P# N+ _3 U    printf("%3d\n",link[i].number);5 Z5 c2 ]- x7 Z( M/ p+ ?+ k, `' `: T

' _/ r! @; Q( i4 |) L- P+ N* D; D" D' r6 S# R
}

& [( d" U, j0 u* n3 B2 l+ u第三种是普通方法for循环

  ]8 K* }) D2 V% h* e3 b#include<stdio.h>& ?6 e+ S9 O' G$ j
void main()
3 d) ]3 n( E  u8 e7 E% L' t" _{ int i,k,m,n,num[50],q,*p;
/ y& @  _" D: ~7 G# ^( m' T    clrscr();
% d* q9 x/ B9 O$ k   printf("input number of person: n=");
2 j6 _# H0 U+ J5 }, N: F+ b/ ^    scanf("%d",&n);& \  `) M% z( i
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
* o+ c% l, M& M    scanf("%d",&q);
6 Y9 n9 |6 t2 X0 {   p=num;( }& G5 e% V3 }1 v
  for(i=0;i<n;i++): I- {4 M$ l) z# I1 r: z0 P" y
    *(p+i)=i+1;# m/ A) Q) C  u+ k
   i=0;1 u/ a8 a  k8 j8 M$ F& u# T
   k=0;
& }0 B5 o5 a) J/ b   m=0;
: K+ f& L$ E/ U/ n" X4 A6 T% ]  while(m<n-1)
7 p# t1 y: X) ~5 i0 c   {if(*(p+i)!=0) k++;
) [# X2 f9 ~$ R     if(k==q)
8 J4 B1 J* ^# \: m( U2 h      { *(p+i)=0;' _: }8 x2 Z% V) \9 F$ ~& G* i( c
        k=0;( ?* b8 @* i0 `3 V
        m++;
5 j: x9 r7 `5 G# K: c% r/ D7 s      }7 P" \( L. |) f% d  L" L, M1 S
    i++;
% R# I, w. Z. k  L0 `) Z    if(i==n)i=0;
0 |$ C  k8 ]7 Y% Y* L   }
- V+ _% n, ~% `3 z- j% U* {9 a/ `  while(*p==0)p++;+ l  Y- v8 n  ~7 W; ]
    printf("The last one is NO:%d\n",*p);" F0 u7 q4 `# x; L4 q6 b) j
     getch();
  x7 b" N  p; j8 ^  Q4 H" D* R  v8 X
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
1 T# K9 m' T  N: {; gnamespace 又费马达又费电5 x! Y$ g/ V7 z# U2 Q1 S; _$ U: K, P) q- K
{
  H9 u) R$ V+ D9 m4 [, D    class Program/ v* f$ u2 i! d" @5 A4 w
    {" V6 M6 T5 Y* ~# s# c
        static void Main(string[] args)% I3 e6 g4 Z2 j* w( n) t
        {7 ]& D  j$ e4 K3 S$ C1 m8 K
            int m, n;6 S- ?* W1 W% h- o
            Console.WriteLine("请输入数组长度");6 j5 t, ~, }7 a' t
            m = int.Parse(Console.ReadLine());//m为数组的大小3 ~8 [. K7 d1 x# S
            Console.WriteLine("请输入要截取数字的大小");
1 `; C/ W4 A9 G4 i) z/ c            n = int.Parse(Console.ReadLine());
& C% ]; S5 F( X% Q  {; M            int [] numw=new int8 d* L8 G( L) N

* G5 x' d1 b2 A! F3 q8 E: Q. |&shy;&shy;&shy;;
9 R& o: S, c2 }            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
% v$ G& X$ R* V' z: Q* S' D            {; w- H4 J. S8 o7 H# ]
                numw[j - 1] = j;
7 j% L) X3 J# t/ e            }$ r2 _4 g4 B7 R) C  Y3 S  g& z
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!/ L& L# k2 U" J% p( L# a. P5 `# k9 P
            while (d != m - 1)
" B3 e; L8 v( t            {
5 Z5 ]9 Y* B: w6 c. V                if (i == m && d != m - 1)
# N" F$ w/ b5 w3 T/ }% w                {
% U2 _5 W8 x% M/ J# t* o' }  J$ j1 v                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
: D; C( y. K' U                    continue;* E8 }2 W0 M/ J; f0 B% g
                }
* b6 ]* r% T/ l% }# y                else
9 A# E2 C9 m  K/ Y                {5 N1 p$ k$ g' \7 Y
                    if (numw[i] != 0)3 [5 \6 @" S! U0 D
                    {% p4 m& [8 f6 t2 Y5 Y
                        i++;
' n! \, D# d$ I7 ]" ]2 }                        k++;
; U* r% \7 T7 a- ]* P3 b                        if (k == n)) P: M+ k6 ?- {4 N* W  L8 G
                        {
2 J5 W" g4 B7 m, ?1 w. v                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
3 F4 e6 `% M7 V; M9 S& L                            k = 0;9 w  ^+ p+ z+ Z! g  n6 n3 ]
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1: X  i9 Z; S' x* b, L
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
0 s0 J6 ?% A9 {4 J& ?" h                        }9 S0 O. w1 [  @
                        else//输出暂时还没有改变数组元素的值% ?( b( r9 W$ s! [( c
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 u) s# y9 m7 f2 p" P                    }  L! c0 c$ R& ~" O% x, Y* X9 m
                    else
2 }2 \: d- x8 e: X# K" g1 P0 x                        i++;//数组元素为0,直接跳过,不计数。。。* [; ?8 ^2 m" p: \* q' B8 D
                }
1 l6 J9 L/ c3 C8 g5 W9 r; E
/ W% {. Z2 H# a, Z- u& m  N6 h
1 v- i" W# b/ \1 U, j  d2 Z            }//结束while循环  \! V0 z7 m- e, l1 [2 M5 n: k& J: \/ J
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦5 `) ]9 a8 V- }
           " ?& n3 o2 V" `( f1 U6 P
                if (numw[i] != 0)
& }1 b1 j- [# k. O- Z0 z                    Console.WriteLine(numw[i]);
+ S9 Z2 H8 W$ I* b+ j: C           9 D* H" }4 C# H, d8 ~9 h% J
            Console.ReadLine();! V8 S( f8 f# w2 j2 \* I. z
        }" J' Q- U9 R  G1 z* E! z" o: Q' b  d3 o
    }% Z9 p4 B, {( e/ Q- e; ~; ], \
}) k4 U& n. \  ]1 K# z/ a
小甲鱼最新课程 -> 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-15 20:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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