tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 理学 >>

算法设计与分析基础课后习题答案(中文版)


Program 算法设计与分析基础中文版答案 习题 1.1 5..证明等式 gcd(m,n)=gcd(n,m mod n)对每一对正整数 m,n 都成立. Hint: 根据除法的定义不难证明: ? 如果 d 整除 u 和 v, 那么 d 一定能整除 u±v; ? 如果 d 整除 u,那么 d 也能够整除 u 的任何整数倍 ku. 对于任意一对正整数 m,n,若 d 能整除 m 和 n,那么 d 一定能整除 n 和 r=m mod n=m-qn;显 然,若 d 能整除 n 和 r,也一定能整除 m=r+qn 和 n。 数 对 (m,n) 和 (n,r) 具 有 相 同 的 公 约 数 的 有 限 非 空 集 , 其 中 也 包 括 了 最 大 公 约 数 。 故 gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输 入的过程中,上述情况最多会发生几次? Hint: 对于任何形如 0<=m gcd(m,n)=gcd(n,m) 并且这种交换处理只发生一次. 7.a.对于所有 1≤m,n≤10 的输入, Euclid 算法最少要做几次除法?(1 次) b. 对于所有 1≤m,n≤10 的输入, Euclid 算法最多要做几次除法?(5 次) gcd(5,8) 习题 1.2 1.(农夫过河 ) P—农夫 W—狼 G—山羊 C—白菜 2.(过桥问题) 1,2,5,10---分别代表 4 个人, f—手电筒 4. 对于任意实系数 a,b,c, 某个算法能求方程 ax^2+bx+c=0 的实根,写出上述算法的伪代码(可 以假设 sqrt(x)是求平方根的函数) 算法 Quadratic(a,b,c) //求方程 ax^2+bx+c=0 的实根的算法 //输入:实系数 a,b,c //输出:实根或者无解信息 If a≠0 D←b*b-4*a*c If D>0 temp←2*a x1←(-b+sqrt(D))/temp x2←(-b-sqrt(D))/temp return x1,x2 else if D=0 return –b/(2*a) else return “no real roots” else //a=0 if b≠0 return –c/b else //a=b=0 if c=0 return “no real numbers” else return “no real roots” 5. 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答: a.将十进制整数转换为二进制整数的算法 输入:一个正整数 n 输出:正整数 n 相应的二进制数 第一步:用 n 除以 2,余数赋给 Ki(i=0,1,2...),商赋给 n 第二步:如果 n=0,则到第三步, 否则重复第一步 第三步:将 Ki 按照 i 从高到低的顺序输出 b.伪代码 算法 DectoBin(n) //将十进制整数 n 转换为二进制整数的算法 //输入:正整数 n //输出:该正整数相应的二进制数,该数存放于数组 Bin[1...n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做

尽可能多的改进. 算法 MinDistance(A[0..n-1]) //输入:数组 A[0..n-1] //输出:the smallest distance d between two of its elements 习题 1.3 1. 考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数, 然后利 用这个信息,将各个元素放到有序数组的相应位置上去 . 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.(古老的 七桥问题) 习题 1.4 1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除 数组的第 i 个元素(1<=i<=n) b.删除有序数组的第 i 个元素(依然有序) hints: a. Replace the ith element with the last element and decrease the array size of 1 b. Replace the ith element with a special symbol that cannot be a value of the array’s element(e.g., 0 for an array of positive numbers ) to mark the ith position is empty. (―lazy deletion‖) 第 2 章 习题 2.1 7.对下列断言进行证明:(如果是错误的,请举例) a. 如果 t(n)∈O(g(n),则 g(n)∈Ω(t(n)) b.α>0 时,Θ(αg(n))= Θ(g(n)) 解: a. 这个断言是正确的。它指出如果 t(n)的增长率小于或等于 g(n)的增长率,那么 g(n)的增 长率大于或等于 t(n)的增长率 由 t(n)≤c·g(n) for all n≥n0, where c>0 1 则:()t(n)? g(n) for all n≥n0 cb. 这 个 断 言 是 正 确 的 。 只 需 证 明 ? (? g(n))? ? (g(n)),? (g(n))? ? (? 。 g(n)) 设 f(n)∈Θ(αg(n)),则有: f(n)? c? g(n) for all n> =n0, c>0 f(n)? c1g(n) for all n>=n0, c1=cα>0 即:f(n)∈Θ(g(n)) 又设 f(n)∈Θ(g(n)),则有:f(n)? cg(n) for all n>=n0,c>0 f(n)? c ? ? g(n)? c1? g(n) for all n>=n0,c1=c/α>0 即:f(n)∈Θ(αg(n)) 8.证明本节定理对于下列符号也成立: a.Ω 符号 b.Θ 符号 证明: a。we need to proof that if t1(n)∈Ω(g1(n)) and t2(n)∈Ω(g2(n)), then t1(n)+ t2(n)∈Ω(max,g1(n), g2(n)})。 由 t1(n)∈Ω(g1(n)), t1(n)≥c1g1(n) for all n>=n1, where c1>0 由 t2(n)∈Ω(g2(n)), T2(n)≥c2g2(n) for all n>=n2, where c2>0 那么,取 c>=min{c1,c2},当 n>=max{n1,n2}时:

