我的加泰罗尼亚数字逻辑出了什么问题？

Question

我想为加泰罗尼亚语编写代码.加泰罗尼亚语数字定义如下:

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.

有人可以帮帮我吗？

Answer 1

即使原始表达式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.