算法设计与分析基础_第二版课后答案

算法设计与分析基础课后答案

课后答案网 -中国第一答案下载门户

答案分类

大学课后答案

进入社区淘答案

高中课后答案

(专业级搜索引擎为你提供服务)

公共基础课 | 通信/电子/电气 | 计算机/软件/网络/高一课后答案 | 高二课后答案 | 高三课后答案

信息/数学 | 物理/光学/声学/热学/力学 | 经济学/管理初中课后答案 学/法学 | 化学/环境/生物/医学/制药 | 土建/机械/材料/制造 | 哲学/心理学/政治学 | 文学/史学/外语/教育 | 其它类别

初一课后答案 | 初二课后答案 | 初三课后答案

考试课后答案

等级考试类答案 | 公务员考试答案

热门答案 最新求助 最新答案

程答案（全）【

k

题答案(微观.宏观

(茆诗松 著) 高

上下册 (同济大学

浩强 著) 清华大

新视野大学英语读写教高鸿业版西方经济学习概率论与数理统计教程高等数学（第五版）含C程序设计 第三版 (谭

新视野英语听力原文及理论力学 第六版 (哈尔线性代数 (同济大学应21世纪大学英语第3册复变函数与积分变换 答案 课后答案【

滨工业大学理论

用数学系 著) 高

（1-4）答案【

khd

第四版 (张元林 西

概率与数理统计 第二,C语言程序设计教程 第西方经济学(微观部分) C语言程序设计教程 第复变函数全解及导学[西三版 (浙江大学

三版 (谭浩强 张

(高鸿业 著) 中

二版 (谭浩强 张

安交大 第四版]

社区服务社区热点进入社区

http://www.77cn.com.cn/2009-10-15

算法设计与分析基础课后答案

算法设计与分析基础

习题1.1

5..证明等式gcd(m,n)=gcd(n,mmodn)对每一对正整数m,n都成立.Hint:

根据除法的定义不难证明:

如果d整除u和v,那么d一定能整除u±v;

如果d整除u,那么d也能够整除u的任何整数倍ku.

对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=mmodn=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:

对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n,即

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.21.(农夫过河)

www.

P—农夫W—狼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

//输出:实根或者无解信息

1

khd

G—山羊

C—白菜

课

aw.co

网

后

答

案

m

算法设计与分析基础课后答案

Ifa≠0

D←b*b-4*a*cIfD>0

temp←2*a

x1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturnx1,x2

elseifD=0return–b/(2*a)elsereturn“norealroots”else//a=0

ifb≠0return–c/belse//a=b=0

ifc=0return“norealnumbers”elsereturn“norealroots”

b.伪代码

算法DectoBin(n)

//将十进制整数n转换为二进制整数的算法//输入：正整数n

//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1

whilen!=0do{Bin[i]=n%2;n=(int)n/2;i++;}

whilei!=0do{printBin[i];i--;}

9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])

2

www.

khd

5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：

a.将十进制整数转换为二进制整数的算法输入：一个正整数n

输出：正整数n相应的二进制数

第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出

课

aw.co

网

后

答

案

m

算法设计与分析基础课后答案

//输入:数组A[0..n-1]

//输出:thesmallestdistancedbetweentwoofits

elements

a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:

a.该算法对列表”60,35,81,98,14,47”排序的过程如下所示:

www.

b.该算法不稳定.比如对列表”2,2*”排序

3

khd

课

aw.co

网

习题1.3

1.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.

后

答

案

m

算法设计与分析基础课后答案

c.该算法不在位.额外空间forSandCount[]4.(古老的七桥问题)

www.

即：f(n)∈Θ(g(n))

第2章习题2.1

7.对下列断言进行证明:(如果是错误的,请举例)a.如果t(n)∈O(g(n),则g(n)∈Ω(t(n))b.α>0时,Θ(αg(n))=Θ(g(n))解:< …… 此处隐藏：5548字，全部文档内容请下载后查看。喜欢就下载吧 ……