01:兔子繁殖问题
Java练习,第一道就是这道题,早有耳闻,看好多答案就是直接摆上来一个斐波那契数列就完了〒▽〒,于是自己就写了一个思考过程,仅供自己将来复习吧~
一、问题概述
题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子对数为多少?
二、分析问题
由题意,先写几个试试找一找其中的规律:
Child(幼年兔)
Young(成长兔)
Old(成年兔)
TotalNum
1月
1
0
0
1
2月
0
1
0
1
3月
1
0
1
2
4月
1
1
1
3
5月
2
1
2
5
6月
3
2
3
8
7月
5
3
5
13
TotalNum = old + young+child
= (last old + last young) + last child + (last old +last young)
= (last old + last young + last child) + (last old +last young)
= last TotalNum + last last TotalNum
由此式可得出:本月兔子总数 = 上个月兔子总数 + 上上个月兔子总数
上式中有 last last TotalNum = last old +last young 这一等价关系,是因为last last TotalNum = last TotalNum - last child,意思就是上上个月兔子总数为,上个月的兔子总数减去其中的幼年兔的数量。
这一数列即是斐波那契数列了,从第三项开始f(n) = f(n-1) + f(n+2.)
三、代码实现
package _01_rabbitFib;
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
System.out.println("第一个月有一对兔子,请输入月份:");
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
System.out.println("第"+n+"个月有"+Fib1(n)+"对兔子");
}
private static int Fib1(int n) {//递归实现
if(n == 1 || n == 2)
return 1;
else
return Fib1(n-1)+Fib1(n-2);
}
四、存在疑问
1. 斐波那契数列往后越来越大,如何存储它?
我想的解决方法是存在数组里?网上给出的斐波那契数溢出的问题是存在string里面,然后再从低位向高位相加进位。
2. 斐波那契的计算时间非常长,如何优化?
在网上搜索了有构造等比数列、线性代数解法、特征方程解法、母函数法,都非常有技巧性。用公式求的快但是用到根号也就会丢失精度吧。