文本内容:
习题
21.T1和T2是两棵有序树，其中每个结点都有一个标签，考虑树上的三种操作,删除一个子树、插入一个子树和更改一个结点的标签，请设计一个算法，求得从T1变化到T2所需要的最少操作数，要求写出递推方程，程序伪代码并分析时间复杂性
2.给定三个字符串A,B和C,设计一个多项式时间动态规划算法，求出它们的最长公共子序列，要求写出递归方程，算法伪代码并分析算法复杂性
3.考虑字符串变换操作，增加一个字符，删除一个字符以及修改一个字符，设增加字符操作的代价为i,删除字符操作代价为d,修改字符的代价为m,给定两个字符串S1和S2,设计一个动态规划算法，求得从S1变换到S2代价最小的变换序列，要求写出递推方程，程序伪代码并分析算法复杂性
4.将一根木棒折成若干份，每折一次的代价是当前这段木棒的长度，总代价是折这根木棒直到满足要求所需要的所有操作的代价例如，将一根长度为10的木棒折成四段，长度分别为2,2,3,3,如果先折成长度为2和8的两段，再将长度为8的折成长度为2和6的两段，最后将长度为6的折成长度为3的两段，这些操作的代价是10+8+6=24；如果先折成长度为4和6的两段，在分别将长度为4的折成长度为2的两段、长度为6的折成长度为3的两段，则这些操作的代价是10+4+6=20,比上一种方案更好一些该问题的输入是木棒的长度L和一些整数cl,…,cn,要求将木棒折成长度为cl,cn的n段且操作代价最小，请设计动态规划算法解决该问题
5.满足递归式/〃=2〃-l+F〃-2和初始值方0=Fl=l的数列称为斐波那契数列考虑如何计算该数列的第〃项551说明根据递归式直接完成计算，将有子问题重复求解；2说明该问题具有优化子结构；3写出求解网〃的动态规划算法，并分析算法的时间复杂性
6.输入是具有n个数的向量x,输出时输入向量的任何连续子向量的最大和，要求写出递归方程、伪代码并分析时间和空间复杂度
7.令〃，…，左是〃个区间，其中任一区间〃=出力假设这些区间按照历•从小到大排序，每一个区间有一个权重应.找一个互不相交区间的集合，使得这些区间的权重之和最大，例如II=1,2,v1=
0.9;12=2,3,v2=
0.5;13=1,4,v3=4;14=4,5,v4=2,解是｛13,14｝给出解决问题P2的动态规划算法，要求写出递归方程和伪代码，并分析算法时间空间复杂性
8.在一个圆形操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆规定每次只能选择相邻的两堆石子合并成新的一堆，并将新一堆石子数记为该次合并的得分试设计一个动态规划算法，计算出将n堆石子合并成一堆的最小得分和最大得分，要求列出递归方程，写出算法的伪代码并分析算法的时间空间复杂性
9.给定两个字符串sl,s2,其上的操作包括增加一个字符、删除一个字符、修改一个字符和交换两个相邻的字符，其中增加和删除一个字符和交换相邻字符的代价均为1,将字符a修改为字符b的代价记作Ca,b,写出一个动态规划算法求出从si变化为s2代价最小的变化序列，要求写出递推方程和伪代码并分析时间复杂性
10.设有n种不同面值的硬币，面值分别为cl,c2,....,cn分钱，求用最少个数硬币来找K分钱的策略要求写出递归方程、伪代码并分析时间和空间复杂度。
个人认证
优秀文档
获得点赞 0
