我的加泰罗尼亚数字逻辑有什么问题？
我想为加泰罗尼亚数字编写代码。加泰罗尼亚数字的定义如下：
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。
有人可以帮我吗？
I wanted to write a code for Catalan Numbers.Catalan Numbers are defined as follows:
C(n) = 2n C n/(n+1). But instead of computing (2n C n) I wanted to calculate the catalan numbers bottom up using the following facts:
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)
Now utilizing the above fact this is my following code:
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)
}
Now,my question is why does the above function return 12 when my input is 4 .It should return 14 because c(4)=14.
Can anyone help me, please?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
尽管
C(n)的原始表达式可能是错误的，但实际的重复是正确。
您可以进一步简化为
但这为您提供了
C(n+1)就C(n)而言。您想要的是用C(n-1)表示的C(n)。插入n-1即可得到另请注意，为了防止整数除法会截断结果，您需要先乘法，然后除法。
编辑：如果
的值需要经常使用而不仅仅是计算一次，使用记忆化可能是个好主意，以避免多次计算它们。
此外，请注意，由于增长率较大，加泰罗尼亚数字很快就会溢出
C具有的任何预定义整数数据类型。Even though the original expression for
C(n)might be wrong, the actual recurrenceis correct.
You can further simplify that to
But that gives you
C(n+1)in terms ofC(n). What you want isC(n)in terms ofC(n-1). Plug inn-1to getAlso note that in order to prevent the integer division from truncating your result, you need to multiply first and then divide.
EDIT: if the values of the
need to be used frequently and not just calculated once, it's probably a good idea to use memoization, to avoid calculating them more than once.
Additionally, notice that due to the large growth rate, the Catalan numbers quickly overflow any of the predefined integer data types
Chas.根据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)到C(n)的转换。According to http://en.wikipedia.org/wiki/Catalan_number the recurrence formula is:
C(n+1)=2(2n+1)/(n+1) * C(n)orC(n)=2(2(n-1)+1)/n * C(n-1)I think you have forgotten this transformation from
C(n+1)toC(n).你的公式有错误。您的公式用于计算 c(n+1) 但您的输入是 n。这可以通过在计算中使用 n 之前将其值减一来解决：
编辑： 正如 abeln 所指出的，上面的代码将由于整数除法丢弃余数而失败。请改用下面的代码：
There is an error in your formula. Your formula is for calculating c(n+1) yet your input is n. This can be fixed by decreasing the value of n by one before using it in the calculation:
Edit: As pointed out by abeln, the code above will fail due to integer division dropping the remainder. Use the code below instead:
当您从数学表达式转向代码时，您会在 Catalan() 部分中隐式地将 n 替换为 n-1，但在表达式本身中则不然。因此，您要计算值 N 的乘数并将其乘以 C(N-1)。尝试用 N-1 代替方程中的 N，结果是：
When you go from the mathematical expression to code, you are implicitly replacing n with n-1 in the Catalan() parts, but not in the expression itself. So you are computing the multiplier for value N and multiplying it by C(N-1). Try substituting N-1 for N in your equation, which leads to:
在您的公式中，
实际上加泰罗尼亚数字的定义是
，即分母上的阶乘太多
In your formula, you have
when in fact the Catalan Numbers are defined as
i.e. you have one factorial on the denominator too much