下载文档原格式
算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。
2.程序：程序是算法⽤某种程序设计语⾔的具体实现。
⼆、简答题：1.算法需要满⾜哪些性质？简述之。
答：算法是若⼲指令的有穷序列，满⾜性质：（1）输⼊：有零个或多个外部量作为算法的输⼊。
（2）输出：算法产⽣⾄少⼀个量作为输出。
（3）确定性：组成算法的每条指令清晰、⽆歧义。
（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。
2.简要分析分治法能解决的问题具有的特征。
答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质；（3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。
3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。
答：将递归算法转化为⾮递归算法的⽅法主要有：（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。
该⽅法通⽤性强，但本质上还是递归，只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。
（2）⽤递推来实现递归函数。
（3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。
后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。
三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]交换a[j]、a[j+1]；分析该算法的时间复杂性。
答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。
（1）设⽐较⼀次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。
算法：EX5_33输入：已排序的数组A[1,…,n]，整数x输出：如果A中存在两个数，它们的和是x，则输出这两个数，若不存在，则输出none find(1,n)end EX5_33过程：find(s,t)// 确定A[s,…,t]中是否存在两个数，它们的和是x，如果存在则输出这两个数，若不存在，则输出noneif s=t then output none;else if s<t thenif A[s]+A[t]=x thenoutput A[s],A[t];else if A[s]+A[t]>x then find(s,t-1);else A[s]+A[t] find(s+1,t);end ifend ifend find6.6EX6_6输入：输出：num=count(1,n,x);end EX6_6过程count(low,high,x)//if high=low thenif A[low]=x then return 1else return 0elsemid=(low+high)/2return count(low,mid)+count(mid+1,high)end ifend count递归出口high<low ?EX6_51输入：输出：h=high(R)return hend EX6_51过程high(T)//if T为空then return -1elseleft=high(T->left);right=high(T->right);return 1+max{left,right}end ifend high递归出口T->left == null and T->right==null then return 0 ? 全局变量？6.52算法SECONDV ALUE输入：正整数n和存储n个元素的数组a[1..n]输出：数组a的第二大元素(x1,x2)=secondvalue(1,n,a);return x2;end SECONDV ALUE过程secondvalue(low,high,a)//返回数对(x1,x2)其中x1>=x2if high-low=0 thenreturn (a[low],-∞); //这个地方有修改else if high-low=1 thenif a[high]>=a[low] thenreturn (a[high],a[low]);else return (a[low],a[high]);end ifend ifend ifmid=(low+high)/2;(x1,x2)=secondvalue(low,mid,a);(y1,y2)=secondvalue(mid+1,high,a);return x1,x2,y1,y2中最大和最小元素对;。
算法设计技巧与分析习题参考答案习题4.13(b)元素最⼤交换次数：A9~A5 各1次；A4~A3 各2次；A2最多3次；A1最多4次最多共需16次元素交换4.13另解：考虑第i个节点，其⼦节点为2i，则最多可交换1次；若⼦节点有⼦节点22i, 则最多可交换2次；若…..有⼦节点i×2k, 则最多可交换k次；因此有i×2k≤ 19求出满⾜上述不等式的最⼤的k值即可。
i=1时, k=4;i=2时, k=3;i=3或4时, k=2;i=5~9时, k=1;因此最多交换4+3+2×2+1×5=16次6.5 ⽤分治法求数组A[1…n]元素和，算法的⼯作空间是多少？输⼊：数组A[1…n]输出：数组的所有元素之和∑A[i] {i=1…n}SUM(low, high)1.if high = low then2.return A[low]3.else4.mid←?(low+high)/2?5.s1←SUM(low,mid)6.s2←SUM(mid+1, high)7.return s1+s28.end if⼯作空间：mid~Θ(logn), s1&s2~Θ(1)（后序遍历树，不断释放空间，故为常数Θ(1)），总的⼯作空间为Θ(logn).6.6 ⽤分治法求元素x在数组A中出现的频次。
freq(A[low, high], x)1.if high=low then2.if A[low]=x then3.return 14.else5.return 06.end if7.else8.mid ←?(low+high)/2?9.f1 ←freq(A[low, mid])10.f2 ← freq(A[mid+1, high])11.return f1+f212.end if复杂度:T(n)=T(?n/2?)+ T(?n/2?)≈2T(n/2) (设2k≤n<2k+1) =…=2k T(n/2k) =2k T(1) = n6.16修改后的MERGESORT算法最⼤⽐较次数(1)/2()2(/2)1n n if n m T nT n n if n m-≤=?+->最⼩⽐较次数1()2(/2)/2n if n m C nC n n if n m-≤=?+>令n/2k=m≥2，展开可知：T(n)= 2k T(n/2k) + kn - (2k-1)= n/m×m(m-1)/2 + nlog(n/m)- n/m+1= n(m-1)/2 + nlog(n/m) -n/m+1若T(n)=Θ(nlogn), 其中表达式有nm, nlogn, nlogm, n/m等. 有n/m < nlogm < nm且须有nm=O(nlogn), i.e., nm ≤ c·nlogn, 则须有m≤c·logn. 可令c=1,则m≤logn. 另⼀⽅⾯，C(n) = 2k C(n/2k)+kn/2 = n/m×(m-1) + (n/2)log(n/m)= Θ(nlogn)6.35split(A[low,...high])1. x←A[low] //备份为x2. while (low3. while (low0) --high;4. A[low] ←A[high]5. while (low6.A[high] ←A[low]7.}8.A[low] ← x//这时, low=high7.3 动态规划法计算⼆项式系数knC ，并分析其时间复杂度。
分治法1、二分搜索算法是利用（分治策略）实现的算法。
9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略）实现的算法。
34．实现合并排序利用的算法是（分治策略）。
实现大整数的乘法是利用的算法（分治策略）。
17．实现棋盘覆盖算法利用的算法是（分治法）。
29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。
不可以使用分治法求解的是（0/1背包问题）。
动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。
下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。
（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。
矩阵连乘问题的算法可由（动态规划算法B）设计实现。
实现最大子段和利用的算法是（动态规划法）。
贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。
回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。
剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。
分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。
分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
第4章书面作业参考答案：一、 设计递归算法求解如下多项式:解：(1)tempi = x 无3 兀2/(2)=无一耳=/(1) + (—1)•⑹妙 1•丽 /(3) = x 一 寺 + 字/(2) + (― 1) • tempi •三 temp3 = (-!)• tempi •三 根据推导得递归方程为：/(I) = x, temp[l]=无(基础步)兀2temp[n] = (-1) - temp[n 一 1] --- : ------- f(n) = / (/? 一 1) +temp[n^ 归纟内) (2〃一2)(2斤一1)(2)时间复杂性分析：[ r(i)= o(i)= T(n -1) + 0(1)用递推法求解：(未求解不扣分)T(n) = T(n -1) + 0(1) = T(n -2)4- 0(1) • 2 =…=T(l) + 0(1)・(n-1) =0(H ) 其中，递归算法描述如下：(未写算法不扣分)输入：x, n输岀:f(x)的前n 项之和double Fun (double x, int n , double &temp)if(n==1) (1) (2) 3 57 X X X / 八〃 ——+ ------------------ + …+ (— 1)" 3! 5! 7!写岀递归表达式(基础步、归纳步)。
f (x) = x 2+1 (2/? + 1)!分析时间复杂度。
(写出递归方程，不用求解)f(l)F 无2tempi - (-!)• tempi・temp = x; return x;}double tempi,lastvalue; lastvalue = Fun (x,n-1,tempi);temp = (-1 )*temp1 *x*x/((2*n-1 )*(2*n-2)); return lastvalue + temp;二、P114 22解：(1)算法思想：划分步：将数组分为基本等长的两部分治理步：若n二2,则直接比较若n>2,则递归求两部分的最大值、次大值组合步：假设两部分求得的最大值和次大值分别为xl,yl； x2,y2。
