C ++中的斐波那契记忆算法 [英] Fibonacci memoization algorithm in C++

问题描述

我在动态编程方面有些挣扎。更具体地说，实现一个用于查找n的斐波那契数的算法。

I'm struggling a bit with dynamic programming. To be more specific, implementing an algorithm for finding Fibonacci numbers of n.

我有一个幼稚的算法可以工作：

I have a naive algorithm that works:

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

但是当我尝试使用记忆功能时，该函数始终返回0：

But when i try to do it with memoization the function always 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存储在所有元素中。

I've defined the lookup_table and initially stored NIL in all elements.

任何想法可能出什么问题吗？

Any ideas what could be wrong?

以下是要求的整个程序：

Here's the whole program as requested:

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

推荐答案

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

使用完全相同的功能，效果很好。

Using the exactly same function, and this is working fine.

在初始化 lookup_table 时，您做错了什么。

You have done something wrong in initialisation of lookup_table.

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