鱼C论坛

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

猴子问题

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

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

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

x
大家好!/ M" p$ e( [- [, [0 k: J8 T
这几天我在忙着编一个问题,我用了一种方法编出来!
) B: W6 ?; _0 N+ `2 C4 j" {( [但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!1 h0 ?1 o. i+ H: `% o" S
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
& [% {0 H) z, J, L8 V/ @
, }% R% V: C0 }/ a! P8 Y" B/ s' S- T# t  a6 O# E/ H. g( A
                            题目
% ~0 d: X( D8 O7 _3 R1 D山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。- X' W4 X7 |$ `) B- a
第一种方法:利用循环链表
) P$ M6 L0 _4 R7 P7 h& g#include<stdio.h>" N" ^( E6 R2 j+ Q8 a
#include<malloc.h>
/ y4 D8 m: B+ ]; n$ e#define M 8            //共有8只猴子
, N8 R/ @# ]9 f$ y$ a6 m7 D#define N 3            //数到3只时退出第三只
! Y4 i# a% j  z5 Itypedef struct monkey5 X. _2 ~$ U3 |# e: ?" ~: F
{int number;) F5 s5 R) v# L2 P3 U; U
int flag;( ?1 o% {- ?* g# ]' R7 E
struct monkey* next;+ @: M" G! S3 l/ p
}MONKEY;
7 D6 i. c. ~4 j  }/ x8 X) c0 ~main()
/ R& T# ]% r$ E1 F" ^. y{ MONKEY *head=NULL,*p,*s;
( b9 i5 {6 g* ?8 E- n0 i8 O- W  int i,sum=0,count=0;
* }' T6 M) e0 n" I4 Y! U  `  clrscr();              //清屏
+ S7 `* T/ X* h0 o) E  w; p0 a. `  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
4 C$ d* F; q/ I2 O# {! U' r5 D  p->number=1;p->flag=1;- U" n; \0 U# L: z7 e8 {
  p->next=head;0 i2 ]8 D# I* u- i1 J
  head=p;
4 w9 J5 K2 B6 [  for(i=2;i<=M;i++)' y7 `2 S  H/ J$ W0 f" q1 P
    { s=(MONKEY *)malloc(sizeof(MONKEY));
% l/ `( [# w) V; T     s->number=i;s->flag=1;
" \2 {% i  a. T% |) Y# h     s->next=head;" ]9 d  F) K4 i! ~7 V7 X
     p->next=s;p=p->next;
$ F! U+ ]% W5 U: Q! Q, w5 J! E    }
' ]4 H$ N, E# J  H* }: M    p=head;* C( B& w9 N# J7 R6 c
   for(;;); k2 y) h: V7 t. M5 ]
    {if(p->flag==1)* h' G+ ?* v& z$ z6 U$ l
       count++;
  E3 d! o" x& @" ^     if(count==N)
1 ^: a* k+ ^; g0 |, [1 K        {p->flag=0;
; v, @" z' y+ V         count=0;
/ P: v/ `6 x6 F% m; p9 T# N: @0 ]         sum++;}$ i, ~6 {9 J, ^3 h
     if(sum==M-1)! n$ G0 O4 ^+ M9 x. d" b9 |
        break;$ T: h+ \" c) W" o* i  S
     p=p->next;! o2 s) q8 ]+ }+ v5 h6 _+ K8 j
    }
7 [1 J/ l  U7 o1 E3 C  Z    p=6 f2 C4 u4 u1 q1 h  |+ M" r0 P& r
    head;0 E' M$ r( I. S* w# L# E  E
    for(i=1;i<=M;i++)
' P+ n. q& O1 o4 e) R: G    { if(p->flag==1)' L$ }8 y/ e) n% R7 B
        printf("\t%d",p->number);% U9 ?: l" y+ T4 L- h4 H
      p=p->next;
8 T1 o, b/ F% F    }/ t4 B5 n  T+ Y+ D9 a6 U$ v5 e
8 G9 r* P5 b9 ]0 G

