假设第1个月有1对刚诞生的兔子,第2个月进入成熟期,第3个月开始生育兔子,而1对成熟的兔子每月会生1对兔子,兔子永不死去……那么,由1对初生兔子开始,12个月后会有多少对兔子呢?
兔子数列即斐波那契数列,它的发明者是意大利数学家列昂纳多•斐波那契(Leonardo Fibonacci,1170—1250)。
问题分析
我们不妨拿新出生的1对小兔子分析:
第1个月,小兔子①没有繁殖能力,所以还是1对。
第2个月,小兔子①进入成熟期,仍然是1对。
第3个月,兔子①生了1对小兔子②,于是这个月共有2(1+1=2)对兔子。
第4个月,兔子①又生了1对小兔子③。因此共有3(1+2=3)对兔子。
第5个月,兔子①又生了1对小兔子④,而在第3个月出生的兔子②也生下了1对小兔子⑤。共有5(2+3=5)对兔子。
第6个月,兔子①②③各生下了1对小兔子。新生3对兔子加上原有的5对兔子这个月共有8(3+5=8)对兔子。
…
可以发现一个有趣的规律,第三个月开始:当月的兔子数=上月兔子数+上上月的兔子数。
斐波那契数列如下:
1,1,2,3,5,8,13,21,34,…
递归式表达式:
算法设计
如下所示,用递归实现是不是很简单
public int recursion(int n){if(n < 1){return -1;}if(n == 1 || n == 2){return 1;}return recursion(n-1) + recursion(n-2);}
算法验证分析
一般下面三个方面来考算法:
算法是否正确?
写个方法来验证他
public static void main(String[] args) {Fib1 fib1 = new Fib1();for (int n = 1; n<10 ; n++){System.out.println(fib1.recursion(n));}}
执行结果:
毋庸置疑,算法是正确的。
算法的复杂度如何?
假设T(n)表示计算Fib1(n)所需要的基本操作次数,那么:
n=1时,T(n)=1
n=2时,T(n)=1
n=3时,T(n)=3;//调用Fib1(2)、Fib1(1)和执行一次加法运算Fib1(2)+Fib1(1)
因此,n>2时要分别调用Fib1(n−1)、Fib1(n−2)和执行一次加法运算,即:
n>2时,T(n)=T(n-1)+T(n-2)+1。
当趋n于正无穷市:
由于T(n) >= F(n) 所以这是一个指数级算法(时间、空间复杂度都是指数级的)。
如何改进?
由于 n >= 3 时 F(n) = F(n-1) + F(n-2),所以可以使用迭代法,每次只需记录单前的值,和上次的值就行。
public int recursion(int n){if(n < 1){return -1;}if(n == 1 || n == 2){return 1;}//前两次的值都为1int s1 = 1;int s2 = 1;//m每次迭代记录单前的值,和上次的值。for(int i = 3; i <= n; i++){s2 = s2 + s1; //当前的值s1 = s2 - s1; //上次的值}return s2;}
该算法时间复杂度为 O(n),空间复杂度为O(1) 。
相关应用
黄金分割数随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值 0.6180339887……杨辉三角
力扣 118. 杨辉三角