ImageVerifierCode 换一换
格式:DOC , 页数:42 ,大小:1.06MB ,
资源ID:3531443      下载积分:20 文钱
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,省得不是一点点
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-3531443.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: QQ登录   微博登录 

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(算法设计与分析基础习题解答.doc)为本站会员(sk****8)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!

算法设计与分析基础习题解答.doc

1、1习题 1.1 5.证明等式 gcd(m,n)=gcd(n,m mod n)对每一对正整数 m,n 都成立.Hint:根据除法的定义不难证明: 如果 d 整除 u 和 v, 那么 d 一定能整除 uv; 如果 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:对于任何形如 00temp2*ax1(-b+sqrt(D)/tempx2(-b-sqrt(D)/tempreturn x1,x2else if D=0 return b/(2*a)else return “no real roots”else /a=0if b0 return c/belse /a=b=0if c=0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答:a.

3、将十进制整数转换为二进制整数的算法 输入:一个正整数 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-13/输出: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.该算法不稳定.比如对

5、列表”2,2*” 排序c.该算法不在位 .额外空间 for S and Count44.(古老的七桥问题)习题 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 nn0)()1(ngtcb. 这个断言是正确的。只需证明 。)()(),()( ngng设 f(n)(g(n),则有

6、:for all n=n0, c0)()(cnffor all n=n0, c1=c01g即:f(n)(g(n)5又设 f(n)(g(n),则有: for all n=n0,c0)(ncgffor all n=n0,c1=c/0)()()(1nf即:f(n)(g(n)8证明本节定理对于下列符号也成立:a. 符号b. 符号证明:a。we need to proof that if t1(n)(g 1(n) and t2(n)(g 2(n), then t1(n)+ t2(n)(maxg 1(n), g2(n)。由 t1(n)(g 1(n),t1(n)c 1g1(n) for all n=n1,

7、where c10由 t2(n)(g 2(n),T2(n)c 2g2(n) for all n=n2, where c20那么,取 c=minc1,c2,当 n=maxn1,n2时:t1(n)+ t2(n)c 1g1(n)+ c2g2(n)c g 1(n)+c g2(n)cg 1(n)+ g2(n)cmax g 1(n), g2(n)所以以命题成立。b. t1(n)+t2(n) ( )(,max(n证明:由大的定义知,必须确定常数 c1、c2 和 n0,使得对于所有 n=n0,有:)(2,1max()(21)(2,1a( ngtgc 由 t1(n)(g1(n)知,存在非负整数 a1,a2和 n

8、1使:a1*g1(n)0,g1(n)+g2(n)g1(n),即 g1+g2max(g1,g2)。则(3)式转换为:C1*max(g1,g2) =n0时上述不等式成立。证毕。习题 2.41. 解下列递推关系 (做 a,b)a.解:b.解:2. 对于计算 n!的递归算法 F(n),建立其递归调用次数的递推关系并求解。解:0)1(5)xn4)1()3xn当 n1 时当 n1 时73. 考虑下列递归算法,该算法用来计算前 n 个立方的和:S(n)=13+23+n3。算法 S(n)/输入:正整数 n /输出:前 n 个立方的和if n=1 return 1else return S(n-1)+n*n*n

9、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/输出: 2 n的值If n=0 return 1Else return power(n-1)+ pow

10、er(n-1)8c. ninC012)(8.考虑下面的算法算法 Min1(A0.n-1)/输入:包含 n个实数的数组 A0.n-1If n=1 return A0Else tempMin1(A0.n-2)If tempAn-1 return tempElse return An-1a.该算法计算的是什么?b.建立该算法所做的基本操作次数的递推关系并求解解:a.计算的给定数组的最小值b. 01)()nC9.考虑用于解决第 8题问题的另一个算法,该算法递归地将数组分成两半.我们将它称为 Min2(A0.n-1)算法 Min(Ar.l)If l=r return AlElse temp1Min2(A

11、l.(l+r)/2)for all n1n=19Temp2Min2(Al.(l+r)/2+1.r)If temp1temp2 return temp1Else return temp2a.建立该算法所做的的操作次数的递推关系并求解b.算法 Min1和 Min2哪个更快?有其他更好的算法吗?解:a.习题 2.6 1. 考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数.算法 SortAnalysis(A0.n-1)/input:包含 n个可排序元素的一个数组 A0.n-1/output:所做的关键比较的总次数count0for i1 to n-1 do vAiji-1while j0 and Ajv do countcount+1Aj+1Ajjj+1Aj+1vreturn count比较计数器是否插在了正确的位置?如果不对,请改正.解:应改为:算法 SortAnalysis(A0.n-1)/input:包含 n个可排序元素的一个数组 A0.n-1/output:所做的关键比较的总次数count0for i1 to n-1 do vAiji-1while j0 and Ajv do 10countcount+1Aj+1Ajjj+1if j=0 count=count+1Aj+1vreturn count

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。