鱼C论坛

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

猴子问题

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

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

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

x
大家好!4 `3 E. k& T1 v+ R9 N6 I$ f* K
这几天我在忙着编一个问题,我用了一种方法编出来!
( |3 h6 k+ @' z4 l: E% z8 ]但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
5 v# Y. }" ]) d+ F" p. H注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 : J5 A8 u( X6 ^6 {% Z# P( e
+ y8 b( o: `0 G( Z. k' y

7 |* K! i: \* ]& E: t7 f
                            题目
) c+ a, k) n4 A8 ^/ H: y5 Q山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
1 I, u  F- B! X$ L6 X1 H% G第一种方法:利用循环链表6 z2 a2 ^9 F. B6 Q5 E
#include<stdio.h>) U& ~+ \( c: r- r5 f$ P. W, X
#include<malloc.h>2 S$ t9 }. |( {+ g
#define M 8            //共有8只猴子
9 S  E' w' k0 C3 x- `; Y: T#define N 3            //数到3只时退出第三只
7 p9 V) H/ C1 D  r( L: `typedef struct monkey# v4 M" s% j5 K1 p. w0 I6 M  o! \' r- p
{int number;) [- H3 _- ?8 j+ a" U, A
int flag;& h6 h5 |/ e: B6 b. W4 L; \
struct monkey* next;6 m9 V& g4 j5 L, |+ N
}MONKEY;6 m+ q' H9 j# w2 g
main()* Z- i* V+ t# p% ~3 C
{ MONKEY *head=NULL,*p,*s;
9 e8 g- d8 g/ ^7 x  int i,sum=0,count=0;
% Q: G, Y" T. Z, P  clrscr();              //清屏
: W  ]% i- m* f6 g8 t$ L; F  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
8 W8 v. ^2 Z+ c, Z0 v" X  N  p->number=1;p->flag=1;
* j) U$ h% Y! i4 F  p->next=head;! ]' S, s4 n$ w2 T! v1 L
  head=p;% ?3 L9 H- ?8 S+ S3 C: D1 w" P
  for(i=2;i<=M;i++)% j4 V9 r5 k$ r" G
    { s=(MONKEY *)malloc(sizeof(MONKEY));1 U! ~: b, i) ]8 B/ a8 C
     s->number=i;s->flag=1;( _0 y% c2 C  z- E1 _3 w
     s->next=head;( b9 V5 y6 P+ i$ p, b) w2 \
     p->next=s;p=p->next;
& x* @+ a1 @5 c    }, A; T2 \8 {- u/ t% ^0 R1 j
    p=head;  y% I+ s2 d. t9 Y) h% C
   for(;;)# A! b# n. d& ?/ i! f' d
    {if(p->flag==1); K0 ?) g5 n. @& U% F
       count++;
/ d; R0 ~0 G4 J  ?: d     if(count==N)! B3 v& N7 e4 U! y4 ]
        {p->flag=0;# ^6 {6 B; @; A' {! d. @8 x
         count=0;* A% @3 H% G2 y* e& H
         sum++;}9 v: Q, Y4 n+ A  G# L& m
     if(sum==M-1)
