《算法分析与设计》作业参考答案
作业一
一、名词解释：
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] 答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。 （1）设比较一次花时间1； （2）内循环次数为：n-i次,（i=1,…n），花时间为： n?1?(n?i) j?1n?i 2.设计一个分治算法计算一棵二叉树的高度。 答：算法思想：对于二叉树T，若为空树，则其高度为0；否则，分别求其左子树和右子树的高度，最 大者加1 即为树T的高度。其描述如下： 1 n（3）外循环次数为：n-1，花时间为： T(n)??(n?i)?(n?1)2i?1int 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>=2 if(hight-low= =2) { if(A[low] 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。 2 作业二 一、名词解释： 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 个整数（可能为负整数）组成的序列a1a2 … 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)。 1?i?k，2.关于多段图问题。设G＝(V，E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi：其中，V1和Vk分别只有一个顶点s（称为源）和一个顶点t（称为汇），图中所有的边（u,v），u?Vi， v?Vi?1。求由s到t的最小成本路径。 （1）给出使用动态规划算法求解多段图问题的基本思想。 （2）使用上述方法求解如下多段图问题。 3