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

分类: 计算机技术
推荐阅读:
如何在MATLAB中画函数的图像 要使用MATLAB绘制函数图形,请按照以下步骤进行操作:
Python divmod()函数 在Python中,divmod()函数是一个内置函数,用于将两个数字相除并返回商和余数。divmod()函数接受两个参数,分别是被除数和除数,并返回一个包含商和余数的元组。其中,商是两个数相除得到的结果,而余数是两个数相除后的余数部分。
Linux找出目录下所有内容重复的文件(包含子目录) 在Linux系统下,如果你想找出某个目录下(包含子目录)所有内容重复的文件,你可以使用这一条命令实现:
在Rust中如何申请堆内存 在Rust中,可以使用 Box 关键字来在堆上分配内存。Box 是一个智能指针类型,它提供了所有权转移语义,可以将其值分配到堆上,然后通过变量引用进行访问。
Kali更换国内源 默认情况下,kali系统使用的是官方提供的源,有的时候速度不错,有的时候速度不敢恭维,所以最好是将Kali源更改为国内的,这样安装软件和更新程序都可以享受到非常快的速度;
PySide6 动态创建按钮数组 动态创建按钮数组在许多场合非常有用,特别是当你需要根据用户输入、数据量或其它条件来生成界面元素时;本片将演示如何使用PySide6来动态的创建按钮数组,并正确响应对应按钮的点击信号;