6 c6 M2 E+ T) I. S7 j) [        break;& b, B1 \' q4 K4 ?7 E' a
     p=p->next;8 h# s: c- s3 j6 o
    }  R  F! r* ?: z+ A) ]: J7 s
    p=  f* c" _: Z: R6 {) E* [1 g
    head;
) A  x7 l5 {9 H( u  H8 C  t    for(i=1;i<=M;i++)$ v: e/ T0 y1 U! J# e7 t- `
    { if(p->flag==1)& L% U: q1 C0 ]) ]
        printf("\t%d",p->number);- W* Y. p. Z  k) C( x; \
      p=p->next;
, h3 u0 R9 a6 r) P3 U    }4 M/ l: a; L5 _# i3 i$ F
2 V" v: m+ m6 C7 G
( d; d7 E! ?  U5 R+ W9 p
/ s/ s! a3 X5 }7 [
}
% b; ]) M9 m% g  b. ^6 p3 h
第二种方法:数组$ H; L% w9 }- ?8 W8 P' F: E6 Y% ^3 B, ~
#include<stdio.h>
" M8 d; I% F( [# E2 @- D$ T#define M 87 K. X4 z5 j" J: u9 Q
struct monkey
) ?, q& q! N; A{int number;7 v8 N3 \" S& {; G  [- G
int nextp;
5 v: H- N9 S; h) {& I}link[M+1];6 Q4 {3 p: J, h. |1 m
8 I' \+ k; ]" ~2 f9 t3 H1 r
void main()
' [1 P: L0 u% M{int i,count,h;
$ t$ F- N: G6 w& _0 b/ B. N! Rfor(i=1;i<=M;i++)
. T7 Y8 ?, Z' j) W* Y. e- i{  if(i==M)3 I% B* S$ K$ t4 K
   link[i].nextp=1;
+ X) p' w1 f' t+ U4 a; w   else
, x9 K/ a$ Z& T$ K5 a: w   link[i].nextp=i+1;
1 z# i# I5 Q1 @* Z9 d  link[i].number=i;7 v* r1 z4 U' B( Y
}
3 f( q: a' T, p# ]4 X7 Q( |printf("\n");
- x3 }% _2 M( N1 a4 Ccount=0;4 Q5 f% c% c* R7 h) n
h=M;& W4 b% r, _5 n6 U+ ?. z
printf("依次退出的猴子: \n");
# E: B7 y( ^4 |' `( l4 Nwhile(count<M-1)
* D" N# [6 F/ F# i{i=0;
3 l' P; [" e5 rwhile(i!=3)' [+ G! X* B: S* L$ N
{ h=link[h].nextp;
' V% d! ^. p6 x% Q- {7 @" r* l   if(link[h].number)
  W( p9 \2 D8 ]4 O" P+ |9 U     i++;}
  a( ]) L2 V. ^4 t
% w8 \! x% e- i2 T* {: E' p  a) w( ~printf("%4d",link[h].number);
  d  Z' B3 }! I/ j$ s9 blink[h].number=0;
. x5 E) Y6 w& M# Icount++;( v" ^- W0 g# y: T# `. F% v
}: |# B3 M$ O1 O3 R& D5 {
. C! N# h" O# k  s. e3 K$ V
printf("\n大王是:");' x8 [! f7 L2 c# f4 s
  for(i=1;i<=M;i++)
