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

分类: 计算机技术
推荐阅读:
Python map()函数 map() 是 Python 中的一个内置函数,它接受一个函数和一个或多个可迭代对象作为输入,返回一个新的可迭代对象,其中每个元素都是将输入函数应用于相应元素的结果。
Python实现插入排序(insertion sort) 插入排序(insertion sort)是一种比较简单的排序算法;其原理类似于对一手扑克牌进行排序;
Python实现链表 链表是一系列数据元素,它们通过指针连接在一起。每个数据元素都包含指向指针形式的另一个数据元素的连接。Python在其标准库中没有链接列表;作者将使用的节点的概念来实现链表。
近期WordPress更新失败以及官网无法打开原因 在WordPress后台进行更新,尝试多次均发生了 429 Too Many Requests 错误。起初以为是当前WordPress更新用户较多导致的,随后几天发现大多数用户还是无法更新,且错误都为429,且WordPress的官网也无法打开,返回429错误。
C/C++程序打印输出中文导致乱码的解决方法 C/C++程序打印输出中文导致乱码的解决方法如下:
Golang实现冒泡排序算法(Bubble Sort) 本文将使用Go语言完成冒泡排序算法(Bubble Sort)的实现;