鱼C论坛

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

猴子问题

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

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

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

x
大家好!, y/ |# |' e5 w. b0 k
这几天我在忙着编一个问题,我用了一种方法编出来!3 N4 n% ~; S3 m- S3 h+ d& T# z2 g
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
5 N% Q; j+ c7 @7 m注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 7 V# I" w& u/ D! Y4 v

# Q6 g8 i/ r+ g
7 m3 g' a- U$ ^( b1 Z% H$ H
                            题目
: P# i% u1 h% n6 N7 C4 t山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
# c% a" M3 J1 V* |4 Y' t第一种方法:利用循环链表! J5 k1 N/ C/ ]- `, D4 ~
#include<stdio.h>' M3 o9 s3 @/ a$ m" G- B5 d
#include<malloc.h>" w& j  r( }$ w2 N+ Z
#define M 8            //共有8只猴子5 K2 p0 X, C7 `9 K. s0 G
#define N 3            //数到3只时退出第三只
2 P- U: P+ s1 e' e- e# T% J; etypedef struct monkey! c2 x0 p$ A/ m! q
{int number;
4 \+ F8 j7 |' a& j! R9 h/ x' Rint flag;  y- g0 ]7 l3 Z: [  _7 u: M
struct monkey* next;# y% o0 s6 b9 g" E
}MONKEY;
9 T# K* f  x  u( \# Nmain()( _" m3 h/ y/ [1 P; o
{ MONKEY *head=NULL,*p,*s;
% R4 e1 I1 h* Y  int i,sum=0,count=0;' A% m( u: `) ^+ b1 m
  clrscr();              //清屏
; V- H  r/ A: Q- P) g* }  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存( u- p" R+ ?/ H
  p->number=1;p->flag=1;
0 T$ R+ L5 w' v9 M$ |) T7 s" V  p->next=head;
* x+ N/ A) Y9 a; n4 t) B& I  head=p;4 c+ B. @. X  p5 U/ ]( k
  for(i=2;i<=M;i++)5 _/ S" E6 o/ |
    { s=(MONKEY *)malloc(sizeof(MONKEY));
  s; ~3 Z# b9 J/ B6 M# s. S8 L     s->number=i;s->flag=1;
& O6 `' Y; B6 {. A1 X% ]     s->next=head;0 z2 Z, L1 n0 r' W
     p->next=s;p=p->next;9 X/ l( |: E0 d% o; ^; G
    }
+ |; M# A5 n% q" J, j1 I( F* t5 O    p=head;
4 I- [" a. A/ o) J* F. B. H   for(;;)
6 a: O' q4 R& g8 K7 k( H& u    {if(p->flag==1)' \" L! v* S+ i9 X8 w/ U) B  @
       count++;
: q: K0 e& h' c) O     if(count==N)% A# t% g8 H! S! [  Z7 |  z
        {p->flag=0;
+ E, [  |+ r/ B: i) p         count=0;' @0 M  {! I$ X# o
         sum++;}" P8 ~3 _1 M6 E3 }! r, S: x
     if(sum==M-1)
* m; |1 s  V' V/ \$ J3 e7 O! }/ E        break;
! D& {- l/ V; t" |     p=p->next;
- |8 Q0 F4 L' a; E7 w! r2 D    }0 M$ I4 s  W( V; h4 o
    p=
' s" |, h0 b7 E# \) \    head;
: Y+ ~0 `/ a. Z+ h4 K    for(i=1;i<=M;i++)/ W9 E1 u2 `5 J) y$ R
    { if(p->flag==1)
4 L& b4 i; f' S7 a" V* V' d' _        printf("\t%d",p->number);2 M% D* |0 |$ X1 U
      p=p->next;6 E* {/ F. O0 y/ m& D
    }
" e! R8 L) \( n, M6 F. J: k( @3 {# A. Q8 ?: f: j1 G

. Q$ [) w9 l8 d+ R8 p
/ g5 ]# H$ S" x+ ~}

" x% I" g" K5 H4 t% v/ P# Z* W第二种方法:数组
$ q7 K0 k, n  Q& w# r#include<stdio.h>
9 m: S, A! E9 v9 d4 S! z#define M 8
# [+ ]* G1 v# ostruct monkey8 Z. a* c  I/ t: O' u) T
{int number;
4 f5 Z2 z  S( dint nextp;
; b' K+ O4 i* w) L- w+ |) y}link[M+1];
8 r" {2 c6 M+ n8 g0 x: w
6 }' D/ b9 g% C$ g; |- Z3 Xvoid main()
9 E, R5 [/ O/ k/ e7 W0 u  U{int i,count,h;" _* J- W2 {- i- d& s" e: K/ t
for(i=1;i<=M;i++)- J4 p" h/ d6 Y  S: Y9 z& A
{  if(i==M)
4 E$ s" C& ^1 I7 ?) _# N2 V/ T; k   link[i].nextp=1;  |) `* m' K9 J" K7 m- x/ a
   else
; [0 T, X, A1 [! ]   link[i].nextp=i+1;3 B2 U( c/ V4 @/ K
  link[i].number=i;
0 q6 H) s1 i$ q" c' _( t" W* D) g}+ P# R+ h! [3 t8 |* X9 g
printf("\n");' s8 q  |! T( l$ a, O
count=0;
: M& x4 D8 ]) t7 c$ w" j1 dh=M;
% L& a. Z# I" c6 F% R) M9 }7 Yprintf("依次退出的猴子: \n");
5 M5 m3 T- d% ~; C" P- J9 xwhile(count<M-1)
7 V' G# {( ]# R  h( q1 s{i=0;3 h$ E# |4 g& H8 [4 X
while(i!=3)
/ I2 W, m% R( P0 R+ q{ h=link[h].nextp;* }' R4 o! u  b+ n& V  N
   if(link[h].number)
+ z' l4 \' U; _( t! b& V     i++;}
1 z: a) k# b. J
! v- ~% u8 M8 N/ tprintf("%4d",link[h].number);
5 e  g/ R: Z- @2 @$ j' Plink[h].number=0;& V7 w: X7 g# v* l3 r# H/ _
count++;' |( }1 u0 u( B
}, h% `! c  ~9 L  C- n  k! ~% G

3 z: ~, H2 e# @) ~* n: \& Qprintf("\n大王是:");
, m& y  o6 ?: x6 q  for(i=1;i<=M;i++)
3 S; F0 Z$ v: m, M+ a  if(link[i].number). L, b1 v) t( w* `$ m" p  O8 t
    printf("%3d\n",link[i].number);: ^3 W6 [: S9 s0 ~6 w# B

. j2 e7 {* F& h0 j
( {$ C! p3 O( ~$ x}

& E  x# @- S4 x第三种是普通方法for循环

- a7 h5 [% _- h" P3 n#include<stdio.h>! j. ~" |  ^3 t4 w$ F- S1 @( q
void main()
$ X. A  C' ]' a9 U5 X{ int i,k,m,n,num[50],q,*p;
: S9 f" s4 I6 z& z    clrscr();$ ]# w7 D3 k! I# c# _5 n$ Y7 R, A5 y
   printf("input number of person: n=");
0 _, u) P6 w# W7 Z% V    scanf("%d",&n);2 Y7 ^) m; U' n4 b* s% B
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
5 U4 i# y1 @1 k: K' A+ \    scanf("%d",&q);
# C/ {# }7 Y7 |5 O2 g   p=num;
: r$ T  L5 ~5 O  R) |# |  for(i=0;i<n;i++)9 y9 C5 h* @. @. ^0 I
    *(p+i)=i+1;
4 s( `, R9 O3 w2 Y+ G   i=0;' I1 E9 j; M  D# V* \1 }
   k=0;
2 I8 p6 h, {& D. M   m=0;
9 M* G" z- K3 g# X$ O  while(m<n-1)
- S! W& y$ S3 B# O8 U& M   {if(*(p+i)!=0) k++;
1 n" I. u+ O! ?. N( O# s3 x     if(k==q)
! @1 E2 G- ]! f& |# Q! X# w1 J      { *(p+i)=0;' d$ o+ R: O$ o& Z! n8 N; P8 ^) k
        k=0;0 o/ B/ r$ _4 ~, f% v
        m++;
$ d. n+ ]* D" u3 p      }
% j9 D- n2 o  i* g5 v    i++;! k  g4 e) X/ p$ n2 A, G
    if(i==n)i=0;
6 I% r$ I* p$ s2 y; V   }7 d( ]1 M" R5 R9 W( Z
  while(*p==0)p++;
( b9 ~5 e: }1 R    printf("The last one is NO:%d\n",*p);" \! E; ?( O5 m
     getch();
% K# S( i! D) l! V& C6 B' r
9 B- M# {+ k, B; G! U8 h}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;$ `5 f2 m3 F$ e( N- q
namespace 又费马达又费电
& `9 R, K- ]& s  w8 b- M{
9 ^: v2 q7 `3 J6 m6 i- Y    class Program5 C* y: K1 Y) R2 O& E9 t
    {; Q, X. ~" B" H3 f0 E
        static void Main(string[] args)
7 G6 \* \2 q3 Q( D1 Y$ i        {% d' q6 I7 d9 S# c6 N0 f$ T5 |: Y0 C
            int m, n;
9 _! S& V% D0 u: s2 Q& S            Console.WriteLine("请输入数组长度");
$ J$ T7 H/ a  K; W: X3 z7 q            m = int.Parse(Console.ReadLine());//m为数组的大小" K; w$ ^. C( E) B) A- A, i
            Console.WriteLine("请输入要截取数字的大小");
. M, \$ _! S/ z: O4 S  P* d% ^            n = int.Parse(Console.ReadLine());+ L4 [; o7 i' ]( \$ ~+ C% t4 L
            int [] numw=new int
, D! J1 @# I3 S# H; E0 D' k- m+ f8 D2 A1 {+ u3 h/ {
&shy;&shy;&shy;;4 T0 Z. R. L5 Z+ E, U
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
) q9 ]) d* r$ P: w; j            {8 W+ M. m1 r, ?* b7 d$ r
                numw[j - 1] = j;& `5 r" S' F: i3 S
            }
4 h" S3 c9 ]) D            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!  h3 j2 s1 q4 Q- p" {6 C
            while (d != m - 1)
' N6 h; t. s$ V# Q4 u            {
4 P# `+ z9 y1 J1 M( Z                if (i == m && d != m - 1)
8 |6 c6 ?, @% b9 r                {
  D- s7 u$ b) Z' d; n                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
. @, G( N! x) M1 ]( c6 z                    continue;
9 O* n  u, X& V' j2 {, _                }
  c  Y# i8 |2 P% Z* q                else2 A4 ~: ^- O  F( a
                {3 H) x- p2 ~4 Q! U
                    if (numw[i] != 0): G* Y' f+ ~4 J7 }( J4 |' m9 Q
                    {; i3 F2 Q& o% e2 c
                        i++;6 m4 m( R: G7 g
                        k++;+ ~! s! h( k- i# |9 }' D3 Z
                        if (k == n)
3 k. c  ]! L& j) a, \                        {5 {3 L$ b! ]# W4 Y8 I
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
2 x* @4 \' V) i4 z0 k+ u" J                            k = 0;
$ }: r7 ~5 j; o2 N5 n6 Y              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
5 |) Q  C0 H! J7 x1 ]" Z# G+ i9 d9 ?                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);1 q: z) Z' W' ]; M7 [; D! d5 `
                        }# X/ ]% }0 R7 z$ p- E
                        else//输出暂时还没有改变数组元素的值+ Y6 v, T, t; h0 B
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
) s. Y* X* C! }* h                    }7 U. l3 p- h: W! d* K
                    else
' P: m5 n1 z) W! y; r0 d1 U                        i++;//数组元素为0,直接跳过,不计数。。。$ \6 ], e; s8 F& d' z% N+ S
                }
7 i: y: K& [- t6 X, S . h5 H" M& v% V9 t2 h3 K
$ a" p1 g- b' B. `- s) }
            }//结束while循环4 u# h! g. F( M0 I; V, H/ O
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
: A* J8 f  F2 x: U7 L+ p( z           & F. \# A5 N" X) \; j
                if (numw[i] != 0)% ?4 s, w5 v1 }( {* X
                    Console.WriteLine(numw[i]);" V3 n' o# h3 S! T# _
           
) }+ `3 M$ j# k. C. K( o( \            Console.ReadLine();& F# G1 m. `* O2 G3 x
        }
! h% F# s( N7 H" p, |    }
$ [2 t& ~; S! j* Y}2 G- l4 y: s7 [' Y3 u1 ]* |
小甲鱼最新课程 -> 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, 2025-7-2 12:48

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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