7 X; {, ]5 |) \3 u* l+ @* A( B+ o  if(link[i].number)
. d) N  w; [8 R; V4 c& z    printf("%3d\n",link[i].number);
$ r) g( n" F* y6 h- r- `" l) w2 `! _7 ?% K' P4 B! u" H( t

" L. E* c' D% L8 I" C8 t" ]7 e) Z}

6 ]6 B( K: x" o. {# a第三种是普通方法for循环

7 ]9 ?- Q2 D4 _8 Z#include<stdio.h>; g' G9 F' U7 L
void main()
3 v. w% Z8 Q) Z- J{ int i,k,m,n,num[50],q,*p;; u: m" L; d" ]1 c2 @) O" B8 I3 h, m( j
    clrscr();
2 s8 T3 y  o% ~( M   printf("input number of person: n=");' A0 X6 ?- J. \
    scanf("%d",&n);9 `/ v5 r. \/ O3 `# w2 h
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只5 e, R1 g) w' z: @0 ^# s" T
    scanf("%d",&q);
9 J  s0 _. ^( s9 k   p=num;% e, \; N1 G' B) B- l
  for(i=0;i<n;i++)
3 m7 p, U- r% }4 C% f    *(p+i)=i+1;
6 C3 K4 |" U* n' {   i=0;, D/ e) G* U0 J0 ^( T
   k=0;9 Q/ r3 x& a/ y
   m=0;
- ]9 \* a6 u5 ~; R' e% f  while(m<n-1)9 C: L4 t4 p; I8 }7 |" @
   {if(*(p+i)!=0) k++;
+ I7 o& W0 G+ Z7 m; m9 w: u     if(k==q)
/ V% ^8 y# j, n      { *(p+i)=0;
$ o7 e( E2 |8 u3 B' y        k=0;; U: n: M" c: y2 ^7 y
        m++;  O3 j& Y% j) ?1 v! Y
      }# k( u, t/ |6 K% R* e& b
    i++;; Q6 a6 f" h: G, E+ g, ?  e
    if(i==n)i=0;
2 ?4 y! w  u9 U   }
) x& Y0 b9 }! s  while(*p==0)p++;
5 j8 ]% }, Q. y: _% M) s: i. y& L    printf("The last one is NO:%d\n",*p);' I, G# B$ ]3 a( r: x, h
     getch();0 P$ R  J) K1 n' N  Z  C( Y) L& n
8 N$ ]& }) F. r, c" M
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
; G% x' r: a& @6 e: L2 c/ ]. E8 w& Inamespace 又费马达又费电7 C" [- e! Q% x1 P9 q
{
$ T1 u# ^8 _2 X6 r3 [% q2 h    class Program
2 N' e# a7 K1 {) P3 m    {, g! G5 Q: K3 H) x/ G) S
        static void Main(string[] args)+ Q$ C( ^( N& H# l: b
        {
. C; ~" b" T; |+ j& Z; I            int m, n;
- ^1 O; f4 y6 }) h. {) N( J            Console.WriteLine("请输入数组长度");% B! v4 |  B. H8 b# \0 h
            m = int.Parse(Console.ReadLine());//m为数组的大小
$ {  T6 b6 n; i% O* l& f1 c            Console.WriteLine("请输入要截取数字的大小");$ `0 \6 B) C. @
            n = int.Parse(Console.ReadLine());( o  {- S  z& {9 f3 l5 |- s
            int [] numw=new int  H1 `9 Z0 L- D7 S/ H6 r0 I
( J7 }' E; d  K5 |( U5 F
&shy;&shy;&shy;;
3 j1 @6 g- J/ m# m- ]3 f+ W# O            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
3 e5 M* M, \; U( e            {2 `  z$ S) ?2 h$ ]: R4 W9 w, B9 Q
                numw[j - 1] = j;
0 D9 }- \: {4 o7 ]1 a. C: e            }- r6 L9 \  B+ W( ^" e* q. Q/ F( Q
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!5 k2 {# g6 O' p& m' E* |/ u
            while (d != m - 1): w+ d  B6 x: p% X  _
            {
% W7 H! v, ~0 L6 d5 Y                if (i == m && d != m - 1)
# t& C1 ^+ C  O- O$ w                {
1 g( B8 M0 L! ?3 ^: j                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
* w& k5 V6 Y9 e4 J! x                    continue;
  j, ~: i, f6 ?0 J                }
3 U0 b7 b  k# R+ x: q1 C( W1 k                else7 F+ D) z8 C. s: H! f3 l% x
                {
! O$ w3 U# y" k2 t: I                    if (numw[i] != 0). M' h! O, E1 W, a  T: t1 d
                    {
" h) f- b4 E- m( v6 i                        i++;, O$ K5 ^* |7 `# ]$ \' @
                        k++;$ S8 i% k! t1 u
                        if (k == n)
5 @8 V" ?* x  T7 w6 q. O% F  y                        {3 d6 C  [& ]* h  r2 S1 k
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了5 n3 v( b2 i& _) @" \
                            k = 0;) @- ]9 P% y; H- e  j6 k6 |
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小11 A4 V& M( [/ A4 W1 Z
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
: k; h, o, @! q$ w: Z7 }1 J                        }, r5 K: V8 F( Y! b% a; ?9 W
                        else//输出暂时还没有改变数组元素的值2 `8 r( I8 f$ M( p* W4 K, n
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
( ]. z2 `8 G+ R                    }. ?5 r( A/ p0 V( ]0 H+ \
                    else: z7 a. [! J0 ~4 M% M6 F: L
                        i++;//数组元素为0,直接跳过,不计数。。。) \, O- P+ {! ?0 E/ K% K
                }
6 \; F6 b! a! {% G" A% n
/ }! A$ l$ ?% z3 ], Z+ g9 r4 V8 u6 w0 p0 }
            }//结束while循环
: F9 x9 B# H6 v: u$ m% N            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
4 b) S3 Q' w" I# V+ E& {/ o% j           ) f2 U2 u! U6 j& R4 R
                if (numw[i] != 0)% W0 P& J& s% ]; p6 ?
                    Console.WriteLine(numw[i]);
) q5 U3 O$ V: g2 s5 t           ! P0 Q4 U; Y- S$ ]5 y0 n6 k
            Console.ReadLine();
* _: n2 Q/ f. C+ N" M  {1 @        }! T2 ^* f4 U& b( m
    }# j& c. G& E- y8 G4 Z% M
}
% ~) u5 T$ [7 L- m* D$ T
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-2-19 06:53

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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