鱼C论坛

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

猴子问题

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

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

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

x
大家好!- E3 g: I5 |' V
这几天我在忙着编一个问题,我用了一种方法编出来!: B; ^# h$ M5 d# G: n
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!8 v$ n# k9 I' p. y/ M( |
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 , H. w  i( |# o; _1 j3 \

7 O7 f- e$ k3 m& e9 ^1 T3 T$ [1 L+ w
/ J6 O! ~3 I  F# M% o
                            题目
7 o6 b9 ]: _+ j0 M山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。' M4 @2 r  P9 P) |: c* k
第一种方法:利用循环链表
9 {" I7 M2 T0 J# ]#include<stdio.h>
0 d$ H5 T. |( ]. k#include<malloc.h>$ m2 i& F7 Z) y4 L3 s5 O6 J
#define M 8            //共有8只猴子
1 m, J& {9 E3 n" i* T#define N 3            //数到3只时退出第三只
+ ^# P" ^6 H( n# ^typedef struct monkey
7 ]' H3 G# R; l2 s" @5 C! ^  a{int number;2 x, n8 L4 s) E. r# K" V+ ^
int flag;+ t- K: g8 a, p
struct monkey* next;
6 G# u& ^6 R) L8 T2 \* ?* u}MONKEY;
  J7 g7 P9 H5 Q9 q7 Z- bmain(): v8 @" \" o# {, P  r
{ MONKEY *head=NULL,*p,*s;" J9 S7 X7 p4 A# L5 W, j0 I
  int i,sum=0,count=0;
6 o- @5 ~$ y$ u4 u  clrscr();              //清屏
! _+ N4 Y- q; e; T  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存  S  g) F& Q' N. q% k- h
  p->number=1;p->flag=1;
/ Z* S) c$ o6 Q1 u  p->next=head;; p* h; k: O5 s/ `
  head=p;
  H. P2 a" V$ v+ ]9 R; }5 F  for(i=2;i<=M;i++)2 D  |" A+ D4 H% f
    { s=(MONKEY *)malloc(sizeof(MONKEY));
0 b; t' |  _! C1 q7 _     s->number=i;s->flag=1;
, ~$ I5 p7 [9 T. a6 H/ a  Y     s->next=head;- a' k0 Y" N' c/ E
     p->next=s;p=p->next;
  j4 b' u, R. u    }. U; i7 O% s$ B7 {4 Z* g7 u7 e
    p=head;
) n4 a& p8 `- w" }; @* y   for(;;)
3 k# ]2 `1 M; L6 z! V) y- y/ F    {if(p->flag==1)6 G# e# m* ~0 P0 c( j
       count++;$ `2 u9 B3 K+ b: J
     if(count==N)
" s8 G7 O. p9 v) \0 _- W        {p->flag=0;4 i7 y5 Z7 U- M
         count=0;
$ D4 d  @& V; Y- Q         sum++;}$ v) U& A+ C% D& d. N1 S! O
     if(sum==M-1)0 ]( J( P, Y- a$ H
        break;
3 `1 u7 j4 ?- ~. d) D* E; z# g" l4 |     p=p->next;7 R. _' x$ M) X, r% Q- W$ ~. u
    }; n, w" V( U+ l6 z( s8 U: N# G
    p=
