C++ 中的斐波那契记忆算法

Question

我在动态规划方面有点吃力。更具体地说，实现一个算法来找到 n 的斐波那契数。

我有一个有效的朴素算法：

int fib(int n) {
    if(n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

但是当我尝试通过记忆来实现时，函数总是 returns 0:

int fib_mem(int n) {
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}

我已经定义了 lookup_table 并且最初在所有元素中存储了 NIL。

有什么想法是错误的吗？

这是要求的整个程序：

#include <iostream>

#define NIL -1
#define MAX 100

long int lookup_table[MAX];

using namespace std;

int fib(int n);
int fib_mem(int n);

void initialize() {
    for(int i = 0; i < MAX; i++) {
        lookup_table[i] == NIL;
    }
}

int main() {
    int n;
    long int fibonnaci, fibonacci_mem;
    cin >> n;

    // naive solution
    fibonnaci = fib(n);

    // memoized solution
    initialize();
    fibonacci_mem = fib_mem(n);

    cout << fibonnaci << endl << fibonacci_mem << endl;

    return 0;
}

int fib(int n) {
    if(n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

int fib_mem(int n) {
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}

Answer 1

我倾向于通过混合简单的实现和记忆来找到编写记忆的最简单方法：

int fib_mem(int n);
int fib(int n) { return n <= 1 ? n : fib_mem(n-1) + fib_mem(n-2); }
int fib_mem(int n)
{
    if (lookup_table[n] == NIL) {
        lookup_table[n] = fib(n);
    }
    return lookup_table[n];
}

Answer 2

#include <iostream>
#define N 100

using namespace std;

const int NIL = -1;
int lookup_table[N];

void init()
{
    for(int i=0; i<N; i++)
        lookup_table[i] = NIL;
}
int fib_mem(int n) {
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}
int main()
{
    init();
    cout<<fib_mem(5);
    cout<<fib_mem(7);
}

使用完全相同的功能，并且工作正常。

你在初始化 lookup_table 时做错了。

Answer 3

你的 initialize() 函数有一个错误：

void initialize() {
    for(int i = 0; i < MAX; i++) {
        lookup_table[i] == NIL; // <- mistake
    }
}

在指向的行中，您比较了 lookup_table[i] 和 NIL（并且不使用结果），而不是将 NIL 分配给 lookup_table[i]。

对于赋值，您应该使用 = 而不是 ==。

此外，在这种情况下，最正确的做法是在启用所有警告的情况下编译您的程序。例如，MS VC++ 显示以下警告：

warning C4553: '==': operator has no effect; did you intend '='?

Answer 4

由于问题是初始化，C++ 标准库允许您初始化序列而无需编写 for 循环，从而防止您犯错误，例如使用 == 而不是 =.

std::fill_n 函数执行此操作：

#include <algorithm>
//...

void initialize()
{
   std::fill_n(lookup_table, MAX, NIL);
}

Answer 5

错误发生在初始化函数上（您在需要属性运算符“=”的地方使用了比较运算符“==”）。但是，在语义上，您不需要使用 -1（NIL）初始化 look_table，因为 Fibonacci 结果永远不会是 0（零）；所以，你可以用零初始化它。下面看最后的解决方案：

#include <iostream>

#define NIL 0
#define MAX 1000

long int lookup_table[MAX] = {};

using namespace std;

long int fib(int n) {
    if(n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

long int fib_mem(int n) {
    assert(n < MAX);
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}

int main() {
    int n;
    long int fibonnaci, fibonacci_mem;
    cout << " n = "; cin >> n;

    // naive solution
    fibonnaci = fib(n);

    // memoized solution
    // initialize();
    fibonacci_mem = fib_mem(n);

    cout << fibonnaci << endl << fibonacci_mem << endl;

    return 0;
}

Answer 6

有趣的概念。通过记忆加速。

有不同的概念。您可以将其称为编译时记忆。但实际上它是所有适合 64 位值的斐波那契数的编译时预计算。

斐波那契数列的一个重要属性是数值呈指数级增长。因此，所有现有的整数数据类型都会很快溢出。

使用 Binet's formula 您可以计算出第 93 个斐波那契数是最后一个适合 64 位无符号值的数。

并且在编译期间计算 93 个值是一项非常简单的任务。

我们首先将计算斐波那契数的默认方法定义为 constexpr 函数：

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

有了它，可以在运行时轻松计算斐波那契数列。然后，我们用所有斐波那契数填充 std::array。我们还使用 constexpr 并使其成为带有可变参数包的模板。

我们使用 std::integer_sequence 为指数 0,1,2,3,4,5, ....

创建斐波那契数列

简单明了，并不复杂：

template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

此函数将输入整数序列 0,1,2,3,4,... 和 return a std::array<unsigned long long, ...> 以及相应的斐波那契数。

我们知道我们最多可以存储 93 个值。因此我们创建了一个 next 函数，它将使用整数序列 1,2,3,4,...,92,93 调用上面的函数，如下所示：

constexpr auto generateArray() noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

现在，终于，

constexpr auto FIB = generateArray();

将为我们提供一个名为 FIB 的编译时 std::array<unsigned long long, 93>，其中包含所有斐波那契数列。如果我们需要第 i 个斐波那契数，那么我们可以简单地写 FIB[i]。运行时不会有计算。

我认为没有更快的方法来计算第 n 个斐波那契数。

请看下面的完整程序：

#include <iostream>
#include <array>
#include <utility>
// ----------------------------------------------------------------------
// All the following will be done during compile time

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}
// We will automatically build an array of Fibonacci numberscompile time
// Generate a std::array with n elements 
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

// Max index for Fibonaccis that for in an 64bit unsigned value (Binets formula)
constexpr size_t MaxIndexFor64BitValue = 93;

// Generate the required number of elements
constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

// This is an constexpr array of all Fibonacci numbers
constexpr auto FIB = generateArray();
// ----------------------------------------------------------------------

// Test
int main() {

    // Print all possible Fibonacci numbers
    for (size_t i{}; i < MaxIndexFor64BitValue; ++i)

        std::cout << i << "\t--> " << FIB[i] << '\n';

    return 0;
}

使用 Microsoft Visual Studio Community 2019 版本 16.8.2 开发和测试。

使用 clang11.0 和 gcc10.2 额外编译和测试

语言：C++17

C++ 中的斐波那契记忆算法

Fibonacci memoization algorithm in C++

c++

algorithm

dynamic-programming

fibonacci