计算高达十亿的加泰罗尼亚数字

Question

我是 python（和一般编程）的新手，我在 class 中被要求计算高达十亿的加泰罗尼亚数字，但我为此编写的程序无法正常工作符合预期。

    from numpy import division 
    C=1
    n=0
    while C<=10000000000:
        print (C)
        C=(4*n+2)/(n+2)*C
        n=n+1

这是它打印的内容

1, 1、 2、 4、 8, 24, 72, 216、 648, 1944年， 5832, 17496, 52488, 157464, 472392, 1417176, 4251528, 12754584, 38263752, 114791256, 344373768, 1033121304, 3099363912, 9298091736,

正如您从我的第四次迭代开始看到的，我得到了错误的数字，我不明白为什么。

编辑：我用的数学定义没有错！我知道 Wiki 有另一个定义，但这个定义没有错。 Co=1, Cn+1 = (4*n+2)/(n+2)*Cn

Answer 1

试试这个：

from scipy.special import factorial

C = 1
n = 0
while C <= 10000000000:
    print(C)
    C = factorial(2*n, exact=True)/(factorial((n+1), exact=True)*factorial(n, exact=True))
    n = n + 1

对我有用:)

Answer 2

问题

翻译成代码时，您对加泰罗尼亚数字的数学定义不正确。

这是因为 Python.

等编程语言中的运算符优先级

乘法和除法的优先级相同，所以它们是从左到右计算的。发生的情况是除法运算 (4*n+2)/(n+2) 发生在与 C 的乘法之前。当n为2时，2*(2*n+2)/(n+2)变为10/4，也就是整数运算中的2。 1*C 在这个阶段是 2，给出 4 而不是预期的 5。一旦系列中的数字不正确，则迭代计算不正确。

可能的解决方法

这是定义Catalan Numbers

也就是说，第 n 个加泰罗尼亚语数由下式给出：

import operator as op

def ncr(n, r):
    r = min(r, n-r)
    if r == 0: return 1
    numer = reduce(op.mul, xrange(n, n-r, -1))
    denom = reduce(op.mul, xrange(1, r+1))
    return numer//denom


def catalan(n):
    return ncr(2*n, n)/(n+1)

这不是很有效，但至少是正确的。

正确的修复

要计算级数，您可以使用递归公式。

N=1000000 # limit
C=1
for i in xrange(0, N+1):
    print i,C
    C = (2*(2*i +1)*C)/(i+2)

对于前几个，它看起来像这样：

Answer 3

这是使用递归解决的：

def catalan(n):
    if n <=1 :
        return 1

    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n-i-1)

    return res

for i in range(10000000000):
    print (catalan(i))

您可以阅读有关加泰罗尼亚数字的更多信息here or here

Answer 4

        C=(4*n+2)/(n+2)*C

这应用了错误的计算顺序。因为您正在使用整数运算，所以如果您尚未考虑 C，(4*n+2)/(n+2) 将丢失信息。正确的计算是：

        C=C*(4*n+2)/(n+2)

Answer 5

基于 Catalan Numbers 的表达式：

from math import factorial

C = 1
n = 0
while C <= 10000000000:
    print(C)
    C = (factorial(2 * n)) / (factorial(n + 1) * factorial(n))
    n = n + 1

Returns:

1
1.0
1.0
2.0
5.0
14.0
42.0
132.0
429.0
1430.0
4862.0
16796.0
58786.0
208012.0
742900.0
2674440.0
9694845.0
35357670.0
129644790.0
477638700.0
1767263190.0
6564120420.0

计算高达十亿的加泰罗尼亚数字

calculate catalan numbers up to a billion

python

catalan

问题

可能的解决方法

正确的修复