" K9 \8 w! F7 B    head;
; x. R9 D' X# L- N1 p- V' Y9 R    for(i=1;i<=M;i++)- D& _; r* @  m- M
    { if(p->flag==1)
4 s& L7 N  S; w        printf("\t%d",p->number);
" e. A* G8 h4 [1 u      p=p->next;
8 M$ y0 f: S/ y! K- V  N; [    }6 V. M* u- Y1 F

" b' K& p6 R4 |0 ~4 b, f' r/ _) H7 S
, k2 l( |, ~, Y) N' e0 |% N5 X, x  j! C- \
}

. N$ I- M& K' Z$ R第二种方法:数组
5 T3 ~7 s2 z# `& p, a- H8 P$ @1 ?#include<stdio.h>
  `5 z+ e$ `$ d% u* @' \, T#define M 8$ P& u  U; e' O" M* R6 D
struct monkey- s' w5 r5 q  v6 W
{int number;
# z+ N& p! t3 F2 wint nextp;7 ?5 m  h  O$ V1 m+ H" w2 E, C
}link[M+1];
+ D1 u4 `- U  V1 s' v1 |" m) d- W0 D( y* \0 @% K) R
void main()
5 W6 W1 ^7 k& F+ _2 \* S{int i,count,h;9 S( d4 I9 x, ?5 |4 Z
for(i=1;i<=M;i++)
+ d4 V- I5 q: G{  if(i==M)4 p; ~5 w5 l* Y- S/ E  K7 C8 e: i
   link[i].nextp=1;
& D0 `5 K6 T( b, @4 l! v   else  ~& `. r$ [4 w# r7 C* g/ |  j
   link[i].nextp=i+1;
5 L8 t$ g8 k/ B. G  link[i].number=i;
( t, [$ Q- [7 \% m, v}1 C: M* e/ [3 f7 W6 Z% \
printf("\n");
; E1 R# g" p: O! B+ _9 b! Zcount=0;* O: p$ x6 x8 c$ ?$ n* L
h=M;
# \* [5 n" C* P* f! Z& Mprintf("依次退出的猴子: \n");
6 s3 X8 E  Z8 ?! S, a1 w) }8 S# w* kwhile(count<M-1)
- h' A  G, u, S# j6 Y{i=0;
- I% _& p0 z$ n" o9 N' R/ x0 z% bwhile(i!=3)
* d2 V/ T+ {  \6 Q" }3 v{ h=link[h].nextp;5 S" w3 U, A+ f! H/ }+ Q
   if(link[h].number). l3 \8 ^+ s5 x, g
     i++;}5 e" D/ M. F, J4 r# c1 r
$ D: ~- _. S! G! D* i) j
printf("%4d",link[h].number);
9 d9 {: B9 Y- j2 P1 N& [link[h].number=0;
- ]/ X% G" s# X0 t1 @5 y1 Jcount++;' d! ~* Y7 x. ^; w6 B) b
}
6 ?, M: w& J  b6 L/ T4 a* n* S; J8 j2 S% e7 ?
printf("\n大王是:");4 o# R5 O% p4 `& Z6 ^1 F4 Z& t
  for(i=1;i<=M;i++)) B: @/ }" f5 q* S8 ~& j
  if(link[i].number)
