算法作业讲解

1、算法习题讲解Sch1-1:设n个不同的整数排好序后存于T1.n中，若存在一个下标i（1 i n），使得Ti=i。试设计一个有效算法找到这个下标，要求算法在最坏情形下的计算时间为O(log n)。解答要点：采用二分查找，当Tmidmid时，在前半部分寻找，当Tmidmid时，在后半部分需找，相等时即找到。Sch1-2：在一个由n个元素组成的表中，出现次数最多的元素被称为众数。试写一个寻找众数及其重数的有效算法，并分析其计算时间复杂性。解答要点：先排序，然后遍历一遍找到重复次数最多的元素。注意：这里不一定能用计数排序，因为题目没说明一定是整数。Sch1-3：设x=a+bi和y=c+di是两个复数，

2、只要做4次乘法就能够计算乘积xy=(ac-bd)+(ad+bc)i。试设计一个方法只用3次乘法计算乘积xy。解答要点：设法将ac、bd、ad和bc四次乘法变为只用3次乘法。保留ac、bd，于是(ad+bc)= (a+b)(c+d)-ac-bd只需计算ac、bd和(a+b)(c+d)三次乘法即可。15.2-1：对矩阵规模序列，求矩阵链最优括号化方案。解答要点：递归求解公式为：15.4-5：设计一个O(n2)时间的算法，求一个n个数的序列的最长单调递增子序列。解答要点：方法一：转化为求LCS对数组的一份拷贝进行排序，然后去重，最后与原序列求LCS。方法二：直接采用动态规划法设Lj表示以aj结尾的数

3、组序列的最长递增子序列长度，则Lj= max(Li)+1, ij且aiaj 注意：看清问题，题目要求的是单调递增。15.4-6:设计一个O(nlgn)的算法，求一个n个数的序列的最长单调递增子序列。解答要点：设Lj保存当前所有长度为j的子序列中尾元素最小的元素下标，对于第i个元素，由于aLi是非降的，可以使用二分查找找到最大的j，使得aLjai，记录当前以ai结尾的最长子序列的前一个元素在a中的位置，以便输出最长子序列。15-5：编辑距离问题。（题目太长，略）解答要点: (a)递归求解公式为：(b): (1)如果xj=yj，1分；对应的是copy操作； (2)如果xi!=yj并且两者都不是空格

4、，-1分；对应的是replace操作； (3)如果xj或者yj是空格，-2分，对应的是insert和delete操作。i1j1cost(copy) i1j1cost(replace) i2j2cost(tw iddle),2, 1 m ini1j1cost(delete)alw ays 1cost(insert)alw ayscif x iyjcif x iyjcif ijx iyjc ijand xyc ijc ij16.1-4：假定有一组活动，我们需要将他们安排到一些教室，任意活动都可以在任意教室进行，希望使用最少的教室完成所有活动。设计一个高效的贪心算法求每个活动应该在哪个教室进行。(区间图着色问题)解答要点：构造一个区间图，顶点表示给定的活动，边连接表示不兼容的活动，然后用最少的颜色对顶点进行着色，使得所有相邻顶点颜色均不相同。16.2-5：设计一个高效算法，对实数线上给定的一个点集x1,x2 xn，求一个单位长度闭区间集合，包含所有给定的点，并要求此集合最小。证明你的算法是正确的。解答要点：对点集进行排序得到y1,y2, yn，贪心的从左到右进行选择，比如选择 y1,y1 +1区间，则属于此区间内的点均可消去。注意：要求是单位长度闭区间集合。Sch2-1:作业分配问题，n个作业分配给n个人，使得总花