改进C ++斐波那契数列 [英] Improve C++ Fibonacci series

问题描述

我知道：

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

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

当n = 5时，fib（5）计算为：

when n=5，fib(5) evaluates as:

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）？

Notice that each base element being used for several times, is there a way to use map to store the previous value and simply do fib(n − 1) + fib（n − 2)?

推荐答案

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

In C++, the two solutions at your disposal that would save you time are the dynamic programming approach and the memoization approach.

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

We just build a table from [1..n] and fill it in:

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 ，但是省去了中间步骤：

Memoization

Here, we implement fib as normal, but save off the intermediate steps:

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），向量会更有效。还是我们？

The more standard approach to memoization would involve a hash-table on the inputs - but in this case since we know that to compute fib(n) we also need fib(1) thru fib(n-1), a vector would be more efficient. Or do we?

我们实际上不必计算 fib （1）至 fib（n-1）以获得 fib（n）。我们可以直接这样做：

We don't actually have to compute fib(1) thru fib(n-1) to get fib(n). We could do it directly:

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

因为数学很酷。

这篇关于改进C ++斐波那契数列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！