《(最新整理)算法设计与分析基础课后习题答案(中文版)》由会员分享，可在线阅读，更多相关《(最新整理)算法设计与分析基础课后习题答案(中文版)（59页珍藏版）》请在金锄头文库上搜索。
1、(完整)算法设计与分析基础课后习题答案(中文版)(完整)算法设计与分析基础课后习题答案(中文版) 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)算法设计与分析基础课后习题答案(中文版)）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为(完整)算法设计与分析基础课后习题答案(中文版)的全部内容。1Program算法设
2、计与分析基础中文版答案习题1。1 5。.证明等式gcd(m,n）=gcd(n,m mod n)对每一对正整数m，n都成立。Hint:根据除法的定义不难证明: l 如果d整除u和v， 那么d一定能整除uv； l 如果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。对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理？该算法在处
3、理这种输入的过程中，上述情况最多会发生几次？Hint：对于任何形如0=mn的一对数字，Euclid算法在第一次叠代时交换m和n， 即gcd（m,n)=gcd(n,m）并且这种交换处理只发生一次.7.a。对于所有1m,n10的输入, Euclid算法最少要做几次除法？(1次） b. 对于所有1m，n10的输入, Euclid算法最多要做几次除法?（5次) gcd(5，8）习题1。2 1。（农夫过河)P农夫 W狼 G山羊 C白菜2.(过桥问题）1,2,5，10-分别代表4个人， f手电筒4. 对于任意实系数a,b，c， 某个算法能求方程ax2+bx+c=0的实根，写出上述算法的伪代码(可以假设sq
4、rt(x）是求平方根的函数)算法Quadratic(a，b，c）/求方程ax2+bx+c=0的实根的算法/输入：实系数a,b，c/输出:实根或者无解信息If a0 Dbb-4a*c If D0 temp2a x1(-b+sqrt(D)）/temp x2（-b-sqrt(D)）/temp return x1，x2 else if D=0 return b/(2a） else return “no real roots”else /a=0 if b0 return c/b else /a=b=0 if c=0 return “no real numbers” else return “no rea
5、l roots”5。 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答： a。将十进制整数转换为二进制整数的算法 输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1，2。.），商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b。伪代码 算法 DectoBin（n）/将十进制整数n转换为二进制整数的算法/输入:正整数n/输出：该正整数相应的二进制数，该数存放于数组Bin1.。n中i=1while n！=0 do Bini=n%2；n=（int)n/2；i+；while i!=0 dop
6、rint Bini;i-;9.考虑下面这个算法，它求的是数组中大小相差最小的两个元素的差。（算法略)对这个算法做尽可能多的改进。算法 MinDistance（A0.。n1）/输入：数组A0.。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，
7、98，14,47排序的过程如下所示：b。该算法不稳定.比如对列表2，2”排序c。该算法不在位。额外空间for S and Count4。（古老的七桥问题)习题1。41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a。删除数组的第i个元素（10时,(g(n）= （g（n）解：a。 这个断言是正确的。它指出如果t(n）的增长率小于或等于g(n)的增长率，那么 g（n）的增长率大于或等于t(n）的增长率 由 t（n)cg(n) for all nn0， where c0 则： for all nn0b. 这个断言是正确的。只需证明。设f(n）(g(n）,则有： for
8、all n=n0, c0 for all n=n0, c1=c0即：f(n)（g(n)又设f(n）（g（n）,则有: for all n=n0，c0 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)（maxg1（n）， g2（n)）。由 t1（n）（g1（n）， t1(n)c1g1（n) for all n=n1， where c10由 t2(n）（g2（n), T2（n)c2g2
9、(n） for all n=n2， where c20那么，取c=minc1,c2，当n=maxn1,n2时： t1(n）+ t2(n)c1g1（n）+ c2g2（n） c g1（n）+c g2（n）cg1（n）+ g2(n) cmax g1(n), g2(n)所以以命题成立。b。 t1（n）+t2（n） (证明:由大的定义知,必须确定常数c1、c2和n0，使得对于所有n=n0，有:由t1（n）(g1(n）知，存在非负整数a1，a2和n1使: a1*g1（n)=t1(n)=a2g1(n）-（1）由t2(n）(g2（n）知，存在非负整数b1,b2和n2使： b1*g2(n）=t2（n）=b2*g
10、2(n）-(2）（1)+(2)：a1*g1（n）+ b1*g2(n)=t1(n）+t2(n) = a2*g1（n)+ b2g2（n)令c1=min（a1,b1)，c2=max（a2，b2），则 C1*（g1+g2）= t1(n）+t2（n) 0，g1（n）+g2(n）g1（n）,即g1+g2max(g1,g2）。则（3）式转换为：C1max(g1,g2) = t1(n）+t2（n） =c2*2max（g1，g2）所以当c1min(a1,b1)，c22c2=2max(c1，c2)，n0max（n1,n2)时，当n=n0时上述不等式成立。证毕。习题2。41. 解下列递推关系 （做a，b）当n1时a
11、。 解：当n1时b。解：2. 对于计算n!的递归算法F（n)，建立其递归调用次数的递推关系并求解。解：3. 考虑下列递归算法,该算法用来计算前n个立方的和：S(n）=13+23+n3。算法S（n） /输入：正整数n /输出：前n个立方的和if n=1 return 1else return S(n1）+n*n*na。 建立该算法的基本操作次数的递推关系并求解b。 如果将这个算法和直截了当的非递归算法比，你做何评价？解：a。7. a。 请基于公式2n=2n-1+2n-1，设计一个递归算法。当n是任意非负整数的时候，该算法能够计算2n的值. b. 建立该算法所做的加法运算次数的递推关系并求解 c.
12、 为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。 d. 对于该问题的求解来说，这是一个好的算法吗?解:a.算法power（n)/基于公式2n=2n1+2n1,计算2n/输入:非负整数n/输出： 2n的值If n=0 return 1Else return power（n-1）+ power（n-1）c。8。考虑下面的算法 算法 Min1(A0.n-1） /输入：包含n个实数的数组A0。.n-1 If n=1 return A0 Else tempMin1（A0。n-2) If tempAn-1 return temp Else return An1a。该算法计算的是什么?b。建立该算法所做的基本操作次数的递推关系并求解解:a。计算的给定数组的最小值for all n
