python-3.x - 使用递归python生成数字序列

Question

目标是生成加泰罗尼亚语数字！我的代码工作到 n = 30（我在 JAVA 中尝试了相同的算法，它完全正确，但是，python 发生了一些奇怪的事情，它在 n = 30 之后返回错误的数字。我完全确定存在问题关于舍入或格式，但我自己无法弄清楚！

def catalan(n):
if n < 0:
    return -1
else:
    if n == 0:
        return 1
    else:
        c_n = (4*n-2)/(n+1)*catalan(n-1)
    return int(c_n)

score 4 · Accepted Answer

通过使用/(n+1)您可以生成一个浮点数，其本质上具有有限的精度。对于 n > 30 出现的较大数字，此精度不够准确。

因此，请改用一个适用于整数的公式：先相乘，然后再执行除法，即整数除法：

 c_n = (4*n-2)*catalan(n-1)//(n+1)

然后也不需要强制转换int，您可以这样做：

 return c_n

旁注：你不需要else当你return在if声明的一部分。所以你可以写：

def catalan(n):
    if n < 0:
        return -1
    if n == 0:
        return 1
    return (4*n-2)*catalan(n-1)//(n+1)

1 回答 1