2 e9 ^9 j1 R; N2 }1 I
, O* V8 \+ G5 A  \+ [5 ?" P; w5 b3 H/ k}
/ x& e- z! |1 O+ r' B! Z: |
第二种方法:数组
, {7 y+ R( U- r#include<stdio.h>
% x0 q' z: t/ Q4 D( E#define M 8
6 ]( O8 a! X2 S6 D4 zstruct monkey* s& ^9 F8 a4 ?/ ?) i2 T" [( g8 _" b
{int number;) q: ]* p2 ^; W9 a7 Q' E0 k
int nextp;
5 O" S. ?; P3 Y+ ]7 N- K! I}link[M+1];( g' _4 N$ b' ~: e/ |

# E; x: A3 e& o9 a  U" |void main()
7 a9 i9 v) ?. q" w5 g{int i,count,h;) k2 o+ \2 ~8 L$ \! ?) ]
for(i=1;i<=M;i++)
; h9 r" e- I9 S0 I{  if(i==M)$ |1 I/ E$ J8 K! d. ~6 q4 Z9 b
   link[i].nextp=1;
6 L8 Y5 v! D% D: T   else8 ?1 _) `" c& S6 ~: d
   link[i].nextp=i+1;5 A9 V( H, G/ e7 @) ^
  link[i].number=i;+ H8 g) C* t  K" B3 _
}/ _7 g, {  k. t; A1 z* u9 q  u
printf("\n");
( @) @! f+ B* ]5 @" y: P8 [count=0;: v( m6 \/ Q- @9 T7 \8 a( Z! q
h=M;7 O6 W1 B* S9 p* L0 x# D! L
printf("依次退出的猴子: \n");$ |. @5 m/ f; M/ B, B+ K6 K- p
while(count<M-1)& H8 l; i7 Y5 z6 |
{i=0;
9 C0 Z, @- U& p% S  cwhile(i!=3)
  o! s  w( C, l1 s0 i" T{ h=link[h].nextp;9 n. m1 @7 a* M
   if(link[h].number)3 T& z0 d; {4 `$ H$ x% _) P
     i++;}; ?5 M6 r% d/ P9 z1 B