t1(n)+ t2(n)≥c1g1(n)+ c2g2(n) ≥c g1(n)+c g2(n)≥c*g1(n)+ g2(n)+ 命题成立。 b. t1(n)+t2(n) ∈Θ(max(g1(n),g2(n)))

≥cmax, g1(n), g2(n)- 所以以

证明:由大? 的定义知,必须确定常数 c1、c2 和 n0,使得对于所有 n>=n0,有: c1max((g1(n),g2(n))? t1(n)? t2(n)? max(g1(n),g2(n)) 由 t1(n)∈Θ(g1(n))知,存在非负整数 a1,a2 和 n1 使: (1) 由 t2(n)∈Θ(g2(n))知,存在非负整数 b1,b2 和 n2 使: (2) (1)+(2): a1*g1(n)<=t1(n)<=a2*g1(n)----b1*g2(n)<=t2(n)<=b2*g2(n)-----

a1*g1(n)+ b1*g2(n)<=t1(n)+t2(n) <= a2*g1(n)+ b2*g2(n) 令 c1=min(a1,b1),c2=max(a2,b2),则 C1*(g1+g2)<= t1(n)+t2(n) <=c2(g1+g2)-----(3) 不失一般性假设 max(g1(n),g2(n))=g1(n). 显然,g1(n)+g2(n) 又 g2(n)>0,g1(n)+g2(n)>g1(n),即 g1+g2>max(g1,g2)。 则(3)式转换为: C1*max(g1,g2) <= t1(n)+t2(n) <=c2*2max(g1,g2) 所以当 c1=min(a1,b1),c2=2c2=2max(c1,c2), n0=max(n1,n2)时,当 n>=n0 时上述不等式成立。 证毕。 习题 2.4 1. 解下列递推关系 (做 a,b) a. ? x(n)? x(n? 1)? 当5 n>1 时 ? ? x(1)? 解: 0 b. ? ? x(n)? 3x(n? 当 1) n>1 时 ? x(1)? 4 解: 2. 对于计算 n!的递归算法 F(n),建立其递归调用次数的递推关系并求解。 解: 3. 考虑下列递归算法,该算法用来计算前 n 个立方的和:S(n)=13+23+…+n3。算法 S(n) //输入:正整数 n //输出:前 n 个立方的和 if n=1 return 1 else return S(n-1)+n*n*n a. 建立该算法的基本操作次数的递推关系并求解 b. 如果将这个算法和直截了当的非递归算法比,你做何评价? 解: a. 7. a. 请基于公式 2n=2n-1+2n-1,设计一个递归算法。当 n 是任意非负整数的时候,该算法 能够计算 2n 的值。 b. 建立该算法所做的加法运算次数的递推关系并求解 c. 为该算法构造一棵递归调用树,然后计算它所做的递归调用次数。 d. 对于该问题的求 解来说,这是一个好的算法吗? 解: a.算法 power(n) //基于公式 2n=2n-1+2n-1,计算 2n //输入:非负整数 n //输出: 2n 的值 If n=0 return 1 Else return power(n-1)+ power(n-1) c. 习题 2.6 1. 考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数. 算法 SortAnalysis(A[0..n-1]) //input: 包含 n 个可排序元素的一个数组 A[0..n-1] //output: 所做的关键比较的总次数

count←0 for i←1 to n-1 do v←A*i+ j←i-1 while j>0 and A*j+>v do count←count+1

A*j+1+←A*j+

j←j+1 A*j+1+←v return count

比较计数器是否插在了正确的位置?如果不对,请改正. 解:应改为: 算法 SortAnalysis(A[0..n-1]) //input: 包含 n 个可排序元素的一个数组 A[0..n-1] //output: 所做的关键比较的总次数 count←0 for i←1 to n-1 do v←A*i+ j←i-1 while j>0 and A*j+>v do count←count+1 A*j+1+←A*j+ j←j+1 if j>=0 count=count+1 A*j+1+←v return count 6.选择排序是稳定的吗?(不稳定) 7.用链表实现选择排序的话,能不能获得和数组版相同的 Θ(n2)效率? Yes.Both operation—finding the smallest element and swapping it –can be done as efficiently with the linked list as with an array. 9.a.请证明,如果对列表比较一遍之后没有交换元素的位置,那么这个表已经排好序了,算法可 以停止了. b.结合所做的改进,为冒泡排序写一段伪代码 . c.请证明改进的算法最差效率也是平方级的 . Hints: a. 第 i 趟冒泡可以表示为: 如果没有发生交换位置,那么: b.Algorithms BetterBubblesort(A[0..n-1]) //用改进的冒泡算法对数组 A[0..n-1]排序 //输入:数组 A[0..n-1] //输出:升序排列的数组 A[0..n-1] count←n-1 //进行比较的相邻元素对的数目 flag←true //交换标志 while flag do flag←false for i=0 to count-1 do if A[i+1] swap(A[i],A[i+1]) flag←true count←count-1 c 最差情况是数组是严格递减的,那么此时改进的冒泡排序会蜕化为原来的冒泡排序. 10.冒 泡排序是稳定的吗?(稳定) 习题 3.2 1. 对限位器版的顺序查找算法的比较次数: a. 在最差情况下 b. 在平均情况下.假设成功查找的概率是 p(0<=p<=1) Hints: a. Cworst(n)=n+1 b. 在成功查找下,对于任意的 I,第一次匹配发生在第 i 个位置的可能性是 p/n,比较次数是 i.在 查找 不成功时,比较次数是 n+1,可能性是 1-p. 6.给出一个长度为 n 的文本和长度为 m 的模式构成的实例,它是蛮力字符串匹配算法的一个 最差输入.并指出,对于这样的输入需要做多少次字符比较运算. Hints: 文本:由 n 个 0 组成的文本 模式:前 m-1 个是 0,最后一个字符是 1 比较次数: m(n-m+1) 7.为蛮力字符匹配算法写一个伪代码,对于给定的模式,它能够返回给定的文本中所有匹配子 串的数量. Algorithms BFStringmatch(T[0..n-1],P[0..m-1]) //蛮力字符匹配 //输入:数组 T[0..n-1]—长度为 n 的文本,数组 P[0..m-1]—长度为 m 的模式 //输出:在文本中匹

配成功的子串数量 count←0 for i←0 to n-m do j←0 while j count←count+1 return count 8.如果所要搜索的模式包含一些英语中较少见的字符 ,我们应该如何修改该蛮力算法来利用 这个信息. Hint:每次都从这些少见字符开始比较,如果匹配, 则向左边和右边进行其它字符的 比较. else if r-l=1 //有两个元素时 if A*l+≤A*r+ Max←A*r+; Min←A*l+ else Max←A*l+; Min←A*r+ else //r-l>1 MaxMin(A[l,(l+r)/2],Max1,Min1); //递归解决前一部分 MaxMin(A[(l+r/)2..r],Max2,Min2); //递归 解决后一部分 if Max1<Max2 Max= Max2 //从两部分的两个最大值中选择大值 if Min2 } b.假设 n=2k,比较次数的递推关系式: C(n)=2C(n/2)+2 for n>2 C(1)=0, C(2)=1 C(n)=C(2k)=2C(2k-1)+2 =2[2C(2k-2)+2]+2 =22C(2k-2)+22+2 =22[2C(2k-3)+2]+22+2 =23C(2k-3)+23+22+2 ... =2k-1C(2)+2k-1+2k-2+...+2 //C(2)=1 =2k-1+2k-1+2k-2+...+2 //后面部分为等比数列求和 =2k-1+2k-2 //2(k-1)=n/2,2k=n =n/2+n-2 =3n/2-2 b.蛮力法的算法如下: 算法 simpleMaxMin(A[l..r]) //用蛮力法得到数组 A 的最大值和最小值 //输入:数值数组 A[l..r] //输出:最大值 Max 和最小值 Min Max=Min=A[l]; for i=l+1 to r do if A*i+>Max Max←A*i+; else if A*i+ 时间复杂度 t(n)=2(n-1) 算法 MaxMin 的时间复杂度为 3n/2-2,simpleMaxMin 的时间复杂度为 2n-2,都属于 Θ(n), 但比较一下发现,MaxMin 的速度要比 simpleMaxMin 的快一些。 6.应用合并排序对序列 E,X,A,M,P,L,E 按字母顺序排序. c. 键值比较次数 M(n) M(n)=2M(n)+2n for n>1 M(1)=0 习题 4.2 1.应用快速排序对序列 E,X,A,M,P,L,E 按字母顺序排序 4. 请举一个 n 个元素数组的例子,使得我们有必须对它使用本节提到的”限位器”.限位器的值 应是多少 年来?为什么一个限位器就能满足所有的输入呢? Hints: With the pivot being the leftmost element, the left-to-right scan will get out of bounds if and only if the pivot is larger than the other elements. Appending a sentinel(限位器) of value equal A*0+(or larger than A*0+) after the array’s last element , the quicksort algorithms will stop the index of the left-to-right scan of A[0..n-1] from

going beyond position n. 8.设计一个算法对 n 个实数组成的数组进行重新排列,使得其中所有的负元素都位于正元素 之前.这个算法需要兼顾空间和时间效率. Algorithms netbeforepos(A[0..n-1]) //使所有负元素位于正元素之前 //输入:实数组 A[0..n-1] //输出:所有负元素位于于正元素之前的实数组 A[0..n-1] A[-1+←-1; A*n+←1 //限位器 i←0; j←n-1 While i While A*i+≤0 do i←i+1 while A*j+≥0 do j←j-1 swap A[i]and A[j] swap A[i]and A[j] //undo the last swap 当全是非负数或全是非正数时需要限位器. 习题 4.3 1.(题略) 习题 5.1 2.a.设计一个递归的减一算法,求 n 个实数构成的数组中最小元素的位置. b.确定该算法的时 间效率,然后把它与该问题的蛮力算法作比较 Algorithms MinLocation(A[0..n-1]) //find the location of the smallest element in a given array //an array A[0..n-1] of real numbers //An index of the smallest element in A[0..n-1] if n=1 return 0 else temp←MinLocation(A*0..n-2]) if A[temp] 时间效率分析见习题 2.4 中 8 C(n)=C(n-1)+1 for n>1 C(1)=0 4.应用插入排序对序列 example 按照字母顺序排序 5.a.对于插入排序来说,为了避免在内部循环的每次迭代时判断边界条件 j>=0,应该在待排序 数组的第一个元素前放一个什么样的限位器? b.带限位器版本和原版本的效率类型相同吗? 解: a. 应该在待排序数组的第一个元素前放-∞或者小于等于最小元素值的元素. b. 效率类型 相同.对于最差情况(数组是严格递减): 7.算法 InsertSort2(A[0..n-1]) for i←1 to n-1 do j←i-1 while j>=0 and A*j+>A*j+1+ do swap(A*j+,A*j+1+) j←j+1 分析 : 在教材中算法 InsertSort 的内层循环包括一次键值赋值和一次序号递减 , 而算法 InsertSort2 的内层循环包括一次键值交换和一次序号递减,设一次赋值和一次序号递减的时 间分别为 ca 和 cd,那么算法 InsertSort2 和算法 InsertSort 运行时间的比率是(3ca+cd)/(ca+cd) 习题 5.2 1.a.(略) b. 4. 习题 5.3 1. DFS 的栈状态: 退栈顺序: efgbcad 拓扑排序: dacbgfe b. 这是一个有环有向图.DFS 从 a 出发,?,遇到一条从 e 到 a 的回边. 4.能否利用顶点进入 DFS 栈的顺序(代替它们从栈中退出的顺序)来解决拓扑排序问题? Hints: 不能. 5. 对第 1 题中的有向图应用源删除算法. 拓扑序列: dabcgef 习题 5.4 4.下面是生成排列的 B.Heap 算法. 算法 HeapPermute(n)

//实现生成排列的 Heap 算法 //输入:一个正整数 n 和一个全局数组 A[1..n] //输出:A 中元素的全排列 If n=1 Write A Else For i←1 to n do HeapPermute(n-1) If n is odd Swap A[1] and A[n] n=2 for i=1 do Else swap A[i] and A[n] 对于 n=2,3,4 的情况,手工跟踪该算法. 解:对于

heappermute(1){write A 即 12} 这时 n not odd, so do A[1]与 A[2]互换,A=21 for i=2 do heappermute(1){write A 即 21} 对于 n=3 For i=1 do Heappermute(2){ heappermute(1) write A 即 123 这时 2 not odd,so,do A[1]与 A[2]互换, A=213 heappermute(1) write A 即 213 这时 2 not odd, do A[2]与 A[2]互换,A=213 } 由于 3 is odd,so do A[1]与 A[3]互换,A=312 For i=2 do Heappermute(2){ heappermute(1) write A 即 312 这时 2 not odd,so,do A[1]与 A[2]互换,A=132 heappermute(1) write A 即 132 这时 2 not odd, do A[2]与 A[2]互换,A=231 } 由于 3 is odd,so do A[1]与 A[3]互换,A=231 For i=3 do Heappermute(2) { heappermute(1) write A 即 231 这时 2 not odd,so,do A[1]与 A[2]互换, A=321 heappermute(1) write A 即 321 这时 2 not odd, do A[2]与 A[2]互换,A=321 } 由于 3 is odd,so do A[1]与 A[3]互换,A=123 n=4 的的情况: 习题 5.5 2. Hints: a. 减常因子 b. c. d.折半查找在最坏情况下的查找效率是 log2n+1.而 4.a. 5.a. 二叉查找树中最大值和最小值分别是树中最右边和最左边的结点 .因此,从根开始,沿着向左 的路径一直走到这样的结点:它的左孩子为空.这个结点里的值就是最小值.同理,可以找到最 大值.最后,这两个值做一次减法运算即可. 算法的效率: Θ(logn)+ Θ(logn)+ Θ(1)= Θ(logn) b.错误. 8. 不成立. 例如:列表{A,B},查找 A,二分查找只做 1 次比较.而在 2-3 树中查找则要做 2 次比较 习题 6.4 1. a. 乘法总次数 M(n) 加法总次数 A(n) 本文档下载自文档之家,www.doczj.com-免费文档分享平台,众多试卷、习题答案、公务

员考试、英语学习、法语学习、人力资源管理、电脑基础知识、学习计划、工作计划、工 作总结、活动策划、企业管理等文档分类免费下载;乐于分享,共同进步,转载请保留出 处:http://www.doczj.com/doc/7b83fadb76eeaeaad1f33083.html


推荐相关:

算法设计与分析基础课后习题答案(中文版).doc

算法设计与分析基础课后习题答案(中文版) - Program 算法设计与分析基础

算法设计与分析基础习题参考答案.doc

算法设计与分析基础习题参考答案 - 习题 1.1 5..证明等式 gcd(m,n

算法设计与分析课后习题解答.doc

算法设计与分析课后习题解答 - 算法设计与分析基础课后练习答案 习题 1.1 4

算法设计与分析基础课后习题答案(中文版).doc

算法设计与分析基础课后习题答案(中文版) - Program 算法设计与分析基础

算法设计与分析基础课后习题答案(中文版).doc

算法设计与分析基础课后习题答案(中文版) - Program 算法设计与分析基础

《算法设计与分析基础(第3版)》部分习题答案.doc

算法设计与分析基础(第3版)》部分习题答案 - 2017-2018-2 学期《算法分析 A》作业 作业一 学号:___ P135 2. a. 为一个分治算法编写伪代码,该算法...

算法设计与分析基础习题参考答案.doc

算法设计与分析基础习题参考答案 - levtin 潘彦译算法教程的详细参考答案。... 算法设计与分析基础习题参考答案_IT/计算机_专业资料。levtin 潘彦译算法教程的详细参考...

算法设计与分析基础课后习题答案solu4.pdf

算法设计与分析基础课后习题答案solu4_IT/计算机_专业资料。算法设计与分析基础(影印版)Anany Levitin 清华大学出版社 课后习题答案 ...

算法设计与分析基础课后习题答案solu10.pdf

算法设计与分析基础课后习题答案solu10_IT/计算机_专业资料。算法设计与分析基础(影印版)Anany Levitin 清华大学出版社 课后习题答案 ...

计算机算法设计与分析(第三版)课后习题答案详解_图文.pdf

计算机算法设计与分析(第三版)课后习题答案详解_IT/计算机_专业资料。 您的评论 发布评论 用户评价 计算机算法设计与分析(第三版)课后习题答案详解,如何下载 2018...

算法设计与分析第二版课后习题解答.doc

算法设计与分析第二版课后习题解答 - 算法设计与分析基础课后练习答案 习题 1.

计算机算法设计与分析(第三版)课后习题答案详解_图文.pdf

计算机算法设计与分析(第三版)课后习题答案详解 2018-06-29 07:30:08 不错,计算机算法设计与分析(第三版)课后习题答案详解 2018-06-28 22:09:28 ...

算法设计与分析基础课后习题答案solu5.pdf

算法设计与分析基础课后习题答案solu5_IT/计算机_专业资料。算法设计与分析基础(影印版)Anany Levitin 清华大学出版社 课后习题答案This...

计算机算法设计与分析课后题答案(第三版)王晓东.doc

计算机算法设计与分析课后题答案(第三版)王晓东_IT/计算机_专业资料。计算机算法设计与分析课后题答案(第三版)王晓东 电子工业出版社 ...

算法设计与分析基础课后习题答案solu3.pdf

算法设计与分析基础课后习题答案solu3_IT/计算机_专业资料。算法设计与分析基础(影印版)Anany Levitin 清华大学出版社 课后习题答案This...

算法设计与分析(第2版)-王红梅-胡明-习题答案.pdf

算法设计与分析(第2版)-王红梅-胡明-习题答案_工学_高等教育_教育专区。算法...算法设计与分析基础课后... 41页 1下载券 算法设计与分析-王红梅-... ...

算法设计与分析C++语言描述(陈慧南版)课后答案.doc

标签: 工学| 陈慧南| 算法|算法设计与分析C++语言描述(陈慧南版)课后答案_工学_高等教育_教育专区。书本课后习题答案,适合复习使用。 ...

算法设计与分析_王红梅_课后答案网(部分).doc

算法设计与分析_王红梅_课后答案网(部分) - 第六章 动态规划法 ? ? P1

算法设计与分析习题答案1-6章.doc

算法设计与分析习题答案1-6章 - 习题 1 1. 图论诞生于七桥问题。 出生于

算法设计与分析答案(2006).doc

算法设计与分析答案(2006) - 注:以上各项请同学用正楷字体认真填写。如因字

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com