一个问题的解法（兔子三个月之后每月都生兔子的问题）

     今天看到一个问题，其实是老问题了，心血来潮，就解决了一下，问题如下：

     有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数？

  这个问题想了有一个小时才想明白，看来智力水平一般，如果要是去面试这道题，肯定不行，所以还是记下来。

  将兔子分为3类，一类是可以生兔子的，一类是出生一个月的，一类是出生两个月的，这样做一个简单图表如下：

 

月份	0	1	2	3	4	5
可以生产的兔子	1	1	1	2	3	4
1个月大的兔子	0	1	1	1	2	3
2个月大的兔子	0	0	1	1	1	2

  可以看出如下的等式

       某月的可以生育的兔子=上月可以生育的兔子+上月出生2月的兔子

       某月的一月的兔子=上月可以生育的兔子

       某月的二月的兔子=上月为1月的兔子

       即：上月可以生育的兔子产生了等数量的1月的兔子，上月1月的兔子变成了2月的兔子，上月2月的兔子变成可以生育的兔子

 所以可以构建一个数组表示：

      a[n+1][0]=a[n][0]+a[n][2]

      a[n+1][1]=a[n][0]

      a[n+2][2]=a[n][1]

     其中a[0][0]=1,a[0][1]=0,a[0][2]=0

 这很容易用递归函数求出月龄不同的兔子数量，总量只要加起来就可以了，用任何语言实现起来都很容易，下面用Java实现：

 

package rabbit;
/**
*
* @author flysy
*/
public class rabbitNum {
public static long getRabbitNum(int k, int i) {
if ((k == 0) && (i == 0)) {
return 1;
}
if ((k == 0) && (i == 1)) {
return 0;
}
if ((k == 0) && (i == 2)) {
return 0;
}
if (i == 0) {
return getRabbitNum(k - 1, 0) + getRabbitNum(k - 1, 2);
}
if (i == 1) {
return getRabbitNum(k - 1, 0);
}
if (i == 2) {
return getRabbitNum(k - 1, 1);
}
return 0;
}
public static void main(String[] args) {
System.out.println("it3月t2月t1月t总量");
for (int i = 0; i < 100; i++) {
long s0 = getRabbitNum(i, 0);
long s1 = getRabbitNum(i, 1);
long s2 = getRabbitNum(i, 2);
long sum = s0 + s1 + s2;
System.out.println(i + "t" + s0 + "t" + s1 + "t" + s2 + "t" + sum);
}
}
}

因为兔子增长的很快，所以用long类型取代int型，输出如下

i
3月
2月
1月
总量
0
1
0
0
1
1
1
1
0
2
2
1
1
1
3
3
2
1
1
4
4
3
2
1
6
5
4
3
2
9
6
6
4
3
13
7
9
6
4
19
8
13
9
6
28
9
19
13
9
41
10
28
19
13
60
11
41
28
19
88
12
60
41
28
129
.........................

这种方式的问题是重复递归的太厉害，在我的电脑上输出到45之后，就变得非常慢了。所以需要优化一下，可以保存一下中间变量，避免重复递归，修改的程序如下：

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package rabbit;
/**
*
* @author flysy
*/
public class RabbitNum1 {
static long a[][] = new long[1000][3];
public static long getRabbitNum(int k, int i) {
if (k == 0) {
return a[k][i];
} else {
for (int m = 0; m < 3; m++) {
if (a[k - 1][m] == 0) {
a[k - 1][m] = getRabbitNum(k - 1, m);
}
}
if (i == 0) {
return a[k - 1][0] + a[k - 1][2];
}
if (i == 1) {
return a[k - 1][0];
}
if (i == 2) {
return a[k - 1][1];
}
return 0;
}
}
public static void main(String[] args) {
a[0][0]=1;
System.out.println("it3月t2月t1月t总量");
for (int i = 0; i < 100; i++) {
long s0 = getRabbitNum(i, 0);
long s1 = getRabbitNum(i, 1);
long s2 = getRabbitNum(i, 2);
long sum = s0 + s1 + s2;
System.out.println(i + "t" + s0 + "t" + s1 + "t" + s2 + "t" + sum);
}
}
}

 

结果是瞬间就出来了，如下：

