鱼C论坛

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

猴子问题

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

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

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

x
大家好!3 w# ]$ C6 R8 ]2 o: A
这几天我在忙着编一个问题,我用了一种方法编出来!+ i4 d- {& i( |9 R4 T1 Y8 d7 U
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!9 P0 {0 |- ]7 k, T( D
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
9 d' I, b) q0 L5 ?! }5 N4 U$ m+ K2 e1 y! c, ~
) d  \1 c" N: n3 Q0 Z6 i7 _) q
                            题目
+ T2 ^/ @2 |6 z4 O$ u# o山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。+ b; |  _& {  T
第一种方法:利用循环链表
+ ^4 W8 v6 k, T/ A2 |: ^# Y#include<stdio.h>
; _" R3 U  l$ b; i% u#include<malloc.h>& ?. V! z  i" i) Z
#define M 8            //共有8只猴子! D2 S$ T* w6 _* L3 I2 I7 E
#define N 3            //数到3只时退出第三只2 b% W6 C0 X$ b5 V" z* ?  v) F$ B
typedef struct monkey
3 A9 {" |/ F0 i$ V- v! N{int number;9 E0 |2 K& ~% v. o% v
int flag;. b) L" ^. }( u1 x) ~6 o5 K
struct monkey* next;
- |2 k& P( s1 I# I& \+ p& p' v}MONKEY;- K3 n# e$ h& J6 P0 [
main()
3 T1 I0 [3 U# a, o; @+ _! K{ MONKEY *head=NULL,*p,*s;
( _+ [, I3 \+ c3 c/ q/ J5 {4 O, F  int i,sum=0,count=0;3 b, \" C, [2 s) u9 @4 k+ ^% b
  clrscr();              //清屏- g9 c& J3 o4 V: ]$ `+ @
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存: U1 W: f* J9 U# H- U) @3 T
  p->number=1;p->flag=1;
5 ]: }, O! b2 q% d+ _  p->next=head;
: g3 S6 e7 h/ S' d# s' h, b  head=p;  t' f8 v1 b) ^7 F& |
  for(i=2;i<=M;i++)
# n2 P9 m4 r1 v6 H    { s=(MONKEY *)malloc(sizeof(MONKEY));/ ?3 S, T. ^& o* h
     s->number=i;s->flag=1;
9 D, t: F2 ^! n1 B     s->next=head;
. i8 F, w, x7 X     p->next=s;p=p->next;
: U* R, G4 T* x# T1 ^9 q    }% l+ I' t2 w  D' L0 \( o( L
    p=head;
, `7 s8 l& K& f: z' Z* R   for(;;)" Q0 m% W& U) `5 v( ]: w# e
    {if(p->flag==1)
8 e- E. [+ n) b# @- U8 b% M+ G& }       count++;, D9 h8 p" C- B5 A& J( R2 a6 x
     if(count==N)! X, r, X( _' D9 r: F* t
        {p->flag=0;+ F" i4 L4 K+ ~" p0 L, j
         count=0;
8 `$ E, n" l% [- S2 {         sum++;}
% v+ _! ?& P9 s7 r; x9 K7 `     if(sum==M-1)
2 ~1 }5 L  S/ u6 m        break;: j. H1 Z9 z  {1 ^( N( M5 x# U3 [
     p=p->next;4 b2 e) }, Q& z5 W( E
    }
6 g; j+ g" D' h( {    p=% b  N$ A/ j4 j  v
    head;$ U& \0 I- q6 K0 s/ b
    for(i=1;i<=M;i++): E( ~+ d1 w7 \
    { if(p->flag==1)
. G) _6 \- b$ O: R( ~        printf("\t%d",p->number);
% c+ j& `, z; S1 W0 A7 U  ~  A      p=p->next;
$ C  v6 ~, D, r) a% G! x, X    }. ?4 Q: F: s8 u  |' h6 h

; }/ T2 z6 N, @7 a$ Y) V( q
, a% d3 D! G0 C+ M5 H7 V$ v1 j6 I/ l0 k1 n- ?
}
; R& @" e  W2 M4 m" b  k/ V: d
第二种方法:数组! L! X; A, m# {7 ]+ Q
#include<stdio.h>7 k4 _% \7 h  t1 T2 S7 Q( d2 s
#define M 8
& p! w3 Q" n! P' Fstruct monkey
2 T/ M. G2 `9 c1 P+ O. R' S{int number;
/ I2 p' u8 _* r$ [6 `9 Iint nextp;
5 S! J5 V5 m5 U  f* i}link[M+1];* T( j! w: C4 \; j$ f

! O7 j0 W4 N" b' a% I/ vvoid main()0 ]; E1 e# Q( f7 H
{int i,count,h;
& z* |' }5 s- cfor(i=1;i<=M;i++)
$ x2 a9 D  L. U# t# z* D{  if(i==M)* d" f( t/ l) `! _
   link[i].nextp=1;7 \0 K* y1 n" e+ A& N* z/ d4 d; ?
   else" h& d0 }8 Q4 W; n. Y4 k# A
   link[i].nextp=i+1;; W0 E9 {+ Q( Q- S* h" h$ ~/ p0 ]
  link[i].number=i;: }% k6 P+ M) H
}
8 ?4 X& ]5 E: f6 ]' |+ ~printf("\n");
3 ~) e4 C2 S& S# x' t9 Vcount=0;
- |% w" V8 Q* e0 c) n, Lh=M;
+ i$ N6 w2 T$ f( e! kprintf("依次退出的猴子: \n");  x8 ?6 c% N, K; N9 @& U
while(count<M-1)- M/ J6 G, r% M0 O0 U& A; d8 ?# F
{i=0;( t' T0 G5 f- k0 P- A* v
while(i!=3)
  d0 @7 ?5 U! p( f+ x9 m9 o{ h=link[h].nextp;
, d2 u+ r# N3 I: Q   if(link[h].number)$ t+ ]" k/ Z0 Q8 \$ r  G
     i++;}! l5 B( w" Y1 i; W5 s, Q
9 o9 n+ G( j9 u7 O  E6 Z
printf("%4d",link[h].number);
; K# \: u5 s$ X6 v, slink[h].number=0;
8 H& s0 f# R6 U  M$ D" l5 T- lcount++;! f! h7 ?* x0 ?7 ~" O' c- Y
}
: |0 O+ d3 ^: P
$ _* B/ X0 k; f! W* A* f  gprintf("\n大王是:");( \3 x: y( p5 a% t; o% q7 K
  for(i=1;i<=M;i++)! f6 Y0 w. g  Q* \, V) c
  if(link[i].number)- B5 v9 B0 y5 g0 ^" g( o5 E) s
    printf("%3d\n",link[i].number);
  `: L2 }; |! M7 Y6 B0 A# M8 A' f6 b- |5 [8 v. f. m. N& v0 w
) P* n# N/ R/ N' s0 m
}

- N/ S( a# |, o6 z! A; T* G第三种是普通方法for循环

- i3 R; C4 p6 ?7 |% Q#include<stdio.h>6 ?$ L2 G( m, ^2 ^, W
void main()
( x- G9 U! m. |+ {7 I{ int i,k,m,n,num[50],q,*p;
# x& X5 c, N" k# ?6 p    clrscr();
+ @  _7 P0 n$ Y) X9 a   printf("input number of person: n=");( J  O, A/ I& \( t5 R& N) L3 d
    scanf("%d",&n);4 A8 q- ]. i( B# z9 G
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
5 m+ n+ S) f9 I4 Q1 x, M    scanf("%d",&q);
0 `0 |7 f9 G& l* ~; D+ X   p=num;0 H+ ^" [$ W+ T: O; s. s, o4 n
  for(i=0;i<n;i++)2 m, a/ w8 Q* ?# V
    *(p+i)=i+1;+ r8 [2 `7 Y/ k, P- p
   i=0;
, `6 Y0 e+ P& x, q9 A  x2 Z   k=0;' Y7 w7 M' m" X: V
   m=0;  C1 }- v" H3 a* a" p, B2 D! z
  while(m<n-1)
: E& L& O8 j* F+ _   {if(*(p+i)!=0) k++;$ p0 U3 ]0 L8 [" d% o
     if(k==q)% x0 t) n$ [5 o, H7 E
      { *(p+i)=0;
% W; }. w2 Q, Q5 q& H        k=0;
$ L( L/ N: F/ b% c1 C5 r' w; Y        m++;
* z( `! S" G" g( h9 H9 v( b      }
6 c6 ^& i- C/ }) F/ s: z2 P    i++;
" w( B/ `. ?& A* a& l    if(i==n)i=0;5 u! T$ o* L' T  E) E3 m
   }
& S! \8 C* a: h, Y: q  while(*p==0)p++;% ]* d# O) I' h  W/ n7 U5 P
    printf("The last one is NO:%d\n",*p);- y9 f! Z5 A  K5 y$ ~
     getch();
# ?5 ^* Q* M1 T/ S: M' B% X3 @
7 D( v  ?: t2 r/ \- g}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
' c6 }0 u6 F2 K  `namespace 又费马达又费电5 h0 ?0 L. ?! p- a# A' V, _
{
, g) c& \, W2 ?7 @/ O6 Y9 m    class Program0 u$ X. m  x, _, ?6 B
    {
, C# e6 h. Z3 v+ |        static void Main(string[] args)/ j! L, s1 i9 B
        {
1 }8 |- J! c$ g' V            int m, n;+ o1 ^  E' y0 Z3 R* r# b
            Console.WriteLine("请输入数组长度");9 F- `& U0 f- X/ H! }% `/ W5 u. U
            m = int.Parse(Console.ReadLine());//m为数组的大小5 [0 T, I5 {$ W; s9 o
            Console.WriteLine("请输入要截取数字的大小");1 s# ?3 Z# L! F! ~' [% C, Q" y# N
            n = int.Parse(Console.ReadLine());
/ K8 I6 O) J/ F) c% R            int [] numw=new int
4 K: M/ ?8 `* y: R4 A  k+ E7 b6 T4 [9 g( l1 [
&shy;&shy;&shy;;
; {% g& [6 ~& v1 K$ j1 a9 a            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
" S5 z5 H8 x3 C            {7 q. v8 E! P3 j2 S$ X7 B3 X9 q* a
                numw[j - 1] = j;
9 |8 j# t6 P$ H& l0 B' O( V9 j% J            }4 a6 X6 c( {7 d; G
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!/ W! `% R4 e# h
            while (d != m - 1)
" ?% N% k4 D+ q/ ?9 w& [            {
8 }+ ^8 d* c& j9 m                if (i == m && d != m - 1)
1 ~/ z* l$ M. ~6 v+ G8 Z" C9 u                {/ c. M5 l4 `8 o0 U
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
/ H- V  M; U. W$ \  @4 {, V" n7 L6 A                    continue;
" V" N2 n) s' \5 f( d( E. K; F* I                }
3 T6 B' ~4 I% Z                else
2 W; G4 [' d( b! ]# C$ R8 h                {
5 S/ Y3 D- j( }2 H7 P: f7 ]4 I% I% A                    if (numw[i] != 0)* m5 |; W& N1 U' y
                    {
8 |' D: W8 v- R0 u' K9 d! n  P                        i++;
5 s! q+ }8 l4 e. b, Q! f5 y: d                        k++;
2 q" g' C7 ^: c' |; @" }- A- U5 ?                        if (k == n)8 G1 j% Z5 S+ z5 }1 k& s
                        {
9 M+ Z# y' L6 _6 m( ]4 B                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
& {3 z5 f% f! g, g5 t3 ~                            k = 0;
9 i. G5 R; G+ U: H5 I0 p" H              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
4 A- C# t. l$ M- r                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
" {: R! L! q* k* ~+ _6 L                        }% T9 o3 v% l) ?& T7 f: t+ b
                        else//输出暂时还没有改变数组元素的值
- d5 z- C; L* Y+ c( P                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);$ C; ?2 ?$ S9 [' n: O. O
                    }
. b4 k9 `: u/ \; N4 ^* G                    else* q  C" P! U8 [2 v; o" W
                        i++;//数组元素为0,直接跳过,不计数。。。
( x7 {1 K$ s0 s7 ]                }
( G& s; `) P/ Z / x( t% ^* v7 s  Z  \) q# X
: d) m0 Z3 l' U$ O9 R; x
            }//结束while循环0 U& n1 d* q# ^- A
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦0 J0 J1 K& J! }
           
2 u& w% x& N, Q                if (numw[i] != 0)
- Q& t! T/ X/ Y5 T! M0 [                    Console.WriteLine(numw[i]);6 O/ z9 c* P7 Z$ v
           
$ |! U8 f3 W0 S! |. [            Console.ReadLine();7 l9 H& O& v% P5 _
        }
4 W5 u& y0 @. L    }
  g, Z$ u' r+ ^" g}) ^! t2 }; r- @. D
小甲鱼最新课程 -> 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-1-31 12:24

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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