WeChat - 微信公众号
JavaScript实现斐波那契数列（Febonacci Array）
-
date_range 02/09/2019 00:00
点击量：次infosortJavaScriptlabel斐波那契febonacci
斐波那契（Febonacci）数列是一个神奇的数列，在很多地方都有应用，可以自行搜索相关图片体会其魅力，这里不赘述，直接来分析一下如何通过 JavaScript 来实现；
概念
斐波那契数列形式如下：
1 1 2 3 5 8 13 21 34...
规律应该很容易看出来，即从第三项开始，每一项的值等于前两项之和，以此类推下去，至于第一项和第二项的值嘛，不要纠结，就是这样规定的…
斐波那契数
首先来实现一下获取指定项的斐波那契数，即获取该数组中第 n 项的值；
方法一：
function getFebNum(n) {
if (n == 1 || n == 2) {
return 1;
} else {
return getFebNum(n - 1) + getFebNum(n - 2);
}
}
方法一使用递归的思路，便于理解代码量也少，但是其算法复杂度较大，当 n 相当大的时候，程序运行也无比复杂；
方法二：
function _getFebNum(n) {
if (n < 1) return 0;
let one = 1, // 初始为第 -2 项
two = 0, // 初始为第 -1 项
three = 0; // 初始为第 1 项
for (let i = 1; i <= n; i++) {
three = one + two;
one = two;
two = three;
}
return three;
}
这种方法算法复杂度就比较小了，只是换了个获取思路，代码量增加也不太容易理解，其中为了缩减代码量，便于递推的进行，把斐波那契数列向后模拟扩展了两项:
| 项 | -2 | -1 | 1 | 2 | 3 | 4 | 5 | … |
|---|---|---|---|---|---|---|---|---|
| 值 | 1 | 0 | 1 | 1 | 2 | 3 | 5 | … |
斐波那契数列
接下来通过代码实现获取指定长度的斐波那契数列：
方法一：
function getFebArr(n) {
let arr = [];
for (let i = 1; i <= n; i++) {
arr.push(getFebNum(i));
}
return arr;
}
这个方法通过挨个获取斐波那契数，最后组成一个斐波那契数列，需要用到前面的 getFebNum 函数；
方法二：
function _getFebArr(n) {
let arr = [];
if (n < 1) return arr;
let one = 1,
two = 0,
three = 0;
for (let i = 1; i <= n; i++) {
three = one + two;
arr.push(three);
one = two;
two = three;
}
return arr;
}
方法二利用之前 _getFebNum 方法的思路，递推地填充斐波那契数列，降低了算法复杂度；
微信公众号：havte