Python计算卡特兰数(catanlan number)


卡特兰数(Catalan number),是组合数学中一种常出现于各种计数问题中的数列;本文使用Python来计算卡特兰数;

使用递归法求卡特兰数

卡特兰数满足以下递归公式:

卡特兰数递归求解

实现代码:

def catalan(n):
    if n <= 1 : return 1
    c = 0
    for i in range(n):
        c += catalan(i) * catalan(n-i-1)
    return c

for i in range(10): #打印前十个卡特兰数
    print(catalan(i), end= ' ')

输出:

1 1 2 5 14 42 132 429 1430 4862 

使用动态规划法求卡特兰数

def catalan(n):
    if (n == 0 or n == 1): return 1
    catalan = [0 for i in range(n + 1)]
    catalan[0] = 1
    catalan[1] = 1
    for i in range(2, n + 1):
        catalan[i] = 0
        for j in range(i):
            catalan[i] = catalan[i] + catalan[j] * catalan[i-j-1]
    return catalan[n]

for i in range (10):
    print (catalan(i),end=' ')

如需转载,请注明出处;本文地址:https://www.perfcode.com/p/catanlan-number-in-python.html