1、 算法设计与分析基础课后练习答案习题 1.1 4.设计一个计算 的算法，n 是任意正整数。除了赋值和比较运算，该算法只能用到基本的四则运算操作。算法求 /输入：一个正整数 n 2/输出：。step1:a=1；step2:若 a*a0temp2*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 retu
2、rn “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/输出：该正整数相应的二进制数，该数存放于数组 Bin1.n中i=1while n!=0 do Bini=n%2;n=(i
3、nt)n/2;i+;while i!=0 doprint Bini;i-;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法 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.
4、该算法在位吗 ?解:a. 该算法对列表 ”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*” 排序c.该算法不在位 .额外空间 for S and Count4.(古老的七桥问题)第 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)cg(n) for all nn0, where c0则： f
5、or all nn0)()1(ngtcb. 这个断言是正确的。只需证明 。)()(),()( ngng设 f(n)(g(n),则有：for all n=n0, c0)()(ngcffor all n=n0, c1=c01即：f(n)(g(n)又设 f(n)(g(n),则有： for all n=n0,c0)(ncgffor all n=n0,c1=c/0)()(1cnf即：f(n)(g(n)8证明本节定理对于下列符号也成立：a. 符号b. 符号证明：a。we need to proof that if t 1(n)(g 1(n) and t2(n)(g 2(n), then t1(n)+ t2
6、(n)(maxg 1(n), g2(n)。由 t1(n)(g 1(n)，t1(n)c 1g1(n) for all n=n1, 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，使得对于所有
7、n=n0，有：)(2,1max()(21)(2,1ax( ngntngc 由 t1(n)(g1(n)知，存在非负整数 a1,a2 和 n1 使：a1*g1(n)0，g1(n)+g2(n)g1(n),即 g1+g2max(g1,g2)。则（3）式转换为：C1*max(g1,g2) =n0 时上述不等式成立。证毕。习题 2.22. 请用 的非正式定义来判断下列断言是真还是假。a. n(n + 1)/2 O(n 3) b. n(n + 1)/2 O(n 2)c. n(n + 1)/2 (n 3) d. n(n + 1)/2 (n)答：c 假，其它真。5.按照下列函数的增长次数对它们进行排列（按照从低
8、到高的顺序）(n2)!, 5lg(n+100)10, 22n, 0.001n4+3n3+1, ln2 n, ， 3n.答：习题 2.31. 计算下列求和表达式的值。答：3. 考虑下面的算法。a 该算法求的是什么？b 它的基本操作是什么？c 该基本操作执行了多少次？d 该算法的效率类型是什么？e 对该算法进行改进，或者设计一个更好的算法，然后指出它们的效率类型。如果做不到这一点，请试着证明这是不可能做到的。9.证明下面的公式：可以使用数学归纳法，也可以像 10 岁的高斯一样，用洞察力来解决该问题。这个小学生长大以后成为有史以来最伟大的数学家之一。数学归纳法：高斯的方法：习题 2.41. 解下列递推关系 （做 a,b）a.解：b.解：0)1(5)xn4)1()3xn当 n1 时当 n1 时2. 对于计算 n!的递归算法 F(n)，建立其递归调用次数的递推关系并求解。
