A41147. 有多少种二叉树输入n(1<n<13)，求n个结点的二叉树有多少种形态输入整数n输出答案样例输入3样例输出5n个结点组成的二叉树形态总数=卡特兰数=C^{_{m}^{n}}/(n+1)，其中m=2n。
填空题
困难
知识点
题目描述
有多少种二叉树
输入n(1<n<13)，求n个结点的二叉树有多少种形态
输入
整数n
输出
答案
样例输入
3
样例输出
5
n个结点组成的二叉树形态总数=卡特兰数=C^{_{m}^{n}}/(n+1)，其中m=2n。
参考答案
//卡特兰数
#include <iostream>
using namespace std;
typedef long long LL;
LL Cmn(int n){
LL a=1,b=1;
for(int i=2*n;i>n;i--) a*=i;
for(int i=n;i>=1;i--) b*=i;
return a/b/(n+1);
}
int main()
{
int n;
cin>>n;
cout<<Cmn(n)<<endl;
return 0;
}
//卡特兰数
#include <iostream>
using namespace std;
typedef long long LL;
LL dp[15];
int main()
{
int n;
cin>>n;
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i]+=dp[j-1]*dp[i-j];
}
}
cout<<dp[n];
return 0;
}
上一题
下一题