本文主要是介绍算法篇：卡塔兰数的两种实现方法（解决凸多边形共有多少三角划分问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//卡特兰数递归实现：超时
/*#include <iostream>
using namespace std;
int catalan(int n){
if (n == 1) return 1;
if (n == 2) return 1;
int res = 0;
for (int i = 1; i <= n - 1;i++){
res += catalan(i)*catalan(n - i);
}
return res;
}
int main(){
int n;
while (cin >> n){
cout << catalan(n-1) << endl;
}
return 0;
}*/
//卡特兰数非递归实现
#include <iostream>
using namespace std;
int arr[22];
int catalanNumber(int n){
int arr[22];
arr[1]=1;
for(int i=2;i<n+1;i++){
arr[i]=0;
for(int j=1;j<i;j++)
arr[i]+=arr[j]*arr[i-j];
}
return arr[n];
}
int main(){
int n;
while (cin >> n){
cout << catalanNumber(n-1) << endl;
}
return 0;
}
这篇关于算法篇：卡塔兰数的两种实现方法（解决凸多边形共有多少三角划分问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
