本文介绍了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 ++中的斐波那契记忆算法
发布评论