首页 > 代码库 > POJ 2084 Catalan数

POJ 2084 Catalan数

2024-07-10 22:08:47   221人阅读

【题意】：

一个环上有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 }

 


联系
我们