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

分类: 计算机技术
推荐阅读:
Rust实现字符串sha1、sha256、sha512加密 本文将在Rust语言中使用sha1、sha256、sha512等安全散列算法对字符串进行加密;
Python使用蒙特卡洛法计算圆周率 蒙特卡洛方法通过在单位正方形内随机生成点,并判断这些点是否在单位圆内的比例来估算圆周率。当随机点数量越多时,估算值越趋近于真实值。
Linux结束正在锁定文件的进程 在Linux系统下,当你想删除或更改某个文件,却发现该文件正在被某个进程访问,处于锁定状态,导致你无法删除或更改;这时你只需要一条命令即可实现结束这个进程:
Golang实现线性搜索算法(Linear Search) 本文将使用Go语言实现线性搜索算法(Linear Search);
Rust中的函数 函数在所有编程语言中都非常普遍,也非常重要;在Rust中,可以使用 fn 关键字来声明一个函数;
Golang实现获取文件的后缀名(扩展名) Golang通过调用 path.Ext() 函数,可获取文件的后缀名。