首页 > 代码库 > 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