首页 > 代码库 > 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 }