斐波那契数列的实现
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：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*）。用通俗一点的话说就是：第 n 项的值等于第 n – 1 项的值加上第 n-2 项的值。
假设已知一个数列的前三项为1,1,2，要求实现一个函数，当我们传入n 的时候，返回这个数列的第 n 项的值。代码实现如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
function fibonacci(n){ var tn = n - 1 var arr = [1,1,2] if(n <= 3) return arr[tn] var temp1 = arr[1] var temp2 = arr[2] var temp for(var i = 2; i < tn; i++){ temp = temp1 + temp2 temp1 = temp2 temp2 = temp } return temp } |
思考：上面的代码功能虽然实现了，但是每次都要有一次 -1 的操作，其目的就是为了我们要找的那个 n 跟索引对应起来，那么，我们可以换一种思路实现索引匹配的问题，代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// 实现2，通过给arr前面设置一个空值，让索引和 n 对应起来 function fibonacci(n){ var arr = [null,1,1,2] if(n <= 3) return arr[n] var temp1 = arr[2] var temp2 = arr[3] var temp for(var i = 3; i < n; i++){ temp = temp1 + temp2 temp1 = temp2 temp2 = temp } return temp } |
变种题1：传入一个数 n，返回前 n 项。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
function fibonacciPrev(n){ var arr = [1,1,2] // arr.splice会修改原数组 if(n <= 2) return arr.splice(0,n) // 注意这里的 -1 var tn = n - 1 var temp1 = arr[1] var temp2 = arr[2] var temmp for(var i = 2; i < tn; i++){ temp = temp1 + temp2 temp1 = temp2 temp2 = temp arr.push(temp) } return arr } |
变种题2：求前 n 项和。
也许你会说，既然前 n 项都知道了，那我们求前 n 项的和还不简单吗，把得到的前 n 项相加一遍即可。
|
1 2 3 4 |
function fibonacciSum(n){ // fibonacciPrev 是上面实现的返回前 n 项的函数 return fibonacciPrev(n).reduce((a,b)=>a+b,0) } |
但是这样的话，有个问题就是我们求前 n 项的时候已经有了一次 for 循环，最后算结果的时候，又有了一次迭代，多了一次循环，所以从时间性能的角度考虑，代码应该像下面这样才更合理：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
function fibonacciSum(n){ var arr = [1,1,2] // arr.splice会修改原数组 if(n <= 2) return arr.splice(0,n).reduce((a,b)=>a+b,0) // 注意这里的 -1 var tn = n - 1 var temp1 = arr[1] var temp2 = arr[2] var temmp var sum = arr[0] + arr[1] + arr[2] for(var i = 2; i < tn; i++){ temp = temp1 + temp2 temp1 = temp2 temp2 = temp sum += temp } return sum } |
好了，本篇划水文章到此结束。
发表评论