鱼C论坛

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

猴子问题

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

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

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

x
大家好!
( R5 `6 E3 ]  i# v' ^. \这几天我在忙着编一个问题,我用了一种方法编出来!
: C  E  Y2 T7 G) H' e但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!; X. T% z* O, A2 E: a1 P
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
5 v  K& W4 n& g  N, _' `0 G2 _- h5 x, L; l

' {: D7 D* i  x, d( K4 w# w
                            题目
9 i& `1 b& J1 [) W- J# Z山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。8 N2 X$ Z  A; U" g/ k
第一种方法:利用循环链表! @7 b/ C$ z) L0 ~% U4 ?, H
#include<stdio.h>/ E0 V# f8 z! {& x( u
#include<malloc.h>
" ^: H- y8 d/ R# J* @5 E# L#define M 8            //共有8只猴子) |9 P7 ^0 B  S: R- q; ]0 v+ T
#define N 3            //数到3只时退出第三只( i7 e5 G* }' p: {2 S) x: T3 k6 |
typedef struct monkey9 L' H8 U. I% Y$ H1 K! ~
{int number;
1 G& @1 u; T3 kint flag;5 w4 A3 h: a6 V( m3 q& i/ x
struct monkey* next;
1 R% ~  X; A# w}MONKEY;
! _8 T( ^" D- d1 u/ z& Smain()
+ c" d$ O% W) k{ MONKEY *head=NULL,*p,*s;8 C+ N' N" m( c
  int i,sum=0,count=0;
/ R4 C" Z! ~3 I  clrscr();              //清屏
" R' [7 A8 }+ [  y; E5 r  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存1 @, ~  j$ F1 G5 t+ j3 p& e2 s8 O* W& U
  p->number=1;p->flag=1;" q! D$ n, M, V) c6 e2 j
  p->next=head;
5 j  v# G5 B5 A* f7 X; d  head=p;& i  S' j  c5 l
  for(i=2;i<=M;i++), ~% j, R3 H1 B6 y, A2 e
    { s=(MONKEY *)malloc(sizeof(MONKEY));
% S. e8 F' y' a     s->number=i;s->flag=1;
" X; I, L) j( f1 S) R3 _; w     s->next=head;  p" j( H5 W# O6 C8 j, S  H' M- S  n
     p->next=s;p=p->next;
: E7 M5 |6 p* V    }
( p: I- c) Y6 N    p=head;, W# m' o7 I% _
   for(;;)
  {( P1 x0 n* l6 J& l    {if(p->flag==1)6 }4 b* W6 U. C- E0 X5 X$ ~* K
       count++;1 p9 r- e1 J3 G+ A% Q
     if(count==N)
  u9 ?' Y  \* A4 S8 C        {p->flag=0;8 i! l: V: _$ e! v/ r  ~  P2 o
         count=0;/ x: Z; r% u2 ]) t
         sum++;}
: c3 L, u+ `: _     if(sum==M-1)" G/ E( y2 z$ H7 _" x. A
        break;
4 ~' T9 @7 O: u$ A- k8 u) n     p=p->next;2 T4 |  M: _- w+ |* ]0 \; o
    }# k* z+ O' p; R9 ?' i; V9 e! S! {
    p=' o/ J+ _2 i/ v8 W
    head;& d0 n" I  U; I* _# u
    for(i=1;i<=M;i++)
6 A' W4 t( F6 m% j( o9 C$ X    { if(p->flag==1)
9 w) L# `. N% b8 j        printf("\t%d",p->number);
$ r9 X+ k% Q1 Z2 n3 ~8 T0 e      p=p->next;) e9 q2 S% w! G/ J$ g8 b
    }
