Python 计算加泰罗尼亚数字

Question

我有使用二项式系数法计算加泰罗尼亚数的代码。

def BinominalCoefficient(n,k):
    res = 1;
    if (k > n - k):
        k = n - k
    for i in range(k):
        res *= (n - i)
        res /= (i + 1)
    return res
def CatalanNumbers(n):
   c = BinominalCoefficient(2*n, n)
   return (c//(n+1))
print (CatalanNumbers(510))

当我尝试计算 n 大于 510 的加泰罗尼亚数字时，我得到了一个“nan”结果。为什么会这样？我该如何解决？

Answer 1

我假设您使用的是 Python 3。

你的 res/= (i + 1) 应该是 res//= (i + 1) 来强制整数运算:

def BinominalCoefficient(n,k):
    res = 1
    if (k > n - k):
        k = n - k
    for i in range(k):
        res *= (n - i)
        res //= (i + 1)
    return res
def CatalanNumbers(n):
   c = BinominalCoefficient(2*n, n)
   return (c//(n+1))
print (CatalanNumbers(511))

返回

2190251491739477424254235019785597839694676372955883183976582551028726151813997871354391075304454574949251922785248583970189394756782256529178824038918189668852236486561863197470752363343641524451529091938039960955474280081989297135147411990495428867310575974835605457151854594468879961981363032236839645

你得到 nan 因为 Python 3 中的除法/= 返回一个溢出到 inf 的 float 。