首页 > 代码库 > 递推第2题—凸多边形的三角形剖分
递推第2题—凸多边形的三角形剖分
[问题描述]
在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形剖分成了若干个三角形。现在的任务是从键盘输入凸多边形的边数n,求不同剖分的方案数Cn。比如当n=5时,有5种不同的方案,所以Cn=5。
[问题分析]
Catalan数……估计都知道,我就不解释了,直接上代码:这是我写的(好像很短啊,最喜欢短代码了):
var c:array[2..22]of longint;//当Catalan数列中n=22时就超出长整型,需要用到高精度 i,n,k:integer;begin fillchar(c,sizeof(c),0); c[2]:=1; readln(n); for i:=3 to n do for k:=2 to i-1 do inc(c[i],[k]*c[i-k+1]); writeln(c[n]);end.
下面给出标准程序:
program p2_2(input,output);const max=21;var c:array[2..max] of longint; n,i,k:integer; total:longint;begin write(‘input n=‘);readln(n); c[2]:=1; for i:=3 to n do begin c[i]:=0; for k:=2 to i-1 do c[i]:=c[i]+c[k]*c[i-k+1]; end; writeln(‘catalan=‘,c[n]);end.
答案给的另外一个参考程序用了高精度运算:
program p2_2a(input,output);const maxn=1000;type arraytype=array[0..maxn] of longint;var i,j,n:longint; h:arraytype;procedure mul(var h:arraytype;k:longint); var i:longint; begin for i:=0 to maxn do h[i]:=h[i]*k; for i:=0 to maxn-1 do begin h[i+1]:=h[i+1]+h[i] div 10; h[i]:=h[i] mod 10 end end;procedure devide(var h:arraytype;k:longint); var d,i,r:longint; begin r:=0; for i:=maxn downto 0 do begin d:=10*r+h[i]; h[i]:=d div k; r:=d mod k end end;begin {Main program} write(‘Input n:‘); readln(n); for i:=1 to maxn do h[i]:=0; h[0]:=1; for i:=3 to n-1 do begin mul(h,4*i-6); devide(h,i) end; i:=maxn; while (i>0) and (h[i]=0) do i:=i-1; for j:=i downto 0 do write(h[j]); writelnend.
感觉用了高精度的程序看起来很没有美感,哪天我会分享个比较短一点的高精度。
Catalan数还有更多的性质和应用,也是OI中比较重要的一部分,有兴趣的读者可以参考wiki百科:http://zh.wikipedia.org/zh/卡塔兰数
或者是百度百科:http://baike.baidu.com/view/2499752.htm
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。