- \& g6 J. w: S  @) e9 b1 ~! H% n! d( K& D' Y

/ `* p0 j6 b( B' t: q
( F1 m8 T. H" r( k1 ^7 j}
/ z& R) w$ x7 B8 X
第二种方法:数组$ a! `. u; e0 P4 F. z3 g% ^& f
#include<stdio.h>
& _2 X0 _+ T( h6 ~# C#define M 86 I3 j; _, f( D# H1 \/ B
struct monkey
$ }! m2 [" }* L% `{int number;
5 w' ?* P& J# H6 D/ ~4 k+ Iint nextp;
8 f- s- P2 E" C% t( l% s% O1 O}link[M+1];
7 i: ?/ N8 h$ e9 _! G2 ~$ f. \
9 I% w- U, |/ }# X6 W  rvoid main()
7 a( V2 j2 J" Z$ e1 E{int i,count,h;: p2 e$ r& c' w, l! y5 i
for(i=1;i<=M;i++)( A0 F6 ]9 r- [% e
{  if(i==M)
) M# O2 v/ `; \% n% E5 y   link[i].nextp=1;. _0 ?! j, K4 r
   else) e3 u; o3 n" R2 z
   link[i].nextp=i+1;
$ K, K) w1 i0 }  link[i].number=i;* S/ v& @$ i7 Y2 ?: v4 g. ?
}
' x4 }% s0 _, ^: v3 [printf("\n");5 m2 U: K7 w9 m1 z
count=0;
5 _0 ]' Y4 x5 v8 s$ B/ o6 O, N, Wh=M;
2 T, K: I: f# ^4 U) r% Yprintf("依次退出的猴子: \n");
, u6 s; J2 i$ u7 m. pwhile(count<M-1)
( s3 D. |# ]4 e- _0 N' _5 K{i=0;4 D9 L8 A% E3 J& Y, O! b7 ~$ K$ \: H
while(i!=3)
+ C3 Z" l( M. x7 i! Y# m{ h=link[h].nextp;
0 A* w9 A7 ^( X# T6 L  t2 |8 ]   if(link[h].number)( |; y2 C8 j( |. f4 Z
     i++;}
, [) m  h. o& K, Z: s/ M6 m$ W* e& o0 ^+ q4 [- J' K
printf("%4d",link[h].number);4 h7 B, U4 Z# `* o9 Z/ {
link[h].number=0;0 _" G  r7 O% F: J
count++;( ?' U3 D9 F" S; l& q
}( d5 s& }# g3 M; b2 o

! k2 D; q' k: g8 s5 Iprintf("\n大王是:");" I* J3 Y) o* l9 O0 V- m' p3 d
  for(i=1;i<=M;i++)
. s) X  \; e2 _3 ]  if(link[i].number)
* `9 R% \' O/ @+ B* f& W    printf("%3d\n",link[i].number);% R/ e6 O1 ]* o8 G

4 r( u8 }' y; N# @
" Z) X- [7 P, ^% ~) r}
2 Y, j2 X1 C3 G( M3 n& ~  {
第三种是普通方法for循环

( c; M. r6 V6 X! N#include<stdio.h>1 ]" T, f! `% a4 b
void main()" P; z$ c1 l! f
{ int i,k,m,n,num[50],q,*p;4 {6 g3 O9 u( S% C  ^0 ?
    clrscr();
8 ^- @2 G+ U, S  Z   printf("input number of person: n=");
; L0 K0 ~" u+ Q5 F  N% v    scanf("%d",&n);
' K4 E3 ]; i- {printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只& U, B3 Z) z- z! L% J: A
    scanf("%d",&q);
$ S( B- W+ z( T' x- m3 Y) t   p=num;1 p; N% M; q- i0 z
  for(i=0;i<n;i++)* J4 g6 }6 w- a& V8 I9 L5 g9 ^
    *(p+i)=i+1;
7 P" Q7 ]# [& p  X9 f   i=0;! a1 n4 U% S2 x+ G5 M" k8 h
   k=0;
4 o& o- E/ K- r  \3 F  J   m=0;0 I. e+ ~+ T9 Y4 j. I8 I: ~
  while(m<n-1)
( k# c2 ~, b" v   {if(*(p+i)!=0) k++;0 }) Q+ R, s8 [' C' e
     if(k==q)7 f8 `5 D& Q+ Y. O% m" h
      { *(p+i)=0;% }3 Z  F6 h  e2 M) x9 `7 q
        k=0;6 l! W8 M) I; l2 s8 l
        m++;
- c; w9 _/ p4 ?8 j: [      }
' S. Q1 R# q2 q, J4 g! @# W    i++;
& v- |0 F7 w6 s" v" S- P2 v    if(i==n)i=0;
/ ]4 ]4 V* A- t: x) a- j- O   }4 u4 ^1 p- p4 c' T% `( Q: O$ ^
  while(*p==0)p++;
