下载

0下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 高二下期5月26日Tro解题报告

高二下期5月26日Tro解题报告.doc

高二下期5月26日Tro解题报告

faint
2018-09-07 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《高二下期5月26日Tro解题报告doc》,可适用于工程科技领域

问题描述一棵树由结点和与它相连子树(有或者)组成这些子树被称作儿子。树的描述是一系列数字如果这个树的儿子数是:、那么树的描述仅仅是一列、那么树的描述是由开始后面跟着其儿子的描述、那么树的描述是由开始后面跟着第一个儿子的描述然后是第二个儿子的描述。树的每个点都必须涂成红、绿或者蓝色但是我们涂的时候必须遵守下面的规则:、结点和它的儿子不能有一样的颜色、如果结点有两个儿子那么它们必须有不同的颜色。问应该有多少个结点是绿色的?任务、从文件TRO.IN读入树的描述、计算能够涂成绿色的结点的最大数和最小数、将结果写入文件TRO.OUT。输入文件TRO.IN唯一一行由一个单词组成(不超过字母)该单词是树的描述。输出文件TRO.OUT的唯一一行有两个由空格分开的整数。第一个数为绿色结点的最多数第二个数为绿色结点的最少数。样例输入样例输出解题报告分析:从问题的规模来看用搜索很难在短时间内通过较大的数据。然而本题的树形结构让我们想到了动态规划。首先我们将各结点按其在输入串中出现的先后顺序编为到N号并将输入串各元素存入一个有n个变量的数组Num里。我们不妨设FI、FI、FI表示以结点I为根的树点I为绿、蓝、红色时树中可以达到的最多绿色结点数而对于点I它的左右子树根结点号分别为L、R(当L或R为时表示该子树不存在)。根据上面设的量我们可以列出如下动态转移方程:  NumI=FI=FI=FI=NumI=FI=Max(FL,FL)FI=Max(FL,FL)FI=Max(FL,FL)NumI=FI=Max(FLFR,FLFR)FI=Max(FLFR,FLFR)FI=Max(FLFR,FLFR)显然最后要求的最大值必定是Max(FRoot,FRoot,FRoot)其中Root表示根结点号。类似的我们也可写出求最小值的转移方程我也不再阐述。从上面的方程可以看出该动态规划算法的时空效率是很高的现在的问题是如何在知道一个结点的编号I后推出它的子结点编号。最容易想到的方法是递归但是这种方法无论从时间上还是从空间上来讲都不理想。我们不妨从另一个角度来思考一下设LinkI表示以I为根的树的最后一个结点号那么我们不难列出如下递推关系式:NumI=LinkI=INumI=LinkI=LinkINumI=LinkI=LinkLinkI不难想到在知道Link数组值的情况下L=IR=LinkI,而通过上面的分析我们也可以看出求出Link数组的各值也只要一个N到的循环所以整个算法的时间复杂度为O(N),而空间复杂度为O(N*)效率已经很高了而且用程序实现起来也很容易至此我们已经很好的解决了该问题。小优化:只要仔细分析就会发现对于一种染色方案将树上的红色、蓝色结点的颜色互换得到的新树仍然满足条件而且这棵树上的绿色结点数并没有变化。由此我们也可以看出上述的动态规划方法还是存在一些重复和不必要的计算。我们可以重新定义一下数组。设:FI、FI表示以I为根的树点I染成绿色与不染成绿色可以得到的最多绿色结点数。那么我们可以列出如下动态转移方程:NumI=FI=FI=NumI=FI=FLFI=Max(FL,FL)NumI=FI=FLFRFI=Max(FLFR,FLFR)问题的最优值为:Max(F,F)用上面的动态转移方程可以少用一个一维数组并使时间复杂度进一步降低但是该算法并没有从本质上起到优化作用而且可读性和应用的广泛程度也不及前面的算法因此从整体上看这两个算法优越性差不多。总结:这是一道比较简单的动态规划试题该问题要想到动态规划方程很容易但要进一步求出Link数组的递推式却不是那么简单就能想到。从这一题也可以看出动态规划试题也可以通过从子问题上加大难度来提高整个问题的难度这样就使动态规划的考察面更广它就不仅仅是考察选手列出动态规划方程与优化动态规划算法(这里指主算法)的能力对于其它方面(如初始化)也可以考验选手构造和优化算法的能力。而我们也应该注意将各问题联系起来在自己头脑中形成一个思维网这对解好这一类问题是很有好处的。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/3

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利