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
