当前位置：首页 > news >正文

C++卡特兰数讲解

news 2025/5/9 15:42:47

前情提要，参考资料:卡特兰数 - OI Wiki

一、定义

卡特兰数（Catalan number）是一个在组合数学中经常出现的数列，应用范围很广，例如括号匹配问题、出栈顺序问题、多边形三角剖分问题等。在 C++ 中，可以使用多种方法来计算卡特兰数，包括动态规划和递归等。

二、推导

1.速记20项:

C0 = 1,         
C1 = 1,         C2 = 2,          C3 = 5,          C4 = 14,          C5 = 42,
C6 = 132,       C7 = 429,        C8 = 1430,       C9 = 4862,        C10 = 16796,
C11 = 58786,    C12 = 208012,    C13 = 742900,    C14 = 2674440,    C15 = 9694845,
C16 = 35357670, C17 = 129644790, C18 = 477638700, C19 = 1767263190, C20 = 6564120420, ...

2.通项公式: $C_n= for(1-n)\frac{4k-2}{k+1}C_{n-1}$ (但其适用范围约1~100)

//算法:Catalan数
//时间复杂度:O(n)
#include <iostream>
#include <algorithm>
#define int unsigned long long
using namespace std;
const int N = 1e5+9;
int n,f[N];signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin >> n;f[0] = 1;for(int i = 1; i <= n; ++i)  f[i] = f[i-1]*(4*i-2)/(i+1);cout << f[n] << "\n";return 0;
}

3.二叉树绘图

说明: 3-0 中左边的数为向左拓几个节点，右边则向右拓节点。那 3 即向左拓 3 个节点，0则不拓。见图

4.括号序列:

注:请对照以上二叉树观察

说明:区域内单独一个括号为向左拓点，标注在括号中的括号为向右拓。若有不清请自行思考。

1. ()()()
2. (())()
3. ()(())
4. (()())
5. ((()))

5.节点式:(或动态规划法)

仍是以以上二叉树为例，n 个节点共 n-1 种搭配方式，一共 $C_n = \sum_{k=0}^{n-1} C_kC_{n-1-k}$ 种方案。

ed:

$C_3 = C_2C_0+C_1C_1+C_0C_2 = 2*1+1*1+1*2=5$

$C_4=C_3C_0+C_2C_1+C_1C_2+C_0C_3=5*1+2*1+1*2+1*5=14$

Code ed:

//算法:卡特兰数
//时间复杂度:O(n^2) 
#include <iostream>
#include <vector>
#include <algorithm>
#define int unsigned long long
using namespace std;int Catalan(int n){//递推法(动态规划)计算第n个卡特兰数vector<int> f(n + 1, 0);f[0] = 1;for(int i = 1; i <= n; ++i){for(int j = 0; j < i; ++j){f[i] += f[j] * f[i - j - 1];}}return f[n];
}signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int n; cin >> n;cout << Catalan(n) << "\n";return 0;
}

6.二项式系数法:

直接公式: $C_n=\frac{1}{n+1}*C(2n,n)$

Code ed:

//算法:卡特兰数
//时间复杂度:O(n) 
#include <iostream>
#include <algorithm>
#define int unsigned long long
using namespace std;int binomialCoeff(int n, int k){if(k > n-k)  k = n-k;int res = 1;for(int i = 0; i < k; ++i){res *= (n - i);res /= (i + 1);}return res;
}int Catalan(int n){int C = binomialCoeff(2*n, n);return C / (n+1);
}signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int n; cin >> n;cout << Catalan(n) << "\n";return 0;
}

注:该算法当 n≥20 时可能溢出 unsigned long long 的范围

且必须使用整数运算，除法必须在最后一步进行。

三、应用

范围较为广泛:

括号序列: 合法的括号序列数量。
二叉树: 二叉搜索树的数量。
出栈序列: 出栈后1~n多少排列方式
Dyck 语言：在形式语言理论中，卡特兰数与 Dyck 语言中的字符串数量有关。
山脉数量：由 nn 个“上”和 nn 个“下”组成的山脉序列的数量。
路径问题：在网格中，从左下角到右上角的非交叉路径的数量。

统一模板:

//算法:卡特兰数
//时间复杂度:O(n^2) 
#include <iostream>
#include <vector>
#include <algorithm>
#define int unsigned long long
using namespace std;int Catalan(int n){vector<int> f(n + 1, 0);f[0] = 1;for(int i = 1; i <= n; ++i){for(int j = 0; j < i; ++j){f[i] += f[j] * f[i - j - 1];}}return f[n];
}signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int n; cin >> n;cout << Catalan(n) << "\n";return 0;
}
/*
//算法:Catalan数
//时间复杂度:O(n)
#include <iostream>
#include <algorithm>
#define int unsigned long long
using namespace std;
const int N = 1e5+9;
int n,f[N];signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin >> n;f[0] = 1;for(int i = 1; i <= n; ++i)  f[i] = f[i-1]*(4*i-2)/(i+1);cout << f[n] << "\n";return 0;
}
*/
/*
//算法:卡特兰数
//时间复杂度:O(n^2) 
#include <iostream>
#include <algorithm>
#define int unsigned long long
using namespace std;int binomialCoeff(int n, int k){if(k > n-k)  k = n-k;int res = 1;for(int i = 0; i < k; ++i){res *= (n - i);res /= (i + 1);}return res;
}int Catalan(int n){int C = binomialCoeff(2*n, n);return C / (n+1);
}signed main(void){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int n; cin >> n;cout << Catalan(n) << "\n";return 0;
}
*/

四、典例

1.出栈顺序:

ed:P1044 [NOIP 2003 普及组] 栈 - 洛谷

思路: 需利用乘法原理和加法原理。1~n分为 1~k-1，序列个数为k-1；另外的是k+1~n，序列个数为n-k。通过递归的、得 $f(n)=f(k-1)*f(n-k)$ 。接着往下推即可得到形似于 $C_n = \sum_{k=0}^{n-1} C_kC_{n-1-k}$ 的公式。