文件名称:
完全二叉树的种类(动态规划\备忘录方法\Catalan数\C++实现)
开发工具:
文件大小: 326byte
下载次数: 0
上传时间: 2012-11-01
详细说明： Description 构造n个(2<=n<=20)叶结点的的完全二叉树(完全二叉树意味着每个分支结点都有2个儿子结点),有多少种构造方法? 注意:不改变n个结点的相对顺序,左右儿子不调换. 例如: 4个叶子节点A1,A2,A3,A4，可构造出如下完全二叉树，共5种。 再例如:5个叶子结点,A1,A2,A3,A4,A5，可构造出如下若干种完全二叉树形状,像这样的完全二叉树共有14种. Input 输入n,表示构造的完全二叉树有n个叶结点(2<=n<=20). Output 输出构造的完全二叉树的种类. Sample Input 5 Sample Output 14 Hint 把所有叶节点从左到右编上号：1，2，…，n。 无论怎样构造的完全二叉树，根节点左边的左子树和右边的右子树又都是完全二叉树， 那么n个节点的完全二叉树构造方法数等于左子树的构造方法数乘以右子树的构造方法数， 且要列举所有可能的左子树和右子树情况，而后相加。假设左子树的叶子为1，…，i。 右子树的叶子就是：i+1，…，n。 设n个叶子的完全二叉树构造方法数为Total(n)。Total(n)的递归公式如下,这是Catalan数： Total(n) = for i=1 to n-1 sum(Total(i) * Total(n-i)) if n>=2 Total(n)=1 if n=1 考虑到计算Total(n)时，所有小于规模n的Total(n-1)，…，Total(1)都可能被计算多次， 存在大量重复计算的问题。因此比较好的方法是对i从2到n，边计算Total(i)，边用表记录下来， 即备忘录的方法，时间复杂度为O(n^2) 。 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
