![点击分享此内容可以赚币 分享](/master/images/share_but.png)
算法设计与分析基础课后习题答案(中文版).doc
《算法设计与分析基础课后习题答案(中文版).doc》由会员分享,可在线阅读,更多相关《算法设计与分析基础课后习题答案(中文版).doc(31页珍藏版)》请在咨信网上搜索。
1、Program算法设计与分析基础中文版答案习题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.对于第一个数小于第二个数的一对数字,欧几里得算法将会如
2、何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0=m0 temp2*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 b0 return c/b else /a=b=0 if c=0 return “no real numbers” else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答:
3、 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 doprint Bini;i-;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这
4、个算法做尽可能多的改进.算法 MinDistance(A0.n-1)/输入:数组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,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额
5、外空间for S and Count4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1=i0时,(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 all n=n0, c0 for all n=n0, c1=c0即:f(n)(g(n)又设f
6、(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(n) for all n=n2, where c20那么,取c=minc1,c2,当n=max
7、n1,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)=a2*g1(n)-(1)由t2(n)(g2(n)知,存在非负整数b1,b2和n2使: b1*g2(n)=t2(n)=b2*g2(n)-(2)(1)+(2):a1*g1(n)+ b1*g2(n)=t1(n)+t2(n)
8、= 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)2g1(n),即g1+g20,g1(n)+g2(n)g1(n),即g1+g2max(g1,g2)。则(3)式转换为:C1*max(g1,g2) = t1(n)+t2(n) =n0时上述不等式成立。证毕。习题2.41. 解下列递推关系 (做a,b)当n1时a. 解:当n1时b.解:2. 对于计算n!的递归算法F(n),建立其递归调用次数
9、的递推关系并求解。解:3. 考虑下列递归算法,该算法用来计算前n个立方的和:S(n)=13+23+n3。算法S(n) /输入:正整数n /输出:前n个立方的和if n=1 return 1else return S(n-1)+n*n*na. 建立该算法的基本操作次数的递推关系并求解b. 如果将这个算法和直截了当的非递归算法比,你做何评价?解:a.7. a. 请基于公式2n=2n-1+2n-1,设计一个递归算法。当n是任意非负整数的时候,该算法能够计算2n的值。 b. 建立该算法所做的加法运算次数的递推关系并求解 c. 为该算法构造一棵递归调用树,然后计算它所做的递归调用次数。 d. 对于该问题
10、的求解来说,这是一个好的算法吗?解:a.算法power(n)/基于公式2n=2n-1+2n-1,计算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 An-1a.该算法计算的是什么?b.建立该算法所做的基本操作次数的递推关系并求解解:a.计算的给定数组的最小值for
11、 all n1n=1b.9.考虑用于解决第8题问题的另一个算法,该算法递归地将数组分成两半.我们将它称为Min2(A0.n-1)算法 Min(Ar.l) If l=r return Al Else temp1Min2(Al.(l+r)/2) Temp2Min2(Al.(l+r)/2+1.r) If temp1temp2 return temp1 Else return temp2a.建立该算法所做的的操作次数的递推关系并求解b.算法Min1和Min2哪个更快?有其他更好的算法吗?解:a.习题2.6 1. 考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数.算法SortAnalys
12、is(A0.n-1)/input:包含n个可排序元素的一个数组A0.n-1/output:所做的关键比较的总次数count0for i1 to n-1 do vAi ji-1 while j0 and Ajv do countcount+1 Aj+1Aj jj+1 Aj+1vreturn count比较计数器是否插在了正确的位置?如果不对,请改正.解:应改为:算法SortAnalysis(A0.n-1)/input:包含n个可排序元素的一个数组A0.n-1/output:所做的关键比较的总次数count0for i1 to n-1 do vAi ji-1 while j0 and Ajv do
13、 countcount+1 Aj+1Aj jj+1 if j=0 count=count+1 Aj+1vreturn count习题3.14. a.设计一个蛮力算法,对于给定的x0,计算下面多项式的值:P(x)=anxn+an-1xn-1+a1x+a0并确定该算法的最差效率类型.b.如果你设计的算法属于(n2),请你为该算法设计一个线性的算法.C.对于该问题来说,能不能设计一个比线性效率还要好的算法呢?解:a. Algorithms BruteForcePolynomialEvaluation(P0.n,x)/由高幂到低幂用蛮力法计算多项式p在给定点x的值/输入:P0.n是多项式按低幂到高幂的
14、常系数,以及定值x/输出: 多项式p在给定点x的值p=0.0for i=n to 0 do power=1 for j=1 to i do power=power*x p=p+Pi*powerreturn p算法效率分析:基本操作:两个数相乘,且M(n)仅依赖于多项式的阶nb. tha above algorithms is very inefficient, because we recompute powers of x again and again as if there were no relationship among them.In fact ,we can move from
15、 the lowest term to the highest and compute xi by using xi-1.Algorithms BetterBruteForcePolynomialEvaluation(P0.n,x)/由高幂到低幂用蛮力法计算多项式p在给定点x的值/输入:P0.n是多项式按低幂到高幂的常系数,以及定值x/输出: 多项式p在给定点x的值 P=P0 power=1 for i1 to n do powerpower*x pp+Pi*power return p基本操作乘法运算总次数M(n):c.不行.因为计算任意一个多项式在任意点x的值,都必须处理它的n+1 个系数
16、.例如: (x=1,p(x)=an+an-1+.+a1+a0,至少要做n次加法运算) 5.应用选择排序对序列example按照字母顺序排序.6.选择排序是稳定的吗?(不稳定)7.用链表实现选择排序的话,能不能获得和数组版相同的(n2)效率?Yes.Both operationfinding the smallest element and swapping it can be done as efficiently with the linked list as with an array. 9.a.请证明,如果对列表比较一遍之后没有交换元素的位置,那么这个表已经排好序了,算法可以停止了.b.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整版 算法 设计 分析 基础 课后 习题 答案 中文版
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。