HDU How Many Trees

2017-11-14 1055

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

How Many Trees?

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 163 Accepted Submission(s): 102

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

卡特兰数

import java.math.BigDecimal;
import java.util.*;
public class Main {
public static void main(String[] args){
BigDecimal []t = new BigDecimal[101];
BigDecimal n,b;
int k;
Scanner cin = new Scanner(System.in);
t[1] = BigDecimal.valueOf(1);
for(int i = 2;i< 101;i++){
n = BigDecimal.valueOf(i);
b = BigDecimal.valueOf(4).multiply(n);
b = b.subtract(BigDecimal.valueOf(2));
n = n.add(BigDecimal.valueOf(1));
b = b.multiply(t[i-1]);
t[i] = b.divide(n);
//System.out.println(t[i]);
}
while(cin.hasNext()){
k = cin.nextInt();
System.out.println(t[k]);
}
}
}

本文转自NewPanderKing51CTO博客，原文链接： http://www.cnblogs.com/newpanderking/archive/2011/07/31/2122523.html ，如需转载请自行联系原作者

文章标签：

Java

HDU How Many Trees

How Many Trees?

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

HDU How Many Trees

How Many Trees?

热门文章

最新文章

相关电子书