鱼C论坛

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

猴子问题

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

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

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

x
大家好!7 O  K( L" J0 U0 u/ w
这几天我在忙着编一个问题,我用了一种方法编出来!3 L1 F- A: F/ A0 J, ^
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!9 N4 n3 y& J0 j: O( O  ?
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
- z; \, i4 S; K7 [5 L4 r+ M9 U' ]- o, O2 Y. M/ W/ `. d: ^
5 A- P, u$ p" J
                            题目$ d" c: S# n1 \% Q5 V" a
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
  R, p; J, v+ k2 ~$ `- O第一种方法:利用循环链表
( |8 j- o* m! R2 U5 e/ t#include<stdio.h>4 L1 \9 @# J/ f- c: t4 [, Z
#include<malloc.h>  s3 l+ k4 |5 L( \
#define M 8            //共有8只猴子
; E: ?/ Q! Y- |8 C1 Y#define N 3            //数到3只时退出第三只6 O& b' x0 R, P/ D
typedef struct monkey0 F' E# R( [# m
{int number;
' z$ ]. ], `" g" k# pint flag;
% r/ x( \4 ~  l) B$ q# wstruct monkey* next;; N! e4 T% H+ t* q# \) M
}MONKEY;! j+ d9 R# x* S' {5 U9 \7 k: n( L
main()+ H2 L6 Y( {9 _% B
{ MONKEY *head=NULL,*p,*s;' `  `  `4 e6 ~% ^
  int i,sum=0,count=0;
2 j0 U2 ^+ j& u  clrscr();              //清屏* Y6 ]2 X5 H+ W* X* M
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
7 C% B) T+ v; G8 Z# Q  p->number=1;p->flag=1;
( X6 S# b; @8 O8 f, ]- w* n  p->next=head;# n3 x4 r3 B6 B- |% i
  head=p;
$ {) ]" K( ~$ Q" V& F  for(i=2;i<=M;i++)
' ~' \+ B3 z4 q& D# d- s    { s=(MONKEY *)malloc(sizeof(MONKEY));
/ |2 k% ^3 e; @: x- y, a" i     s->number=i;s->flag=1;0 ]* |9 p8 _( W1 ^
     s->next=head;0 l1 F6 b: G5 S, s4 i: T$ j
     p->next=s;p=p->next;  g3 v) I: Y- o" i! k8 M
    }7 K  }4 w2 @1 S3 M
    p=head;" q8 Z4 s# y) p8 J4 k& v
   for(;;)
5 g( U5 E! _+ H; c+ q    {if(p->flag==1)
5 D# F- n  A6 x0 K       count++;
, c- F# l; t* c: {% j9 G     if(count==N)- F" y& P. ?9 P7 f8 k
        {p->flag=0;0 o6 H; U, _4 g+ l$ g
         count=0;
# [: }, c! q# d: K' R, t0 l         sum++;}
' V/ s8 ^) d0 y     if(sum==M-1)
6 V. \$ e  `. J# Z, \# n. e        break;2 X6 w. |4 e1 M6 d3 v) b
     p=p->next;
' W* H0 p( \7 o1 n% j    }
3 t' A& |$ m& W    p=
3 @" y. D6 ]6 M" a2 \    head;
- K# a/ |# F* h0 @/ ?8 p    for(i=1;i<=M;i++)# q& V( \( O4 r/ i2 K- E
    { if(p->flag==1)
; E. j) b: f& I* S( B        printf("\t%d",p->number);6 O( M) l% ?( `. D0 M
      p=p->next;
: P& I) A% F+ v- E" e$ Z    }1 x$ B) H0 q2 K" `

' z) W* q% K! X5 G9 R3 k9 A* R9 T7 ^1 q

3 ^$ t/ x5 h" }+ ?6 O4 r$ F: R}

8 w/ }+ {0 m$ ]: J  }+ Y第二种方法:数组
9 s1 K7 R/ K5 P" o% Q8 [#include<stdio.h>0 X# {3 \- S8 X; E" E! h/ E5 |
#define M 8
! {9 o& y& T" e6 S" x( T5 zstruct monkey
, T- B" G- q: E& M" T, q4 H{int number;9 V! G: Y; N0 s
int nextp;
3 r5 ?6 v& P" T}link[M+1];
  r0 Q! e& t9 m$ D
" K  B4 S! O; P9 Kvoid main(). v; D, ~) [8 h2 W! Y" k
{int i,count,h;
# b# }% h0 d/ P8 Y9 @$ m! Y9 nfor(i=1;i<=M;i++)
3 y# C7 z6 o0 u; S) x* |3 L{  if(i==M)* s- \6 e' a% l* v1 M, Z' q
   link[i].nextp=1;6 }& m- B0 `3 k
   else
, }. I' N8 {# d! s/ b   link[i].nextp=i+1;
8 S# J+ r' d4 ^  X/ l7 m  link[i].number=i;4 L6 \1 W5 f! v% y0 |" B4 }
}+ U* w2 k& a' G4 p
printf("\n");
7 a- ]  d3 T9 Z+ h* E9 ~& {count=0;
3 d7 g/ z& e+ W1 _: w* m7 C6 c5 `+ s* wh=M;/ I; X+ @& \- U# m$ d2 D
printf("依次退出的猴子: \n");0 R0 K3 c: @& B/ _# e# i9 K
while(count<M-1)
. a* |5 n9 T' h& V{i=0;
* T2 I) O7 q0 {( h& I! xwhile(i!=3)
; q9 X+ N, k: o* S5 L{ h=link[h].nextp;1 p7 M5 K8 @! r; Y/ _  k: ~0 R
   if(link[h].number)0 ?* m' W& x+ N; [
     i++;}) L! X( S! j& Q. O) P

; A. c! Z3 S$ `" E0 Hprintf("%4d",link[h].number);
1 Y2 b: h9 y% q# c& @4 p9 N; Slink[h].number=0;# \* P0 }0 T' p0 J* M9 f
count++;# ^( B1 l! q# B1 @: w7 h
}
: n9 v: b% m8 [: M; p0 w" |% A6 |/ p$ ]
printf("\n大王是:");, I6 `8 H  J6 |% o3 \6 m# I
  for(i=1;i<=M;i++)
4 M" w! n1 e) Q! I  if(link[i].number)4 {) ~, l/ E3 I( Z" l+ V
    printf("%3d\n",link[i].number);" l  z- `. m  Y, I) u+ }

) K/ s$ P6 u: V2 z  f0 ?5 V
2 b% s9 A& c. D; Q$ y}

