鱼C论坛

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

猴子问题

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

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

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

x
大家好!
% O& x* b% X9 @这几天我在忙着编一个问题,我用了一种方法编出来!$ E2 c- h2 R. l: Z% T
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!& L0 M. E. |2 J( Q/ P& ?
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
  j( k9 h9 m5 g- r0 n) s$ u& ^/ |( o' o0 z6 _8 }* B/ `$ v' r

: S& s/ M* b# z% _+ o6 c% [
                            题目
, o3 a% y0 c- k% g5 _山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
$ R5 O  k! \- \0 B第一种方法:利用循环链表
: V% b  R) N. R' J( @3 T3 a#include<stdio.h>" I" r% v# O% T9 W$ q
#include<malloc.h>! x4 d6 Q4 r/ G) a( V; M9 r) T
#define M 8            //共有8只猴子1 S; d7 y. R* P9 `
#define N 3            //数到3只时退出第三只8 f+ f9 M" Q4 V! M( s
typedef struct monkey
" U1 I" S/ ?, A* D% g{int number;
: _* K0 A' F: O% fint flag;
; O$ S/ v2 ?4 ?struct monkey* next;
5 S9 A8 H* ^% a}MONKEY;9 F# Y& u# \3 f6 d3 U" [, C
main()* d2 W7 t1 e! \3 S
{ MONKEY *head=NULL,*p,*s;( {- H  t9 r' c
  int i,sum=0,count=0;3 @, V: L4 o: N/ z
  clrscr();              //清屏
8 w& N0 o- Z* S+ w: |  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存. D* y) j+ r1 c/ i5 V' b: M; n
  p->number=1;p->flag=1;9 m, r+ W! d/ n* q+ d+ {- r
  p->next=head;
1 L) Z9 o! R/ [# R9 r+ \  head=p;
! w3 J6 `0 x# b! E  for(i=2;i<=M;i++)2 U6 w% D3 P, _4 a9 H2 D
    { s=(MONKEY *)malloc(sizeof(MONKEY));: f: T2 l" s; Y% q* x
     s->number=i;s->flag=1;: i2 N# _: P4 E4 ]% k9 q9 z* N
     s->next=head;
5 A3 r! E5 l3 |- C7 Y     p->next=s;p=p->next;. _$ o0 K- G' ?. y6 x: R
    }; M$ _" h; o% [
    p=head;* B6 t0 y8 Z* b: u
   for(;;)' p0 H. ]0 z$ w: _: S
    {if(p->flag==1)
  P. f  C2 _, \9 T/ w; ]7 {       count++;
1 F3 {; t! B% r' F/ Y0 N6 v     if(count==N)3 K3 _& V+ P" k6 P. o/ D
        {p->flag=0;( w8 D# Q- H' w7 r& M) a
         count=0;4 F$ l$ @0 b( n% F' h4 K
         sum++;}
+ R3 M9 ?4 m  p; S/ z     if(sum==M-1)( `: p+ _8 w) G  a2 D- y8 \
        break;
! \/ ^: f$ U* p7 P3 _     p=p->next;
2 E2 p1 x0 o6 L' ]    }
( g8 q) `; ^0 |- y. V    p=
& n( n) A5 C6 R+ y: g9 c    head;  T" S7 W7 h% t
    for(i=1;i<=M;i++)
1 O% ~5 U4 C& O! j4 h    { if(p->flag==1)+ H2 [9 P/ R# x6 Y! e. a
        printf("\t%d",p->number);
& Y! ]2 E8 A, ~      p=p->next;
/ F% o2 N3 c6 ^    }
! x. b8 p/ o4 r4 Y/ T9 ]1 j) v6 g0 P$ M3 r* U1 R4 ]

5 C( Y: W3 s2 V# c, Z
0 f1 K5 c0 Z% X}

: J; C$ p/ V7 D! U9 m第二种方法:数组. v' D; ]+ L, ?4 N8 B' L
#include<stdio.h>, h% e8 J* E1 G# c- e- K# ~$ ?
#define M 8  g! F" z" G* P8 n; A/ ^/ q# Q1 {; n
struct monkey
) B: `; h9 m' R( U' d{int number;; a: v& I% }' O8 Z1 p
int nextp;
# b+ P6 [" e; R( h}link[M+1];
3 n3 C: q* w4 Q! @
/ {( M7 N7 D5 r. W. q1 avoid main()) t: S5 ]1 i8 C( m
{int i,count,h;
0 ~! d4 T* a1 Yfor(i=1;i<=M;i++)6 q9 B, h1 {2 z/ c7 U- k& X3 L
{  if(i==M)
6 M- a$ @, F) x8 d( j2 Y  x   link[i].nextp=1;
) w3 M) p2 z$ Q" m6 v. k   else5 w9 Y( F3 z- M$ Y) J+ [& ?" o
   link[i].nextp=i+1;$ K5 X+ U* y1 p: x! e8 a
  link[i].number=i;1 R0 d# B8 s: D% v( M' ]
}; R4 A& A* Z- v0 V3 [; `8 h
printf("\n");
5 E$ @, f3 N( v& Icount=0;
4 d, W9 L& T! D+ Ch=M;
5 n4 I5 T0 c6 g: ~printf("依次退出的猴子: \n");& S! I7 ]2 l3 ]( P6 X1 r  ?9 `  j
while(count<M-1)
, a  J  Z2 W* a+ n{i=0;
1 B7 ^" p. L1 v9 R4 ]% b3 nwhile(i!=3)
% a0 f# p$ U6 R" O& X7 c' j{ h=link[h].nextp;3 j* K3 k" ]9 {# H* y1 [9 X' U
   if(link[h].number)
* T/ K9 [7 n) @% j. ?9 [/ f" L     i++;}
% ^7 n5 H- e8 D3 k
; T+ _1 O1 j: Hprintf("%4d",link[h].number);, m1 ]7 s" x: |/ ?) l% U, u8 |
link[h].number=0;
0 g/ b2 x+ X6 v, Z9 `$ F% gcount++;
; ?+ l+ C' M- |! r+ e$ q}
) q2 I7 a+ @8 a. G2 u. B9 A9 j+ j
- ?' T6 O* W1 V& w1 t1 F/ e, Yprintf("\n大王是:");
- J/ s5 E9 t' a' g  H# i; ?  for(i=1;i<=M;i++)
* J* j% F6 ]+ Z+ l" `, L% Y0 B8 s  if(link[i].number)% [% B; M" l6 p# S) I" R
    printf("%3d\n",link[i].number);
7 o& J7 A8 ~6 F; @) v. f( ]/ X- O1 W+ b2 A: g# ~4 ?4 ~; M! X( ]

3 t' W/ y/ [/ y}

3 s& M) f* t1 \0 [/ G# ]# G1 v! ]第三种是普通方法for循环
6 ?, X5 X( u) m3 l
#include<stdio.h>: K; w9 Y1 p$ o$ S7 K7 _
void main()
7 i. f  s5 s7 j9 x+ T! y8 G{ int i,k,m,n,num[50],q,*p;, B% u) T+ F- g# ~
    clrscr();' X8 q1 ~; R: q( T
   printf("input number of person: n=");3 t' y9 `1 F* r! n8 q$ {
    scanf("%d",&n);/ o9 L, Q, B5 e6 N
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只: w( H  H( `4 b
    scanf("%d",&q);2 R% M7 |4 X7 D+ e' c
   p=num;& n* k8 C/ g" f' ^
  for(i=0;i<n;i++)
5 R- w6 U0 E; u% {    *(p+i)=i+1;
+ i" [6 i; n6 K, I   i=0;
$ u, ?8 ?/ U  z" ?6 q$ f8 \   k=0;" C( @2 N! ~! ~; D  O3 H
   m=0;+ X# |4 @) m  o8 j% R
  while(m<n-1)) g; A: B, x! A8 x
   {if(*(p+i)!=0) k++;8 Z2 c' V  v" F- `
     if(k==q)' I8 [4 x/ |( c. X: B
      { *(p+i)=0;
4 ~9 `1 f. a" ?* x; g2 k        k=0;4 a( T8 _% t# Q* \2 _5 a$ b
        m++;- }0 w' U$ M3 F6 s0 ?; [
      }
5 \% }" _; @! l. q    i++;
0 V# T. F) e  b' W/ e$ Z4 [+ L' Z; y    if(i==n)i=0;3 K4 m4 i, A; w
   }) F" V/ C# i- c
  while(*p==0)p++;6 f- U+ z% q" s  k, A
    printf("The last one is NO:%d\n",*p);0 Y* Z3 f! a$ q2 K( r+ P
     getch();' k) X0 E: ]. m. K
" ~( O2 V- e' u* \
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;- `$ I5 u3 L) {8 \$ N" I5 f6 v: A0 P% }
namespace 又费马达又费电
" j6 X7 D- S' M! b$ ]{
& i# B8 E/ ^7 y1 V' `    class Program
# b  y- `% \8 f1 A, y    {2 [4 O* \) C$ T/ O2 y
        static void Main(string[] args)
" `" ^# P  l% q3 I; }( P        {
/ \( b) `3 {# [8 {& G% y' z            int m, n;# z% y- |' s% l
            Console.WriteLine("请输入数组长度");
  _/ k2 N/ K* v7 K7 J; h4 j            m = int.Parse(Console.ReadLine());//m为数组的大小
% G1 X  h8 s* {$ b7 d0 l' p            Console.WriteLine("请输入要截取数字的大小");
4 |# h8 P2 D* v0 \6 N            n = int.Parse(Console.ReadLine());; z0 _# x; C( B9 l! y
            int [] numw=new int! M8 S/ x  Y% T9 R2 P2 v* e, ?
7 M( {5 @$ Z% z- {5 c# Y+ G
&shy;&shy;&shy;;
) T2 @+ J7 e: @, R+ c. h3 c" }            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
8 L8 a' t4 B0 y( ?, I            {
' T% T% z( J% N2 E1 B7 p0 |                numw[j - 1] = j;8 K3 p8 m% j3 J) ~- Z
            }
! Y9 ^  G% S: X            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!8 j6 l5 ?7 G4 \9 x+ l" `) t8 n
            while (d != m - 1)8 j3 x0 K1 i1 f$ O
            {4 h1 R, q3 {7 ~; ]; z* x
                if (i == m && d != m - 1)
& ^5 O3 C- G7 l4 t' T                {
1 i9 B- x! w5 D1 u8 W2 i                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!7 H( v8 T" z1 w- k
                    continue;
1 S! z6 A4 k1 Y6 X- A. v& y                }9 ]0 M: |3 u- F$ X
                else* n8 r9 N' Q) c+ S: Q
                {
2 U/ `) M3 Y1 ?( ]                    if (numw[i] != 0)
: P; }- [, _, f+ s' d2 P                    {
' C9 u* S6 [1 O                        i++;
3 n/ B1 {6 Y7 X& Z0 A                        k++;( T+ ^7 p* f) N4 X& x
                        if (k == n)
1 h$ K0 u! o9 m; J( h. p, G! b                        {& L" z1 Q$ ~; H- z$ P* [  H
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
" `) J% B" d. I( {- c  O2 I                            k = 0;
- T+ g6 h1 m3 b( _2 _              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小19 v# f6 q0 [' S5 d5 T- V
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);2 S, a# ]  S0 [0 v2 o+ }; A
                        }
7 }4 y/ Y6 \& j+ ~                        else//输出暂时还没有改变数组元素的值/ j/ x1 V" K# V0 k5 k% D
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);2 }. x$ e3 x9 ?  u* V4 ~7 d
                    }
( h2 S( l7 `* Z  x; z                    else
6 h% D2 u7 {3 K, A$ Q' e                        i++;//数组元素为0,直接跳过,不计数。。。
. |+ m% I9 }* T; D/ w. w2 c6 ~                }1 w5 {; W7 z7 M* @4 ~

* d/ H( V% {4 r' S( S& j) V9 H+ K4 E1 f3 R' y% r& u" b
            }//结束while循环4 ]* D: r0 @* H2 T% `
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
: d) Q$ B5 l0 \$ h% Q; D& z           : L7 W, S, ]  r( Q/ B; J
                if (numw[i] != 0)
& S( M$ e, l/ F                    Console.WriteLine(numw[i]);! ]. T8 U" u6 l3 o/ \
           " @) e9 v3 J5 J' O# Y! q
            Console.ReadLine();
% n4 b. K9 c. t. f2 o5 s        }
3 z0 _. ?3 p  ^4 R    }: Y  s$ r2 V4 Y/ c& ~
}1 P. l0 m7 f+ L( X
小甲鱼最新课程 -> 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-11-11 16:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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