首页 > 代码库 > 递推第2题—凸多边形的三角形剖分

递推第2题—凸多边形的三角形剖分

2024-07-17 19:02:57   213人阅读

[问题描述]

在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形剖分成了若干个三角形。现在的任务是从键盘输入凸多边形的边数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

 


联系
我们