首页 > 代码库 > HDU 1131
HDU 1131
N个节点的不同的树的数目。这样
随便取一个节点作为根,那么他左边和右边的儿子节点个数就确定了,假定根节点标号为x,那么左子树的标号就从1到x-1,共x-1个,右子树的标号就从x+1到n,共n-x个,那么我们的x从1取到n,就获得了所有的情况数。
这是一个递推的式子,初始值与卡特兰数的初值相同。所以,解正是卡特兰数。又由于节点有序,所以乘上N!。
import java.math.BigDecimal;import java.math.BigInteger;import java.util.Scanner;import java.io.InputStreamReader;class Cont{ BigDecimal []num; Cont(){ num=new BigDecimal[110]; num[0]=new BigDecimal(1); BigDecimal Tmp; for(int i=1;i<=100;i++){ Tmp=new BigDecimal(i); num[i]=num[i-1].multiply(Tmp); } }}public class Main{ public static void main(String args[]){ Scanner in=new Scanner(System.in); BigDecimal []Can=new BigDecimal[110]; Can[0]=new BigDecimal(1); BigDecimal B,C,D; Cont Conmul=new Cont(); for(int i=1;i<=100;i++){ B=new BigDecimal(4*i-2); C=new BigDecimal(i+1); D=Can[i-1].multiply(B); Can[i]=D.divide(C); } while(in.hasNext()){ int x=in.nextInt(); if(x==0) break; BigDecimal ans=new BigDecimal(1); ans=ans.multiply(Can[x]); ans=ans.multiply(Conmul.num[x]); System.out.println(ans); } }}
HDU 1131
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。