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

分类： 计算机技术
推荐阅读:
Python isinstance()函数 在Python中，isinstance()函数用于判断一个对象是否是指定类或类型的实例。
Golang中的数组切片 数组切片和数组在Go语言中不是同一种数据类型，但他们很相似，区别是数组只能是固定长度，而数组切片可灵活的改变长度。
C语言使用fork()系统调用创建子进程 有些时候，创建多个子进程可用于提高任务处理效率或提高程序的并发性；在Linux系统下可使用fork()系统调用创建一个新的子进程；
Golang中如何使用go test进行单元测试 单元测试的意义在这里就不多说了；本文将示范如何在Go语言环境下使用go test进行简单的单元测试。
一条Linux命令让你看起来很忙还很酷 在Linux系统下，如果你想让你的终端看起来很忙，或者想在某人面前装酷，那么你一定需要这条命令来实现：
Python globals()函数 globals() 是 Python 内置函数之一，用于返回当前全局作用域中所有变量的字典。这个字典包含了所有已定义的全局变量，键为变量名，值为对应的值。可以通过修改这个字典中的变量来更新全局作用域中的变量。