0

为了计算加泰罗尼亚数字，我写了两个代码。一 (def "Catalan") 递归工作并返回正确的加泰罗尼亚数字。

dicatalan = {} 
def catalan(n):
if n == 0:
    return 1
else: 
    res = 0
    if n not in dicatalan:
        for i in range(n):
            res += catalan(i) * catalan(n - i - 1)
        dicatalan[n] = res
return dicatalan[n]

另一个 (def "catalanFormula") 应用隐式公式，但从 n=30 开始计算不准确。问题源于浮点 - 对于 k=9，程序返回“6835971.999999999”而不是“6835972”，并且从这一刻起累积错误直到最终错误答案。

（打印线用于检查）

def catalanFormula(n):
result = 1
for k in range(2, n + 1):
    result *= ((n + k) / k)
    print (result)
return int(result)

我尝试了四舍五入但失败了，尝试了十进制导入，但仍然一无所获。

我需要“catalanFormula”完美地像“catalan”一样工作；有任何想法吗？

谢谢！

4

2 回答 2

0

尝试分别计算分子和分母，最后除以它们。如果你这样做，你应该能够用浮点使它更远一点。

我确信 Python 有一个用于有理数的包。使用理性是一个更好的主意。

于 2012-12-09T11:38:48.943 回答
0

请参阅bigfloat包。

from bigfloat import *

setcontext(quadruple_precision)
def catalanFormula(n):
    result = BigFloat(1)
    for k in range(2, n + 1):
        result *= ((BigFloat(n) + BigFloat(k)) / BigFloat(k))
    return result

catalanFormula(30)

输出：

BigFloat.exact('3814986502092304.00000000000000000043', precision=113)
于 2012-12-09T11:36:02.840 回答