如何创建公司网站,做标签网站是干嘛的,网络规划方案计划书,哈尔滨招标信息网官网【题目来源】 https://www.acwing.com/problem/content/3694/ 【题目描述】 求 N 个相同结点能够组成的二叉树的个数。 【输入格式】 一个整数 N。 【输出格式】 输出能组成的二叉树的个数。 【数据范围】 1≤N≤20 【输入样例】 3 【输出样例】 5 【算法分析】 ● 卡特…【题目来源】 https://www.acwing.com/problem/content/3694/ 【题目描述】 求 N 个相同结点能够组成的二叉树的个数。 【输入格式】 一个整数 N。 【输出格式】 输出能组成的二叉树的个数。 【数据范围】 1≤N≤20 【输入样例】 3 【输出样例】 5 【算法分析】 ● 卡特兰数Catalan number是组合数学中一个常出现在各种计数问题中的数列。若从第 0 项开始则卡特兰数列 h[n] 为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, …。 ● 常用的卡特兰数列 h[n] 有如下 4 种等价的递推式 h[n]h[0]*h[n−1]h[1]*h[n−2]...h[n−1]*h[0], (n≥2, h[0]h[1]1) h[n]h[n−1]*(4*n−2)/(n1), (n≥2) h[n]C(2n,n)−C(2n,n−1), (n0,1,2,...) h[n]C(2n,n)/(n1), (n0,1,2,...) ● 卡特兰数的第 20 项为 6564120420大于 2×10^9所以代码中要声明为 long long 型。 ● 二叉树是有向树 1左子树的结点数为 0右子树的结点数为 n-1。左子树的结点数为 1右子树的结点数为 n-2。左子树的结点数为 n-1右子树的结点数为 0。依此类推可得“左子树的结点数为 k右子树的结点数为 n-k-1”。 2显然若设 h[k] 表示 k 个结点组成的二叉树的个数那么由 n 个结点组成的二叉树的个数为 h[0]*h[n−1]h[1]*h[n−2]...h[n−1]*h[0]且 h[0]h[1]1。显然就是上文卡特兰数的第一个通项公式。 【算法代码】
#include bits/stdc.h
using namespace std;const int maxn25;
long long c[maxn];
int n;int main() {cinn;c[0]1,c[1]1;for(int i2; in; i)for(int j0; ji-1; j)c[i]c[j]*c[i-j-1];coutc[n];return 0;
}/*
in:
3out:
5
*/ 【参考文献】 https://www.acwing.com/solution/content/104520/ https://blog.csdn.net/hnjzsyjyj/article/details/129148916
