本文主要是介绍POJ2084 Game of Connections（catalan数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=2084
大意：有2n个数字形成一个圆形，直线段连接一对数字，每一个数字必须连接到另一个数字上。（没有相交的线段）
分析：
现在假设1是要连接的点，它和4相连，为了不破坏规矩——“ 没有相交的线段"，2,3只能在右边的圆形区域进行匹配，4——8也不能越过红线，在三角形中进行连线匹配。设n个点的匹配方案数是h(n)，那么中的结果就该是h(2)h(5)。极限情况：1和2连接，答案就该是h(0)h(n-1)； 1和8连接，答案是h(n-2)h(1)。没错，真相只有一个！这是catalan数。注意：这里的n不是2n，因为1，4相连和4，1相连是一回事。
由通项公式得到：h(n)=C(2n,n)/(n+1)=(2n)!/[n!(n+1)!]
n达到了100，涉及到 大数。。
import java.math.BigInteger;
import java.util.*;
public class Main {public static BigInteger []fac=new BigInteger[405];public static void get(){fac[1]=BigInteger.ONE;for(int i=2;i<=400;i++){fac[i]=fac[i-1].multiply(BigInteger.valueOf(i));}}public static void main(String[] args) {Scanner cin=new Scanner(System.in);int n;get();while(cin.hasNext()){n=cin.nextInt();if(n==-1) break;System.out.println(fac[2*n].divide(fac[n]).divide(fac[n+1]));}}
}
做题时，如果不能严格证明它是catalan，也可以从前几项猜想可能性。catalan的前几项：
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
爆炸型增长，哈哈哈。
这篇关于POJ2084 Game of Connections（catalan数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
