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

问题描述 投票：0回答：7

我在动态规划方面有点吃力。更具体地说，实现一个算法来查找 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];
}
c++ algorithm dynamic-programming fibonacci
7个回答
5
投票

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

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];
}
3
投票
#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
时做错了。

2
投票

由于问题是初始化，C++ 标准库允许您初始化序列而无需编写 

for
循环，从而防止您犯错误，例如使用 
==
而不是 
=
.

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

#include <algorithm>
//...

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

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

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

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

使用 Binet 的公式 您可以计算出第 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 个值。因此我们创建了一个 next 函数，它将使用整数序列 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

0
投票

你的

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 '='?
0
投票

错误出现在初始化函数上（您在需要属性运算符“=”的地方使用了比较运算符“==”）。但是，在语义上，您不需要使用 -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;
}
0
投票

在我的解决方案中，我使用地图而不是数组来存储备忘录。

#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;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.