【HDU】1130 - How Many Trees?（java - BigDecimal & 卡特兰大数打表）

点击打开题目

How Many Trees?

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3718 Accepted Submission(s): 2088

Problem Description

A binary search tree is a binary tree with root k such that any node v reachable from its left has label (v) <label (k) and any node w reachable from its right has label (w) > label (k). It is a search structure which can find a node with label x in O(n log n) average time, where n is the size of the tree (number of vertices). Given a number n, can you tell how many different binary search trees may be constructed with a set of numbers of size n such that each element of the set will be associated to the label of exactly one node in a binary search tree?

Input

The input will contain a number 1 <= i <= 100 per line representing the number of elements of the set.

Output

You have to print a line in the output for each entry with the answer to the previous question.

Sample Input

   1
2
3

Sample Output

   1
2
5

Source

UVA

题意：给你一个数字 n ，问从1~n 可以构成多少种二叉树。

这种组合数学的思想还不是很清晰，但是知道是卡特兰数后就好办了，用 java 的 BigDecimal 打表就行了。

卡特兰数的递推公式：

F ( i ) = F ( i - 1 ) * ( 4 * i - 2 ) / ( n + 1 )

代码如下：

import java.math.BigDecimal;
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
	    Scanner sc = new Scanner(System.in); 
	    BigDecimal one = new BigDecimal(1);
	    BigDecimal two = new BigDecimal(2);
	    BigDecimal four = new BigDecimal(4);        //三个常数
	    BigDecimal f[] = new BigDecimal [111];
	    f[0] = f[1] = new BigDecimal(1);
	    f[2] = new BigDecimal(2);
	    for (int i = 3 ; i <= 100 ; i++)
	    {
	        BigDecimal t = new BigDecimal(i);
	        f[i] = f[i-1].multiply(four.multiply(t).subtract(two)).divide(t.add(one));
	    }
	    while (sc.hasNext())
	    {
	        int n = sc.nextInt();
	        System.out.println(f[n]);
	    }
	}
}