首页 > 代码库 > UVa 10312 - Expression Bracketing
UVa 10312 - Expression Bracketing
题目:求n个元素构成的树中,不是二叉树的个数。
分析:组合,计数,卡塔兰数。
n个元素组成的二叉树的个数为卡塔兰数Cn-1;有如下递推关系:
n个元素组成的所有树的个数为超卡塔兰数Sn;有如下递推关系:
卡特兰数参考:http://blog.csdn.net/mobius_strip/article/details/39229895
超卡塔兰数参考:http://mathworld.wolfram.com/SuperCatalanNumber.html
输出S(n)- C(n-1)即可。
说明:超卡塔兰数的资料好少╮(╯▽╰)╭。
#include <iostream> #include <cstdlib> using namespace std; long long C[30] = {0}; long long S[30] = {0}; int main() { S[0] = S[1] = S[2] = 1; for (int i = 3 ; i < 30 ; ++ i) S[i] = (3*(2*i-3)*S[i-1]-(i-3)*S[i-2])/i; C[0] = C[1] = 1; for (int i = 2 ; i < 30 ; ++ i) for (int j = 0 ; j < i ; ++ j) C[i] += C[j]*C[i-j-1]; int n; while (cin >> n) cout << S[n]-C[n-1] << endl; return 0; }
UVa 10312 - Expression Bracketing
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。