斐波那契数列
AprilTong 11/18/2021 简单算法
# 斐波那契数列
描述 用 JavaScript 实现斐波那契数列函数,返回第 n 个斐波那契数。 f(1) = 1, f(2) = 1 等; 题目链接 (opens new window)
斐波那契数列介绍
斐波那契数列,又称黄金分割数列,因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)在
# 自己实现
方法一:通过递归实现,时间复杂度较高
function fibonacci(n) {
if (n === 1 || n === 2) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}
1
2
3
4
2
3
4
方法二:通过 map 将每个斐波那契数存储起来
function fibonacci(n) {
let map = new Map()
map.set(1, 1)
map.set(2, 1)
if (n === 1 || n === 2) return map.get(n)
for (let i = 3; i <= n; i++) {
let temp_result = map.get(i - 1) + map.get(i - 2)
map.set(i, temp_result)
}
return map.get(n)
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
方法三:使用迭代
function fibonacci(n) {
if (n === 1 || n === 2) return 1
let first = 1
let second = 1
let third = null
for (let i = 3; i <= n; i++) {
third = first + second
first = second
second = third
}
return third
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12