斐波那契数列的算法实现(javasript语言)
兔子繁殖问题
斐波那契数列因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、…… 在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
算法一：递归
let fibnacci= n => {
return n <= 0 ? 0 : n==1 ? 1 : fibnacci(n-2) + fibnacci(n-1);
}
这个时间复杂度是指数级的，计算到40的时候已经需要几秒钟的时间了。
递归算法的引申应用
求解最大公约数--采用欧几里德算法
public static int gcd_recursive(int m, int n){
if(m < n)
{
int tmp = m;
m = n;
n = tmp;
}
if(n == 0)
return m;//基准条件
return gcd_recursive(n, m%n);//不断推进
}
算法二：迭代法
动态规划的思想
let fibnacci = n=>{
if(n==0)
return 0;
let a1=0,a2=1;
for (let i=1;i<n;i++){
[a1,a2]=[a2,a1+a2]
}
return a2;
}
fibnacci(4); //---结果为3
算法时间复杂度：O(n)
引申
斐波那契数列的其他应用
爬楼梯问题(答案也是斐波那契数列)
有一楼梯共n级，刚开始时你在第一级，若每次只能跨上一级或者二级，要走上n级，共有多少走法？
输入：台阶数量 n
输出：多少种走法 m
