鱼C论坛

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

猴子问题

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

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

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

x
大家好!  Z1 E6 u- Y$ P/ Y+ c. [2 G
这几天我在忙着编一个问题,我用了一种方法编出来!+ G* M4 A7 Q# S* U: t
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!4 q0 c9 l3 `+ F7 e3 \- O7 ~' ]
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
  t$ R- s- {( q4 X; q1 S" i8 w8 F

4 |8 N# s- h6 ^, F4 c9 u
                            题目4 {$ t# g: q2 l
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。. g  R% ~. J- O' |" C
第一种方法:利用循环链表: x$ R, @; r/ L5 e3 t
#include<stdio.h>
5 j  B- \- {. }$ N8 |4 a# o( U' _#include<malloc.h>6 X. e. L( o% h$ p' a6 N
#define M 8            //共有8只猴子. M& e: g4 |# e1 Q  O, F
#define N 3            //数到3只时退出第三只
' q# f, s; U/ N+ l8 G# V# a4 Ntypedef struct monkey$ C5 F. v$ b2 i* H9 F5 l
{int number;5 W2 d0 @+ H' W9 }6 ?
int flag;
8 R6 ?( [5 _: z* \/ nstruct monkey* next;
- ?- M$ {* _+ r+ ^+ l1 v' h}MONKEY;: j1 T9 ], M1 r
main()# [! H: U% z8 {$ h. @
{ MONKEY *head=NULL,*p,*s;) j& K) y1 H8 W+ I- J) l
  int i,sum=0,count=0;
! i, X) W3 e% x- `) p  clrscr();              //清屏
4 s! Y# K1 x& c2 c! N  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存- k' K* B2 Y3 ?0 A9 Y/ X" d* _
  p->number=1;p->flag=1;+ _! Z8 P8 h0 _' g- e+ {
  p->next=head;* x' f/ l: o# Z6 s8 ~: d; i& g
  head=p;
2 w' q' t  {) \0 _1 B9 Q. I  for(i=2;i<=M;i++)
  H& S2 K* c/ i+ q2 u+ X    { s=(MONKEY *)malloc(sizeof(MONKEY));0 k9 B2 h( \( I
     s->number=i;s->flag=1;+ F# e, Q; l! R3 @
     s->next=head;
6 b) P' ]8 I& s9 s1 h/ `' `3 R     p->next=s;p=p->next;- L! R% I' i) Z( C2 s
    }
; {8 l& ?1 v9 Z/ `( z* u8 c5 e) I    p=head;
+ m5 k0 R8 ]( Y8 O" W6 y   for(;;)
' c* g7 C8 Z8 j    {if(p->flag==1)
0 v+ P: {4 C) l- d/ u       count++;
4 g: P/ R% c7 Y/ V9 o     if(count==N)' n$ n( N8 M+ o. i" _1 C- z% I
        {p->flag=0;$ _0 \6 k: C2 g. A/ ^4 H* M
         count=0;! w2 }& b; P7 A4 M% ~  q+ @
         sum++;}5 f1 }5 H7 L4 T
     if(sum==M-1)! Z4 T+ m! B$ u' i
        break;7 `" ^2 d8 a; l% i6 k  ?
     p=p->next;
& M$ P" r0 `7 b1 r1 g1 z. R" @    }  G) A, m" D9 g0 ?! R
    p=3 Q" ~5 j5 P; g
    head;- x0 V- z2 _0 \/ O
    for(i=1;i<=M;i++)1 i+ H2 T7 @) |
    { if(p->flag==1)
! |/ W) e7 F2 g+ \6 W        printf("\t%d",p->number);
& i% ~. F; M& X% ]: w% O! z      p=p->next;+ Q0 K: K$ l" U0 x7 g. m% X" }2 x; U. q0 k1 O
    }
/ q2 H) G. J: s# H9 W
# ?. _9 X0 k( ~; w. V  i5 t' M( Y: h) t' E7 v5 v) r- }- f/ Q

