田翠华著算法设计与分析课后习题参考答案.doc

参考答案61参考答案第1章一、选择题1. C2. A3. C4. C A D B 5. B6. B7. D8. B9. B10. B11. D12. B二、填空题1. 输入；输出；确定性；可行性；有穷性2. 程序；有穷性3. 算法复杂度4. 时间复杂度；空间复杂度5. 正确性；简明性；高效性；最优性6. 精确算法；启发式算法7. 复杂性尽可能低的算法；其中复杂性最低者8. 最好性态；最坏性态；平均性态9. 基本运算10. 原地工作三、简答题1. 高级程序设计语言的主要好处是：（l）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可移植性好、重用率高；（4）把复杂琐碎的事务交给编译程序，所以自动化程度高，发用周期短，程序员可以集中集中时间和精力从事更重要的创造性劳动，提高程序质量。2. 使用抽象数据类型带给算法设计的好处主要有：（1）算法顶层设计与底层实现分离，使得在进行顶层设计时不考虑它所用到的数据，运算表示和实现；反过来，在表示数据和实现底层运算时，只要定义清楚抽象数据类型而不必考虑在什么场合引用它。这样做使算法设计的复杂性降低了，条理性增强了，既有助于迅速开发出程序原型，又使开发过程少出差错，程序可靠性高。（2）算法设计与数据结构设计隔开，允许数据结构自由选择，从中比较，优化算法效率。（3）数据模型和该模型上的运算统一在抽象数据类型中，反映它们之间内在的互相依赖和互相制约的关系，便于空间和时间耗费的折衷，灵活地满足用户要求。（4）由于顶层设计和底层实现局部化，在设计中出现的差错也是局部的，因而容易查找也容易纠正，在设计中常常要做的增、删、改也都是局部的，因而也都容易进行。因此，用抽象数据类型表述的算法具有很好的可维护性。（5）算法自然呈现模块化，抽象数据类型的表示和实现可以封装，便于移植和重用。（6）为自顶向下逐步求精和模块化提供有效途径和工具。（7）算法结构清晰，层次分明，便于算法正确的证明和复杂性的分析。3. 算法的复杂度是算法运行所需要的计算机资源的量。4. 当问题的规模递增时，将复杂度的极限称为渐进复杂度。5. 采用复杂性渐近性态替代算法复杂度，使得在数量级上估计一个算法的执行时间成为可能。四、计算题1. 验证下面的关系：O（1）O(logn)O(n)O(nlogn)O(n2) 及 O(2n)O(n!)O(nn)。证明1：数学归纳法。证明2：反证法。证明3：定义证明令f1(n)= O（1），f2(n)= O(logn)，f3(n)= O(n)，f4(n)= O(nlogn)，f5(n)= O(n2)。根据|f(n)| = |O(g(n)|定义，可知一定存在两个正的常数C和n0，使得对所有的n n0，有f(n) C g(n) 。那么，就有f1(n) C1，f2(n) C2 logn，f3(n) C3 n，f4(n) C4 nlogn，f5(n) C5n2。所以，O(g(n)之间的比较可以通过f(n)之间的比较得以实现。而当n n0时，C1 C2 logn C3 n C4 nlogn C5 n2成立。再根据O（g（N）表示所有f（N）增长的阶不超过g（N）的函数的集合，它用以表达一个算法运行时间的上界。则f1(n)的上界 f2(n)的上界 f3(n)的上界 f4(n)的上界 f5(n)的上界那么就验证了O（1）O(logn)O(n)O(nlogn)O(n2)。同理，有：O(2n)O(n!)O(nn)。证明4：极限法（通常使用罗比塔法则）。 2. 找出下述证明中的错误：因为n= O(n)，2n= O(n)，故：解答：概念不清。n= O(n)，2n= O(n)，是集合，是说n，2 n，的阶是n，不是数值上相等。是数值求和，即首项为n的n项等差为n的数列求和所以，。应该是：= 1 n +2 n +3 n +nn= n(n+1)n/2 ，而 = O(max（1 ,2 ,3,4 ,n）) / 根据性质O（f）十O（g）O（max（f，g）= O(n) /集合操作，上界的并取最大者3. 求以下各式的渐进表达式:5 n2+8 n ，3n2/11 + 3n ，56 + 3/ n ，logn5 ，6 log4 n。解答：5n2+8 n = O (n2);13n2/11 + 3n = O (3n) ;56 + 3/ n = O （1） / O （1）表示常数;logn5 = O (logn)；6 log4 n= O (n) 。4. 按照渐进阶从低到高的顺序排列下列表达式：n2，logn，3n，45 n，6，3n3/2，n！。解答：logn，45 n，3n3/2，5 n2， 3n， n！。5. 确定关系：对于下列各组函数f（n）和g（n），确定f（n）O（g（n）或f（n）（g（n）或f（n）Q（g（n），并简述理由。（1）f（n） log n2，g（n） log n7；（2）f（n） 1og n2，g（n） n1/2；（3）f（n） n，g（n） log 2 n；（4）f（n） n 1og n n ，g（n） log n；（5）f（n） 11，g（n） og 11；（6）f（n） log 2 n，g（n） log n；（7）f（n） 2n，g（n） 100 n2；（8）f（n） 2n，g（n） 3n。解答：（1）f（n）log n2Q（log n7）Q（g（n）；（2）f（n）1og n2O（n1/2）O（g（n）；（3）f（n）n（log 2 n）=（g（n）；（4）f（n）n 1og n n（log n）=（g（n）；（5）f（n）11Q（log 11）Q（g（n）；（6）f（n）log 2 n（log n）=（g（n）；（7）f（n）2n =（100 n2）=（g（n）；（8）f（n）2n = O（3n）= O（g（n）。6. 证明：n！= O(nn)。证明： 7. 证明：如果一个算法在平均情况下的计算时间复杂度是Q（f（n），则该算法在最坏情况下所需的计算时间是（f（n）。证明：8. 硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n2，n3和n！的各算法，若用ABC公司的计算机在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n=100n;n2=100n2， n=10n;n3=100n3， n=102/3n=4.64n;n!=100n!， nn+log100=n+6.64。9. （1）假设某算法在输入规模为免时的计算时间为T（n）32n。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（2）若上述算法的计算时间改进为T（n）n2，其他条件不变，则在新机器上用t秒时间能解输入规模为多大的问题？（3）若上述算法的计算时间进一步改进为T（n）8，其他条件不变，那么我们在新机器上用t秒时间能解输入规模为多大的问题？解答：（1）设新机器用同一算法在t秒内能解输入规模为n的问题，则有T（n） = 32n = 32n/64，得n = n+6；（2）n2=64n2，得n = 8n；（3）由于T（n）8为常数，因此算法可以为解任意规模的问题。五、上机题二分检索是指在一个已经排序的数组中查找一个指定的数据是否存在的问题。进一步说，假定一个具有N个元素的整型数组a和一个整数x，数组a的元素已经按由小到大的顺序排序，希望查找x在数组a中是否出现。若出现，输出对应的数组元素下标，否则，输出不存在信息。编程时具体的实现方法是：将x与a的中间元素aN2比较，如果相等则结束。否则，若xaN2，由于a是有序的，可以肯定x只可能出现在前半个数组中；若xaN2，则x只可能出现在后半个数组中。然后，将得到的半个数组看成原来昀数组，继续重复上述过程直到数组的所有元素比较完毕或发现一个相等的元素为止。在进行程序设计时，N是数组大小的上限，实际的元素个数由键盘输人。# include . #defne N 50 int bsearch(int * a, int n, int x) /参数为数组、元素个数和被查找的值 int k=0,m=n-1,mid; / k，m，mid为被查找区间的最小、最大和中间元素下标while(k = m) /若最小下标超过最大下标则终止循环，说明不存在 mid = (k+ m)/2; /取中间下标，注意整数相除取整 if(x = = amid;retum mid; /相等时绔束，返回元求下标 elseif(x amid)m = mid-l; / x应在前半个数组中，最大下标凋整elsek = mid+ 1; / x应在后半个数组中，最小下标调整 return -1; /执行此语句时，必有km，即x不存在，返回-1作标志void rnain( ) int aN, x, n, rt, k;printf(“input count( =50):”); /输人数组元素个数scanf(“%d”,&n); printf(“Input all elermnts:); for(k=0;kn;k+);scanf(“%d”,&ak); /输人数组元素, 元素可用空格分隔 printf(“input data searched”);scanf(“%d”,&x);/输人被查找的值xrt=bsearch(a,n,x);/执行查找(rt=-1)?printf(“nNot found.”):printf(“nFound:%d.”,rt); /显示查找结果第2章一、选择题1. C2. C二、填空题1. 递推法；生成函数法；特征方程法；数学归纳法；不规则法2. 递归消除有利于提高算法的时空性能；研究递归消除有利于透彻理解递归机制三、简答题1. 人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是在解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。2. 假定所求解递归方程的解（系列）是某个函数（如G（x）展开成无穷级数后的系数，于是，可以先利用递归方程求出G（x）的解析表达式，然后，再将G（x）展成无穷级数，其xn项的系数自然就是递归方程的通解形式。四、计算题1. 求和：（1）（2）解答：（1）设和为S，则有S=a+2a2+3 a3+n an 等式两边同乘a，得a S=a2+2 a3+n an+1 -得：(1- a)S= a+a2+a3+an- nan+1整理得：S = a(1- an)/(1-a)2- nan+1/(1-a)（2）设和为S，则有当n为偶数时，当n为奇数时，2. 设m，n都是整数，计算（1）(n+m)/2 + (n-m+1)/2（2） (n+m)/2 + (n-m+1)/2 解答：（1）因为m,n都是整数，所以n+m与n-m同时为奇数或偶数。当n+m与n-m同时为奇数时，原式=(n+m-1)/2 + (n-m+1)/2= n当n+m与n-m同时为偶数时，原式=(n+m)/2 + (n-m)/2= n（2）同理，m,n都是整数，所以n+m与n-m同时为奇数或偶数。当n+m与n-m同时为奇数时，原式=(n+m+1)/2 + (n-m+1)/2= n+1当n+m与n-m同时为偶数时，原式=(n+m)/2 + (n-m)/2+1= n+13. 判断下述等式的真伪：（1）( x )1/2 = x1/2（2） ( x ) 1/2 = x1/2（3） ( x ) 1/2 = x1/2 解答：（1）当x=k2, k为整数时，原等式成立。当xk2,k为整数时，原等式不成立。此时左端不一定为整数，而右端为整数。（2）等式成立。（3）当x=k2, k为整数时，原等式成立。当xk2, k为整数时，原等式不成立。此时,( x ) 1/2 x 1/2,所以左端小于右端。4. 求证：（1） x + y x + y（2） x + y x+y （3） log(n+1) = logn +1 （4） (x+m)/n = (x +m)/n（5） 证明：（1）当x, y为整数时，原等式成立。当x, y不为整数时，令x = x +x, y = y +y, 其中0 x , y 1。则有x + y = x + x + y + y = x + y + x + y因为0 x , y 1，所以0 x+y x + y ，即有：x + y x + y 所以，原不等式 x + y x + y 成立。（2）当x, y为整数时，原不等式成立。当x, y不为整数时，令x = x x, y = y y, 其中0 x , y 1。则有： x+y = x x + y y = x + y （x y）因为0 x , y 1，所以有 0 x+y 2。因此， x+y x + y = x + y。所以，原不等式 x + y x+y 成立。 （3）当n为2k时, log(n+1) = k+1, 而 logn +1 = k+1, 所以，原等式成立。当n不为2k时，则2kn2 k+1, 此处k = logn ，那么2k+1n +12 k+1, 则有：log(n+1) =k+1, logn +1= k+1, 所以，原等式成立。（4）若要使原等式成立，必有, 这里x = x + x，0 x 0。用数学归纳法证明命题：当n=2时，有x mod 3=2，成立。 当n=3时，有x mod 5=3，成立。 假设当n = k时,有xmod(2k-1)=k成立， 然后证明当n=k+1成立。所以，命题成立。即有：x mod (2(k+1)-1) = k+1。根据命题xmod(2n-1)=n,有在xmod(2n-1)=xmod15中，2n-1=15,则n=8。所以，xmod15=8。 x mod 3=2，x mod 5=3，此时x0，否则不满足定义存在整数k1，k2，使得：x = 3 k1 + 2，同时，x = 5 k2 + 3，即有：3 k1 + 2 = 5 k2 + 3，得 k1 =（5 k2 +1）/3 = 5（k2 -1）/3 +2 k1，k2为整数 存在整数k，使得：k = （k2 -1）/3，即有：k2 = 3 k +1 x = 5 k2 + 3 = 5（3 k +1）+ 3 = 15 k + 8 xmod15=8。6. 求序列2，5，13，35，2n+3n的生成函数。解答：根据题义，得 H(0)=2 , n=0 H (n)= 2n+3n, n=1,2,3, 设生成函数为,将H(n)= 2n+3n代入，得 ,将上式展开并整理，得G(x)=2-5x+(2n+2+3n)xn+1+(3*2n+1+2*3n+1)xn+2/(1-2x)(1-3x)7. 给定a0=1,a1=1,an+2=an+1+6an,试求出an的非递归形式的表达式。解答：原方程所对应的特征方程为：a2-a-6=0为齐次方程，则齐次解: q1=3, q2=-2,重数均为1。记通解的形式为: an=Aq1n+Bq2n=A3n+B(-2) n将a0=1,a1=1代入上式，得 A+B=1 3A-2B=1解得：A=3/5， B=2/5从而，得an的非递归形式的表达式为：an=（3n+1+(-2) n+1）/5。8. 设有a0=0，a1=1，a2=-1和an=- an-1+16 an-2-20 an-3，当n3。求出an的表达式。解答：原递归方程所对应的特征方程为：x3+x2-16X+20=0解得特征方程的根：q1=-5, q2=2,重数分别为1和2。记通解的形式为: an=(A+Bn)q1n+Cq2n=(A+Bn)*2 n+C*(-5)n将a0=0，a1=1，a2=-1代入上式，得 A+C=0 2(A+B) - 5C =1 4(A+2B) + (-5)2C=-1解得：A=5/49, B=1/7, C=-5/49从而，得an的非递归形式的表达式为：an=（5/49+n/7）*2n +(-5)n+1/49。9. 设a0=1,a1=5,an=an-1+6an-2, 当n2。求出an的解析表达式。解答：原递推方程的特征方程为x2-x-6=0，则齐次特征方程为齐次特征的解为：q1=3, q2=-2,重数均为1。记通解的形式为: an=Aq1n+Bq2n=A3n+B(-2) n将a0=1,a1=5代入上式，得 A+B=1 3A-2B=5解得：A=7/5， B=-2/5记通解的形式为: an=Aq1n+Bq2n=（7*3n+ (-2) n+1）/510. 求解方程： T（2）=1,n=1 T(n)=n1/2T(n1/2)+n, n2, 且有k，使得解答：由递归方程，递推得T(n) =n1/2T(n1/2)+n=n1/2(n1/2)1/2T(n1/2)1/2)+n1/2+n=n1/2 n 1/4T(n1/4)+ n+n=n1/2 n 1/4(n1/4)1/2T(n1/4)1/2)+n1/4+2n=n1/2 n 1/4 n 1/8T(n1/8)+3n令，则有 T(n)=n(1/2+log(logn)11. 求证方程的解是x(n+1)=Cn2n/(n+1)证明: 根据递归方程，递推得x（2）= x（1） x（1）=1= C12/2x（3）= x（1） x（2）+ x（2） x（1）=1+1=2= C24/3x（4）= x（1） x（3）+ x（2） x（2）+ x（3） x（1）=5= C36/4x（5）= x（1） x（4）+ x（2） x（3）+ x（3） x（2） + x（4） x（1）=14= C48/5x(n)=Cn-12(n-1)/nx(n+1)=Cn2n/(n+1)12. 求证递归方程 T（1）=0 T(n)=T( n/2 )+ T( n/2 ) + n -1 ,n1的解是T(n)=n logn 2 logn +1。证明：（1）当n=2时，由递归方程和初值，推得T（2）=T（1）+T（1）+2-1=0+0+2-1=1由方程的解，得 T（2）=2-2+1=1。所以，结论成立。（2）假设当nk时成立,既有T(k)=k logk 2 logk +1是原递归方程的解。那么当n=k+1时，下面证明T(k+1)=( k+1) log(k+1) 2 log(k+1) +1是原递归方程的解。当nk时, T(k/2 )+ T( k/2 ) +k-1=k logk 2logk +1当n=k+1且k为奇数时，有T( (k+1)/2 )+ T( (k+1)/2 ) +k+1-1= T(k/2+1)+ T( k/2 ) + k=2 T( k/2 )+k=2 k/2 log k/2 2 log k/2 + 1 + k=(k+1) log k/2 2log k/2 +1 + 2+k=(k+1)( log（k+1）/ 2+ 1 ) 2log（ k1）/2 + log 2 + 1=(k+1) log(k+1) 1+ 1 2log( k+1) + 1=(k+1) log(k+1) 2log( k+1) + 1=T(k+1) 当n=k+1且k为偶数时，有T( (k+1)/2 ) + T( (k+1)/2 ) +k+1-1= T(k/2) + T(k/2+1) +k= (k/2) log(k/2)2log(k/2) +1 + (k/2+1) log(k/2+1) 2log(k/2+1) +1 +k=(k/2+k/2+1) log(k/2) (2log(k/2) + 2log(k/2+1) )+2 + k =(k+1) log(k/2) 2log(k/2) +1 +2 + k=T(k+1)即当n=k+1时，命题成立。所以，原命题成立。 五、上机题1计算Hermite多项式Void main() Printf(“n%f“,H(2,2.0); /输出结果76.000000 Dobule H(int n,float x) Switch(n) Case 0: return 1; Case 1: 2*x; Return 2*x*H(n-1,x)-2*(n-1)*H(n-2,x) 2求解汉诺塔问题汉诺塔问题：设A、B、C是三根金针。开始时，在金针A上有n只纸盘，这些纸盘自下而上，由大到小地叠放一起，各纸盘从小到大编号为1，2，n，如图A-1所示。现要求将金针A上的这一叠纸盘移到金针B上，并仍按同样顺序叠置。图A-1 汉诺塔问题的初始状态在移动纸盘时应遵守以下移动规则：规则（1）：每次只能移动一个纸盘；规则（2）：任何时刻都不允许将较大的纸盘压在较小的纸盘之上；规则（3）：在满足移动规则（1）和（2）的前提下，可将纸盘移至A，B，C中任一根金针上。分析与解答：（1）汉诺塔问题的递归算法如下：public static void Hanoi (int n, int A, int B, int C)if (nO) Hanoi (n-1,A,C,B) Move( n, A , B) ; Hanoi (n-l,C,B,A); （2）汉诺塔问题的非递归算法。教材中所述非递归算法的目的塔座不确定。当n为奇数时，目的塔座是B，按顺时针方向移动；而当n为偶数时，目的塔座为C，按反时针方向移动。为确定起见，规定目的塔座为B。汉诺塔问题的非递归算法可描述如下： public static void Hanoi(int n) int top=0，0，0 inttower=new intn+13; int x, y, min= O; Boolean b,bb; for(int i=0;i=n;i+) toweri0=n-i+1;toweri1=n+l; toweri2=n+l; top0=n;b=odd(n);bb=true; ; while(top1towertopy|y) int tmp=x;x=y;y_tmp; move(towertopxx,x+1,y+l); towertopy+ 1y = towertopxx ; topx-;topy+; 下面用数学归纳法证明递归算法和非递归算法产生相同的移动序列。当n1和n2时容易直接验证。设当k n1时，递归算法和非递归算法产生完全相同的移动序列。考察kn的情形。将移动分为顺时针移动（C）、逆时针移动（CC）和非最小圆盘塔座间的移动（O）。当n为奇数时，顺时针非递归算法产生的移动序列为：C，O，C，O，C；逆时针非递归算法产生的移动序列为：CC，O，CC，O，CC。当n为偶数时，顺时针非递归算法产生的移动序列为：CC，O，CC，O，CC；逆时针非递归算法产生的移动序列为：C，O，C，O，C。 当n为奇数时，顺时针递归算法Hanoi（n，A，B，C）产生的移动序列为：Hanoi（n1，A，C，B）产生的移动序列，O，Hanoi（n1，C，B，A）产生的移动序列。Hanoi（n1，A，C，B）和Hanoi（n1，C，B，A）均为偶数圆盘逆时针移动问题。由数学归纳法知，产生的移动序列均为：C，O，C，O，C。因此，Hanoi（n，A，B，C）产生的移动序列为：C，O，C，O，C。 当n为偶数时，顺时针递归算法Hanoi（n，A，B，C）产生的移动序列为：Hanoi（n1，A，C，B）产生的移动序列，O，Hanoi（n1，C，B，A）产生的移动序列。Hanoi（n1，A，C，B）和Hanoi（n1，C，B，A）均为奇数圆盘逆时针移动问题。由数学归纳法知，产生的移动序列均为：CC，O，CC，O，CC。因此，Hanoi（n，A，B，C）产生的移动序列为：CC，O，CC，O，CC。当n为奇数和偶数时的逆时针递归算法也类似。由数学归纳法即知，递归算法和非递归算法产生相同的移动序列。 （3）双色汉诺塔问题：设A、B、C是三根金针。开始时，在金针A上有n只纸盘，这些纸盘自下而上，由大到小地叠放一起，各纸盘从小到大编号为1，2，n，奇数编号圆盘为白色，偶数编号圆盘为黑色。如图A-2所示。现要求将金针A上的这一叠纸盘移到金针B上，并仍按同样顺序叠置。图A-2 双色汉诺塔问题的初始状态在移动纸盘时应遵守以下移动规则：规则（1）：每次只能移动一个纸盘；规则（2）：任何时刻都不允许将较大的纸盘压在较小的纸盘之上；规则（3）：任何时刻都不允许将同色圆盘叠在一起；规则（4）：在满足移动规则（1）和（3）的前提下，可将纸盘移至A，B，C中任一根金针上。试设计一个算法，用最少的移动次数将塔座A上的n个圆盘移到塔座B上，并仍按同样顺序叠置。分析与解答：可用教材中的标准Hanoi塔算法。问题是要证明标准Hanoi塔算法不违反规则（3）。用数学归纳法。设Hanoi（n，A，B，C）将塔座A上的n个圆盘，以塔座C为辅助塔座，移到目的塔座B上的标准Hanoi塔算法。归纳假设：当圆盘个数小于n时，Hanoi（n，A，B，C）不违反规则（3），且在移动过程中，目的塔座B上最底圆盘的编号与n具有相同奇偶性，辅助塔座C上最底圆盘的编号与n具有不同奇偶性。当圆盘个数为n时，标准Hanoi塔算法Hanoi（n，A，B，C）由以下3个步骤完成。 Hanoi（n1，A，C，B）； Move（A，B）； Hanoi（n1，C，B，A）。按归纳假设，步骤不违反规则（3），且在移动过程中，塔座C上最底圆盘的编号与n-1具有相同奇偶性，塔座B上最底圆盘的编号与n-1具有不同奇偶性，从而塔座B上最底圆盘的编号与n具有相同奇偶性，塔座C上最底圆盘的编号与n具有不同奇偶性。步骤也不违反规则（3），且塔座B上最底圆盘的编号与n相同。按归纳假设，步骤不违反规则（3），且在移动过程中，塔座B上倒数第2个圆盘的编号与n1具有相同奇偶性，塔座A上最底圆盘的编号与n1具有不同奇偶性，从而塔座B上倒数第2个圆盘的编号与n具有不同奇偶性，塔座A上最底圆盘的编号与n具有相同奇偶性。因此在移动过程中，塔座B上圆盘不违反规则（3），而且塔座B上最底圆盘的编号与n具有相同奇偶性，塔座C上最底圆盘的编号与n具有不同奇偶性。由数学归纳法即知，Hanoi（n，A，B，C）不违反规则（3）。第3章一、选择题1. B2. B二、填空题1. logn12. 2n-1三、简答题1. 将一个难以直接解决的大问题，分割成一些规模较小的类型相同问题，这些子问题相互独立，以便各个击破，分而治之。如果原问题可分割成m个子问题，1mn，并且这些子问题都可解，然后求解这些问题，那么就可利用这些子问题的解求出原问题的解；如果子问题还比较复杂而不能直接求解，还可以继续细分，直到子问题足够小，能够直接求解为止。此外，为了得到原始问题的解，必须找到一种途径能够将各个子问题的解组合成原始问题的一个完整答案。2. 将待查的数据与非降序数组中的中间元素进行比较，若二者相等则表示查到；若该数据小于中间元素的值，则下次在数组的前半部分中继续找；否则，在数组的后半部分中查找。即每次检索将与待查数据的比较次数减半。如此继续进行下去，直到查到该值的元素或不存在所查找的数据。此种分治方法，称为二分检索。四、计算题1. 作一个“二分”检索算法，它将原集合分成1/3和2/3大小的两个子集。分析此算法并与算法3.1比较。输入：已按非减序分类的n个元素的数组A和X，X是被检索的项。A0未用。输出：若X在A中，输出下标j满足Aj= X，否则输出0。Int BinarySearch (A, n, X) int k=1; m=n; while (k=m) j = (k+m)/3; /* j=(k+m)/3*/ if (X=Aj) return j; if (XAj) m= j-1 else k= j+1; return 0；时间分析：比较次数2. 作一个“三分”检索算法，它首先检查1/3处的元素是否与X相等，然后检查2/3处的元素，等等。这样，或者找到X，或者将集合缩小到原来的1/3。试写出此算法并分析其复杂性。输入：已安排减序分类的n个元素的数组A和X，X是被检索的项。A0未用。输出：若X在A中，输出下标j满足Aj= X，否则输出0。Int ThirdSearch(A,n, X) int k =1; m = n; While (k=m) i = (k + m )/3; /* i = (k +m)/3 */ if (X=Ai) return i; if (XAi) m= i-1 else j = 2 (k + m)/3) /; /* j = 2 (k + m)/3) */ if (X=Aj) return j; if (X2时，则需要进行两次递归调用及之后的比较。故有： T(n) = 5 n/24. 求解最接近中位数的k个数：给定由n个互不相同的数组成的集合A以及正整数kn，设计一个O（n）时间复杂度的查找A中最接近A的中位数的k个数的算法。在采用分治法进行查找时，为了满足分治法的平衡原则，需要将数组分成两个大小基本相同的子数组，其中的那个划分点就是中位数。所以，中位数是指数组中能将数组划分成两个大小基本相同的两个子数组的那个元素，即中位数是第 n2 小的数。解析：（1）找出A中的中位数mid；（2）计算T = |a - mid|，aA；（3）找出T的第k小元素b；（4）根据b找出所要的解 |a - mid|b，aA 。由于在最坏情况想选择的时间复杂度为O（n）。所以，（1）和（3）需要O（n）次计算，（2）和（4）也只需要O（n）次计算。因此，本算法在最坏情况下，时间复杂度为O（n）。例如，A = 50，13，80，30，6，27，35，k = 3，求最接近中位数的k个数。（1）找出A中的中位数mid：将A排序 = 6，13，27，30，35，50，80，mid=30。（2）计算T = |a - mid|，aA：T=20，13，50，0，24，3，5。 （3）找出T的第k小元素b：T的第k小元素b = 5。（4）根据b找出所要的解 a，|a - mid|b，aA ：30，27，35。5. 求有序数组A和B的中位数设A0n-1和B0n-1为两个数组，每个数组中含有n个已排好序的数。设计一个O(1ogn)时间复杂度的算法，找出A和B的2n个数的中位数median。解析：（1）算法设计思想。考虑问题的一般性：设Ail：j1和Bi2：j2是A和B的排序好的子数组，且长度同，即j1-i1 = i2-j2。找出这两个子数组中2(j1-i11)个数的中位数。首先注意到，若Ai1Bj2，则中位数median满足Ai1medianBj2。同理，若Ai1Bj2，则Bj2medianAi1。设m1(i1j1)2，m2 = (i2j2)2，则m1十m2 (i1j1)2(i2十j 2)2i1(j1一i1)2 + i2 (j2i2)2i1i2(j1一i l)2(j2i2)2。由于j1i1j2i2，故(j1一i1)2(j2一i2)2j1一i1j2一i2。因此，m1m2i1i 2jl一i1i2jli1i2j2i2i1j2。当Am1Bm2时，medianAm1Bm2。当Am1Bm2时，设median1是Am1：jl和Bj 2：m2的中位数，则medianMedian1。当Am1Bm2时，设median2是Ai1：m1和Bi2：j2的中位数，类似地有medianmedian2。通过以上的讨论，可以设计出查找两个子数组Ai1:j1和Bi2:j2的中位数median的算法。（2）算法复杂性。设在最坏情况下，算法所需的计算时间为T(2n)。由算法中m1和m2的选取策略可知，在递归调用时，数组A和B的大小都减少了一半。因此，T(2n)满足递归式：解此速归方程可得：T(2n)O(logn)。比如 A=12，34，56，62，78，81，95，B=23，38，45，67，89，103，120。求数组A和B中位数。解析：m1(i1j1)23，m2 = (i2j2)23。 Am1 62，Bm2 67，则根据 当Am1Bm2时，设median1是Am1：jl和Bi2：m2的中位数，则medianMedian1。有：median Am1：jl和Bi2：m2的中位数 A3：6和B0：3的中位数 62，78，81，95和23，38，45，67的中位数 62再比如 A=12，34，56，62，78，81，95，B=23，38，45，60，89，103，120。求数组A和B中位数。解析：m1(i1j1)23，m2 = (i2j2)23。 Am1 62，Bm2 60，则根据 当Am1Bm2时，设median2是Ai1：m1和Bm2：j2的中位数，类似地有medianmedian2。有：median A0：3和B3：6的中位数 A3：6和B0：3的中位数 12，34，56，62和60，89，103，120的中位数 606. 利用整数相乘算法3-7计算两个二进制数1011和1101及两个十进制数3141和5327的乘积。解答：（1）x=1011, y=1101Mul(1011, 1101,4) /整数相乘算法3.1 A=10, B=11, C=11, D=01 m1=Mul(A,C,n/2)=Mul(10,11,2) /递归调用 A=1, B=0, C=1, D=1 m1=Mul(A,C,n/2) =Mul(1,1,2/2)=1/递归调用并返回Mul(1,1,2/2) m2=Mul(A-B,D-C,n/2) =Mul(1,0,2/2