OpenJudge

18:凸n边形的不同划分方式

总时间限制:
1000ms
内存限制:
65536kB
描述

卡特兰数又称卡塔兰数,英文名Catalan number,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。

最初,给卡塔兰数建立的数学模型是:一个凸n边形,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数目用hn表示,hn即为Catalan数。例如五边形有如下五种拆分方案(如图),故h5=5。求对于一个任意的凸n边形相应的hn


输入
一个正整数n,代表凸n边形的边数 (2≤n≤37)
输出
一个正整数,凸n边形划分成若干三角形的不同划分方式
样例输入
样例输入一:4
样例输入二:5
样例输出
样例输出一:2
样例输出二:5
提示
找出递推式,三角形可认为是独立的1种拆分方式
全局题号
17007
添加于
2018-04-10
提交次数
166
尝试人数
48
通过人数
40