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

本文介绍了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.