题目描述

由n个节点可组成多少个不同的二叉树？

输入格式

一个正整数n。

输入格式

不同的二叉树的个数。

限制

40%的数据n<=35；
100%的数据n<=5000。

分析：
设f(n)为含有n个节点的不同形态的二叉树的个数。
n=1时，f(n)=1
n=2时，f(n)=2
n=3时，f(n)=5
……对于一棵二叉树，它必定是由根、左子树和右子树构成如果左子树和右子树的形态固定了，那么整棵树的形态也就确定了。





如果左子树有i个节点，右子树有n-i-1个节点，根据乘法原理，这种情况下的不同形态的总数目就是f[i]*f[n-i-1]。根据加法原理，一棵有n个节点的二叉树的总形态数就是:
该递推式，就是Catalan数的形式之一。
使用Catalan数递推式求解。

Catalan数递推式程序实现方式：
当n不是很大时：
S:=1;
For i:=1 to n do s:=s*(2*n-i+1) div I;
S:=s div (n+1);
涉及到高精乘单精运算。接下来的重点是：如何进行高精乘与高精除。
高精乘和高精除技巧：
1、边乘边除，这样可以极大地提高运算效率。
2、更强的优化是，直接将乘数和除数分解质因数，同时统计各个质因数个数，最后将这些质因数相乘即 可。这也是本题的标准算法。
3、最后有一种基于位移的高精度乘法，这是在乘数过多时使用的，具体参见其他资料这里不作详解。
请先尝试如何当n比较大时，如何更高效率得到结果。 Catalan数程序优化措施
递归式：
h(n)=C(2n,n)/(n + 1) (n=1,2,3,...)
=(2n)!/((n+1)×n!×n!)
=(2n×(2n-1)×……×(n+2))/(n×(n-1) ×……×1)
优化方法：求各数的质因子，合并相同的质因子，最后求得合并后的质因子乘积。
procedure main;
var i,j:longint;
begin
getprime;//获取质数
t:=n div 2;
for i:=2 to t do begin
count(i+t,1);//求分子质因子
count(i,-1);//求分母质因子 end;
ans[0]:=1; ans[1]:=1;
for i:=1 to prime[0] do//求质因子的乘积
for j:=1 to m[i] do mul(ans,prime[i]);
end; procedure getprime;//筛法求质数
var i,j:longint;
begin
for i:=2 to trunc(sqrt(2*n) do//关键点只需筛到开方
if p[i] then
for j:=2 to n div i do p[i*j]:=false;
prime[0]:=0;
for i:=2 to n do
if p[i] then begin
inc(prime[0]);
prime[prime[0]]:=i;
point[i]:=prime[0];
end;
end;
procedure count(number,e:longint);//求质因子个数
var i:longint;
begin
i:=1;
while not p[number] do begin
while (number mod prime[i])=0 do begin
m[i]:=m[i]+e;
number:=number div prime[i];
end;
inc(i);
end;
if number<>1 then m[point[number]]:=m[point[number]]+e;
end;

MSN空间完美搬家到新浪博客!