$ _2 f1 d; c9 q6 w# C    printf("The last one is NO:%d\n",*p);
+ {. \8 q) B9 n! ?3 P5 @$ r     getch();( Y: P- W, u! c+ y9 J

' M/ F' R# N+ |9 `8 j1 }}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;1 F5 }9 k2 w. P% {2 x
namespace 又费马达又费电5 B& N0 n, n* c9 x( h
{
: M7 S  z( }) k' i    class Program
2 s: A' C- M1 H    {7 I* v; `+ D$ w  {9 F5 t( P+ F
        static void Main(string[] args)
7 t+ A) ~! |5 V0 x3 k) P' H        {) T% T+ ~! x4 v3 o% m
            int m, n;7 [0 r. T* Y, x; B
            Console.WriteLine("请输入数组长度");
. B1 \, q" o" N. w; t            m = int.Parse(Console.ReadLine());//m为数组的大小. A6 {# B$ K6 D, O1 F8 {
            Console.WriteLine("请输入要截取数字的大小");
8 l% w8 o  [4 y8 h- e) n/ r            n = int.Parse(Console.ReadLine());
! P; G9 t! T; f* X9 Z8 F+ p            int [] numw=new int( ~; P1 u9 y* D

6 N( S  g& @' _- F7 y- `&shy;&shy;&shy;;: X: N' @: q$ B% x
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数3 H3 C9 z" w( Y2 C9 u! q
            {
! o2 u& t7 K3 z2 n                numw[j - 1] = j;
2 ~: `  |9 j9 }8 |  c' ~            }. J! h3 t$ M$ e, W0 @9 B7 `
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
2 c7 E: y  h' s& R! \  }            while (d != m - 1)8 Q$ Z3 v; }: T8 j0 w& g
            {
/ K8 Y# a# f( j  b  ?                if (i == m && d != m - 1)
$ ?) G& }3 f$ ~- @+ l                {1 i- F' g. L, i$ n
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
% Z: y* a% Z: e* C0 T9 [                    continue;
" X7 z$ O3 }8 m( V$ [1 O3 K                }, V5 Z+ x* T2 N6 L% v  [4 F
                else
0 c. R$ k2 F; }1 h  `1 d                {7 R/ u4 T% m$ B1 I
                    if (numw[i] != 0)
' W+ a8 L2 K2 s1 `" m5 F: S  V                    {
: d/ ~2 ?5 x- Y                        i++;
: R: _6 N& _* D+ O5 f1 u( C                        k++;
. ]3 l9 e1 x6 A                        if (k == n)
, P/ A7 `3 J& @1 P3 q1 B5 x                        {- f/ v( ~  [- i- X9 g; q0 ?
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
' R( l7 x! H8 i& z7 Q" w5 L                            k = 0;! \: S! Y; R7 R% ]3 P' U& u
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1! m  m8 O. e2 f7 D( e: k
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);/ s" h* J- l8 `3 x
                        }, v+ _' g' J! U2 r
                        else//输出暂时还没有改变数组元素的值" U4 h  c. n& b* u5 Y, }/ `
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);; |* j. ]/ t( ~0 C" s# t+ U
                    }
' f; e: S/ ?* ~' C( o. m                    else: ]9 E' |8 y) S; x# B! \% Z
                        i++;//数组元素为0,直接跳过,不计数。。。
5 a. k7 m9 s; @$ P0 d                }  m  x) y8 d% I/ ~1 X1 F+ ^0 m

/ o, ~5 r+ ~5 y+ }* q4 x: E
" x  ~0 T/ K( T4 j- ?. h$ C0 T            }//结束while循环
( y  v; @  ]7 y) X* \/ U            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
8 J% `, r% [# N% W8 b& K7 u, {) \           , h/ d" g5 s- ^; {
                if (numw[i] != 0)
" G9 R+ x7 f; h$ y. M                    Console.WriteLine(numw[i]);
, ~) J  x( l" f           , X& W5 |' E. Q* m. j/ [
            Console.ReadLine();0 V4 c1 N+ x" v
        }
9 W# @& U  F0 I# V' C; Z) G% O    }
, M8 K5 z: K. Y" R0 P: I) i}
; ~+ z' b( k, G" s& Q4 G
小甲鱼最新课程 -> 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-10 05:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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