【java练习题1】--费伯纳契数列【程序1】 ??题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，
【java练习题1】--费伯纳契数列
【程序1】 ??
题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ ??
1.程序分析： ? 兔子对的规律为数列1,1,2,3,5,8,13,21.... ?
?
2.
public static int count(int yuefen){
if(yuefen==1||yuefen==2){
return 1;
}else{
return count(yuefen-1)+count(yuefen-2);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int yuefen=1;
Scanner s=new Scanner(System.in);
System.out.println("输入月份");
yuefen=s.nextInt();
System.out.println("兔子对的总数是:"+count(yuefen));
}
1 楼 mfkvfn 2012-04-25 代码性能非常不好。
count(6)
=count(5)+count(4)
=[count(4)+count(3)]+[count(3)+count(2)]
={[count(3)+count(2)]+[count(2)+count(1)}+[count(3)+count(2)]
={[count(3)+count(2)]+[count(2)+count(1)}+[count(3)+count(2)]
={[count(2)+count(1)+count(2)]+[count(2)+count(1)}+[count(2)++count(1)+count(2)]
你有没有发现你计算了1次count(6)，1次count(5)，2次count(4)，3次count(3)，5次count(2)和3次count(1)?严重的浪费。count(6)=count(5)+count(4)=count(4)+cpunt(3)+count(4)根本不需要算2次count(4)，一次就够了。
应该从前面开始算，然后缓存结果。
比如
n F(n-1) F(n)
1 F(0)=0 F(1)=1
2 F(1)=1 F(2)=1
3 F(2)=1 F(3)=2
4 F(3)=2 F(4)=3
5 F(4)=3 F(5)=5
...
每一行F(n-1)等于上一行的F(n)。每一行的F(n)等于上一行2个数之和。
这样算F(6)时只需要各计算一次F(1)、F(2)、...、F(6)。而不是你那样的分别计算3次、5次、3次、2次、1次。
