24h購物| | PChome| 登入
2012-05-02 06:37:46| 人氣1,099| 回應0 | 上一篇 | 下一篇

[UVA][Java][Math] 10303 - How Many Trees?

推薦 0 收藏 0 轉貼0 訂閱站台

Problem D

How Many Trees?

Input: standard input

Output: standard output

Memory Limit: 32 MB

 

A binary search tree is a binary tree with root k such that any node v in the left subtree of k has label (v) <label (k) and any node w in the right subtree of k has label (w) > label (k).

When using binary search trees, one can easily look for a node with a given label x: After we compare x to the label of the root, either we found the node we seek or we know which subtree it is in. For most binary search trees the average time to find one of its n nodes in this way is O(log n).

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 and Output

The input will contain a number 1 <= i <= 1000 per line representing the number of elements of the set. 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

公式 f[n] = C(2*n,n)/(n+1)
原本的遞迴公式 f[n]=f[0]*f[n-1]+f[1]*f[n-2]+…+f[n-1]*f[0]
產生遞迴後 f[n]=(4n-2)/(n+1)*f[n-1]


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

public class Main {
    public static void main(String[] args) {
        BigInteger[] f = new BigInteger[1001];
        f[1] = BigInteger.valueOf(1);
        for(int i = 2; i <= 1000; i++) {
            f[i] = f[i-1].multiply(BigInteger.valueOf(4*i-2)).divide(BigInteger.valueOf(i+1));
        }
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int n = cin.nextInt();
            System.out.println(f[n]);
        }
    }
}

我要檢舉
#10303#How Many Trees#二元樹
台長： Morris

您可能對以下文章有興趣

人氣(1,099) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][Math] 10223 - How many nodes ?
此分類上一篇:[UVA] 11349 - Symmetric Matrix

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文