《算法设计与分析》习题第一章引论习题1-1 写一个通用方法用于判定给定数组是否已排好序。

解答：Algorithm compare(a,n)BeginJ=1;While (j<n and a[j]<=a[j+1]) do j=j+1;If j=n then return trueElseWhile (j<n and a[j]>=a[j+1]) do j=j+1;If j=n then return true else return false end ifEnd ifend习题1-2 写一个算法交换两个变量的值不使用第三个变量。

解答：x=x+y; y=x-y; x=x-y;习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件(n2-mn-m2)2=1 且使n2+m2达到最大的m、n。

解答：m:=k; flag:=0;repeatn:=m;repeatl:=n*n-m*n-m*n;if (l*l=1) then flag:=1 else n:=n-1;until (flag=1) or (n=0)if n=0 then m:=m-1until (flag=1) or (m=0);第二章基础知识习题2-1 求下列函数的渐进表达式：3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。

解答： 3n 2+10n=O （n 2）， n 2/10+2n =O （2n ）， 21+1/n=O （1）， log n 3=O （log n ），10 log3n =O （n ）。

习题2-2 说明O (1)和 O (2)的区别。

习题2-3 照渐进阶从低到高的顺序排列以下表达式：!n ，3/22,2,20,3,log ,4n n n n n 。

解答：照渐进阶从低到高的顺序为：!n 、 3n、 24n 、23n 、20n 、log n 、2习题2-4（1） 假设某算法在输入规模为n 时的计算时间为n n T 23)(⨯=。

在某台计算机上实现并完成该算法的时间为t 秒。

现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t 秒内能解输入规模为多大的问题？（2） 若上述算法的计算时间改进为2)(n n T =，其余条件不变，则在新机器上用t 秒时间能解输入规模多大的问题？（3） 若上述算法的计算时间进一步改进为8)(=n T ,其余条件不变，那么在新机器上用t 秒时间能解输入规模多大的问题？解答：（1） 设新机器用同一算法在t 秒内能解输入规模为1n 的问题。

因此有64/23231n n t ⨯=⨯=，解得61+=n n 。

（2） n n n n 8641221==>=。

（3） 由于=)(n T 常数，因此算法可解任意规模的问题。

习题2-5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC 公司同类产品的100倍。

对于计算复杂性分别为n ，2n ，3n 和!n 的各算法，若用ABC 公司的计算机能在1小时内能解输入规模为n 的问题，那么用XYZ 公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n n 100='。

n n n n 1010022='=>='。

n n n n 64.4100100333==>='。

64.6100log !100!+=+<'=>='n n n n n 。

习题2-6对于下列各组函数)(n f 和)(n g ，确定))(()(n g O n f =或))(()(n g n f Ω=或))(()(n g n f θ=，并简述理由。

（1）5log )(;log )(2+==n n g n n f 。

（2）n n g n n f ==)(;log )(2。

（3）n n g n n f 2log )(;)(==。

（4）n n g n n n n f log )(;log )(=+=。

（5）10log )(;10)(==n g n f 。

（6）n n g n n f log )(;log )(2==。

（7）2100)(;2)(n n g n f n ==。

（8）n n n g n f 3)(;2)(==。

解答：（1）)5(log log 2+=n n θ。

（2）)(log 2n O n =。

（3）)(log 2n n Ω=。

（4）)(log log n n n n Ω=+。

（5）)10(log 10θ=。

（6）)(log log 2n n Ω=。

（7）)100(22n nΩ=。

（8）)3(2nn O =。

习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为))((n f θ，则该算法在最坏情况下所需的计算时间为))((n f Ω。

证明：)(),()(),(),(max )(),()()(max **N T I N T I P I N T I N T I P I N T I P N T NNN ND I D I D I D I avg ==='≤=∑∑∑∈∈∈'∈因此，))(()))((())(()(max n f n f N T N T avg Ω=Ω=Ω=θ。

习题2-7 求解下列递归方程: s 0=0s n =2s n -1+2n -1 解答：步骤: 1应用零化子化为齐次方程，2解此齐次方程的特征方程， 3由特征根构造一般解，4再由初始条件确定待定系数，得到解为：习题2-8 求解下列递归方程:01122844nn n h h h h h--=⎧⎪=⎨⎪=-⎩ 解 h n =2n +1(n +1)第三章 递归与分治策略习题3-1 下面的7个算法都是解决二分搜索问题的算法。

请判断这7个算法的正确性。

如果算法不正确，请说明产生错误的原因。

如果算法正确，请给出算(1)21n n s n =-+法的正确性证明。

public static int binarySearch1(int []a,int x,int n) {int left=0; int right =n-1;while (left<=right) {int middle = ( left + right )/2;if ( x == a[middle]) return middle;if ( x> a[middle]) left = middle;else right = middle;return -1;}public static int binarySearch2(int []a, int x, int n) {int left = 0; int right = n-1;while ( left < right-1 ) {int middle = ( left + right )/2;if ( x < a[middle]) right = middle;else left = middle;}if (x == a[left]) return left;else return -1}public static int binarySearch3(int []a, int x, int n) {int left = 0; int right = n-1;while ( left +1 != right) {int middle = ( left + right)/2;if ( x>= a[middle]) left = middle;else right = middle;}if ( x == a[left]) return left ;else return -1;}public static int binarySearch4(int []a, int x, int n) {if (n>0 && x>= a[0]) {int left = 0; int right = n-1;while (left < right ) {int middle = (left + right )/2;if ( x < a[middle]) right = middle -1 ;else left = middle;}if ( x == a[left]) return left;}return -1;}public static int binarySearch5(int []a, int x, int n) {if ( n>0 && x >= a[0] ) {int left = 0; int right = n-1;while (left < right ) {int middle = ( left + right +1)/2;if ( x < a[middle]) right = middle -1;else left = middle ;}if ( x == a[left]) return left;}return -1;}public static int binarySearch6(int []a, int x, int n) {if ( n>0 && x>= a[0]) {int left = 0; int right = n-1;while ( left < right) {int middle = (left + right +1)/2;if (x < a[middle]) right = middle – 1;else left = middle + 1;}if ( x == a[left]) return left ;}return -1;}public static int binarySearch7(int []a, int x, int n) {if ( n>0 && x>=a[0]) {int left = 0; int right = n-1;while ( left < right) {int middle = ( left + right + 1)/2;if ( x < a[middle]) right = middle;else left = middle;}if ( x == a[left]) return left;}return -1;}分析与解答：算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。