& x# m) U  ], U- N0 a7 M第三种是普通方法for循环
1 p, M3 L$ ^+ U% {
#include<stdio.h>
" r. _3 Q7 R' a8 ]* {! _, Xvoid main()
$ U5 B# m% T4 i{ int i,k,m,n,num[50],q,*p;( ]' v0 @5 G2 W/ u3 A) {9 r5 P  Q
    clrscr();/ }! |: E6 h% K0 r
   printf("input number of person: n=");* Q/ O7 S' U0 E& E$ x) u) e% i/ F
    scanf("%d",&n);2 K% k. T) p3 H% ~& o
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只, m0 o) a- E, o+ X: v- W3 @
    scanf("%d",&q);
+ Y" T' z& P1 z5 l   p=num;
8 u; a/ j! E* D3 L  for(i=0;i<n;i++)2 b- _; G6 q& e; L
    *(p+i)=i+1;
8 p1 {3 E6 O5 |& ~8 \, M1 R   i=0;8 [% P9 r6 d5 u& @% ~
   k=0;
( V3 M6 U( ]" G   m=0;, n: b" M0 V7 l, h, K/ ^
  while(m<n-1)
, H4 e7 a4 {) \* Z9 l& `   {if(*(p+i)!=0) k++;
; U* c; |$ X# O# m% c# n- g* s     if(k==q)( P: ^; W4 M2 R
      { *(p+i)=0;
7 r* P0 \; e1 y# v8 U: _        k=0;" W' P1 [3 H& s; }
        m++;( @- V6 ~- q. E/ Z* F
      }2 I: v% Z% g9 D1 l
    i++;( i# Z& q1 N, \4 }- l' o
    if(i==n)i=0;
5 I7 i# n& V( g2 L/ p& Y' r& t   }: S( v3 I" _/ ~3 H2 N
  while(*p==0)p++;* G" Z2 Z" v8 o1 B
    printf("The last one is NO:%d\n",*p);
2 b4 f2 w5 [% b' y" _     getch();
( J2 t3 N. l. D2 s. F: m5 r. ]4 w' Q
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
! c& r7 i" ^$ Z# L) g- @& tnamespace 又费马达又费电
4 j6 _7 m3 B. Q2 N( g. e; S7 ^{! U" H; ]8 K4 J8 Q, j8 b. E
    class Program
0 R$ P- ]% `$ Y- Z    {( k: [; k/ b+ V
        static void Main(string[] args)
$ P5 \* T: G7 Q5 }5 s1 j        {
' E9 U1 J# [) M( o% w! N            int m, n;
" s# P8 F! _2 |7 l# {            Console.WriteLine("请输入数组长度");; v2 I$ D2 h, y7 ~0 a
            m = int.Parse(Console.ReadLine());//m为数组的大小
9 Y) @  R$ j. f* O" p- f+ r            Console.WriteLine("请输入要截取数字的大小");
7 B% n7 N, C$ j3 [" V            n = int.Parse(Console.ReadLine());
, m" j7 [3 S0 [' J( ]- n            int [] numw=new int
6 k& O" E3 N. x9 D% Y' t; [/ ~; s  i* E1 ]' F+ k0 ]2 ]" U$ Y4 c0 t
&shy;&shy;&shy;;
5 r, q2 [$ `4 [6 R4 L            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数% f& L* t9 {) U, x9 J6 n" `! n
            {0 I4 @- ]) p' b1 ~
                numw[j - 1] = j;
, Z% H5 h: o" y+ B$ K            }) V" n- R* ~  p* x9 a( |0 O
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!+ Q' T* c" u  O4 U* K( d9 h
            while (d != m - 1)
2 w0 O2 a8 o' a4 l& C: L            {' p& i0 w8 a  }: V2 @' g' k
                if (i == m && d != m - 1)
- @! x$ m2 s7 s, ]8 l                {, `/ M) ]; o6 O6 M! \4 z, l; S
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!# m5 P( v9 v- _& _0 P& g+ S& U
                    continue;1 g; l- `& o7 V' i6 O2 i
                }; [  x6 X; J* J. m
                else
3 v; m2 P  ^& `% v                {
3 }1 ]$ }, Q7 D8 J2 w; J) t4 o                    if (numw[i] != 0)
8 T8 b- N1 J# V3 r, ?: t. Q                    {
9 W3 Z, Q8 D& b% u& v2 P" [                        i++;
5 Y6 Z* o5 c& Y+ N0 U; b- Q                        k++;
* t" K% v+ Z) p0 Y# d8 N                        if (k == n)' n( c( S/ c" n' F
                        {
8 _: \0 c# J  E7 U$ q                            numw[i - 1] = 0;//把在n位置数组元素的值改变了6 ^! `9 ]5 y& E. S
                            k = 0;
/ ?3 d6 W3 I: t. g9 c" V8 U- V              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1, c' U9 \1 B: ]+ N* a1 p
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
2 i% _. N* _1 T5 M, `) n                        }! n+ h9 k6 q% m, [% ^1 A7 e2 q. O
                        else//输出暂时还没有改变数组元素的值
* |3 z# B- X, K3 m& J. i9 M                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
7 z( n, |/ H( U6 k6 t1 n* r                    }
) D3 o0 s! A1 I, J& D                    else$ J& Y# G; Y1 f; s) F
                        i++;//数组元素为0,直接跳过,不计数。。。. j  Q4 h0 J* u; i7 J( b. ~# f3 f
                }. m  M8 M' z3 I- z0 t  _: \' \
: c  Y4 Z7 z: l1 Z  O
$ z7 S. a% V7 ^9 b, _
            }//结束while循环0 Z% Q6 v1 {2 G: B: i
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
3 r+ U; _% z# p+ M: m' \3 e% M           
. G' F% r6 ^& r: S9 i! M                if (numw[i] != 0)8 e+ e) R# q4 J6 q- T% Z
                    Console.WriteLine(numw[i]);, I3 C  q3 z" V  o9 M
           
4 z9 J' S  J% A2 ~            Console.ReadLine();& G7 v) n8 @- Z1 r
        }
8 I' z$ N6 U( w2 {, I4 P    }" M+ A( b& `$ s; j9 g$ q
}5 E- {4 l2 G# B1 |$ D  J
小甲鱼最新课程 -> 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-6-3 11:20

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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