1

我想为加泰罗尼亚数字编写代码。加泰罗尼亚数字定义如下：

C(n) = 2n C n/(n+1). 但是，(2n C n)我不想计算，而是想使用以下事实自下而上计算加泰罗尼亚数字：

Catalan(n) =    
2n! /n! * n! * (n+1)  

Catalan(n+1) =  
2*(n+1)  
--------------------------- =    
(n+1)! * (n+1)! * ((n+1)+1)  

(2n+2) * (2n+1) * 2n!    
------------------------------- =  
(n+1) * n! * (n+1) * n! * (n+2)    

(2n+2) * (2n+1) * 2n!    
----------------------------------- =    
(n+1) * (n+2) * n! * n! * (n+1)    

(2n+2) * (2n+1)    
--------------- * Catalan(n)      
(n+1) * (n+2)

现在利用上述事实，这是我的以下代码：

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       return (((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan(n-1)
}

现在，我的问题是为什么当我的输入为 4 时上述函数会返回 12。它应该返回 14，因为 c(4)=14。

任何人都可以帮助我吗？

4

5 回答 5

9

尽管 for 的原始表达式C(n)可能是错误的，但实际的重现

在此处输入图像描述

是正确的。

您可以进一步简化为

在此处输入图像描述

但这给了你C(n+1)。C(n)你想要的C(n)是C(n-1). 插入n-1即可获得

在此处输入图像描述

另请注意，为了防止整数除法截断您的结果，您需要先乘然后除。

int catalan(int n) {
  if (n == 1)
    return 1; 
  else
    return 2 * (2*n - 1) * catalan(n-1) / (n+1);
}

编辑：如果在此处输入图像描述需要经常使用的值而不仅仅是计算一次，那么使用memoization可能是一个好主意，以避免多次计算它们。

此外，请注意，由于增长率较大，加泰罗尼亚数字会迅速溢出任何预定义的整数数据类型C。

于 2011-04-19T14:38:36.207 回答
4

根据http://en.wikipedia.org/wiki/Catalan_number，递归公式为：

C(n+1)=2(2n+1)/(n+1) * C(n)或者C(n)=2(2(n-1)+1)/n * C(n-1)

我想你已经忘记了这种从C(n+1)to 的转变C(n)。

于 2011-04-19T14:06:45.693 回答
3

当您从数学表达式转到代码时，您在 Catalan() 部分中将 n 隐式替换为 n-1，而不是在表达式本身中。因此，您正在计算值 N 的乘数并将其乘以 C(N-1)。尝试用 N-1 代替等式中的 N，这会导致：

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       return (((2*n) * (2*n-1))/((n)*(n+1))) * catalan(n-1)
}
于 2011-04-19T14:23:40.323 回答
3

你的公式有错误。您的公式用于计算 c(n+1) 但您的输入是 n。这可以通过在计算中使用之前将 n 的值减一来解决：

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       n=n-1
       return (((2*n+2) * (2*n+1))/((n+1)*(n+2))) * catalan(n)
}

编辑：正如 abeln 所指出的，上面的代码将由于整数除法丢弃余数而失败。请改用以下代码：

int catalan(int n)
{
    if (n == 1)
       return 1 //since c(1)=1 is my base case
    else
       n=n-1
       return ((catalan(n) * (2*n+2) * (2*n+1))/((n+1)*(n+2)))
}
于 2011-04-19T14:35:41.687 回答
0

在你的公式中，你有

         (2n)!
C(n) = ----------------
        (n+1)! * n! * n!

事实上，加泰罗尼亚数字被定义为

         (2n)!
C(n) = ----------------
        (n+1)! * n!

即你在分母上有一个太多的阶乘

于 2011-04-19T14:10:37.260 回答