首页 > 代码库 > POJ 2084 Catalan数
POJ 2084 Catalan数
【题意】:
一个环上有2*N个连续的数,求将这些数两两连接且连接的边不相交的方法数。
【知识点】:
数学+Catalan数
令h(1)=1,h(0)=1
递归式1:h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)
递归式2:h(n)=((4*n-2)/(n+1))*h(n-1);
该递推关系的解为:h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
【题解】:
Catalan数典型的应用,2*N的答案为h(N)。
【代码】:
1 import java.io.*; 2 import java.util.*; 3 import java.math.*; 4 5 public class Main { 6 public static void main(String args[]){ 7 Scanner cin = new Scanner( 8 new BufferedInputStream(System.in)); 9 BigInteger[] B = new BigInteger[120];10 B[0] = new BigInteger("1");11 B[1] = new BigInteger("1");12 for(int i = 2; i <= 100; i++){13 B[i] = B[i - 1].multiply(14 BigInteger.valueOf(4 * i - 2)).divide(15 BigInteger.valueOf(i + 1));16 }17 while(true){18 int n = cin.nextInt();19 if(n == -1)20 break;21 System.out.println(B[n]);22 }23 }24 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。