首页 > ACM题库 > HDU-杭电 > HDU 1130 How Many Trees?-递推-[解题报告] Java
2013
11-27

HDU 1130 How Many Trees?-递推-[解题报告] Java

How Many Trees?

问题描述 :

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?

输入:

The input will contain a number 1 <= i <= 100 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.

样例输入:

1
2
3

样例输出:

1
2
5

题目大意:输入一棵树的节点数,求这棵树有多少颗二叉树

 

解题思路:卡特兰公式  h(n
) = h(n-1)*(4*n-2) / (n+1)
;(咦??貌似这个递推公式产生的数也不怎么大,,为什么要用大数???哈哈哈你随便输入一个100就知道大不大了。。。)


代码如下:

 

package com.njupt.bigInteger;

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

public class HDU_1130_1 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		BigInteger one = new BigInteger("1");
		//BigInteger one1 =BigInteger.ONE;等价于上面的那一种写法
		BigInteger two = new BigInteger("2");
		BigInteger four = new BigInteger("4");

		BigInteger N ;

		while(scanner.hasNextInt()){
			int n = scanner.nextInt();
			BigInteger catalan = one;
			for(int i = 1 ; i <= n ; ++i){
				N = new BigInteger(String.valueOf(i));
				catalan = catalan.multiply(four.multiply(N).subtract(two)).divide(N.add(one));

			}
			System.out.println(catalan);

		}
	}
}

  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  4. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!