鱼C论坛

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

猴子问题

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

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

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

x
大家好!
" w3 K# B8 Q! _( [' j1 X! L8 G2 {这几天我在忙着编一个问题,我用了一种方法编出来!
$ i) w+ `$ I% z9 X% e+ m+ c但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!4 ^" _7 D. W) t6 k9 w+ x! i
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 W2 x) L. C, X( C9 a
  b2 ?; {9 o* i$ I+ }) [$ i: ?6 v% M1 i" z
                            题目
- e3 m( B! @2 |山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
1 q/ U( f2 g' c2 R第一种方法:利用循环链表1 J6 }, U7 [9 o' k% B6 S9 P- I
#include<stdio.h>* [8 \6 g; L* t8 s+ V0 T
#include<malloc.h>- s+ o1 ]! c* ]; r3 m
#define M 8            //共有8只猴子5 I% ]% s- I# s# e( i/ d" g$ z
#define N 3            //数到3只时退出第三只
1 C# D# j0 ]5 j3 j, `typedef struct monkey9 M; O7 _  @) \7 z6 T# I
{int number;
: N4 F. K$ F" gint flag;) L8 ?; v. f& N7 Q7 q* a
struct monkey* next;! t/ I3 H! F3 N4 q
}MONKEY;* n) g& {2 ~9 d3 m
main()5 i7 E( j/ C. n0 p! s+ ?" G7 B; A
{ MONKEY *head=NULL,*p,*s;
9 C3 r& K' W; Z' H4 s: B  int i,sum=0,count=0;- ^0 S% `8 m$ ~# N9 t  Z/ O
  clrscr();              //清屏! A* H9 i$ t, m
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存+ i/ v! c1 x4 r4 T0 S7 W
  p->number=1;p->flag=1;* Q0 m  Y7 ~/ i0 h$ L
  p->next=head;" d, y& E3 ?" d/ m# t  l) T( x7 ^) ?( Z$ w
  head=p;
, F6 c0 O. C7 r+ Y+ Z$ Z+ G  @) b. B  for(i=2;i<=M;i++)
" H$ L3 d: b- P  q& i    { s=(MONKEY *)malloc(sizeof(MONKEY));0 N' p3 I: u, D2 W
     s->number=i;s->flag=1;
, D. Q% S9 y: b  u! `! |     s->next=head;
4 R; ]* r4 @' {1 _: ?/ h     p->next=s;p=p->next;
! R7 V1 i4 b5 f5 C- I4 w; a    }
3 B+ h3 I5 }# ]    p=head;
  G$ o  W5 R7 d( v2 ]   for(;;)
+ e& a! ^. u: M+ b+ K' L    {if(p->flag==1)
: U% i! g/ l+ m. `0 m       count++;' \) l% j- }% B8 J& O
     if(count==N)* ]7 h/ \) n, g& k' Q' ?
        {p->flag=0;; s, y( A: k2 U' q; G1 l# [  D
         count=0;3 A4 n2 {( f9 B
         sum++;}
9 x  `8 I4 ?# q, ~# v4 }* [' C  L( e     if(sum==M-1)
: C% c# M7 t/ E        break;
& S" n' l8 N* w& ]  K8 N     p=p->next;
% X. j6 j, f6 Q3 `4 `4 Z" z; z    }
) R9 R2 n, t& |    p=
- L" T) }1 c. Q; N    head;
; _5 l( S9 F5 w$ C9 r/ _6 w  A    for(i=1;i<=M;i++)
0 e$ L8 ?- y/ i8 c! I/ W/ L    { if(p->flag==1)) k; R" d( O/ d3 a$ T# G
        printf("\t%d",p->number);( b' B. J, q* L* _3 l
      p=p->next;
0 A) V$ x! `% F, N; I! l    }
+ Q4 V, y! g# d( Z9 k4 S8 o1 c/ p( G" Y
) L0 s% z* H6 R. z4 n, y3 a

/ o: r& M# W3 R/ ~( ^# B}
2 F1 x8 v: x- T3 `) I6 K
第二种方法:数组
  V: M8 X) F+ V6 d$ ^# A#include<stdio.h>
