《算法分析与设计》作业参考答案作业一一、名词解释：1.递归算法：直接或间接地调用自身的算法称为递归算法。

2.程序：程序是算法用某种程序设计语言的具体实现。

二、简答题：1.算法需要满足哪些性质？简述之。

答：算法是若干指令的有穷序列，满足性质：（1）输入：有零个或多个外部量作为算法的输入。

（2）输出：算法产生至少一个量作为输出。

（3）确定性：组成算法的每条指令清晰、无歧义。

（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

答：将递归算法转化为非递归算法的方法主要有：（1）采用一个用户定义的栈来模拟系统的递归调用工作栈。

该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。

（2）用递推来实现递归函数。

（3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善，但其适用范围有限。

三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下：for i ←1 to n-1 do for j ←1 to n-i do if a[j]<a[j+1] then 交换a[j]、a[j+1]； 分析该算法的时间复杂性。

答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n 的关系。

（1）设比较一次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计一个分治算法计算一棵二叉树的高度。

答：算法思想：对于二叉树T ，若为空树，则其高度为0；否则，分别求其左子树和右子树的高度，最大者加1 即为树T 的高度。

其描述如下：)1(2)()(1-=-=∑=n ni n n T niint BTLength(BT T)//为了便于描述，假定二叉树类型为BT。

T 的左子树为T.lchild，右子树为T.rchild。

{if(T= =NULL) return 0; //T为空树return max(BTLength(T.lchild),BTLength(T.rchild)) +1}3.设计一个分治算法来判定给定的两棵二叉树T1 和T2 是否相同。

答：算法思想：对于两棵二叉树T1 和T2，若其根结点值相同，且其左右子树分别对应相同，则T1＝T2；否则T1≠T2。

其描述如下：boolean BTEQUAL(BT T1，BT T2)//为了便于描述，假定二叉树类型为BT。

二叉树T的左子树为T.lchild，右子树为T.rchild。

二叉树T的根结点值T.data。

{if(T1= =NULL&& T2= =NULL) return True; //均为空树if(T1&&T2&&T1.data==T2.data&&BTEQUAL(T1.lchild,T2.lchild)&&BTEQUAL (T1.rchild, T2.rchild))return True;return False;}4.给出一个分治算法来找出n 个元素的序列中的第2大元素，并分析算法的时间复杂度。

答：算法思想：当序列A[1..n]中元素的个数n=2 时，通过直接比较即可找出序列的第2 大元素。

当n>2 时，先求出序列A[1..n-1]中的第1 大元素x1 和第2 大元素x2；然后，通过2次比较即可在三个元素x1x2 和A[n]中找出第2 大元素，该元素即为A[1..n]中的第2 大元素。

算法描述如下：SecondElement(A[low..high],max1,max2){//假设主程序中调用该过程条件为high-low>=2if(hight-low= =2){if(A[low]<A[hight]){max2= A[low];max1=A[high];}else {max2= A[high];max1=A[low];}}else{SecondElement(A[low..high],x1,x2);if(x1<=A[n]) { max2=max1; max1=A[n];}else if(x2>=A[n]) { max2=x2; max1=x1; }else { max2=A[n]; max1=x1; }}}该算法的时间复杂度满足如下递归方程：T(n)=T(n-1)+2；T(2)=1。

解得T(n)=2n-3。

作业二一、名词解释：1.MST 性质：G=(V,E)是连通带权图，U 是V 的真子集。

如果(u,v)∈E ，且u ∈U ，v ∈V-U ，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G 的一棵最小生成树，它以(u,v)为其中一条边。

这个性质称为MST 性质。

2.子问题的重叠性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。

二、简答题：1.简述动态规划算法求解的基本要素。

动态规划算法求解的基本要素包括：（1）最优子结构是问题能用动态规划算法求解的前提；（2）动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。

2.备忘录方法和动态规划算法相比有何异同？简述之。

备忘录方法是动态规划算法的变形。

与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。

备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。

因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。

3.贪心算法求解的问题主要具有哪些性质？简述之。

贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个基本要素；另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

三、算法编写及算法应用分析题：1.设计求解如下最大子段和问题的动态规划算法。

只需给出其递推计算公式即可。

最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a 1a 2 … an ，求该序列形如Σi ≤k ≤j ak 的子段和的最大值。

当所有整数均为负整数时定义其最大子段和为0。

依次定义，所求的最优值为max{0, max1≤i ≤j ≤n Σi ≤k ≤j ak }。

答：下面给出求解该问题的动态规划算法中的递推计算公式。

记 b (j )=max1≤i ≤j {Σi ≤k ≤j ak }，1≤j ≤n ，则所求最大子段和为max1≤j ≤nb (j )。

而计算b [j ]的递推计算公式为：b (0)=0 b (j )=max{b (j -1)+aj , aj }， 1≤j ≤n 。

该算法的时间复杂度为O(n )；空间复杂度为O(n )。

2.关于多段图问题。

设G ＝(V ，E)是一个赋权有向图，其顶点集V 被划分成k>2个不相交的子集V i ：1i k ≤≤，其中，V 1和V k 分别只有一个顶点s （称为源）和一个顶点t （称为汇），图中所有的边（u,v ），i u V ∈，1i v V +∈。

求由s 到t 的最小成本路径。

（1）给出使用动态规划算法求解多段图问题的基本思想。

（2）使用上述方法求解如下多段图问题。

s tV1V2V3V4V5解：（1）基本思想：设P(i,j)是从Vi 中的节点j 到汇点t 的最小成本路径，Cost(i,j)是其成本。

则i+1Cost(i,j)=min{c(j,h)+Cost(i+1,h)|h V ,(j,h)E}∈∈。

边界条件是（1）若h=t ，则Cost(h,t)＝0；（2）Cost(k-1,j)＝c(j,t)。

（2）求解过程可以表示为：s tV1V2V3V4V5其中每个节点标示的序偶(p,q)中，p 表示节点到t 的成本，q 表示后继节点的编号。

从而，最优路径为：1→2→7→10→12和1→3→6→10→12，成本为16。

3.最优二元归并问题：已知将两个分别包含 a 个和b 个记录的已分类文件归并在一起得到一个分类文件需作a +b 次记录移动。

现有n 个已分类文件F 1,F 1,⋯,Fn ，它们的记录个数分别为l 1, l 2,⋯, ln 。

现在考虑使用二元归并模式将这n 个文件归并成一个分类文件，要求记录移动次数最少。

设计一个贪心算法来求解一种最优的二元归并（即记录移动次数最少的二元归并）。

答：（1）贪心准则：依次将文件序列中记录最少的两个文件进行归并成一个文件，直到文件序列中只剩下一个文件为止。

（2）贪心算法：Algorithm BINARYTREE输入：n 个单结点二元树列表L ，这些棵树的根结点的权分别为l 1, l 2,⋯, ln 。

输出：一棵最优二元归并树L BeginFor i ←1 To n -1 DoGETNODE(T ) //该过程产生一个新结点TLCHILD(T)←LEAST(L) //将表L 中其根权最小的树取出并作为T 的左孩子RCHILD(T)←LEAST(L) ////将表L 中其根权最小的树取出并作为T的右孩子WEIGHT(T)←WEIGHT(LCHILD(T))+WEIGHT(RCHILD(T))RepeatReturn(L)End.4.带限期的作业调度问题：n 个作业需要在一台机器上处理，每个作业可在单位时间内完成。

每个作业i都有一个截止期限di>0(di 为整数)，当且仅当作业i 在它的截止期限之前被完成，获得pi>0 的效益。

一种可行的调度方案为n 个作业的一个子集J，其中J 中的每个作业都能在各自的截止期限内完成。

该可行调度方案的效益是J 中作业的效益之和。

试设计贪心算法求效益最大的可行调度方案（即最优调度方案）。

答：（1）贪心准则：从J=开始，不断添加作业到J 中。

每次加入J 的作业是保证J 是可行的前提下使得J 中效益达到最大。