0

您好所有强大的黑客、数学家和编码员！

我努力为下面的加泰罗尼亚数字方程创建一个递归算法

C(n) =∑ C(i−1) C(n−i) （并且不能使用斯特林数或其他形式来简化这个方程。）

到目前为止，这是递归算法：

int Cval[1024];//1024 just for example

int C( int n )
    {
    if( Cval[n] ) != ­1 ) return Cval[n];
        int ans = 0;
        if( n == 0 ) ans = 1;
        for( int i = 1; i <= n; i++ )
            ans += C( i ­- 1 ) * C( n ­- i );
                return Cval[n] = ans;
    }

int main()
{
    for( int i = 0; i < 1024; i++ ) Cval[i] = ­1;
    // call C(n) for any n up to 1023
}

现在，我正在尝试将其转换为迭代算法。我需要您的宝贵帮助；）有什么想法吗？

4

2 回答 2

0

创建一个 C 数字数组，并构建它。它实际上比递归版本的处理更少（它将多次计算大部分数字），并且占用更少的空间（因为数组位于连续内存中，而不是通过调用堆栈展开）。

这还具有可以缓存结果以进行高效处理的优点。

于 2011-05-17T21:23:45.643 回答
0

您正在尝试实现一种更通用的模式，称为Dynamic Programming。

您使用的缓存机制有时称为自顶向下动态规划，因为您首先从最大的 N 开始计算。（顺便说一句，在你的主要你只需要调用C()最大的 N，因为加泰罗尼亚数字的规则使它递归地调用所有其他值）。

为了将此算法转变为自下而上（迭代方法），您需要以C(x)仅取决于小于的元素的方式找到参数的排序x。通过按此顺序计算 C 的值，您始终可以直接使用数组值，而不必依赖记忆函数：

//initialize your base cases by hand, in 
Cval[0] = 1

//Now handle the inductive cases:
for n from 1 up to N:
    Cval[n] = 0
    for i from 1 to n:
        Cval[n] += Cval[i -1] * Cval[n -i];
    // i-1 and n-i are both less than n, so we know that
    // Cval has already been calculated for them.
于 2011-05-18T03:32:40.153 回答