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

除了xnx's answer，请注意，从Python 3.8开始，在标准库中添加^{}（二项式系数），我们也可以这样计算加泰罗尼亚数字：

import math

def catalan(n):
  return math.comb(2*n, n) / (n+1)

catalan(511) # 2.1902514917394773e+303

Answer 2

我假设您使用的是python3。在

您的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))

退货

^{pr2}$

得到nan，因为python3中的除数/=返回一个溢出到inf的浮点。在