HDU 1130(Catalan数的应用)

spoiler posted @ 2011年4月21日 20:19 in Catalan数的各种应用 , 1357 阅读

题目大意:就是给你1到N个数,让你求他能构成多少种二叉树;

题目分析:这里又是一种组合数学里的重要知识点!Catalan数的应用。

如果数据比较小,建议模拟这个公式:

Catalan的原始递推公式就是这个,这个是专门针对给出节点,有多少二叉数构造方法的方程。

$$C_{N}^{M}$$=$$C_{N-1}^{M}$$+$$C_{N-1}^{M-1}$$

用二维数组模拟,当前元素的值等于他正上方的值+左边的值;

当然所消耗的内存是很大的 :M*N*4 Bytes,所以数字小才能模拟50以内比较保险 哈哈{^_^}!

然后大数的就只有应用到大数的算法啦,反正我认为C++里的模拟太费事了 ,所以今天第一次也学习写

JAVA里的大数的运算了, 建议您也学学,嘿嘿,方便啊 。

首先分析一下思路:

这个方程进一步化简:

F( N )=$\sum_{k=1}^n{{F( N-1-K )*F(K)}}$    (k=0....N-1)

根据这个公式进行计算就可以了

import java.math.*;
import java.util.*;
public class Main{
	public static void main(String args[]){
		List list=new ArrayList(101);
		BigInteger f=BigInteger.valueOf(1);
		list.add(f);
		list.add(f);
		for(int i=2;i<=100;i++){
			f=BigInteger.valueOf(0);
			for(int j=0;j<i;j++)
				f=f.add(((BigInteger)list.get(j)).multiply( (BigInteger)list.get(i-1-j)));
			list.add(f);
		}
			Scanner cin=new Scanner(System.in);
			int inputInt=0;
			while(cin.hasNext()){
				inputInt=cin.nextInt();
				System.out.println(list.get(inputInt));
			}
	}
}

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter