使用 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))

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

Answer 1

问题出在除法 / 时。结果（除法本身，在乘法之前）可能不是整数，并且由于 python2 中的 / 默认情况下是整数除法，小数部分得到 "cropped" 而你得到错误的结果。

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

改变等式中的顺序，而不是(((4*cat_input) - 2) / (cat_input + 1)) * (catalan(cat_input-1))使用(((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到"activate" python3-like除法

编辑：一般情况下（至少在python）建议尽可能不要使用递归，因为它效率不高，你可能会运行递归限制等问题

Catalan number calculation using Python?