在写题解之前给自己打一下广告哈~

http://edu.csdn.net/course/detail/209

题目：

? ? ? ??

1
2
3

1
2
5

题目大意：

? ? ? ? ? ? ? ?给你一个n个节点，问能够成多少棵二叉树。

题目分析：

? ? ? ? ? ? ? 简单题，只要知道有这个公式就好。卡特兰公式的一个应用就是用来求“给出n个节点，问能够成多少棵二叉树”。

an?=C(2n,n)/(n+1)=(4n-2)*(an-1)/(n+1)

先花O(n)时间打表，把前100项的结果全部算出来。以后就是O(1)的时间输出结果

代码如下：

import java.math.BigInteger;
import java.util.Scanner;


public class Main {
	
	
	public static void main(String[] args) {
		BigInteger catalans[] = new BigInteger[101];
		
		BigInteger four = new BigInteger("4");
		BigInteger two = new BigInteger("2");
		BigInteger one = new BigInteger("1");
		
		catalans[1] = new BigInteger("1");
		
		int i;
		for(i = 2 ; i <= 100 ; ++i){
			catalans[i] = catalans[i-1].multiply(four.multiply(BigInteger.valueOf(i)).subtract(two)).divide(BigInteger.valueOf(i+1));
		}
		
		
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int n = scanner.nextInt();
			System.out.println(catalans[n]);
		}
		
	}
}