! f" v! t+ D/ @# |* C* W#define M 8
8 D  }( H, R- b7 t) lstruct monkey
# d2 q; H8 N2 e9 Y+ q( ~{int number;
7 F; p' d& d. i' Jint nextp;5 d; m  A0 B# c6 N/ X# Q
}link[M+1];
# f* S! A; h' J, O. e9 j" \8 Q# \8 Z8 X- H* j. C/ K, U7 @
void main(); J7 r1 X1 k+ }/ X
{int i,count,h;
/ w& `$ \6 e, o/ d$ P6 Kfor(i=1;i<=M;i++)
  T. l' T! H9 J& s{  if(i==M)
* S* R/ m/ _8 W* g0 M4 i   link[i].nextp=1;, D' l5 e' T. R
   else3 t$ S/ @& i6 R$ z7 ]) g
   link[i].nextp=i+1;
2 ]; N- d2 i( P  link[i].number=i;& \4 U7 n" I8 g" @+ u1 k
}
- L4 Q7 ]+ D3 c6 e0 aprintf("\n");' P! ^& r3 O+ d, G" q2 W
count=0;# a7 i7 H; F) ~  v5 l# V
h=M;/ C! v# [/ h6 Q
printf("依次退出的猴子: \n");
3 Q) ^9 `$ [/ i4 Awhile(count<M-1)1 r3 A% X5 {$ K- H: p7 b0 e: ^
{i=0;
/ h) Y! j  J' l( N8 g& v# zwhile(i!=3)7 k6 L! u% P7 k+ Q, `. W, t
{ h=link[h].nextp;( m) l" [9 H2 l
   if(link[h].number)
1 \' i2 m" Y9 t) V) J- [/ {     i++;}
( W' t/ p4 c$ b" }5 o
; g% \+ a; [  k7 P% n1 Gprintf("%4d",link[h].number);
, R. t) J1 x& q) b1 [; ~link[h].number=0;" k7 H" T+ x( R) M- l& h
count++;
0 s5 E  H. E$ f3 r6 W& z5 K}
, L9 D" X# x5 _# I2 ?$ p7 l# {+ F; E: g7 w' N  X4 u
printf("\n大王是:");
9 q$ P& C8 t/ _* ~4 ]/ J* @9 a( Q  for(i=1;i<=M;i++)4 |/ \: k8 j, Y7 [& c9 P1 I
  if(link[i].number)* q0 h' t, G! }: n5 a: ?. Y
    printf("%3d\n",link[i].number);
+ d  s/ o2 a3 A1 ~9 i) ]
3 g, m& N$ H. B6 ^. o
6 {$ @. M$ b& F}
/ @: s4 ]. l1 K" E% s  t0 J
第三种是普通方法for循环

- Q) Y9 N1 }; @. k#include<stdio.h>
( r$ e# ^4 @' X0 ovoid main()7 b' I! o) }: _; K& S2 {, y
{ int i,k,m,n,num[50],q,*p;4 b7 ?( J- }+ X
    clrscr();6 H9 @- M. E) Q0 O+ L# E4 |% ^1 P
   printf("input number of person: n=");
: Z" O  t- d& ]9 \- J    scanf("%d",&n);
- W  @- I$ W, E1 ]# y0 b* L, B) pprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只: s$ p( @& h  n# v5 y) p* j6 P
    scanf("%d",&q);, x- a1 L" z' F3 B3 h
   p=num;* N) w% G( y. X$ S
  for(i=0;i<n;i++)" X! O2 H9 K  f( [
    *(p+i)=i+1;& |# R7 d: O1 W: t7 Y: y# z; r
   i=0;
7 T7 P- b* |- ?" N# X   k=0;* W$ y9 o- |* d) G4 G- M2 V
   m=0;1 r3 n( I; M) n. _* K6 y. W
  while(m<n-1)
2 T$ A, J! x. F+ M1 G. x+ r   {if(*(p+i)!=0) k++;
4 c* ^5 l7 K5 E2 Y. O- `     if(k==q)
0 `3 Y1 f% Y9 c7 ~( M( z      { *(p+i)=0;
  p; u6 A* R& g) U4 k/ i        k=0;7 a% |( T4 j  A  }5 e: |6 l
        m++;
; G5 @8 R% l" o/ M" ^% N      }
3 |- R7 @" ^$ {    i++;
" h4 g% {6 `0 {' R! F  U    if(i==n)i=0;* C+ o8 s/ s0 m3 @! Y9 p
   }
/ N3 `" x# {- u8 B  while(*p==0)p++;
2 ]/ ~7 n8 E+ R/ a, e: R    printf("The last one is NO:%d\n",*p);0 o. U; B8 X; ~$ r. b
     getch();7 v) R  b9 {0 P; K: }
( _1 J8 Q) ~) k/ X
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;& ^9 m5 t6 B0 H0 s! v- }3 H
namespace 又费马达又费电
0 C2 J4 W& y, |4 @$ J+ V{
" M2 B* X' ]. _7 f    class Program  q# Z+ E- Y' U7 B
    {
3 k7 }, Q5 p) t8 W( F* C        static void Main(string[] args)
- X& L$ C, S9 |8 w9 f1 K  v        {# x5 `+ c# n# D+ V8 R4 `) y; t
            int m, n;9 L) q2 u" t' z+ H2 f! v
            Console.WriteLine("请输入数组长度");
" r% Z# m( x- ~8 G1 B            m = int.Parse(Console.ReadLine());//m为数组的大小
- t: m  @/ }, Y( A9 d0 W            Console.WriteLine("请输入要截取数字的大小");
- S/ ?+ i6 k5 X0 X) \            n = int.Parse(Console.ReadLine());
$ G' r- h' B- j* t6 K: G            int [] numw=new int
; b7 F4 W" v2 }0 Z+ f2 p
# {0 \2 _( U; X9 f# G3 J&shy;&shy;&shy;;$ M8 Q, k$ U9 _4 I: G7 @) U
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数/ x( V& ^! u! N
            {% R5 V( Z$ |5 d) t
                numw[j - 1] = j;
" X0 X5 X1 X! v( Z            }
& [$ A/ W4 K* C1 r7 I. L0 E0 _            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!4 R) j! k: ~& n$ Q6 P4 g0 m
            while (d != m - 1)9 z" }' F/ J9 f. k% X6 b9 F
            {
! i5 h6 \1 a) v5 j& a- @  f                if (i == m && d != m - 1)
- _* F) n7 G+ U! r1 E  g6 R; a& ?! s                {  v% |1 g+ k' n
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
1 J! U  b" Z- Y* O4 _) C3 n' J9 Y                    continue;
- }1 E, d- ?* @7 t* e6 r4 L                }% |8 F) u# a/ h  R8 X+ R6 ]& l
                else
