hrbust 2153 凸多边形的划分 (数论)

xiaoxiao2021-02-28  9

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

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

Input

有多组测试数据。对于每组测试数据输入n4<=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]); } }

转载请注明原文地址: https://www.6miu.com/read-1100287.html

最新回复(0)