改进 C++ 斐波那契数列

Question

我知道：

int fib(int n) 
{
    if (n == 0 || n == 1)
        return 1;

    return fib(n − 1)+ fib(n − 2);
}

当n=5时，fib(5)计算为：

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

注意每个基本元素被多次使用，有没有办法用map来存储以前的值并简单地做fib(n − 1) + fib（n − 2)？

Answer 1

当然可以！

python 中的非常基本的示例：

cache = {}

def fib(n):
    if n <= 1:
        return n
    if n not in cache:
        cache[n] = fib(n-1) + fib(n-2)
    return cache[n]

Answer 2

是的。原始递归解决方案需要很多时间。这样做的原因是每计算一个数，就需要把前面所有的数都计算一遍以上。

甚至更糟糕的是，对于您在列表中计算的每个斐波那契数，您都没有使用您已知的先前数字来加速计算 –您“从头开始”计算每个数字。

有几个选项可以加快速度：

1。 “自下而上”创建列表

最简单的方法是只创建一个斐波那契数列，直到您想要的数字。如果你这样做，你可以说是“自下而上”构建，你可以重复使用以前的数字来创建下一个。如果您有斐波那契数列 [0, 1, 1, 2, 3]，您可以使用该列表中的最后两个数字创建下一个数字。

这种方法看起来像这样：

>>> def fib_to(n):
...     fibs = [0, 1]
...     for i in range(2, n+1):
...         fibs.append(fibs[-1] + fibs[-2])
...     return fibs
...

然后你可以通过

得到前20个斐波那契数列

>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

或者你可以通过

从前 40 个列表中得到第 17 个斐波那契数列

>>> fib_to(40)[17]
1597

2。 Memoization（比较高级的技术）

存在另一种使其更快的替代方法，但它也稍微复杂一些。由于您的问题是您重新计算已经计算出的值，因此您可以选择将已经计算出的值保存在字典中，并在重新计算之前尝试从中获取它们。这称为 memoization。它可能看起来像这样：

>>> def fib(n, computed = {0: 0, 1: 1}):
...     if n not in computed:
...         computed[n] = fib(n-1, computed) + fib(n-2, computed)
...     return computed[n]

这使您可以轻而易举地计算大斐波那契数：

>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675

这实际上是一种常见的技术，Python 3 包含一个装饰器来为您完成这项工作。送给你，自动备忘！

import functools

@functools.lru_cache(None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

这与前面的函数几乎相同，但是所有 computed 的东西都由 lru_cache 装饰器处理。

3。算一算（一个朴素的迭代解决方案）

第三种方法，如 Mitch 所建议的，是只计算而不将中间值保存在列表中。你可以想象做

>>> def fib(n):
...     a, b = 0, 1
...     for _ in range(n):
...         a, b = b, a+b
...     return a

如果您的目标是创建斐波那契数列列表，我不推荐这最后两种方法。 fib_to(100) 比 [fib(n) for n in range(101)] 快很多因为对于后者，您仍然会遇到从头开始计算列表中每个数字的问题。

检查不同的算法： https://www.nayuki.io/page/fast-fibonacci-algorithms

致谢：kqr

Answer 3

在 C++ 中，两种可以节省时间的解决方案是动态编程方法和记忆化方法。

动态规划

我们只是从 [1..n] 构建一个 table 并填写：

int fib(int n) 
{
    if (n <= 1)
        return n;

    std::vector<int> table(n + 1);
    table[0] = table[1] = 1;
    for (int i = 2; i <= n; ++i) {
        table[i] = table[i-1] + table[i-2];
    }    
    return table.back();
}

记忆

在这里，我们照常实施 fib，但省去了中间步骤：

int fib(int n) {
    static std::vector<int> table; // our cache
    if (n <= 1) {
        return n;
    }
    else if (n >= table.size()) {
        table.resize(n+1);
    }

    if (table[n] == 0) {
        // only recalc if we don't have a value
        table[n] = fib(n-1) + fib(n-2);
    }
    return table[n];
}

更标准的记忆方法将涉及输入的哈希-table - 但在这种情况下，因为我们知道要计算 fib(n) 我们还需要 fib(1) 通过 fib(n-1)，vector 会更有效率。或者我们呢？

次线性

我们实际上不需要计算 fib(1) 到 fib(n-1) 来得到 fib(n)。我们可以直接这样做：

int fib(int n) {
    const double sqrt5 = std::sqrt(5);
    const double phi = (1 + sqrt5) / 2;
    return (int)(std::pow(phi, n+1) / sqrt5 + 0.5);
}

因为数学很酷。

Answer 4

高效的斐波那契数列动态规划解决方案。

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int fib[n];
    fib[0]=fib[1]=1;
    for(int i = 2;i<n;i++)
    {
        fib[i]=fib[i-1]+fib[i-2];
    }
    for(int i = 0;i<n;i++)
    {
        cout<<fib[i]<<" ";
    }
    return 0;
}
/*input and output
5
1 1 2 3 5
Process returned 0 (0x0)   execution time : 2.557 s
Press any key to continue.*/

改进 C++ 斐波那契数列

Improve C++ Fibonacci series

c++

dynamic-programming

fibonacci

1。 “自下而上”创建列表

2。 Memoization（比较高级的技术）

3。算一算（一个朴素的迭代解决方案）

动态规划

记忆

次线性