Python 程序中的第 N 个加泰罗尼亚数

pythonserver side programmingprogramming更新于 2025/12/20 17:16:17

在本文中，我们将学习如何计算第 n 个加泰罗尼亚数。

加泰罗尼亚数是由递归公式 − 定义的自然数序列

$$c_{0} = 1\;and\; c_{n+1} = \displaystyle\sum\limits_{i=0}^nc_{i} c_{n-i}\; for n\geq 0 ;$$

n = 0、1、2、3 的前几个加泰罗尼亚数……分别是 1、1、2、5、14、42、132、429，...................

Catalan 数既可以通过递归也可以通过动态规划获得。

那么让我们看看它们的实现。

方法 1:递归方法

示例

方法 1:递归方法

# 递归解决方案
def catalan(n):
   #负值
   if n <=1 :
      return 1
   # Catalan(n) = catalan(i)*catalan(n-i-1)
   res = 0
   for i in range(n):
      res += catalan(i) * catalan(n-i-1)
   return res
# main
for i in range(6):
   print (catalan(i))

输出

所有变量和递归调用的范围如下所示。

方法 2:动态规划方法

示例

# 使用动态规划
def catalan(n):
   如果 (n == 0 或 n == 1):
      返回 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]
# main
for i in range (6):
   print (catalan(i),end=" ")