44
技术社区[云栖]
斐波那契数列(Fabonacci)兔子练习题
Java练习题：兔子问题
此问题又叫斐波那契数列(Fabonacci)，是最先研究这个数列的人是比萨的列奥那多（又名费波那契），他描述兔子生长的数目时用上了这数列。
- 第一个月有一对刚诞生的兔子
- 第二个月之后它们可以生育
- 每月每对可生育的兔子会诞生下一对新兔子
- 兔子永不死去
假设在 n 月有新生及可生育的兔子总共 a 对，n+1 月就总共有 b 对。在 n+2 月必定总共有 a+b 对： 因为在 n+2 月的时候，所有在 n 月就已存在的 a 对兔子皆已可以生育并诞下 a 对后代；同时在前一月(n+1月)之 b 对兔子中，在当月属于新诞生的兔子尚不能生育。参照下表：
|
所经过的月数 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
新诞生的兔子 |
0 |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
|
兔子对数 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
89 |
144 |
由此可用数学归纳法定义为：
F(n) = F(n-1)+F(n+1);(n>2,F(1)=1,F(2)=1);
如果我们用普通的迭代方法该怎么样实现呢？假设我们要打印12个月兔子的对数，代码如下：
public static void main(String args[]) {
int R[] = new int[12]; //每月的兔子数
R[0] = 1; //第一月份的兔子数
R[1] = 1; //第二月份的兔子书
for (int a = 2 ; a < 12; a++) {
R[a] = R[a-1] + R[a-2];
System.out.println(R[a]);
}
}
代码很简单，用数组实现，但我们如果用递归的话，代码更加简洁：
public static void main(String args[]) {
System.out.println(Fbi(12)); //打印
}
static int Fbi(int i) {
if (i < 2) return i==0?0:1;
return Fbi(i-1) + Fbi(i-2); //自己调用自己的函数
}
递归的另外一种晦涩点的写法：
package com.zzk.cn;
/***
* 古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子
* 假如兔子都不死，每个月的兔子总数为多少？
* @author zhuzhengke
*
*/
public class test01 {
public static void main(String[] args) {
testnumber(5);
}
public static void testnumber(int i) {
System.out.println("第一个月的兔子对数： 1");
System.out.println("第二个月的兔子对数： 1");
int f1=1,f2=1,f,M=24;
for(int k=3;k<=M;k++)
{
f=f2;
f2=f1+f2;
f1=f;
System.out.println("第"+ k+"个月的兔子对数："+f2);
}
}
}
最后更新：2017-04-02 18:30:39