C++ 组合数

引言

卡特兰数 也可以明确地定义为自然数序列，它们出现在许多计数问题中：有效括号表达式的数量、二叉搜索树的数量、网格中的路径数量等等。它们以十九世纪中叶的比利时数学家 Eugène Charles Catalan 的名字命名。它以 1, 1, 2, 5, 14, 42 等开始。

在 C++ 中，有两种方法可以解决卡特兰数问题：使用递归或使用动态规划。递归方法遵循上述递归关系，但由于重复计算，在输入较大时可能效率不高。然而，动态规划会保存已计算的结果，因此不必一次又一次地计算相同的内容，这使其更有效率。通过使用数组或向量等简单数据结构并实现阶乘运算，您可以轻松地在 C++ 中实现卡特兰数的生成。与任何问题解决算法一样，在 C++ 中应用这些数字的技能可以提高在不同组合问题中的解决问题的能力。

卡特兰数的数学概念

卡特兰数是自然数的多项式，在组合数学的许多领域都有应用。第 n 个卡特兰数，记作 Cn，由以下公式给出：

其中 (²ⁿ_n) 表示二项式系数。该公式表示正确匹配 n 对括号的方法数，以及其他组合结构。

递推关系

卡特兰数也可以递归定义为：

基例为 C0=1

示例

输入： n = 6

输出 132

输入： n = 8

输出 1430

程序 1

我们来看一个使用动态规划计算第 n 个卡特兰数的 C++ 程序。

输出

 
Enter the value of n: 6
The 6th Catalan number is: 132   

说明

1. 动态规划数组： 在程序中，使用数组 catalan[] 来存储卡特兰数的先前计算结果。这可以最大程度地减少同一值被计算多次的情况。
2. 基例： 前两个卡特兰数取为 C0 = 1 和 C1 = 1。
3. 填充数组： 循环使用递归关系填充数组
   
4. 时间复杂度： 此方法的时​​间复杂度是二次的，这意味着该方法在计算相当大的卡特兰数方面是有效的。

程序 2

我们来看另一个使用递归编程计算第 n 个卡特兰数的 C++ 程序。

输出

 
Enter the value of n: 8
The 8th Catalan number is: 1430


=== Code Execution Successful ===   

说明

• 此递归解决方案直接遵循递归关系：
  
• 基例 为 C0=1，函数递归调用自身来计算更小的 n 值。

递归的问题

• 效率低下： 此方法具有指数时间复杂度，因为它会一遍又一遍地重新计算许多值，复杂度为 O(2n)。
• 堆栈溢出： 随着 n 的增加，递归深度可能会超过系统的堆栈大小，这会影响时间复杂度。

相比之下，动态规划版本运行时间为 O(n2)，对于较大的 n 效率更高。

动态规划和递归编程的复杂度分析

1. 递归方法复杂度

在递归方法中，使用以下公式计算卡特兰数 Cn：

每次计算 n 的值时，函数都会对下一个较小值 n 调用两次。这会导致多次重新计算较小的卡特兰数，从而使时间复杂度呈指数级增长。

• 时间复杂度： 递归方法的时间复杂度是指数级的。因此，我可以将其数学表示为 2^n。这是因为一个特定的函数调用会产生两个相同的函数调用，从而导致分支约为 2 的递归树。因此，总调用次数会迅速与 n 成正比。
• 空间复杂度： 然而，程序的空间复杂度由递归树的深度定义，由于调用堆栈，为 O(n)。它们与递归类似，每次递归调用都会在堆栈中形成一个层，因此最大深度是指末端。

2. 动态规划方法复杂度

在动态规划方法中，卡特兰数的计算无需重新计算所有值，而是将结果存储在数组中以供以后使用。公式保持不变，但值是按降序计算的。

对于每个 Cn，计算包括将通过乘以 Ci * Cn-i-1 获得的一个数字相加。该总和包含 n 个项，并且所有上述过程都为 n = 0, 1, 2, ...., n 进行迭代。

• 时间复杂度： 此方法的时​​间复杂度为 O(n2)。原因如下：
  
  • 为了计算 Cn，我们需要计算一个包含 n 个项的总和，并且我们对所有整数 n 都这样做；因此，总时间与 Sum i=0 to n 的数量成正比，即 O(n²)。
• 空间复杂度： 空间复杂度为 O(n)。这是因为使用了大小为 n+1 的数组来存储已计算的卡特兰数。

复杂度总结

卡特兰数的应用

卡特兰数出现在广泛的组合问题中，并在数学和计算机科学的不同领域有许多应用。以下是一些最常见的卡特兰数应用：

1. 有效括号表达式（平衡括号）

卡特兰数计算正确匹配 nnn 对括号的方法数。例如，对于 n=3n = 3n=3，有效的组合是：

• ()()()
• (())()
• ()(())
• (()())
• ((()))

2. 二叉搜索树 (BST)

第 n 个卡特兰数是您可以将 n 个不同元素放入有序列表中的方法数。这在搜索算法和数据库索引问题中尤为重要。

3. 凸多边形三角剖分

具有 n+2 条边的凸多边形的三角剖分方法数等于使用 n 个不同节点的第 n 个卡特兰数。这对于优化搜索算法和数据库索引很有用。

4. 网格中的路径

卡特兰数计算从 n×n 网格的左下角到右上角移动的方法数，只采取向右和向上的步骤，同时从不越过对角线。

5. 非交叉握手

如果 2n 个人围成一圈坐着，形成 n 次握手而不交叉的方法数是卡特兰数。这个问题也可以在弦图的背景下看到。

6. 迪克路径

迪克路径是从 (0,0) 到 (n,n) 的格子路径，且从不低于 y=x 线。n 步的此类路径数由第 n 个卡特兰数给出。

7. 山峦

卡特兰数计算绘制具有 n 个峰的山峦的方法数，其中每个山都从海平面开始并回到海平面，且没有两个山重叠。

8. 非交叉分区

卡特兰数计算将 n 个元素的集合划分为非交叉子集的方法数，其中没有子集的连接会相互交叉。

9. 堆栈排序问题

卡特兰数计算可以使用堆栈排序的 1,2,...,n 的排列数（称为“堆栈可排序排列”）。

10. 满二叉树

第 n 个卡特兰数计算具有 n 个内部节点的满二叉树的数量，其中每个内部节点恰好有两个子节点。

结论

总之，卡特兰数是组合学中的一个基本序列，为广泛的计数问题提供了解决方案，包括有效括号表达式、二叉搜索树和多边形三角剖分。在 C++ 中，可以使用动态规划高效地计算它们，这可以避免递归的低效率。了解如何实现卡特兰数可以提高解决问题的能力，尤其是在优化递归结构的算法方面。它们在离散数学和计算机科学中的多功能性，加上其指数增长，使其成为在理论和实践中处理复杂组合挑战的重要工具。