0

我是 python 的新手（和一般的编程），我在课堂上被要求计算加泰罗尼亚语数字高达 10 亿，但我为它编写的程序没有按预期工作。

    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

4

5 回答 5

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

这会以错误的顺序应用计算。因为您使用的是整数算术，所以(4*n+2)/(n+2)如果您尚未考虑C. 正确的计算是：

        C=C*(4*n+2)/(n+2)
于 2016-09-09T15:57:05.917 回答
0

试试这个：

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

这个对我有用 ：）

于 2016-09-09T15:52:58.950 回答
0

问题

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

这是因为 Python 等编程语言中的运算符优先级。

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

一个可能的解决方法

这是加泰罗尼亚数字的定义

在此处输入图像描述

这意味着，第 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)

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

0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
于 2016-09-09T15:54:06.063 回答
0

这是使用递归解决的：

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

您可以在此处或此处阅读有关加泰罗尼亚数字的更多信息

于 2016-09-09T15:56:56.407 回答
0

基于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

回报：

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
于 2016-09-09T15:57:39.103 回答