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

分类: 计算机技术
推荐阅读:
Linux终端如何输入复杂的命令 在Linux下,当你要输入的命令过于复杂,比如有许多参数,你可以先按 ctrl + x ,再按 ctrl + e 快速打开一个编辑器编辑命令。
C/C++程序打印输出中文导致乱码的解决方法 C/C++程序打印输出中文导致乱码的解决方法如下:
Python字符串替换函数replace() replace()是Python中的一个内置函数;可通过replace()函数将字符串中的一部分替换成另一部分,并返回一个新的副本;
SQL重命名数据库 当您需要更改数据库名称时,将使用RENAME DATABASE;
Python complex()函数 在Python中,complex()函数用于创建一个复数对象,它可以接受两个参数,表示复数的实部和虚部,也可以只传入一个参数,此时表示复数的实部为该参数,虚部为0。
如何卸载 Dev Home Dev Home是Windows的一个新的控制中心,提供了使用可定制的小部件在仪表板中监控项目的能力,通过下载应用程序,包或存储库来设置开发环境;要卸载Dev Home,需以管理员权限打开 PowerShell,并执行以下命令: