注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

组合数学_卡特兰数zz  

2011-08-23 10:06:30|  分类: ACM_组合数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
转载自:http://www.cppblog.com/MiYu/archive/2010/08/07/122573.html
1.令h(0)=1,h(1)=1,catalan数满足递归式:
      h(n)= h(0)*h(n-1) + h(1)*h(n-2) + …… + h(n-1)h(0) (其中n>=2)
该递推关系的解为:
      h(n)=C(2n,n)/(n + 1) (n=1,2,3,)
      另类递归式:  h(n)=((4*n-2)/(n+1))*h(n-1);
2.
1)括号化问题。
      矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(n)种)
2)出栈次序问题。
      一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
      类似:
      (1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)
      (2)在圆上选择2n个点,将这些点成对连接起来,使得所得到的n条线段不相交的方法数。

3.将多边行划分为三角形问题。
      将一个凸多边形区域分成三角形区域的方法数?
      类似:一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她
      从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
      类似:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?

4.给顶节点组成二叉树的问题。
      给定N个节点,能构成多少种形状不同的二叉树?
      (一定是二叉树!
      先去一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘,
       就是h(0)*h(n-1) + h(2)*h(n-2) +  + h(n-1)h(0)=h(n))
     (能构成h(N)个)

5     

        *
        * *

        * * *
        * * * *
        * * * * *

   形如这样的直角三角形网格,从左上角开始,只能向右走和向下走,问总共有多少种走法?

6
     n个1和n个0组成一2n位的2进制数,要求从左到右扫描,1的累计数不小于0的累计数,试求满足这条件的数有多少?

  评论这张
 
阅读(147)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018