i
3月
2月
1月
总量
0
1
0
0
1
1
1
1
0
2
2
1
1
1
3
3
2
1
1
4
4
3
2
1
6
5
4
3
2
9
6
6
4
3
13
7
9
6
4
19
8
13
9
6
28
9
19
13
9
41
10
28
19
13
60
11
41
28
19
88
12
60
41
28
129
13
88
60
41
189
14
129
88
60
277
15
189
129
88
406
16
277
189
129
595
17
406
277
189
872
18
595
406
277
1278
19
872
595
406
1873
20
1278
872
595
2745
21
1873
1278
872
4023
22
2745
1873
1278
5896
23
4023
2745
1873
8641
24
5896
4023
2745
12664
25
8641
5896
4023
18560
26
12664
8641
5896
27201
27
18560
12664
8641
39865
28
27201
18560
12664
58425
29
39865
27201
18560
85626
30
58425
39865
27201
125491
31
85626
58425
39865
183916
32
125491
85626
58425
269542
33
183916
125491
85626
395033
34
269542
183916
125491
578949
35
395033
269542
183916
848491
36
578949
395033
269542
1243524
37
848491
578949
395033
1822473
38
1243524
848491
578949
2670964
39
1822473
1243524
848491
3914488
40
2670964
1822473
1243524
5736961
41
3914488
2670964
1822473
8407925
42
5736961
3914488
2670964
12322413
43
8407925
5736961
3914488
18059374
44
12322413
8407925
5736961
26467299
45
18059374
12322413
8407925
38789712
46
26467299
18059374
12322413
56849086
47
38789712
26467299
18059374
83316385
48
56849086
38789712
26467299
122106097
49
83316385
56849086
38789712
178955183
50
122106097
83316385
56849086
262271568
51
178955183
122106097
83316385
384377665
52
262271568
178955183
122106097
563332848
53
384377665
262271568
178955183
825604416
54
563332848
384377665
262271568
1209982081
55
825604416
563332848
384377665
1773314929
56
1209982081
825604416
563332848
2598919345
57
1773314929
1209982081
825604416
3808901426
58
2598919345
1773314929
1209982081
5582216355
59
3808901426
2598919345
1773314929
8181135700
60
5582216355
3808901426
2598919345
11990037126
61
8181135700
5582216355
3808901426
17572253481
62
11990037126
8181135700
5582216355
25753389181
63
17572253481
11990037126
8181135700
37743426307
64
25753389181
17572253481
11990037126
55315679788
65
37743426307
25753389181
17572253481
81069068969
66
55315679788
37743426307
25753389181
118812495276
67
81069068969
55315679788
37743426307
174128175064
68
118812495276
81069068969
55315679788
255197244033
69
174128175064
118812495276
81069068969
374009739309
70
255197244033
174128175064
118812495276
548137914373
71
374009739309
255197244033
174128175064
803335158406
72
548137914373
374009739309
255197244033
1177344897715
73
803335158406
548137914373
374009739309
1725482812088
74
1177344897715
803335158406
548137914373
2528817970494
75
1725482812088
1177344897715
803335158406
3706162868209
76
2528817970494
1725482812088
1177344897715
5431645680297
77
3706162868209
2528817970494
1725482812088
7960463650791
78
5431645680297
3706162868209
2528817970494
11666626519000
79
7960463650791
5431645680297
3706162868209
17098272199297
80
11666626519000
7960463650791
5431645680297
25058735850088
81
17098272199297
11666626519000
7960463650791
36725362369088
82
25058735850088
17098272199297
11666626519000
53823634568385
83
36725362369088
25058735850088
17098272199297
78882370418473
84
53823634568385
36725362369088
25058735850088
115607732787561
85
78882370418473
53823634568385
36725362369088
169431367355946
86
115607732787561
78882370418473
53823634568385
248313737774419
87
169431367355946
115607732787561
78882370418473
363921470561980
88
248313737774419
169431367355946
115607732787561
533352837917926
89
363921470561980
248313737774419
169431367355946
781666575692345
90
533352837917926
363921470561980
248313737774419
1145588046254325
91
781666575692345
533352837917926
363921470561980
1678940884172251
92
1145588046254325
781666575692345
533352837917926
2460607459864596
93
1678940884172251
1145588046254325
781666575692345
3606195506118921
94
2460607459864596
1678940884172251
1145588046254325
5285136390291172
95
3606195506118921
2460607459864596
1678940884172251
7745743850155768
96
5285136390291172
3606195506118921
2460607459864596
11351939356274689
97
7745743850155768
5285136390291172
3606195506118921
16637075746565861
98
11351939356274689
7745743850155768
5285136390291172
24382819596721629
99
16637075746565861
11351939356274689
7745743850155768
35734758952996318