鱼C论坛

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

猴子问题

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

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

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

x
大家好!! G% l7 S3 u' ^* y
这几天我在忙着编一个问题,我用了一种方法编出来!2 g# \. s5 b7 W" u/ I. p0 F) i! G* h
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!. k2 z  S& k( c, T; S: E
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
1 r, y1 U  A' }9 J; F2 N5 s  @0 q( U2 q: T$ q: k3 k+ v

* g$ G6 h9 L1 y5 F% W; O5 Q
                            题目, L6 Y$ G# Q% n; `; `
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。% f+ _3 B* J2 E
第一种方法:利用循环链表
; Y$ \! g9 v3 Y: ^7 ^#include<stdio.h>$ T/ u! n4 t5 n- a7 Q
#include<malloc.h>7 w9 i- I- U! a
#define M 8            //共有8只猴子2 Y8 R5 }0 [! P  K
#define N 3            //数到3只时退出第三只0 ?' w7 {& o# n
typedef struct monkey
9 A7 j5 V- i$ k: V+ D{int number;* `6 A% G6 N. ?- I7 f# j
int flag;" B  i9 [) g% f# F5 A) l
struct monkey* next;
$ T  }1 L; U& V* P6 Z, V2 O3 n}MONKEY;8 n) G& s4 q5 V7 G: h0 D  a. n
main()
- g% X# }% I7 P7 c% c{ MONKEY *head=NULL,*p,*s;
% y, U, q% g+ _  int i,sum=0,count=0;
! X" T+ X3 X* N  x  clrscr();              //清屏! H$ d2 B5 t  |/ s# B
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
& }5 Z5 \- K2 n. ~% |  p->number=1;p->flag=1;
8 [1 {- h  Q5 L9 |/ a$ P: e. X  p->next=head;
! V8 M3 u4 t" K0 A. O/ o  head=p;
! s! M7 ?, o+ [7 v5 W  for(i=2;i<=M;i++)
  ?6 |8 {* v/ r8 [& T6 ~% _# p    { s=(MONKEY *)malloc(sizeof(MONKEY));
9 P. O3 k- `* Z     s->number=i;s->flag=1;2 l/ i! a: z: Y
     s->next=head;: X: X5 o) w4 P  P) B9 g
     p->next=s;p=p->next;
