鱼C论坛

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

猴子问题

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

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

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

x
大家好!3 e2 c, h$ }, q1 O; {0 e& a
这几天我在忙着编一个问题,我用了一种方法编出来!
2 d& n3 p$ g( e# s1 t# I8 M但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
) E- I" A) `! {注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
/ o% l" \) a! Y( }$ S" I8 k8 ]1 e, r/ K6 a# T" |3 Z* F
4 m' I( h2 I" _/ t. V, Q
                            题目. j& k# Z% I* v" c6 p7 H
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。+ U! t) y1 W: Y, [) \4 Q. j
第一种方法:利用循环链表
# M1 F8 e" [3 X, i9 |- e' N; \#include<stdio.h>
0 ?) V/ {3 \3 s% y( I#include<malloc.h>% w% |. G$ a. G8 D- X4 A, |
#define M 8            //共有8只猴子
1 K7 z5 {1 E' _( t" ]#define N 3            //数到3只时退出第三只# a2 _. ^, B9 j3 O
typedef struct monkey
; s- O2 J4 R8 h8 u! n3 U{int number;' x9 a6 G. Q+ ~6 f& @1 A
int flag;; q+ W% i. T* R- u$ C+ `9 `8 d! U
struct monkey* next;+ @% Z9 ?, [& E! q3 d: S
}MONKEY;
+ f- E0 U( Q1 I# Gmain()
0 `0 p1 O9 A) K{ MONKEY *head=NULL,*p,*s;
- N0 A. e- j1 t  int i,sum=0,count=0;% w0 E0 a% k) j/ z
  clrscr();              //清屏& n9 w6 @9 W  I: c) \
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
8 t9 a0 {  \2 v1 u" v  p->number=1;p->flag=1;' Z1 y6 m- |) W& k
  p->next=head;1 P7 Z& d0 \$ Y8 c1 ~
  head=p;3 S% |7 o7 V" z5 o: S/ E8 g2 S6 ~
  for(i=2;i<=M;i++)% P  ?  I* a: Y
    { s=(MONKEY *)malloc(sizeof(MONKEY));! Z- w0 l) @: n
     s->number=i;s->flag=1;+ i  u& Q( V( o1 A+ p( \
     s->next=head;6 \# I) S+ z9 U# {1 G3 b8 h! l6 o
     p->next=s;p=p->next;
/ h4 W# s9 J# Y' |+ k* Q    }" p3 }. s$ ?, H/ ^1 M
    p=head;+ A, U8 v% Q! g# C" w6 q) d6 Q
   for(;;)1 A$ b1 G" U5 l( y( o; C. S. U
    {if(p->flag==1)  Q' d5 v' ]2 {( F0 L% y, E
       count++;3 y$ Z. F! d+ P! k# j
     if(count==N)
  `. E( Q7 u* K; v        {p->flag=0;
* Q8 N& m1 e3 z. B; S. G# p         count=0;4 c* C0 j1 J3 `" Z
         sum++;}. Y& S5 |8 P2 b8 V- u2 o
     if(sum==M-1)0 I1 e; B! R& ~6 a7 ?8 c
        break;9 ~7 {" R* s. o0 g/ q
     p=p->next;5 U) B, ~4 n! a% x% Z+ B
    }3 v0 T% q  z7 Q
    p=4 i/ c/ B% G) M
    head;
2 H) G7 h$ D; Q' t* a2 f6 ^. D    for(i=1;i<=M;i++)1 i, f0 T, ^0 }2 A* Y9 S
    { if(p->flag==1)
  r. z# g& K/ A& Q6 W3 w        printf("\t%d",p->number);, ~/ u: O! ~7 r
      p=p->next;  _* j) Z) k- S8 ~- E
    }
* v0 ^8 B3 {- B% q9 ]( N5 y$ A5 p9 m0 E) T! k6 `; G

5 `; C2 \9 ]2 J  t
% Q: M! Z. U1 U, t}
! F  [9 d% |+ p" W; [+ E
第二种方法:数组: e/ z' t* v4 F# u# W
#include<stdio.h>
4 Q2 d1 H1 t2 W4 f#define M 8
6 _% k& V  x1 q- e' a& \) Wstruct monkey9 \( ^$ W% j4 F- V5 b1 a7 ?& s, t
{int number;8 M, T4 b4 F9 x0 G/ K% X* }
int nextp;0 P+ c9 v1 j, Q
}link[M+1];; B- N: a* C( S# P

$ U& v# m: K  b) [7 yvoid main()
! R6 ]; u$ T0 m+ S# ]9 z' k{int i,count,h;
# R  m. l) g2 S6 ^* M/ v& e" Cfor(i=1;i<=M;i++)1 a- v" O5 C6 z7 A. g, Y  E  [0 m
{  if(i==M)
0 f. s( E5 N" v, u5 X   link[i].nextp=1;1 K, {+ B2 r3 |) l6 T: n) J
   else, P6 X4 ^' P4 X2 U
   link[i].nextp=i+1;6 \! _4 y/ M# \, @% x  @6 p( b- O
  link[i].number=i;
( B8 z  B5 V5 p}
1 G/ r1 c% R% I) e2 Uprintf("\n");! p) |7 v0 {! [3 M, S: s& o
count=0;, F9 s! \, s4 y" \7 N
h=M;, D1 c( |) N, t' H
printf("依次退出的猴子: \n");8 C6 j6 R2 A, T+ X
while(count<M-1)3 }/ V% I& R  i3 E5 P6 d4 n* o7 O2 B
{i=0;
' e5 `- G5 |% C% C: K$ qwhile(i!=3)4 G0 k! P* p- t" m; R  o) S
{ h=link[h].nextp;
" X& K' K, A- U- K   if(link[h].number)( |8 n5 X. h. f9 k! s, C4 s
     i++;}" [/ L$ v) e. R  m  \& A2 I
; [5 M3 o0 U4 O4 {, s8 V' t
printf("%4d",link[h].number);
- X9 p& S0 ^1 L* |link[h].number=0;% W4 G. c- B. J7 A: p' C5 B) Z4 ~
count++;
0 l/ @$ a8 l, J! ?0 R}
: s7 q5 e3 B# m/ o# v. z
# G4 Y5 R7 b# t' m0 Zprintf("\n大王是:");6 U& t! b/ i* Q0 u" M! g
  for(i=1;i<=M;i++)
' E0 M; T  C8 R' d/ a2 g  if(link[i].number)5 q+ f9 @1 l2 F. N
    printf("%3d\n",link[i].number);
& e$ f2 N) f5 D3 G# X7 h2 ?, F! e
- C! T. @* j' ]: a1 k: O* P2 G8 a# [% P  K! K
}

' ]4 a9 A) [8 V; X2 }第三种是普通方法for循环
3 @# c1 u0 t, s) w7 T& G6 ~
#include<stdio.h>
. u! Y* \" X* {1 ^0 B" ~4 |void main()- P  o5 \3 b; @7 T% j6 |8 z& j/ d
{ int i,k,m,n,num[50],q,*p;+ u7 R0 P4 j7 ^4 {2 n9 Y! y1 N
    clrscr();/ E0 c' x. M3 n' \7 J5 J- p1 Z
   printf("input number of person: n=");- ?- I: w( w: h9 u- c+ a0 r
    scanf("%d",&n);
6 h- D1 i) }0 t4 G/ zprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
7 t2 {- ~: z) u* y' }# Q; W    scanf("%d",&q);
: e3 x3 {5 k( i+ M   p=num;& }4 b$ j- ]  Z1 V5 L8 j" f
  for(i=0;i<n;i++)
+ o3 y" F/ [' ^$ x5 H    *(p+i)=i+1;
( n3 V0 N! P5 i0 F   i=0;
5 S- j" [- u1 |" n$ e* e7 o) m   k=0;7 n8 N( ^" N( E" v* T0 |2 Q# A& {
   m=0;
: @9 r1 b( H. a! ]" A  while(m<n-1)
+ \3 l, v7 ]3 j1 u0 [# b   {if(*(p+i)!=0) k++;) E7 N" V; e$ j2 o0 z, E% I  ^
     if(k==q)
( ^3 ~: E3 \% t  ?9 Q      { *(p+i)=0;
; V0 S& o7 w1 [        k=0;
0 |  t2 T+ O# a/ Z/ ]: x/ b        m++;- M: W/ K) i6 E0 ?. ^, p# d
      }
2 A4 i' x+ D5 h( {" Y2 V; }( z    i++;: a- p- ^7 f! s6 }$ q
    if(i==n)i=0;5 E+ G+ N) U' @/ C. B
   }. M" P1 c& l4 R5 d' G' y
  while(*p==0)p++;
5 ]: i( i: ~* X- f! W" G, y    printf("The last one is NO:%d\n",*p);
: t, I$ s  ]) i: P/ t( X     getch();$ W& x  z0 f% f6 m. }2 o
' `: j% O4 O( H9 K9 }# v4 T/ a5 h3 p
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;6 Q* [  [: n1 a  Q- D+ l
namespace 又费马达又费电
( {6 \8 z: ^. M- K7 o9 O6 q' \{
" y$ w  i- L) |- k+ i3 M    class Program% z8 M: J& D8 o
    {6 b8 w$ M: w, l& j
        static void Main(string[] args)# b! l0 X7 G" E, ^0 K
        {6 F5 Q$ }5 Q+ p/ l" P% Z
            int m, n;1 m/ C/ T1 {: ?- ^0 R
            Console.WriteLine("请输入数组长度");
0 J% k4 {* [# ^) P1 B6 h) d! g5 V            m = int.Parse(Console.ReadLine());//m为数组的大小9 O& f6 c# o6 x# _6 V7 Z( D
            Console.WriteLine("请输入要截取数字的大小");+ w( }# O# p$ y  a3 q
            n = int.Parse(Console.ReadLine());
' T& Z& g. q# u7 C+ E: D6 W0 D            int [] numw=new int8 f9 |1 c8 o# j# m  |  j4 l

; t/ j1 ]! d0 K9 o! G3 [: o&shy;&shy;&shy;;) ^* O# x# p$ P7 v' k
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
- A8 k" J4 R3 `, b- {: G, |( D            {
+ i# f/ H2 u+ Z. c0 J/ @. @, H                numw[j - 1] = j;9 h. [8 S0 J% g5 x- V* V: Y
            }
" x7 I% a; o7 G7 M6 ~1 n0 h            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
2 V2 ^8 [! b$ o            while (d != m - 1)
' E. ^2 ^) i7 T# z            {
! b8 \) g; |9 k                if (i == m && d != m - 1)- X% O* B, Q; B" B6 G5 {
                {0 y' Z4 D. r8 W5 k9 J2 b
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
/ ]; Q. \1 _; j5 v) H! _% [                    continue;4 S  z2 M$ Q4 J7 l" U; g8 P
                }5 {% b# f5 B1 ~4 j7 v# s
                else
% u4 o( E! u8 o+ K. ]                {' ]. f! K% \8 ^/ V) c
                    if (numw[i] != 0)
+ g; t3 n- d- V$ K- y                    {1 B1 n  v6 L9 l: }+ W- X
                        i++;
+ E" m5 ~5 O* Z9 j* ]! e( Y                        k++;9 e" ^) U; m2 ^* S2 `
                        if (k == n)
5 v* b: @+ o4 e( C                        {
3 P9 N' S% q9 A( T7 z" I; r# r                            numw[i - 1] = 0;//把在n位置数组元素的值改变了% i3 h1 @, `) F  O- |  D
                            k = 0;- m; ~- D: T! v0 k  [
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
3 W' J* V! o5 K4 K* ~) r                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);( M2 b1 e3 P9 Z! @
                        }
' _7 B  e, n; E3 N5 n: h$ q                        else//输出暂时还没有改变数组元素的值
/ N! y3 }# n. w. n                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);3 q" g( E' t' M
                    }' L; }% k5 f# A2 g/ i1 s/ K  Z9 l. @
                    else! F& K& V$ V) [4 |! |8 L' n
                        i++;//数组元素为0,直接跳过,不计数。。。% O0 v+ {' S/ E/ c
                }
3 e7 b( j8 V; Z5 H' h( d  X2 c4 n ! h2 K- _: j' `+ H
% u( o2 L$ X- K: A7 |
            }//结束while循环
6 G! @5 d7 X. ?# b3 ^2 P            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦/ R2 a% @) }: |+ B
           " v5 c1 A; i+ T/ n! W- K* U
                if (numw[i] != 0)! Q* }- Q/ b' ^; H
                    Console.WriteLine(numw[i]);
3 w# g/ j1 N- N& ]( y# J; k           6 Y: Y+ I  g0 t
            Console.ReadLine();
7 N3 v3 I) T) }6 K        }( U& E9 t- g% K9 ?( J5 F/ [
    }
6 b- C; D# x3 l$ }% E. _}' _- Y5 g" Z2 H. T, `
小甲鱼最新课程 -> 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-4-4 14:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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