8 b; A1 g; K7 Dprintf("%4d",link[h].number);
- X# j: z( c+ I( @6 glink[h].number=0;; ^, M5 d" |, E3 [4 ?, o
count++;( X* S- s. r. l5 S" L
}  J( p9 }: n) `: U+ m* t+ p. j
! N' U6 h5 G  l+ ?3 y. ^/ ]
printf("\n大王是:");$ c9 H9 [9 c* |( p/ X5 D% d* b
  for(i=1;i<=M;i++)  j  e! P( d5 ]% V+ G2 }
  if(link[i].number). b- ], u6 R0 F) J6 v! O
    printf("%3d\n",link[i].number);  v+ h0 b$ i2 C% {& V
9 v# p! a* ~. J; |
' ^5 e$ h: o& g8 X, o
}

0 v$ [, e3 a" }% O1 p  U第三种是普通方法for循环
% j7 K1 f" `2 P9 d7 R9 O
#include<stdio.h>, G. k& M( Y5 z; y' v5 `8 F
void main()* c, _; e; ~3 x/ Y) u$ I' H0 M
{ int i,k,m,n,num[50],q,*p;2 l+ c* |7 r1 ?7 F
    clrscr();
7 n+ L- B8 W4 q3 l   printf("input number of person: n=");
! c+ Y* b7 b( B3 d' N    scanf("%d",&n);
* o9 Q, f7 ^" d" F( nprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
: b% f3 a% S& o: Z+ b$ @    scanf("%d",&q);; q; \; I& D9 c* @3 i
   p=num;
/ S: r! n" j8 t/ R' Y; S# _6 i" s  for(i=0;i<n;i++)& F# u5 L5 l# |4 B2 W8 d
    *(p+i)=i+1;
7 P7 F2 x0 Q) Q' s& i9 d   i=0;
/ f2 h" w  Z1 n/ `3 o" G   k=0;$ W# `4 `4 n; T, _& V
   m=0;) w% J% @& Y* a0 M+ R: z; z
  while(m<n-1)
5 e, f, _8 e" c   {if(*(p+i)!=0) k++;4 E2 F, a; o3 a* C# Z! u) O' X" J1 W
     if(k==q)8 E* G5 w5 G5 r( f8 z
      { *(p+i)=0;$ [, o+ F! s! H: l: n2 J
        k=0;! L$ i$ T, ]; ?! O8 p/ r& d0 E% q
        m++;
; s$ L. j" x5 q8 v      }$ E$ v2 C3 X2 n: f
    i++;9 H, F- c, J& {. p3 U' W7 w; e
    if(i==n)i=0;
8 _) A# @: A- ]% Q   }
$ [8 k5 F) b4 N! s1 m7 M3 R, H  while(*p==0)p++;0 V: o+ L/ g8 X4 D5 M1 E6 \7 `- o" @' X
    printf("The last one is NO:%d\n",*p);
4 E1 q1 P7 l0 y5 g" w% Q. a; X# g     getch();
, b6 j. I# O/ E, ~- y; k5 A
' B* m" ^1 A/ k6 ^! e6 K}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
8 D( Y/ w% X! C/ Bnamespace 又费马达又费电
: C+ _% {+ O- g% G3 Z/ X' V5 T! E{
; i( t2 N; v. O. _6 ~    class Program
# r/ i- z+ D( B  Z    {! o+ `( |0 p; j2 o: B0 Q, F0 m
        static void Main(string[] args)
4 G( V1 ?$ V  m  q  @( u, [        {
- N1 {/ Q2 K$ X6 m8 ?; `- k            int m, n;
2 `0 y* ?9 t. v3 \) ]/ p            Console.WriteLine("请输入数组长度");7 o% w1 e! |! h1 y2 b+ n5 y4 {% Q
            m = int.Parse(Console.ReadLine());//m为数组的大小
! b, z* i5 U/ W/ T- Z) b7 J5 _7 v            Console.WriteLine("请输入要截取数字的大小");
, x$ z0 {  @- w" Q+ w) c            n = int.Parse(Console.ReadLine());$ `4 S- X/ T2 p5 h) C
            int [] numw=new int
; g' i& ^7 m, m; |+ h0 K
6 t* B; P6 _8 q2 F, }& \5 j5 H&shy;&shy;&shy;;
# I* B5 z& Z  V' }            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
% i' c2 B' L6 B7 \, s9 _            {
! u2 D' h4 u# ~  @3 o) n                numw[j - 1] = j;
$ C. Z, I3 q, f            }
0 Z; T9 S1 F9 u* t: y            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!' a2 R; ]$ q/ U
            while (d != m - 1): g; v$ h  U( G, y
            {" R0 D7 D* S" F
                if (i == m && d != m - 1)
$ s; C" ?) ~8 R                {1 P2 `) @. T' a% ~/ m( [
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
) `+ L3 X! t7 l" P                    continue;( p! Y( w8 g1 O! g/ M% u' a" T; |
                }
* E, u+ b! C$ D( H  A& ~: J                else# Z7 Y4 q2 j8 X$ G
                {
: S! B  P2 P' n# C* @                    if (numw[i] != 0)* V+ n$ f0 d: Y! Y( x# x8 Y1 W7 n: \
                    {
* r/ a  o2 v- ]' F                        i++;
9 V- j. D$ T. d" A( H: H' ]                        k++;
' |% M1 N' f4 r  L5 d                        if (k == n)
+ W6 u0 @8 I  K! `                        {8 X, Y" g2 _4 \' n$ ?" v9 f
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& P7 _9 K8 b  N$ o: E, Y8 ]
                            k = 0;
" e5 t* G  I* J              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小14 q) O6 ]' C% I6 u. w" N! `
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* |: q- l/ o2 c
                        }! d9 U% E% N- Y# _2 M. I
                        else//输出暂时还没有改变数组元素的值) o4 V( S# T6 ]' g+ g
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);2 T8 }$ [. B' _: a2 |, \
                    }
2 e1 k- w2 n0 I( Q! S                    else0 U' A% P2 H( [
                        i++;//数组元素为0,直接跳过,不计数。。。( _' e+ V2 z5 Y$ I8 M$ a8 @3 K
                }
# O3 T) D2 p5 o9 a3 G   u7 v/ @; Z; ?
/ L# Y% Z9 W( C! @4 O( p
            }//结束while循环
# R) ^+ A  V, C6 o9 ^( q6 G/ K            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦+ j' S3 L+ N0 h9 w; \- W5 B
           + v" [5 E) T. X# n# U- z3 p
                if (numw[i] != 0)
: w+ p" E4 v: J4 ^% U9 W                    Console.WriteLine(numw[i]);
: n/ J0 |1 J, a( A/ T) S" G3 _* E           * E; s. D% w) h# j& z: Z
            Console.ReadLine();
4 ]9 ~5 x' J! A. P- {: o3 U        }
/ c; A( w8 ~" X/ B    }
$ j+ E2 w$ w$ ?7 C: o8 F}2 M, @, T* M8 s3 y; z
小甲鱼最新课程 -> 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-10 05:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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