& e- g+ x* N# R1 B7 l& a7 R* a; ^    }/ j9 _: p6 a0 x+ r  ^. f6 v1 F
    p=head;; @  y8 ?# R, z5 a
   for(;;): T5 r5 x+ M) z- g
    {if(p->flag==1)7 q0 Q& L  v6 b( H/ \! L6 `
       count++;! f5 g" q7 w- y- q( O4 k% C
     if(count==N)* ~8 [. j& I. @* ^) _
        {p->flag=0;( R! a" S" d4 A4 }$ P1 u; I7 `
         count=0;/ d1 N- D' k1 D
         sum++;}
: r. {1 }) X  o* x2 V: d* Z     if(sum==M-1)
2 O, d2 n) o! ^: f+ E( i$ P$ n( Y. j        break;
- W5 k/ K! q4 [; t3 C/ b     p=p->next;
$ R2 u0 @& z2 ?* ]) J    }
5 M6 j1 E6 ~; H    p=
! j* j+ [. e( h5 I- `& k' e    head;
  X. D1 z' s4 V9 z7 b  y/ Z3 Q# Z    for(i=1;i<=M;i++)& {1 _1 B( \5 a( G
    { if(p->flag==1)
* _/ i6 ~! ?. C9 m  b0 J: V- Y5 F        printf("\t%d",p->number);
0 A( ?. x% `/ K" A8 ?- H4 {5 I      p=p->next;
. X0 Z, o2 `7 y. B* x/ K2 W2 I( s    }
8 s+ ^; o4 W) x' J" l1 C& K& v
( V( X5 h7 N* I' B  O, X( o  \5 a  ?9 T/ V2 g9 C

: L: C  |0 _/ d3 P+ C" e9 N1 N}

& X$ h; O" e) x. t: R. Y第二种方法:数组6 u! m7 t, }) J7 g3 |, I9 E
#include<stdio.h>- G2 c8 b6 E, ]3 C/ c
#define M 8; ~* ~' F: X8 X
struct monkey( |1 c$ U0 i. L) i2 M
{int number;
3 n0 Z# k6 V# ^- D" I' `int nextp;( q7 f5 D+ x6 l5 h# {2 g
}link[M+1];8 s! G1 E0 @* j
1 ]8 Y. z& Z! P! S0 |
void main()5 ^" J( J0 ^, C+ b; P% W
{int i,count,h;
: o- y% E4 ]( d- @2 S; G1 W3 xfor(i=1;i<=M;i++)" U$ s' l0 G& O) G
{  if(i==M): \5 G6 x. Q! |$ u" j% R" Q, U  B
   link[i].nextp=1;! z6 N& {3 J# v. N# ?
   else
" F$ p/ B; u) T+ J2 {: L2 t, a   link[i].nextp=i+1;
( G$ K$ n  x) A. z$ e  link[i].number=i;
9 u- X; A* Q, s' R8 l4 R}/ b8 {1 X) C( Y+ f
printf("\n");1 w9 z' k7 S0 m) A' U- R( q
count=0;( n$ f9 [9 t' b0 `: U5 N
h=M;7 l) }0 M+ p, P+ z/ i7 W5 _! C. U
printf("依次退出的猴子: \n");
+ l& S( \0 q" }7 U, L$ Vwhile(count<M-1)) I, C1 |! }& f  d1 l# d& j5 Z
{i=0;
( B+ Z$ k7 \. k& mwhile(i!=3)
) g3 }" ?, D; U$ B) C{ h=link[h].nextp;4 i/ [  r8 J, R% g, z2 _
   if(link[h].number)
, \  h2 Z" W. E* ?7 E     i++;}
+ o7 f- F5 O1 f4 ^' w. [2 O0 ^( r: z/ t7 W3 G, h- U
printf("%4d",link[h].number);) t5 D1 w- b8 `9 X' G6 u" M
link[h].number=0;
8 a: V  Z8 S4 D0 ucount++;
$ F4 P* {) Z9 s( I* m}4 x% x) H% a" J9 _

5 n& q& n  u  Q0 Cprintf("\n大王是:");
( z3 d# P: P& b( q  o5 H  for(i=1;i<=M;i++)
- l& m: G( {/ {; X7 C  if(link[i].number)6 W# T1 |( F$ d1 H- Q8 c
    printf("%3d\n",link[i].number);
0 r  |: l! n1 h, k. N: R
6 }, t5 e$ e& N
  w. ]( s! f. @2 a+ G}
2 w* K* ]% |2 w6 L0 N* g! W: p
第三种是普通方法for循环
  \( \* f9 n) r0 m, @$ J7 }* i% C5 I
#include<stdio.h>/ P. X5 V% T6 D9 J8 j2 n! H6 }( E
void main()1 e2 I% w- o  z
{ int i,k,m,n,num[50],q,*p;
1 y, G% [5 ~( o. m    clrscr();+ _2 ^- g* q3 A- J% h
   printf("input number of person: n=");
* y2 j0 u+ o  @2 X. G: c2 y" s    scanf("%d",&n);
; H3 j. K& E9 M. t( y" Rprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
/ ?7 y5 \9 m8 b& k- e7 O    scanf("%d",&q);8 O2 N- o: o4 z8 c, m
   p=num;( q! Z- m. ?5 p* h4 O
  for(i=0;i<n;i++)0 s! B- e/ s. l- R; `
    *(p+i)=i+1;
( C7 b' J/ `0 C% t3 ^! y   i=0;
9 K# l5 C( `5 g: L. R. g   k=0;
) l( |& {7 X( G" H0 C   m=0;# E. Y. f$ ?; |: x2 C/ l
  while(m<n-1)
7 t; O1 c9 U. E: o   {if(*(p+i)!=0) k++;4 p* p4 Q- h. c1 b$ A. M* R& S
     if(k==q)) w2 L- E& F" G; f6 ?
      { *(p+i)=0;. W8 |1 Z8 T/ n4 m; }" Q( [
        k=0;
: X/ `$ R% f! b1 z" v" _* E) o        m++;1 N# X- H. r' A) L% _" }9 `3 D  E
      }
5 a' @' C9 p6 w: B    i++;' S9 ^9 d; _/ E/ U  H/ e# K
    if(i==n)i=0;
8 `, t* l( [9 L* Y# L& N2 E   }
4 V5 V1 q+ T1 Q. ~& Z  T- u; c  while(*p==0)p++;
0 o. T+ V! v6 x5 q! C& i5 N    printf("The last one is NO:%d\n",*p);
0 n0 T- U# ^* L* w+ ]3 N     getch();$ l9 d6 @! I  W) {
8 S" D7 t+ |4 P6 D8 `( k
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
2 t( n6 B% `+ B& q2 {namespace 又费马达又费电6 Z5 x9 Q" |3 R7 F- d* Y( V2 U
{
( k' _+ N6 ~; q/ \! L4 _0 `    class Program
5 H# v# d! E4 |$ Z) @    {3 \5 t" p2 Q% J. Q2 f& C. A. d# R
        static void Main(string[] args)" K# G! f# A" r( e- P4 J
        {
1 ^/ ~. F# q: O. i            int m, n;( M. h+ K% w0 S/ ^1 E3 \/ @! r& D
            Console.WriteLine("请输入数组长度");
5 [1 z% e% z$ y: C# Y            m = int.Parse(Console.ReadLine());//m为数组的大小0 g: ]3 R: B, c2 J) _6 Q9 d) N# G, z
            Console.WriteLine("请输入要截取数字的大小");! W* j- I1 E! E* Y8 Z
            n = int.Parse(Console.ReadLine());' G/ b; S" n! L# B  M7 M! q, Y
            int [] numw=new int
, K( n8 Q: t0 e8 D! k3 x, A; G* X9 ?; C2 [' b5 Y
&shy;&shy;&shy;;& S5 a" t, O8 I6 G( K* k. x8 d
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数, G" |2 O( l; j( [
            {) k: I- s* T+ g
                numw[j - 1] = j;  _5 d, N. b9 W8 U) ^9 g
            }+ {; s5 d% u; S7 a/ |- G+ l8 D
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
! m& B) L  R, Y3 m$ {            while (d != m - 1)) V- k0 z, F% U8 _: ~
            {
( {5 m# h6 R3 M$ H                if (i == m && d != m - 1)
" V$ O: r" X7 d, k- W2 l) c                {. q9 ^4 K- N) Y, R  L) I( F
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!. M: N2 l; _; ]/ v. T+ X+ l& N; [7 {
                    continue;
( |2 n5 Y8 m: }! d+ D5 F% N: x+ W8 e                }5 k9 g7 R8 ~! Y/ x9 d8 D
                else: k8 N7 M% z/ S- `  M
                {
+ C# ?$ f6 p( W: X1 u                    if (numw[i] != 0)
  O& c% G: e- O0 d0 C8 F                    {
4 c: v+ L, u" A! w& M0 h9 ]                        i++;
$ g+ v6 Z; n0 y  V                        k++;1 D7 w7 f. }0 o5 C4 S9 z% F2 ?
                        if (k == n)* a5 [$ U8 @. j7 [3 Y2 F  s
                        {* ~# t/ z: t7 c$ ?# E, T. B9 C
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
3 w. y& M4 ]8 c; U                            k = 0;5 \" V* q8 p' l9 P
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
3 B6 K4 N3 q/ A  O9 i! Z                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
0 V# J( r. u. x; v* r                        }4 ]; G5 O2 z/ Z$ R4 I1 Y/ _
                        else//输出暂时还没有改变数组元素的值# f! e7 w  C) a% h" M  T8 y- ~2 V
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 I' X& @4 z3 X                    }- k  _* x4 F. O. n( m
                    else8 M. e( H3 Q( Z& n8 z5 h* b
                        i++;//数组元素为0,直接跳过,不计数。。。+ @" x. X7 B7 [0 a7 B
                }) G' V! X$ |9 `, p* r1 A8 a" D. C
% I9 b" y" }/ R) f
% V7 s7 E$ E  R  o& b2 i) ]8 V2 W0 b
            }//结束while循环8 P! q" ^1 u& K( K
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
7 a! L( o: s% w, x* u* r/ ]           
5 X) W) C. L* @, i, g) {8 I                if (numw[i] != 0)8 L, B: a- p/ o) W5 _
                    Console.WriteLine(numw[i]);4 n; p" @) M- Y4 W1 r3 B
           
1 c) @: R1 q3 S            Console.ReadLine();2 P, f' P) D* s3 }: L5 Z, K
        }4 D, d% q9 p8 R; Z5 |
    }9 _. f4 W7 P2 z7 U* \" r  m
}1 i( c& k  t% k8 L6 U
小甲鱼最新课程 -> 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-7-5 10:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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