C++中的Fibonacci记忆化算法

Question

我在动态规划方面有些困难。更具体地说，是实现一个找到n个斐波那契数列的算法。

我有一个原始的算法可行：

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

但是当我尝试使用记忆化时，该函数总是返回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];
}

- Peter Faarup

---

иҝҷж®өд»Јз ҒзңӢиө·жқҘжІЎй—®йўҳгҖӮжӮЁиғҪеҗҰеҲҶдә«lookup_tableзҡ„еҲқе§ӢеҢ–д»Јз ҒпјҢNILзҡ„е®ҡд№үд»ҘеҸҠеҰӮдҪ•и°ғз”Ёfib_memпјҹ - alexeykuzmin0

lookup_table 未定义。 - stark

NIL被定义为什么？ - StoryTeller - Unslander Monica

很可能这是一个越界读取，但我们需要整个程序。 - MSalters

请发布整个程序。 - n. m.

你在初始化中使用了 ==。 - harmands

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

- YSC

---

我希望lookup_table是一个std::array<std::optional<int>, some_size>，而NIL则是constexpr std::optional<int> NIL{}。 - YSC

很好的使用了std::optional。我们都需要更多地习惯它。是否有与旧的“哨兵值”代码相比的基准测试？（我想抱怨std::array，因为没有人提到上限，但是...好吧现在问题已经被编辑为具有上限。不用在意了。） - Kenny Ostrom

@KennyOstrom，有一个上限限制：对于大数字，整数将最终溢出;) - YSC

有没有人担心在C++中进行记忆化时，求值顺序是未指定的？因此，并不一定是fib_mem(n-1) + fib_mem(n-2)会先遍历左侧再遍历右侧。https://en.cppreference.com/w/cpp/language/eval_order - trev

@trev 你应该自己尝试一下并检查它是否重要。如果是的话，你可以指定你想要的操作数顺序。 - YSC

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”时，您做错了什么。

- harmands

---

你不知道它是否完全相同的函数。你假设了lookup_table和NIL的声明，但可能不成立。 - StoryTeller - Unslander Monica

IEW，#define NIL 0。实际上没有什么好的理由。如果你需要一个命名常量，const int NIL = 0 是类型安全的。此外，你对 n<=1 的检查是不高效的。更容易的方式是将表初始化为 {1,1,0}。但是真正错误的是在读取表格之前缺少对 n<10 的检查。 - MSalters

我使用了 #define NIL -1。 - Peter Faarup

你是对的...问题在于使用了错误的运算符进行初始化。我猜这是初学者的错误... - Peter Faarup

@PeterFaarup 下次使用 std::fill(lookup_table, lookup_table + MAX, NIL); 代替循环。 - PaulMcKenzie

Answer 3

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

std::fill_n函数可以实现此功能：

#include <algorithm>
//...

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

- PaulMcKenzie

Answer 4

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

还有另一个概念。你可以称之为编译时记忆化。但是实际上，它是一个适合于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,...，并返回一个相应的斐波那契数列std::array<unsigned long long, ...>。我们知道最多可以存储93个值。因此，我们编写下一个函数，使用整数序列1,2,3,4,...,92,93来调用上述函数，如下所示：

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

现在，最终的结果：

constexpr auto FIB = generateArray();

将为我们提供一个编译时的std::array<unsigned long long, 93>，名称为FIB，其中包含所有的斐波那契数。如果我们需要第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

- A M

Answer 5

你的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 '='?

- alexeykuzmin0

Answer 6

错误在于初始化函数（您使用了比较运算符“==”，而实际上需要赋值运算符“=”）。但是从语义上讲，您不需要将look_table初始化为-1（NIL），因为斐波那契数列的结果永远不会为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;
}

- Carlos Camargo

Answer 7

在我的解决方案中，我使用了一个map而不是数组来存储备忘录。

#include <iostream>
#include <map>
using namespace std;

map<int, unsigned long long> memo;

unsigned long long fibo(int n) {
    if (memo[n]) {
        return memo[n];
    }

    if (n <= 1) {
        return n;
    }
    memo[n] = fibo(n-1) + fibo(n-2);
    return memo[n];
}

int main() {
    int n; 
    cin >> n;
    cout << "Ans: " << fibo(n);
    return 0;
}

- Souvik Datta