zhgw01

括号数和catalan数

给定 P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案

n=4的例子如下
((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))

假设这个数是h(n-1), (这里之所以是n-1,是因为实际上n指的是元素个数,每2个元素乘一次,只要n-1次就可以乘完)
那么显然h(n-1)=h(0)h(n-2)+h(1)h(n-3)+...+h(n-2)h(0) 
对应的例子则是
a(b(cd)) a((bc)d)    h(0)h(n-2)  (只要先对右边的n-2个元素进行乘积,接着再跟最左边的元素相乘,h(0)=1)
(ab)(cd)                  h(1)h(n-3)  (先乘最左边的2个元素,再乘最右边的n-3个元素,之后再把这2个元素相乘)
(a(bc))d ((ab)c)d    h(n-2)h(0) 


从括号化展开的应用
1. 进出栈
   对括号进行进出栈的模拟,左括号代表进栈,右括号代表进行出栈,那么进出栈的顺序就相当于括号化的方案
2.三角剖分
   三角剖分就是从距阵乘法类比过来的,而距阵乘法就是括号化的问题

posted on 2008-06-05 23:03 apacs 阅读(665) 评论(0)  编辑 收藏 引用 所属分类: 算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