《算法设计与分析》习题 第一章 引 论 习题1 -1 写一个通用方法用于判定给定数组是否已排好序。 解答： Algorithm compare(a,n) Begin J=1; While (j=a[j+1]) do j=j+1; If j=n then retu rn tru e else retu rn false end if End if end 习题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; repeat n:=m; repeat l:=n*n-m*n-m*n; if (l*l=1) then flag:=1 else n:=n-1; u ntil (flag=1) or (n=0) if n=0 then m:=m-1 u ntil (flag=1) or (m=0); 第二章 基础知识 习题2 -1 求下列函数的渐进表达式： 3n2+10n; n2/10+2n; 21+1/n; logn3; 10 log3n 。 解答： 3n2+10n=O（n2）， n2/10+2n=O（2n）， 21+1/n=O（1）， logn3=O（log n），10 log3n=O（n）。 习题2 -2 说明O(1)和 O(2)的区别。 习题2 -3 照渐进阶从低到高的顺序排列以下表达式：!n ，3/22,2,20,3,log,4nnnnn。 解答：照渐进阶从低到高的顺序为：!n 、 3n、 24n 、23n 、20n、logn、2 习题2 -4 （1） 假设某算法在输入规模为n 时的计算时间为nnT23)(。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64 倍，那么在这台新机器上用同一算法在 t秒内能解输入规模为多大的问题？ （2） 若上述算法的计算时间改进为2)(nnT，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？ （3） 若上述算法的计算时间进一步改进为8)(nT,其余条件不变，那么在新机器上用 t秒时间能解输入规模多大的问题？ 解答： （1） 设新机器用同一算法在 t 秒内能解输入规模为1n 的问题。因此有64/23231nnt，解得61 nn。 （2） nnnn8641221。 （3） 由于)(nT常数，因此算法可解任意规模的问题。 习题2 -5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC 公司同类产品的100 倍。对于计算复杂性分别为n ，2n ，3n 和!n 的各算法，若用 ABC 公司的计算机能在 1...
