鱼C论坛

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

猴子问题

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

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

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

x
大家好!
5 c! Q0 s( h& p* V这几天我在忙着编一个问题,我用了一种方法编出来!* j, _, D: w8 h6 {2 n0 c& d
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!: H: z9 T$ [, z1 n8 S' u' V2 b- W2 Q
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 1 b$ h7 k* e0 e% S  S( e9 v
2 f4 B0 Z" \3 `

8 r/ B5 @* f- ^0 F+ Q
                            题目9 m4 F6 e1 q( M- J
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。4 @2 r7 Q6 N$ V" R
第一种方法:利用循环链表$ |: ~9 h: R8 t3 x; j' k" u
#include<stdio.h>  j4 d& i7 l( a9 X+ [$ s
#include<malloc.h>4 }1 J0 C/ c$ q
#define M 8            //共有8只猴子  F5 h) F$ P, L4 }% X
#define N 3            //数到3只时退出第三只0 Q8 ^( }8 t; v) _3 H6 i
typedef struct monkey
8 y* v! ]5 r, f4 @1 x+ T2 Z{int number;
* ~3 R6 v) w, ~" uint flag;. v6 q2 Z9 O$ y8 s
struct monkey* next;
# T# U, C, Y  c0 R8 t}MONKEY;
, l0 m" @+ v& w! qmain()
6 m8 z0 `  S- E3 j{ MONKEY *head=NULL,*p,*s;1 R) M! G. m0 q1 |8 |5 m4 J3 {0 S
  int i,sum=0,count=0;
  c! y* L5 _" Z- H% {; M) R1 f  clrscr();              //清屏
$ g# F1 U& {5 f* }' `  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
) a2 o0 E- S  c* A. G  p->number=1;p->flag=1;. t- H) L4 a  J. o5 U# M
  p->next=head;
' R, K/ A0 R$ W9 q5 q  head=p;/ b6 u+ b+ f: M' {7 X
  for(i=2;i<=M;i++)
9 l; ?2 d  n$ ]    { s=(MONKEY *)malloc(sizeof(MONKEY));6 e- i# x: j3 [/ ^
     s->number=i;s->flag=1;% w* i8 N5 t: w9 w" J  k; h
     s->next=head;6 q# C' o9 ?  e3 P1 t% S* o
     p->next=s;p=p->next;
4 J  d0 E- f' Y# T. S    }
3 w' l6 P9 \, k% }- x5 q, C% n    p=head;
" h* s9 p; x3 W' O! w5 w6 ^2 S4 ]! s   for(;;)0 A1 E$ ~6 d7 @: n7 Y$ n+ p
    {if(p->flag==1)
& O0 P1 \, U" G: T  C, B       count++;" J; ~" O" ]/ S0 [1 O
     if(count==N)
& p: [3 x/ \) b/ q6 G/ |        {p->flag=0;
, b/ }& R. N, e9 C/ |5 v* |         count=0;
9 m2 W9 F3 @, J( {- V  q; q* {         sum++;}5 B1 Q7 b. \# G4 v: _
     if(sum==M-1)- t3 l% S+ V' b4 }+ i" x
        break;
. d/ _8 m8 @8 `2 j# a1 n     p=p->next;
' w3 q' P- `; ^- G) {5 R0 O    }
1 T# Z) C) `+ H2 ]* ^) n    p=5 C2 y% a8 k0 l' j6 a0 N0 S1 @
    head;8 s7 G. ?+ _8 M5 R5 g
    for(i=1;i<=M;i++)# F2 v+ o5 _$ c2 `
    { if(p->flag==1)4 E" S) q9 M5 h% `! b6 i
        printf("\t%d",p->number);
! E* i! `9 k" \! z7 |' }1 Y& I+ v      p=p->next;
! a" n) Q) A- A# h    }
) W3 S" }; T- Y  p
8 s9 C: P' e) f* n* O9 G: e; ~* ^7 P4 Q' e4 @4 U" @; v1 ]8 X# s! R- L+ \

. x& C8 a% p/ t3 g3 {. p0 {}
5 d3 t5 w3 \7 A: [* d. x
第二种方法:数组- E8 l( @, {; s9 N: u% M5 f, I/ V/ q
#include<stdio.h>
# b" ~, D" @7 L, Y# R2 j#define M 8
) r1 K8 |2 i  e" [; \struct monkey
) F, D: M1 r# x' G{int number;3 ]5 {# `& i! h/ J4 ~8 w5 @
int nextp;- @- h; ^  W' m% K% V1 m6 O
}link[M+1];
; U) H% j+ Z* [6 ~8 w
: {9 H/ D% o9 T$ }! L$ Rvoid main()7 [! _1 [, k$ d
{int i,count,h;
3 |% n! Z# v# U8 ]! Kfor(i=1;i<=M;i++)3 {2 x& E$ L7 Y  E% Q
{  if(i==M)* U9 X; }! W) e, x2 D, z, f# ^
   link[i].nextp=1;
+ R) g' R/ g7 h5 Q' m5 o   else9 [: ^! s4 K; `" S; k. w) J" F+ r
   link[i].nextp=i+1;7 V3 s/ Z; l6 D0 ?7 |
  link[i].number=i;
4 c2 ~$ N* _- Y5 e}
" Q2 h8 j: P% |0 {: P' [printf("\n");, r- Z5 l2 v4 ~8 P2 C: w( @+ b
count=0;
2 ?0 G* D6 b) V$ T" |h=M;( F; z/ f, u, [
printf("依次退出的猴子: \n");
1 p; l3 k  H% L, [4 p9 D2 Z, ]while(count<M-1)
8 t; p, A7 c2 Z$ s  k) n# y  j* h{i=0;4 R/ |$ Z" z9 c
while(i!=3)  B! ~8 t6 r! Z) U1 q) O# P
{ h=link[h].nextp;- E+ c* _3 C% o" g& Y9 v0 X
   if(link[h].number)7 @2 ?. p, w+ v' Y8 Y1 R
     i++;}  k) v' _/ a1 ]2 w3 n3 j" f$ o

4 u$ F  \( y9 o3 C" Y1 c$ L. fprintf("%4d",link[h].number);
7 X- N8 y% B3 h0 A6 olink[h].number=0;& B' j" \" K; J. {/ V& Y
count++;
5 p% C2 T+ l5 Q+ H}
) i! e; v6 ^7 x5 s2 E$ d' d- F1 S: M# n$ t: M" ]4 Z2 g+ h
printf("\n大王是:");
3 c" l& z- e  N% c3 y  for(i=1;i<=M;i++)- E2 ^4 l4 L# ~% j  A( p; [* f4 E
  if(link[i].number)
/ G# \9 b( T  ^* S+ w    printf("%3d\n",link[i].number);
  ^* ~) T0 G! ]0 g9 {+ q
. G. U6 Y5 p6 f/ j) p4 ]. l6 ~; q
- z8 n, e+ u/ U8 N* Q}
' S  t0 ?  w7 g, v+ f/ t' ~/ `* h
第三种是普通方法for循环
- ?( h6 D; S0 p( P' i. K. B. G
#include<stdio.h>7 m, m( j$ O" @5 w! G
void main()+ S0 t* m. t( ]  }' D5 p
{ int i,k,m,n,num[50],q,*p;: j, y. F' S- M0 v  P
    clrscr();
0 q, l, z/ {5 a# s0 r& I8 T, c   printf("input number of person: n=");
, v. W- Y$ m# G) c- Q" d    scanf("%d",&n);. q- b* \% }/ h3 C$ O1 D' F" [
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
6 x2 c" {8 S, a+ J* x: G    scanf("%d",&q);
/ `8 L6 {. s6 Y8 v& O# }7 U' _   p=num;
) w- z  n7 g; T' E2 m  u( j9 n  for(i=0;i<n;i++)
, Q& d$ R# b( J1 _" F  [7 w    *(p+i)=i+1;
$ V# ]5 `! ]9 Y* ~0 M; q8 C& K$ S+ d   i=0;7 K) s$ Q' J* l/ X
   k=0;( V% |/ B3 P4 h+ D, f
   m=0;
' c0 \; A' v/ ^7 Y+ {  while(m<n-1)7 b- \: M4 G  z* Y; U: j" x# @: n
   {if(*(p+i)!=0) k++;
# D" v! P* K1 R. ?: K- H8 k* ]     if(k==q)
' w! d6 C9 h' U      { *(p+i)=0;
5 l7 n  }4 c. C        k=0;
7 X# S- A5 b8 c5 P: J% q        m++;
: U' N; G- x! y3 u" C5 f  r. u+ X      }
  i* g" B3 v0 g* {    i++;& H: f7 a6 g+ a9 p8 m
    if(i==n)i=0;
1 E( V7 r- x1 w' D) a/ s2 \* e* G   }
5 ~! _% |& _; K6 A" q  while(*p==0)p++;
9 V, J; B) c, g* F/ J    printf("The last one is NO:%d\n",*p);
( C+ b, u; p3 Z6 H  [1 Z     getch();2 v2 R- i- L/ Z6 m: K- y! ^# Z
' w- C8 v; k, i2 i, X( A( P8 S+ U
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;, t# \% M8 T9 r8 Y+ w
namespace 又费马达又费电! Q; f( p7 I- r  S  k0 c4 l
{1 G. D+ w5 V7 q0 }
    class Program
' s  S7 f* s. _/ T    {% L& u$ X) |5 h. M
        static void Main(string[] args)
$ i& W: J: h- e' \9 K, h/ L, ?        {* f6 H5 c/ }2 w# F$ M
            int m, n;
4 [7 V. E1 B) X! [            Console.WriteLine("请输入数组长度");
$ Y+ c* J4 J9 t6 p" J" [7 Z            m = int.Parse(Console.ReadLine());//m为数组的大小1 V8 @0 T) e8 K) W
            Console.WriteLine("请输入要截取数字的大小");$ Y" K8 s# h# Q; k' T
            n = int.Parse(Console.ReadLine());3 Q- @) D& T+ b/ l- _
            int [] numw=new int: T& W- j( ?7 T4 Y. S0 d8 e

( U: F; s% B2 a/ N* E&shy;&shy;&shy;;
3 T' K; l" e3 s8 Y            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
& W/ ^+ s2 W5 E; W4 {, R            {
7 X) l. \8 v9 s) M% X: w                numw[j - 1] = j;
( b+ `0 J) `, `# a! ?            }
- \* A& b  f; |# T            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
4 ?9 M+ J. k" y6 r4 q, E1 O8 ]            while (d != m - 1)
' x8 r) i1 X9 {4 j) x( I; |* l            {  T& D% o. ]6 f
                if (i == m && d != m - 1)
3 K# s# m8 ]! Q; C' h                {' i& X! ?9 O1 @6 V8 J$ d
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
4 B9 q8 W9 T' I: ?6 C% U                    continue;
2 e) ^5 A) Q! T: D1 X/ j5 m. ]7 `                }
3 S* e; J# R4 P9 n5 f                else3 k6 }, A# x5 t3 r+ k
                {6 a+ s9 s) I# W# J2 D2 B. j
                    if (numw[i] != 0)+ k  n8 Q* @! N3 o9 z0 d' X
                    {2 i0 f* u  h$ I5 |# A) J* \
                        i++;, J, y$ B! ?! @3 C/ s
                        k++;0 m% Y: `! o* V5 ~
                        if (k == n)
" k& n- c* t) f2 f! Y- v0 _4 ]                        {
/ P& q) g0 @8 F/ P0 n; t                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
# O9 H# M. b; `2 P2 q" f                            k = 0;" t( S; {% Q8 p" P  D/ `! A
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小12 o8 q" I- f, s. b
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
; f' P; P9 ^- |: D/ \                        }8 H4 f9 ~; [2 J7 m# n
                        else//输出暂时还没有改变数组元素的值( F( c6 C7 i" |' @) y. w) g' P
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
$ T: m8 Q. i4 f  ]: \0 v                    }
- c; V+ R5 s1 ?& J  {  U, I                    else7 a7 b* i* g. c9 q; [. G* U
                        i++;//数组元素为0,直接跳过,不计数。。。
- K* P# }/ t# L9 \' X; t, Q" \                }
* ^6 q+ m9 o- d5 q' e. R! p9 A 7 a, a0 a! z+ }% {5 H# y: W
" Q4 R8 u% v4 K4 o4 R& d; D
            }//结束while循环# g# F; g6 w8 k2 k. J- o
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦5 W1 C$ ]- r: n
           
/ g( z% t# ]& x/ _' Y: ^  U! v! |( j                if (numw[i] != 0)$ B, K( _8 k1 P4 x0 p
                    Console.WriteLine(numw[i]);
; r$ t9 S8 N. x1 ?7 l9 O& p           ! y% l' D$ x# `( S" ?2 k3 y0 F
            Console.ReadLine();. v( t& O# I7 j3 n
        }0 F7 v. ]2 Z- F- \0 ]
    }$ Y+ ?+ d( F1 Q1 \
}/ N' U2 C, l4 ^9 ?3 T+ O$ u2 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-8-6 08:37

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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