斐波那契数列

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

方法二:通过 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

方法三:使用迭代

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
上次更新: 11/18/2021, 11:42:27 AM