python - 使用 Python 计算加泰罗尼亚语数？

Question

我正在编写 Python 代码以使用此处给出的数学公式生成加泰罗尼亚数字：

C(0) = 1 和 C(n) = (2(2n - 1) / (n + 1)) * C(n - 1) 每个网站在这里。（https://rosettacode.org/wiki/Catalan_numbers）

但是，当我在 python 中将它作为函数编写时，它给了我错误的结果。

例如：对于 20 答案应该是 6564120420.0 而我的代码给了我 344373768。

这里：

def catalan(cat_input):

    if cat_input==0:
    return 1 

    else:
    return  (((4*cat_input) - 2) / (cat_input + 1)) * (catalan(cat_input-1))

有人可以帮我解决这个问题吗？

score 0 · Accepted Answer

问题是在划分的时候/。原样的结果（除法本身，在相乘之前）可能不是整数，并且由于/在 python2 中默认为 int-division 小数部分被“裁剪”并且你得到错误的结果。

有几种方法可以解决这个问题（选择你最喜欢的）：

更改等式中的顺序，而不是(((4*cat_input) - 2) / (cat_input + 1)) * (catalan(cat_input-1))use (((4*cat_input) - 2) * (catalan(cat_input-1)) / (cat_input + 1))，这样可以保证除法后得到整数
将等式第一部分的类型更改float为强制浮点除法：(float((4*cat_input) - 2) / (cat_input + 1)) * (catalan(cat_input-1))
使用 python3 而不是 python2 因为 python3 默认使用十进制除法
用于from __future__ import division“激活”类似 python3 的除法

编辑：一般来说（至少在python中），如果可能的话，建议不要使用递归，因为它效率不高，你可能会遇到递归限制等问题

1 回答 1