c++ - 改进 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

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

动态编程

我们只是从 [1..n] 构建一个表并填充它:

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];
}

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

次线性

我们实际上不必通过 fib(n-1) 计算 fib(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);
}

因为数学很酷。