【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次。