Python计算卡特兰数（catanlan number）

Python
2023-02-22 13:36:42

卡特兰数（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

分类： 计算机技术
推荐阅读:
C语言程序反转一个数字 在本文中，你将学会使用C语言反转一个整数；用户输入一个整数，程序将其进行反转；例如：12345 => 54321
Python locals()函数 在 Python 中，locals() 是一个内置函数，用于返回当前作用域中的所有局部变量的字典。在函数内部，locals() 返回该函数的局部变量。在模块级别上，locals() 返回全局变量。
C语言交换两个变量 在C语言中交换两个变量，需要创建一个临时变量来存储其中的一个值；例如交换a，b两个值时，需创建一个临时变量保存a的值，再将b值赋予a，最后将临时变量的值赋予b，完成交换过程；
Python实现节点 在某些情况下，无法在连续的内存块中为数据分配内存。 因此，我们在数据元素中记录下一个数据的内存地址；此类结构称为指针。 但是在Python中，我们将它们称为节点。
Rust实现冒泡排序算法（Bubble Sort） 本文将使用Rust语言实现冒泡排序算法；
禁用Visual Studio自动下载更新 近日，作者使用Visual Studio发现，Visual Studio会自己在后台下载更新内容，然后提醒你是否安装；因为Visual Studio的更新包体积庞大，不仅占用网络资源也会消耗磁盘性能，所以我决定禁用它；