0 k$ z! A) c; T- P4 Q    printf("%3d\n",link[i].number);2 i3 n; ~/ `* g6 O. i/ |
( M5 o' G6 {* ]4 K/ V) V

0 A! P) ^/ d& t  w( q}
$ @' o! u" L7 Z" R
第三种是普通方法for循环

& t4 R' L  c* T7 D: m#include<stdio.h>) v7 b& c3 m  D8 J% U" x- u) S
void main()
2 H1 u' s, Q# ?4 v, g{ int i,k,m,n,num[50],q,*p;' O: F4 {% `% W( n( ~1 T; \" E
    clrscr();
8 r+ ?+ F1 y# G3 b+ N. x+ Z   printf("input number of person: n=");9 s0 j) F) n. ~. |
    scanf("%d",&n);
" @% c: L1 b: q( @' Lprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
, O6 k+ N( F: j5 w" M2 w8 \    scanf("%d",&q);2 e3 @  k4 w8 H7 L' J: l. \; Z1 ^
   p=num;
0 y1 Z5 ~, `) g, ~/ p+ M1 i  for(i=0;i<n;i++)/ m- X$ u% Y8 h  ~( p) c4 f
    *(p+i)=i+1;0 r" w. H2 r7 o1 P4 {. N% ?
   i=0;
" H7 H' B1 B% M: K3 u8 A# @   k=0;
* m$ n4 M* v4 Z+ Q4 C! f: J0 C   m=0;
, `, F8 F: i; M  while(m<n-1)
' u3 v7 ?1 R+ f% W, W. Q   {if(*(p+i)!=0) k++;- A6 n: I$ n( l/ R, a$ V
     if(k==q)0 v2 p' L0 G4 _5 L9 H
      { *(p+i)=0;
% Q' R* H5 I/ F- w% ?. f        k=0;
; q5 }- t, s3 s        m++;% y5 E$ W# Z. ?- s9 `- v6 u
      }. Z7 i9 E  [) C: V1 C
    i++;2 ?: q2 {. E1 L- X3 D
    if(i==n)i=0;( ~" W3 e' \& `) U; A: c
   }
  [" w: Z1 N4 L% J; Q: N- K0 Z  while(*p==0)p++;
/ P  q2 r+ r) \: ?2 h; U, t    printf("The last one is NO:%d\n",*p);2 ?+ c9 I1 e) I- d; l
     getch();
/ X2 H9 S, o& P
9 h+ R8 j/ d+ A+ h+ r( i) y}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
% \  G( T' d8 tnamespace 又费马达又费电: ?) @9 M! b/ r6 W* P
{8 R! _9 ?5 Y( g; d3 p* n+ P. W
    class Program0 Z' ?! u& P* U  X) z- l
    {0 c  L9 f; Y8 e* l' {
        static void Main(string[] args)
. h; U. F+ V; d2 v" P# J  S) B6 i        {( p, c, ?4 G$ L! Z
            int m, n;" d  l- C5 B$ j5 C7 M8 e0 B9 D
            Console.WriteLine("请输入数组长度");
& m' [) M! U( c6 m8 O( _& g- `            m = int.Parse(Console.ReadLine());//m为数组的大小' j/ \+ K* [9 |" \
            Console.WriteLine("请输入要截取数字的大小");
, W" p  S3 q; k            n = int.Parse(Console.ReadLine());
/ |" ^, s$ k- N# `* `, C            int [] numw=new int
% o, g6 y% Q! D% m8 i8 ^- M
( Z1 ?8 {4 Y1 _# U8 B! t7 W&shy;&shy;&shy;;5 j# P+ `7 R- M" m6 ~
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
- c: V( j- s% ~5 u* k5 B# f1 A            {4 U6 X# A6 j  I
                numw[j - 1] = j;2 \; N( J2 h0 z7 K9 i! a, c
            }* @! w! X+ e# c3 Z3 H: b
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
5 z4 u! m# c2 z6 ?+ R7 O            while (d != m - 1)
7 I% J4 P: i) w! i8 W: V            {
7 F. k0 v* o) W0 I! b4 T, s                if (i == m && d != m - 1)
8 f* k( y2 u2 R, R                {
7 w* O" o9 C  g' Y6 P                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
: U% p# P/ ?7 d  {                    continue;
, L( w* @9 F" x8 }' N! O+ U8 `+ c; [                }
1 q& g( Q2 w1 L0 e; `; O2 y                else: b3 w* l/ E9 l, e7 v
                {5 k3 s0 N* ^6 _' Z; C. V
                    if (numw[i] != 0)
' T% J3 @. e+ K/ [                    {
! o9 H4 m+ o, `7 l- w# U/ Y; C                        i++;
  i6 x) n0 n9 f7 y5 S                        k++;' F! v& V- m2 H- n
                        if (k == n)
) K3 J3 M1 f' W+ r                        {
2 G( y# K6 I9 C; e% {. `                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
2 h. V. Z/ D: {; ^1 o8 T                            k = 0;
7 z) o6 |# u% n              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1! @; g/ a: Z1 E
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
% X2 D1 W* |: ^% v7 d                        }
/ o( p. M! s9 `/ y                        else//输出暂时还没有改变数组元素的值6 t+ @0 B2 S) R
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);  l# a6 {. r- s9 b# U# t4 Q  ~# [3 |
                    }
1 Q2 E# Z' _" U, I# ?: t                    else
$ n& M% `4 j3 P                        i++;//数组元素为0,直接跳过,不计数。。。
8 [# x8 a& w( n$ P  h8 I. f0 P0 F) K                }
9 }& a% E- r# C) r# ` # T! _$ R$ ?2 E$ g" ~6 n2 b

  c' P' d7 X. a$ t            }//结束while循环
# b* L* s" Z0 C4 i, Y% e4 h/ I            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
" [! I# v6 B- W/ ]0 `% y           # m+ V8 U. ^+ F
                if (numw[i] != 0)2 `! K7 y' V% F* B
                    Console.WriteLine(numw[i]);/ y( N6 f) Q- \0 u, L
           " z8 Z2 Z9 F6 {& D* M0 j
            Console.ReadLine();
: n( O$ n( {6 x& C7 w6 ?        }" ]" t  `0 N, a8 C' u9 w
    }0 X+ q8 \8 g* p
}
% ^7 _, H1 ~" S' Y5 k
小甲鱼最新课程 -> 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-2-15 12:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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