乐趣区

关于算法:力扣之斐波那契数列

jiezi

题目形容

写一个函数，输出 n，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
如：fib(2) == 1、fib(5) == 5

力扣原题目地址：https://leetcode.cn/problems/…

解决方案

计划一 间接递归

递归本人调用本人，一直执行，直到遇到某一条件进行递归

寻找法则 

 第 0 项 == 0
第 1 项 == 1
第 2 项 == 第 1 项 + 第 0 项
第 3 项 == 第 2 项 + 第 1 项
第 4 项 == 第 3 项 + 第 2 项
......
第 i 项 == 第 i - 1 项 + 第 i - 2 项 // 从第 2 项开始，即 i >= 2

应用递归示意法则 

function fib(i) {if (i == 0) {return 0}
    if (i == 1) {return 1}
    if (i >= 2) {
        /**
        * 这句话能够了解为：fib(i) 函数执行的后果值等于 return fib(i - 1) + fib(i - 2)
        * 即：fib(i) == fib(i - 1) + fib(i - 2)
        * 合乎上方法则：第 i 项 == 第 i - 1 项 + 第 i - 2 项 // 从第 2 项开始，即 i >= 2
        */ 
        return fib(i - 1) + fib(i - 2) 
    }
}
console.time()
console.log('斐波那契第 10 项', fib(10)); // 55
console.timeEnd() // default: 0.279052734375 ms

咱们应用 timeEnd() 打印出 fib(10) 第十项大抵递归执行工夫，发现是 279 毫秒。这里是有点慢了，起因举例：

比方咱们要执行 fib(4) 找到第四项的值，在寻找法则中咱们不难发现，第二项和第一项都反复计算了，节约性能，所以这种形式能够实现，然而因为反复计算导致性能并不是太好（所以递归写法在力扣中，是不通过的）

接下来，咱们看看能不能缩小反复计算，思路是：曾经计算过的数据，就不计算了，间接复用

计划二 应用对象缓存保留计算结果，不便复用

思路：

先提前定义一个对象，存储第 0 项和第 1 项的值，后续在计算的过程中，计算一项的值，就把这个值存储到对象当中去；如果持续计算发现某一项的值曾经存到对象当中去了，就间接用，如果没有存到对象当中，就持续存一份，不便后续的应用，以缩小反复计算，晋升性能

代码：

let obj = {
    0: 0, // 第 0 项的值为 0
    1: 1 // 第 1 项的值为 1
}

function fib(i) {if (i == 0) {return obj[0]
    }
    if (i == 1) {return obj[1]
    }
    /**
     * 如果 i 不在 obj 中，即 i 不属于 obj 的 key，比方 i == 2
     * 就间接新增一份：obj[2] = obj[1] + obj[0]
     *       等式变换：obj[2] = fib(1) + fib(0)
     *       以此类推：obj[i] = fib(i - 1) + fib(i - 2) 
     *       这个表达式成立的条件是从 i >= 2 开始，也就是 i 不在 obj 的 key 中
     *       所以如果不在的时候，就存一份使其在，那么后续须要再次计算的时候
     *       就间接复用即可
     * */
    // 这是从第 2 项开始的。若没有的，即之前没计算过的，就间接存一份在对象中，不便下次复用
    if (!(i in obj)) {obj[i] = fib(i - 1) + fib(i - 2)
        console.log('看看 obj 对象中存储的数据', obj);
        return fib(i - 1) + fib(i - 2)
    } else if (i in obj) { // 若是有的，即之前计算过的，就间接取到这个后果，间接用
        return obj[i]
    }
}

console.log('斐波那契', fib(6)); // 8

打印 obj 对象截图：

这里也能够应用数组去做一个缓存数据，存储一份计算过的值，这里不赘述。思路是一样的，大家能够本人试一下

计划三 定义变量累加到某一项

思路：

既然斐波那契数列是累加的，那么咱们就不停的加就行了。当求：fib(6) 的时候，咱们就从 fib(1) 开始加 … 当然，要定义一个变量作为累加的容器

代码：

function fib(n) {
    let firstVal = 0 // 头一项为 0
    let secondVal = 1 // 第二项为 1
    let thirdVal = null // 第三项先定义一个 null，预留着后续的累加
    if (n == 0) {return firstVal}
    if (n == 1) {return secondVal}
    if (n >= 2) {for (let i = 2; i <= n; i++) {
            thirdVal = secondVal + firstVal // 这一项等于前一项加上前前一项
            /** 相当于整体往后退一位 */
            firstVal = secondVal // 把前一项的值赋值给前前一项
            secondVal = thirdVal // 把这一项的值赋值给前一项
            console.log('看看累加的值', thirdVal);
        }
        return thirdVal
    }
}
console.log('斐波那契', fib(10)); // 55

打印累加的值：

总结

好忘性不如烂笔头，记录一下吧 ^_^，尽管后面记录着，前面遗记着 …

解决斐波那契数列的形式有很多种，比方还能够应用通项公式表达式之类的。次要是思路，在咱们日常工作中，对于一些数据的校验、以及数据架构加工，经常须要应用一点算法的思维在外面，这样写进去的代码，才优雅（装 X）

退出移动版