下载文档原格式
算法分析与设计（线下作业⼆）《算法分析与设计》学习中⼼：专业：学号：姓名：作业练习⼆⼀、名词解释1、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 }。
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 +∈。
算法设计与分析习题答案算法设计与分析是计算机科学中一个重要的领域，它涉及到算法的创建、优化以及评估。
以下是一些典型的算法设计与分析习题及其答案。
习题1：二分查找算法问题描述：给定一个已排序的整数数组，编写一个函数来查找一个目标值是否存在于数组中。
答案：二分查找算法的基本思想是将数组分成两半，比较中间元素与目标值的大小，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。
这个过程会不断重复，直到找到目标值或搜索范围为空。
```pythondef binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return Trueelif arr[mid] < target:low = mid + 1else:high = mid - 1return False```习题2：归并排序算法问题描述：给定一个无序数组，使用归并排序算法对其进行排序。
答案：归并排序是一种分治算法，它将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并成一个有序数组。
```pythondef merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1arr = [38, 27, 43, 3, 9, 82, 10]merge_sort(arr)print("Sorted array is:", arr)```习题3：动态规划求解最长公共子序列问题问题描述：给定两个序列，找到它们的最长公共子序列。
算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：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.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。
第一章习题（1-1,1-2,1-3,1-6）1-1 求下列函数的渐进表达式3n2+10n = O(n2)n2/10+2n = O(2n)21+1/n = O(1)logn3 = O(logn)10log3n = O(n)知识点：如果存在正的常数C和自然数N0，使得：当N>=N0时有f(N)<=Cg(N)，则称f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)).这时，可以说f(N)的阶不高于g(N)的阶。
1-2 论O(1)和O(2)的区别O(1)和O(2)差别仅在于其中的常数因子，根据渐进上界记号O的定义可知，O(1)=O(2)。
1-3 从低到高排列以下表达式（按渐进阶排列以下表达式）结果：2 logn n2/320n 4n23n n! 分析：当n>=1时，有logn< n2/3当n>=7时，有3n < n!补充：当n>=4时，有logn> n1/31-6 对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=Θ(g(n))。
知识点：f(n)的阶不高于g(n)的阶：f(n)=O(g(n))；f(n)的阶不低于g(n)的阶：f(n)=Ω(g(n))；f(n)与g(n) 同阶：f(n)=Θ(g(n)) (1)f(n)= logn2 ; g(n)= logn+5f(n)与g(n)同阶，故f(n)=Θ(g(n)) (2) f(n)= logn2 ; g(n)= n1/2当n>=8时，f(n)<=g(n)，故f(n)=O(g(n))分析：此类题目不易直接看出阶的高低，可用几个数字代入观察结果。
如依次用n=1, 21, 22, 23, 26, 28, 210 (3) f(n)= n ; g(n)= log2nf(n)=Ω(g(n))(4) f(n)= nlogn+n; g(n)= lognf(n)=Ω(g(n))(5) f(n)= 10 ; g(n)= log10f(n)=Θ(g(n))(6) f(n)= log2n ; g(n)= lognf(n)=Ω(g(n))(7) f(n)= 2n ; g(n)= 100 n2f(n)=Ω(g(n))(8) f(n)= 2n ; g(n)= 3nf(n)=O(g(n))。
算法设计与分析1、(1) 证明：O(f)+O(g)=O(f+g)（7分）(2) 求下列函数的渐近表达式：（6分）① 3n 2+10n;② 21+1/n;2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。
（15分）(1);5log )(;log )(2+==n n g n n f (2);)(;log )(2n n g n n f == (3);log )(;)(2n n g n n f == 3、试用分治法对数组A[n]实现快速排序。
（13分）4、试用动态规划算法实现最长公共子序列问题。
（15分）5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。
试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。
（12分）6、试用动态规划算法实现下列问题：设A 和B 是两个字符串。
我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括：(1)删除一个字符。
(2)插入一个字符。
(3)将一个字符改为另一个字符。
将字符串A 变换为字符串B 所用的最少字符操作数称为字符串A 到B 的编辑距离，记为d(A,B)。
试设计一个有效算法，对任给的两个字符串A 和B ，计算出它们的编辑距离d(A,B)。
（16分）⎣⎦2/)(;3)(i i g i i f ==。
对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。
（16分）1、⑴证明：令F(n)=O(f),则存在自然数n 1、c 1，使得对任意的自然数n ≥n 1，有：F(n)≤c 1f(n)……………………………..（2分）同理可令G(n)=O(g),则存在自然数n 2、c 2，使得对任意的自然数n ≥n 2，有：G(n)≤c 2g(n)……………………………..（3分）令c 3=max{c 1,c 2},n 3=max{n 1,n 2},则对所有的n ≥n 3，有： F(n)≤c 1f(n)≤c 3f(n)G(n)≤c 2g(n)≤c 3g(n)……………………………..（5分） 故有：O(f)+O(g)=F(n)+G(n)≤c 3f(n)+c 3g(n)=c 3(f(n)+g(n)) 因此有：O(f)+O(g)=O(f+g)……………………………..（7分） ⑵ 解：① 因为;01033)103(lim 222=+-+∞→n n n n n n 由渐近表达式的定义易知： 3n 2是3n 2+10n 的渐近表达式。
算法设计与分析第二版课后习题及解答算法设计与分析基础课后练习答案习题1.14.设计一个计算的算法,n是任意正整数。
除了赋值和比较运算,该算法只能用到基本的四则运算操作。
算法求 //输入:一个正整数n2//输出:。
step1:a1; step2:若a*an 转step 3,否则输出a; step3:aa+1转step 2;5. a.用欧几里德算法求gcd(31415,14142)。
b. 用欧几里德算法求gcd(31415,14142),比检查min{m,n}和gcd(m,n)间连续整数的算法快多少倍?请估算一下。
a. gcd31415, 14142 gcd14142, 3131 gcd3131, 1618 gcd1618, 1513 gcd1513, 105 gcd1513, 105 gcd105, 43 gcd43, 19 gcd19, 5 gcd5, 4 gcd4, 1 gcd1, 0 1.b.有a可知计算gcd(31415,14142)欧几里德算法做了11次除法。
连续整数检测算法在14142每次迭代过程中或者做了一次除法,或者两次除法,因此这个算法做除法的次数鉴于1?14142 和 2?14142之间,所以欧几里德算法比此算法快1?14142/11 ≈1300 与2?14142/11 ≈ 2600 倍之间。
6.证明等式gcdm,ngcdn,m mod n对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和rm mod nm-qn;显然,若d能整除n和r,也一定能整除mr+qn和n。
数对m,n和n,r具有相同的公约数的有限非空集,其中也包括了最大公约数。
故gcdm,ngcdn,r7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0mn的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcdm,ngcdn,m并且这种交换处理只发生一次.8.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?1次b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?5次gcd5,8习题1.21.农夫过河P?农夫W?狼 G?山羊 C?白菜2.过桥问题1,2,5,10---分别代表4个人, f?手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c0的实根,写出上述算法的伪代码可以假设sqrtx是求平方根的函数算法Quadratica,b,c//求方程ax^2+bx+c0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D0temp←2*ax1←-b+sqrtD/tempx2←-b-sqrtD/tempreturn x1,x2else if D0 return ?b/2*ael se return “no real roots”else //a0if b≠0 return ?c/belse //ab0if c0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答:a.将十进制整数转换为二进制整数的算法输入:一个正整数n输出:正整数n相应的二进制数第一步:用n除以2,余数赋给Kii0,1,2,商赋给n第二步:如果n0,则到第三步,否则重复第一步第三步:将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBinn//将十进制整数n转换为二进制整数的算法//输入:正整数n//输出:该正整数相应的二进制数,该数存放于数组Bin[1n]中i1while n!0 doBin[i]n%2;nintn/2;i++;while i!0 doprint Bin[i];i--;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.算法略对这个算法做尽可能多的改进.算法 MinDistanceA[0..n-1]//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements 习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.古老的七桥问题第2章习题2.17.对下列断言进行证明:如果是错误的,请举例a. 如果tn∈Ogn,则gn∈Ωtnb.α0时,Θαgn Θgn解:a这个断言是正确的。
算法设计与分析习题解答第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。
若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。
由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。
必要性。
同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。
2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。
由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。
3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。
证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。
4）log(n!)= Θ(nlogn)证明：由于log(n!)=∑=ni i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。
由于对所有的偶数n 有，log(n!)= ∑=ni i 1log ≥∑=nn i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。
《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1. 确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
3.3.算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。
4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。
时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。
最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6.简述二分检索（折半查找）算法的基本过程。
6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<x，则A[i：(i+j)/2-1]找x，否则在A[ (i+j)/2+1：j] 找x。
上述过程被反复递归调用。
7.背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。
目标函数：获得最大利润。
最优量度：最大利润/重量比。
8.采用回溯法求解的问题，其解如何表示？有什么规定？8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i<n)一定合理。
算法分析与设计试题及答案一、选择题1. 下列哪个是属于分治算法的例子？A. 冒泡排序B. 归并排序C. 顺序查找D. 选择排序答案：B2. 在排序算法中，时间复杂度最优的是：A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序答案：C3. 哪个不是动态规划的特点？A. 具有重叠子问题B. 通过递归求解C. 需要保存子问题的解D. 具有最优子结构答案：B4. 在图的广度优先搜索算法中，使用的数据结构是：A. 栈B. 队列C. 数组D. 堆栈答案：B5. 在最小生成树算法中，下列哪个不属于贪心策略？A. Kruskal算法B. Prim算法C. Dijkstra算法D. Prim-Kruskal混合算法答案：C二、简答题1. 请简述分治算法的思想和应用场景。
答案：分治算法的思想是将原问题分解成若干个规模较小且类似的子问题，然后解决子问题，最后将子问题的解合并得到原问题的解。
其应用场景包括排序算法（如归并排序、快速排序）、搜索算法（如二分查找）等。
2. 什么是动态规划算法？请给出一个动态规划算法的示例。
答案：动态规划算法是一种通过将问题分解成子问题并解决子问题来解决复杂问题的方法。
它的特点是具有重叠子问题和最优子结构性质。
以斐波那契数列为例，可以使用动态规划算法求解每一项的值，而不需要重复计算。
3. 图的深度优先搜索和广度优先搜索有什么区别？答案：图的深度优先搜索（Depth First Search，DFS）是一种先访问子节点再访问兄弟节点的遍历算法，通常使用递归或者栈实现。
而广度优先搜索（Breadth First Search，BFS）则是以层次遍历的方式展开搜索，使用队列来实现。
DFS更适合用于搜索路径，BFS则适用于寻找最短路径等。
4. 请简述贪心算法的特点及其应用场景。
答案：贪心算法的特点是每一步都采取当前状态下最优的选择，以期望得到全局最优解。
然而，贪心算法并不一定能求解所有问题的最优解，但对于一些特定问题，贪心算法往往能得到近似最优解。
算法分析与设计19春在线作业1-0002
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 40 分)
1.下列算法描述所用的方法是() Begin（算法开始）输入 A，B，C IF A>B 则 A→Max 否则B→Max IF C>Max 则 C→Max Print Max End （算法结束）
A.流程图
B.N-S流程图
C.伪代码表示
D.程序设计语言
答案:C
2.某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为（）。
A.n+1
B.n-1
C.2n
D.n/2
答案:A
3.下列叙述中正确的是（）
A.线性链表是线性表的链式存储结构
B.栈与队列是非线性结构
C.双向链表是非线性结构
D.只有根结点的二叉树是线性结构
答案:A
4.设有如下函数定义 int fun(int k) { if (k<1) return 0; else if(k==1) return 1; else return fun(k-1)+1; } 若执行调用语句：n=fun(3);，则函数fun 总共被调用的次数是()。
A.2
B.3
C.4
D.5
答案:B
5.strchr（）函数用来（）。
A.字符串连接
B.比较字符
C.求字符位置
D.求子串位置
答案:C
6.下面4句话中，最准确的表述是()。
A.程序=算法+数据结构
B.程序是使用编程语言实现算法
C.程序的开发方法决定算法设计。
《算法分析与设计》作业参考答案作业一一、名词解释：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+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 中效益达到最大。