8 |% u, H( u, E9 c' ]}

+ D& |( r# `( M; d. w; t第二种方法:数组
, k" |  b6 r1 Z( a/ }#include<stdio.h>) g: p4 |( d  b, h7 R
#define M 8
6 r2 {6 R& Y. [struct monkey
, Z2 C  F- F. w1 s1 P" T; |{int number;; u9 ^, y5 @  i2 W: r, M6 I
int nextp;
# \6 W3 g# v+ {7 K9 m$ |}link[M+1];
5 X+ J1 F4 }" x& o( O9 z% N& V6 d" K  _2 q
void main(). \9 [9 z8 ^3 Y0 z+ Y( W
{int i,count,h;2 t6 m' H8 w" X0 D; W3 e; ~
for(i=1;i<=M;i++)% A3 B( X7 e. @" p& e
{  if(i==M)
; U4 |5 H6 c  i: a   link[i].nextp=1;. `. c: d; a" i$ N( W  `
   else
. z' o5 }. g0 ?3 S) F# t9 {   link[i].nextp=i+1;. s+ P# N1 {. x" v
  link[i].number=i;% k: N2 t+ f: S
}% X; T; A2 n6 t" q; P! U: }# S3 E
printf("\n");$ J4 g1 R+ z  p% h0 h
count=0;" Q0 F+ n& E) A& G$ _+ P
h=M;
4 E( P0 J9 G6 c  |# `printf("依次退出的猴子: \n");2 y# j6 ~$ [/ I# y1 D4 Q
while(count<M-1)4 U. r/ {1 l% B; C+ `/ Y- X8 Q
{i=0;9 w" t$ N7 m0 ^8 n7 _! }
while(i!=3)
5 w1 K4 g! j8 k& k{ h=link[h].nextp;- i8 Y2 A. E4 s; W
   if(link[h].number)$ G! \7 ?6 P/ l4 d4 K! L! ?
     i++;}
! x$ P! N% W2 z  }, v' N! X( `- R# }6 L. p
printf("%4d",link[h].number);
5 V: [7 I% s8 G9 O  u1 @link[h].number=0;
4 D  D& v1 Q9 F. S  H, b, Acount++;0 X, Q8 D2 A9 {$ b
}
3 |$ `1 X3 T( \0 J5 _
) ~7 E+ Z6 Z4 w+ r; D6 s4 xprintf("\n大王是:");  y( a) X9 {& a, Y) R; S8 ]
  for(i=1;i<=M;i++)
* @' ^- K# I* D( e  if(link[i].number)5 ?2 s! N1 U: I7 J* Y  g+ q
    printf("%3d\n",link[i].number);
9 c& [& ], {( `$ {( V) k9 k0 S
  t, A, i/ d. E
) X% D! z2 @. z9 w}
- f2 }5 n1 r! x( S  \
第三种是普通方法for循环

' ~4 z# ]. J0 J" u7 P: J#include<stdio.h>0 r( h6 Q: t7 t. A8 \
void main()8 @" _4 G- m% e' E4 s) k) n2 O! A2 p% X
{ int i,k,m,n,num[50],q,*p;! k6 ~6 m/ s/ x( N4 @
    clrscr();
% ^; O2 r  _2 y5 V0 |! V   printf("input number of person: n=");* Y+ q& _) R% D2 d, y0 M& p- i% D
    scanf("%d",&n);5 k# @% H# Y" g' h+ M% q! w
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
& |+ i  |- |# ?$ r" B: |( N0 M    scanf("%d",&q);
. b  h* E0 D% a, X7 V   p=num;* z/ z. l8 U5 G9 ~
  for(i=0;i<n;i++)
8 u$ S) q7 G# G- g9 |    *(p+i)=i+1;
0 I, ~1 `* p% I   i=0;
0 J8 ]$ e) w/ P7 P  m3 J) m$ S   k=0;
* H, e2 G3 i/ Q0 |  k   m=0;, l- U5 l7 n( ^4 A% g' p: c3 X! f
  while(m<n-1)7 M: m( c( r# K; W* ^! a& R; y+ ?; d
   {if(*(p+i)!=0) k++;0 b& _: `+ p& {! ?* ?
     if(k==q)" B% ^* B) B+ s2 y7 I6 S
      { *(p+i)=0;
4 N8 }9 f. D8 _' {2 H8 D8 I3 d8 y" G        k=0;$ O6 e3 j2 r2 \4 J7 E( r; l* ^
        m++;
$ Y; U# ]) e5 U* [' G7 @- k& K      }
( m8 I$ ?! c# z    i++;) j1 l% H8 Y: s8 e& p' m$ j6 z
    if(i==n)i=0;
; m+ P5 D. I, n- x   }
' S, I3 V: ~# D! v4 T' P! o  while(*p==0)p++;
9 ]* O6 W- F: Q4 I$ }; h7 B    printf("The last one is NO:%d\n",*p);! c' N7 b, ^. U. h2 o
     getch();6 s& }# W! ~9 G1 N4 k

! k+ J) ?1 Q- n+ ^( g0 x}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;1 `2 ^+ g6 n2 q& o
namespace 又费马达又费电
& f, d# ?- D3 O  [{
& O5 ^( Q: V3 @* P    class Program7 r1 ]$ R! a- h8 P
    {4 p1 s4 {- B5 R6 @4 p1 v: R
        static void Main(string[] args)6 g) F% H, Y- Q6 R7 z
        {" m+ F  O. x3 U) h/ N9 d6 R1 q
            int m, n;
3 C/ E$ I2 |+ g  @            Console.WriteLine("请输入数组长度");
+ {  c1 X4 r1 k5 L; T3 `9 K& S. d            m = int.Parse(Console.ReadLine());//m为数组的大小9 o1 F* K6 f' ]- f. x
            Console.WriteLine("请输入要截取数字的大小");
3 p: p: u0 w) R" Q5 R            n = int.Parse(Console.ReadLine());, Y( V+ c: B: l1 _
            int [] numw=new int7 q) X" `" p4 `6 M+ ?6 ]& c: p
6 P4 L. ^) a1 l& I( g4 D2 @" p
&shy;&shy;&shy;;
. p$ @, K9 ]/ m1 L            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数8 n" L* X+ \# y# b$ h" w$ ]- i
            {
6 D7 o' b3 H1 J, O                numw[j - 1] = j;
* m" V9 G- q0 |; F5 L) S- D            }3 m  i7 H0 |/ j0 K* i6 E/ @
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
- a5 k& l8 m7 J- L            while (d != m - 1)% `8 m/ y* D1 {
            {1 r: V" t/ N. f" |
                if (i == m && d != m - 1)
" O/ x& j% m: D) U# o' p% w0 y                {0 t* {9 _8 Q# h0 u& u) {
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!# k7 V( e4 H8 `2 q" Q, i1 w/ g
                    continue;
, Q7 M' v( |, }0 L# Q                }
+ O$ i  ?* A6 c                else% q8 s- _0 m4 r8 C( l
                {
3 }  a3 {) c4 S8 `                    if (numw[i] != 0)
- q$ o: O5 d5 z9 }  |# f                    {& A- {: j4 {$ }0 \0 w; H
                        i++;
% _$ u$ n. X4 u1 L2 ^  R                        k++;
1 ^8 \  M# ~6 N* n8 U                        if (k == n)
+ N5 M2 _. I! ^2 h8 W% k                        {* k* ]" v4 e6 m2 ~! {, q
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了) q& x1 ]2 @' O& c- ?. D
                            k = 0;
2 X" G5 j5 e7 E$ T* z0 d6 d, k7 i              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小19 y  l' U) Q) V" w4 ^
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);; Z$ |  m) l6 j  d- `7 \! e
                        }
# p3 I  _! o/ Z4 N- W- L6 z                        else//输出暂时还没有改变数组元素的值# O3 Q* O# {; v$ F4 O1 W
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* r+ ]7 A* h1 c2 _' J2 H
                    }$ i& w& n% B( t+ @+ V# h
                    else
; y1 g/ Q4 \9 l                        i++;//数组元素为0,直接跳过,不计数。。。2 ?) @  u. U( d7 D* E
                }( n# x2 d) g/ ]

8 v/ n- r& @( P" T: W1 r' s4 K/ e
            }//结束while循环
+ |6 h- y, L# p* x6 a. r( a4 A            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
5 U7 L4 C& N5 A8 M           
$ }6 o( t$ E' N& F5 i                if (numw[i] != 0)
: E, u8 J1 \. c+ c* X                    Console.WriteLine(numw[i]);: r# b3 m1 f4 y
           
+ F! Q0 w) C+ X. g+ E3 K! ~( P            Console.ReadLine();  D- F: a. ]: R
        }' r4 H+ o6 K' V9 r/ \3 v
    }
& J. O6 A+ o. J& Y8 R4 F}4 M* b* D  o7 S/ u6 e1 {8 I! q
小甲鱼最新课程 -> 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-17 19:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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