1

我最近第一次读到记忆化（我是菜鸟），我想尝试制作一个使用记忆化的斐波那契函数。这是我尝试过的，但任何超过 1 的东西都会给我一个分段错误。任何帮助表示赞赏！ 

unsigned int fibonacci( unsigned int n )
{
    vector<unsigned int> fibvector;
    if ( n <= 1 )
        return n;
    if ( fibvector.size() >= n )
        return fibvector[n];
    unsigned int add = fibonacci( n-1 ) + fibonacci( n-2 );
    fibvector[n] = add;
    return add;
}
4

2 回答 2

6 
vector<unsigned int> fibvector;

是一个局部变量。每次调用fibonacci(n)都会创建一个没有元素的新向量。您可以通过使其成为静态来修复它。

static vector<unsigned int> fibvector(MAXELEMENTS);

MAXELEMENTS 用于初始化目的。在这种情况下，您需要使用

if(fibvector[n] != 0) return fibvector[n];

编辑：如果你不想需要固定数量的元素，你可以使用以下

unsigned int fibonacci( unsigned int n )
{
    static vector<unsigned int> fibvector;
    unsigned int fib;

    if ( fibvector.size() > n )
        return fibvector[n];
    if(n <=1){
       fib = n;
    }
    else{
       unsigned int v2 = fibonacci( n-2 );
       unsigned int v1 = fibonacci( n-1 );
       fib = v2 + v1;
    }
    fibvector.push_back(fib);
    return fib;
}

这个想法是斐波那契（n）的递归方法将首先计算斐波那契（0），斐波那契（1），斐波那契（2）直到斐波那契（n）。这意味着它将按照 n 的自然顺序进行计算，并且 push_back 将准确地遵循此顺序。

于 2013-06-23T12:45:35.130 回答
0

其他人评论了您缺乏push_backs矢量。我要补充一点，您的向量对于您的函数的一次调用来说纯粹是本地的——它在递归调用堆栈上下没有范围，因此它不会像您预期的那样运行。相反，您需要制作 vector static，或者最好通过引用每个递归调用来传递它。最好还是把它变成一个类。

于 2013-06-23T12:51:11.443 回答