实际上这是一道很简单的acm题,但是我不会做……
描述
一个凸N边形,通过不相交于N边形内部的对角线,把N边形拆分成若干个三角形,不同拆分方案的数目用Hn表示,Hn就是Catalan数.
例如N=5的时候Hn=5(自己画画);
可以发现对于N条边的图形,可以利用递归式求解,现在已知递归式如下:
Hn+1=h2*hn+h3*hn-1+...+hn-1*h3+hn*h2;h2=1;
请写程序求Hn.
输入
输入有多组数据,每组数据一行,包含一个整数N。(提示:(cin>>n)的布尔值表示文件是否结束。)
输出
对于每组数据,输出一行,包含Hn.
样例输入
5样例输出
5
蝴蝶不菲
ITMISS