7 ~9 E- x8 x* e6 l                {" V, q" b$ i- B  R2 W6 S
                    if (numw[i] != 0)- b8 Y* j- O$ o/ L5 C% b+ q
                    {
* e' `. x; h+ z) S9 V: p7 E                        i++;( F6 k' s/ s/ D% X4 c7 r
                        k++;5 n1 ~/ W, N% V! E/ ]9 A
                        if (k == n)+ F! d5 O" I( C5 ~) B
                        {% e1 E( l) y8 H2 f
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& [; I5 {# [$ s  K
                            k = 0;! X" u1 T2 Z3 p9 |9 b, Y9 Q' d
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
. |+ p8 Y! i+ \1 r7 T4 b                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);$ q  o% T* R. P- y2 z. I' i
                        }
( n8 f8 M" c- E! F                        else//输出暂时还没有改变数组元素的值
' K+ k3 T/ n4 m) R2 M# z                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);4 x( Q: I5 K, h- b( K
                    }, r: |4 J) p1 N4 W" l2 L
                    else5 w2 P& D6 ~7 F4 w0 v2 @
                        i++;//数组元素为0,直接跳过,不计数。。。
1 z1 F7 T9 }5 {5 g, N                }+ Q. Z1 Z; W0 V, v: w$ U' w* j
! P5 c6 l2 ]0 `' j2 M

0 O$ O0 ]# W5 Z3 {) F0 ]            }//结束while循环, a; M1 D  L9 C; R; w) `; A
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
! i% i! q- t- T& ?6 O           . q5 }, d* h& ~( c' v' m
                if (numw[i] != 0)) y+ i$ N, f) r
                    Console.WriteLine(numw[i]);6 g' B: ^9 ?/ f# U$ l
           
2 ?3 \) a  n: a1 ^7 O            Console.ReadLine();( T2 J6 w3 I+ Z. B  d( f
        }
6 a% N. U  B& \1 k) |% w3 ^    }
  R; ?- C& w4 Y) Z$ g}
. d3 D# l9 p+ J/ @" s" O
小甲鱼最新课程 -> 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-18 14:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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