1882: 【递推】Ⅳ.Catalan数(例题)
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:2
解决:1
题目描述
Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的,它经常出现在组合计数问题中。
问题的提出:在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数目用hn表示,hn即为Catalan数。例如五边形有如下五种拆分方案,故h5=5。求对于一个任意的凸n边形相应的hn。
输入
一个正整数n
输出
Catalan数(所有数据均在long范围内)。
样例输入 复制
5
样例输出 复制
5