hrbust 2153 凸多边形的划分 （数论）

凸多边形的划分 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 97(54 users)Total Accepted: 45(45 users)Rating: Special Judge: No Description

在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。

Input

有多组测试数据。对于每组测试数据输入n，4<=n<=21。

Output

每组输出数据输出一行，包含一个整数f(n)。

Sample Input

4

5

Sample Output

2

5

Source 数论 ——卡特兰数 #include<stdio.h> #include<string.h> using namespace std; /** 1 通项公式：h(n)=C(n,2n)/(n+1)=(2n)!/((n!)*(n+1)!) 2递推公式:h(n)=((4*n-2)/(n+1))*h(n-1); h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0). 3前几项为：h(0)=1,h(1)=1,h(2)=2,h(3)=5,h(4)=14,h(5)=42,...... **/ long long h[1003]; int main() { h[0]=1; for(int n=1;n<=19;n++) { h[n]=h[n-1]*(4*n-2)/(n+1); } int n; while(~scanf("%d",&n)) { printf("%lld\n",h[n-2]); } }