本文主要是介绍UVa 991 Safe Salutations 卡特兰数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源：UVa 991 Safe Salutations
题意：圆上2*n个点均匀分布 两两相连 求不相交的方案数
思路：卡特兰数的应用
以下总结转自某大牛
/*
最典型的四类应用：（实质上却都一样，无非是递归等式的应用，就看你能不能分解问题写出递归式了）
1.括号化问题。矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
2.出栈次序问题。
一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?类似：(1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)(2)在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。
3.将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域的方法数?类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
4.给顶节点组成二叉树的问题。给定N个节点，能构成多少种形状不同的二叉树？(一定是二叉树!先去一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘,就是h(0)*h(n-1) + h(2)*h(n-2) + + h(n-1)h(0)=h(n))
*/#include <cstdio>
#include <cstring>
int a[10];
int main()
{a[1] = 1;for(int i = 2;i <= 10; i++)a[i] = a[i-1] * (4 * i - 2) / (i + 1);int n;int flag = 0;while(scanf("%d", &n) != EOF){if(flag++)puts("");printf("%d\n", a[n]);}return 0;
}
如果n很大 要用到大数
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
import java.math.BigInteger;
public class Main {/*** @param args*/public static void main(String[] args) {Scanner cin = new Scanner(System.in);BigInteger[] a = new BigInteger[1010];a[1] = BigInteger.ONE;for (int i = 2; i <= 1000; i++) {a[i] = a[i-1].multiply(BigInteger.valueOf(4*i-2));a[i] = a[i].divide(BigInteger.valueOf(i+1));//System.out.println(a[i]);}int flag = 0;while(cin.hasNext()){if(flag == 1)System.out.println();flag = 1;int n = cin.nextInt();System.out.println(a[n]);}}
}
这篇关于UVa 991 Safe Salutations 卡特兰数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
