算法设计与分析书后参考答案

PAGE4 算法设计与分析 参考答案 PAGE3参考答案第1章一、选择题1.C 2.A 3.C 4.CADB5.B 6.B7.D 8.B 9.B 10.B 11.D 12.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)≤Cg(n)。那么，就有f1(n)≤C1，f2(n)≤C2logn，f3(n)≤C3n，f4(n)≤C4nlogn，f5(n)≤C5n2。所以，O(g(n))之间的比较可以通过f(n)之间的比较得以实现。而当n≥n0时，C1<C2logn<C3n<C4nlogn<C5n2成立。再根据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，2n，…，的阶是n，不是数值上相等。是数值求和，即首项为n的n项等差为n的数列求和所以，。应该是：=1n+2n+3n+……+nn=n(n+1)n/2，而=O(max（1,2,3,4,…,n）)//根据性质O（f）十O（g）＝O（max（f，g））=O(n)//集合操作，上界的并取最大者3.求以下各式的渐进表达式:5n2+8n，3n2/11+3n，56+3/n，logn5，6log4n。解答：5n2+8n=O(n2);13n2/11+3n=O(3n);56+3/n=O（1）//O（1）表示常数;logn5=O(logn)；6log4n=O(n)。4.按照渐进阶从低到高的顺序排列下列表达式：n2，logn，3n，45n，6，3n3/2，n！。解答：logn，45n，3n3/2，5n2，3n，n！。5.确定关系：对于下列各组函数f（n）和g（n），确定f（n）＝O（g（n））或f（n）＝Ω（g（n））或f（n）＝（g（n）），并简述理由。（1）f（n）＝logn2，g（n）＝logn＋5；（2）f（n）＝1ogn2，g（n）＝n1/2；（3）f（n）＝n，g（n）＝log2n；（4）f（n）＝n1ogn＋n，g（n）＝logn；（5）f（n）＝10，g（n）＝log10；（6）f（n）＝log2n，g（n）＝logn；（7）f（n）＝2n，g（n）＝100n2；（8）f（n）＝2n，g（n）＝3n。解答：（1）f（n）＝logn2＝（logn＋5）＝（g（n））；（2）f（n）＝1ogn2＝O（n1/2）＝O（g（n））；（3）f（n）＝n＝Ω（log2n）=Ω（g（n））；（4）f（n）＝n1ogn＋n＝Ω（logn）=Ω（g（n））；（5）f（n）＝10＝（log10）＝（g（n））；（6）f（n）＝log2n＝Ω（logn）=Ω（g（n））；（7）f（n）＝2n=Ω（100n2）=Ω（g（n））；（8）f（n）＝2n=O（3n）=O（g（n））。6.证明：n！=O(nn)。证明：7.证明：如果一个算法在平均情况下的计算时间复杂度是（f（n）），则该算法在最坏情况下所需的计算时间是Ω（f（n））。证明：8.硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n2，n3和n！的各算法，若用ABC公司的计算机在1小时解答：n'=100n;n'2=100n2，n'=10n;n'3=100n3，n'=102/3n=4.64n;n'!=100n!，n'<n+log100=n+6.64。9.（1）假设某算法在输入规模为免时的计算时间为T（n）＝3×2n。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（2）若上述算法的计算时间改进为T（n）＝n2，其他条件不变，则在新机器上用t秒时间能解输入规模为多大的问题？（3）若上述算法的计算时间进一步改进为T（n）＝8，其他条件不变，那么我们在新机器上用t秒时间能解输入规模为多大的问题？解答：（1）设新机器用同一算法在t秒内能解输入规模为n'的问题，则有T（n）=3×2n=3×2n'/64，得n'=n+6；（2）n'2=64n2，得n'=8n；（3）由于T（n）＝8为常数，因此算法可以为解任意规模的问题。第2章一、选择题1.C 2.C二、填空题1.递推法；生成函数法；特征方程法；数学归纳法；不规则法2.递归消除有利于提高算法的时空性能；研究递归消除有利于透彻理解递归机制三、简答题1.人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是在解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。2.假定所求解递归方程的解（系列）是某个函数（如G（x））展开成无穷级数后的系数，于是，可以先利用递归方程求出G（x）的解析表达式，然后，再将G（x）展成无穷级数，其xn项的系数自然就是递归方程的通解形式。四、计算题1.求和：（1）（2）解答：（1）设和为S，则有S=a+2a2+3a3+…+nan=1\*GB3①等式两边同乘a，得aS=a2+2a3+…+nan+1=2\*GB3②=1\*GB3①-=2\*GB3②得：(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为整数时，原等式成立。当x≠k2,k为整数时，原等式不成立。此时左端不一定为整数，而右端为整数。（2）等式成立。（3）当x=k2,k为整数时，原等式成立。当x≠k2,k为整数时，原等式不成立。此时,(x)1/2<x1/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,∆y1，所以0∆x+∆y2则x+y+∆x+∆yx+y，即有：x+yx+y所以，原不等式x+y≤x+y成立。（2）当x,y为整数时，原不等式成立。当x,y不为整数时，令x=x－∆x,y=y－∆y,其中0∆x,∆y1。则有：x+y=x－∆x+y－∆y=x+y－（∆x＋∆y）因为0≤∆x,∆y1，所以有0≤∆x+∆y2。因此，x+y≤x+y=x+y。所以，原不等式x+y≥x+y成立。（3）当n为2k时,log(n+1)=k+1,而logn+1=k+1,所以，原等式成立。当n不为2k时，则2k<n<2k+1,此处k=logn，那么2k+1<n+1≤2k+1,则有：log(n+1)=k+1,logn+1=k+1,所以，原等式成立。（4）若要使原等式成立，必有,这里x=x+∆x，0≤∆x1左端=右端所以，原等式成立。（5）当n=2m+1时,m=0,1,2,3,…,左端=0+1+1+2+2+3+3+…+m+m=2*(1+m)m/2=m(1+m)右端=(2m+1)2/4=(4m2+4m+1)/4=m所以，原等式成立。当n=2m时,m=0,1,2,3,…,左端=0+1+1+2+2+3+3+…+(m-1)+(m-1)+m=2*(1+m-1)(m-1)/2+m=m2右端=(2m)2/4=m2=m2=所以，原等式成立。5.设x,y为任意实数，定义：xmody=x-yx/y,当y≠0xmod0=x依据上述定义：（1）若x=-1，计算xmod28。（2）若xmod3=2，xmod5=3，求xmod15。解答：（1）当x=-1时,xmod28=(-1)mod28=(-1)-28(-1)/28=-1-28*(-1)1/28=27（2）=1\*GB3①当xmod3=2，xmod5=3，那么有命题xmod(2n-1)=n成立，此时x>0。用数学归纳法证明命题：当n=2时，有xmod3=2，成立。当n=3时，有xmod5=3，成立。假设当n=k时,有xmod(2k-1)=k成立，然后证明当n=k+1成立。所以，命题成立。即有：xmod(2(k+1)-1)=k+1。根据命题xmod(2n-1)=n,有在xmod(2n-1)=xmod15中，2n-1=15,则n=8。所以，xmod15=8。=2\*GB3②∵xmod3=2，xmod5=3，此时x>0，否则不满足定义∴存在整数k1，k2，使得：x=3k1+2，同时，x=5k2+3，即有：3k1+2=5k2+3，得k1=（5k2+1）/3=5（k2-1）/3+2∵k1，k2为整数∴存在整数k，使得：k=（k2-1）/3，即有：k2=3k+1∴x=5k2+3=5（3k+1）+3=15k+8∴xmod15=8。6.求序列2，5，13，35，…2n+3n的生成函数。解答：根据题义，得H(0)=2, n=0H(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=13A-2B解得：A=3/5，B=2/5从而，得an的非递归形式的表达式为：an=（3n+1+(-2)n+1）/5。8.设有a0=0，a1=1，a2=-1和an=-an-1+16an-2-20an-3，当n≥3。求出an的表达式。解答：原递归方程所对应的特征方程为：x3+x2-16X+20=0解得特征方程的根：q1=-5,q2=2,重数分别为1和2。记通解的形式为:an=(A+Bn)q1n+Cq2n=(A+Bn)*2n+C*(-5)n将a0=0，a1=1，a2=-1代入上式，得A+C=02(A+B)-5C4(A+2B)+(-5)2C解得：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,当n≥2。求出an的解析表达式。解答：原递推方程的特征方程为x2-x-6=0，则齐次特征方程为齐次特征的解为：q1=3,q2=-2,重数均为1。记通解的形式为:an=Aq1n+Bq2n=A3n+B(-2)n将a0=1,a1=5代入上式，得A+B=13A-2B解得：A=7/5，B=-2/5记通解的形式为:an=Aq1n+Bq2n=（7*3n+(-2)n+1）/510.求解方程：T（2）=1,n=1T(n)=n1/2T(n1/2)+n,n>2,且有k，使得解答：由递归方程，递推得T(n)=n1/2T(n1/2)+n=n1/2[(n1/2)1/2T((n1/2)1/2)+n1/2]+n=n1/2n1/4T(n1/4)+n+n=n1/2n1/4[(n1/4)1/2T((n1/4)1/2)+n1/4]+2n=n1/2n1/4n1/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/5┇x(n)=Cn-12(n-1)/nx(n+1)=Cn2n/(n+1)12.求证递归方程T（1）=0T(n)=T(n/2)+T(n/2)+n-1,n>1的解是T(n)=nlogn–2logn+1。证明：（1）当n=2时，由递归方程和初值，推得T（2）=T（1）+T（1）+2-1=0+0+2-1=1由方程的解，得T（2）=2-2+1=1。所以，结论成立。（2）假设当n≤k时成立,既有T(k)=klogk–2logk+1是原递归方程的解。那么当n=k+1时，下面证明T(k+1)=(k+1)log(k+1)–2log(k+1)+1是原递归方程的解。当n≤k时,T(k/2)+T(k/2)+k-1=klogk–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=2T(k/2)+k=2[k/2·logk/2–2logk/2+1]+k=(k+1)·logk/2–2logk/2+1+2+k=(k+1)(log（k+1）/2+1)–2log（k＋1）/2+log2+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时，命题成立。所以，原命题成立。第3章一、选择题1.B 2.B二、填空题1.logn＋12.2n-1三、简答题1.将一个难以直接解决的大问题，分割成一些规模较小的类型相同问题，这些子问题相互独立，以便各个击破，分而治之。如果原问题可分割成m个子问题，1＜m≤n，并且这些子问题都可解，然后求解这些问题，那么就可利用这些子问题的解求出原问题的解；如果子问题还比较复杂而不能直接求解，还可以继续细分，直到子问题足够小，能够直接求解为止。此外，为了得到原始问题的解，必须找到一种途径能够将各个子问题的解组合成原始问题的一个完整答案。2.将待查的数据与非降序数组中的中间元素进行比较，若二者相等则表示查到；若该数据小于中间元素的值，则下次在数组的前半部分中继续找；否则，在数组的后半部分中查找。即每次检索将与待查数据的比较次数减半。如此继续进行下去，直到查到该值的元素或不存在所查找的数据。此种分治方法，称为二分检索。四、计算题1.作一个“二分”检索算法，它将原集合分成1/3和2/3大小的两个子集。分析此算法并与算法3.1比较。输入：已按非减序分类的n个元素的数组A和X，X是被检索的项。A[0]未用。输出：若X在A中，输出下标j满足A[j]=X，否则输出0。IntBinarySearch(A,n,X){intk=1;m=n;while(k<=m){j=(k+m)/3;/*j=(k+m)/3*/if(X==A[j])returnj;if(X<A[j])m=j-1elsek=j+1;return0；}时间分析：比较次数2.作一个“三分”检索算法，它首先检查1/3处的元素是否与X相等，然后检查2/3处的元素，等等。这样，或者找到X，或者将集合缩小到原来的1/3。试写出此算法并分析其复杂性。输入：已安排减序分类的n个元素的数组A和X，X是被检索的项。A[0]未用。输出：若X在A中，输出下标j满足A[j]=X，否则输出0。IntThirdSearch(A,n,X){intk=1;m=n;While(k<=m){i=(k+m)/3;/*i=(k+m)/3*/if(X==A[i])returni;if(X<A[i])m=i-1else{j=2(k+m)/3)/;/*j=2(k+m)/3)*/if(X==A[j])returnj;if(X<A[j]){k=i+1;m=j-1}elsek=j+1;}}return0；}时间分析：比较次数解得方程：T(n)=1+log3n3.设计一个在有n个元素的集合中通过比较找出最大和次最大元素的算法，使其复杂度为n+logn-2。算法：找最大和次大元素输入：有n个元素的数组A输出：最大和次最大元素Max和SubMax。voidFind(A)//递归算法{if(|A|==2){设A={a,b}(Max,SubMax)(Max(a,b),SubMax(a,b));}else{把A分成两个子集A1和A2，各有一半元素；(Max1,SubMax1)Find(A1);(Max2,SubMax2)Find(A2);SubMax3=Min(Max1,Max2);SubMax4=Max(SubMax1,SubMax2)(Max,SubMax)(Max(Max1,Max2),SubMax(SubMax3,SubMax4))}}时间分析：T(n)为算法的最坏时间。当n=2时，T(n)=1；当n>2时，则需要进行两次递归调用及之后的比较。故有：T(n)=5n/24.求解最接近中位数的k个数：给定由n个互不相同的数组成的集合A以及正整数k≤n，设计一个O（n）时间复杂度的查找A中最接近A的中位数的k个数的算法。在采用分治法进行查找时，为了满足分治法的平衡原则，需要将数组分成两个大小基本相同的子数组，其中的那个划分点就是中位数。所以，中位数是指数组中能将数组划分成两个大小基本相同的两个子数组的那个元素，即中位数是第n／2小的数。解析：（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的中位数设A［0∶n-1］和B［0∶n-1］为两个数组，每个数组中含有n个已排好序的数。设计一个O(1ogn)时间复杂度的算法，找出A和B的2n个数的中位数median。解析：（1）算法设计思想。考虑问题的一般性：设A［il：j1］和B［i2：j2］是A和B的排序好的子数组，且长度同，即j1-i1=i2-j2。找出这两个子数组中2(j1-i1＋1)个数的中位数。首先注意到，若A［i1］≤B［j2］，则中位数median满足A［i1］≤median≤B［j2］。同理，若A［i1］≥B［j2］，则B［j2］≤median≤A［i1］。设m1＝(i1＋j1)／2，m2=(i2＋j2)／2，则m1十m2＝((i1＋j1)／2＋(i2十j2)／2＝i1＋(j1一i1)／2+i2＋(j2—i2)／2＝i1＋i2＋(j1一il)／2＋(j2—i2)／2。由于j1—i1＝j2—i2，故(j1一i1)／2＋(j2一i2)／2＝j1一i1＝j2一i2。因此，m1＋m2＝i1＋i2＋jl一i1＝i2＋jl＝i1＋i2＋j2—i2＝i1＋j2。当A［m1］＝B［m2］时，median＝A［m1］＝B［m2］。当A［m1］＜B［m2］时，设median1是A［m1：jl］和B［j2：m2］的中位数，则median＝Median1。当A［m1］＞B［m2］时，设median2是A［i1：m1］和B［i2：j2］的中位数，类似地有median＝median2。通过以上的讨论，可以设计出查找两个子数组A［i1:j1］和B［i2: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＝(i1＋j1)／2＝3，m2=(i2＋j2)／2＝3。A［m1］＝62，B［m2］＝67，则根据当A［m1］＜B［m2］时，设median1是A［m1：jl］和B［i2：m2］的中位数，则median＝Median1。有：median＝A［m1：jl］和B［i2：m2］的中位数＝A［3：6］和B［0：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＝(i1＋j1)／2＝3，m2=(i2＋j2)／2＝3。A［m1］＝62，B［m2］＝60，则根据当A［m1］＞B［m2］时，设median2是A［i1：m1］和B［m2：j2］的中位数，类似地有median＝median2。有：median＝A［0：3］和B［3：6］的中位数＝A［3：6］和B［0：3］的中位数＝{12，34，56，62}和{60，89，103，120}的中位数＝60解答：（1）x=1011,y=1101Mul(1011,1101,4)//整数相乘算法3.1A=10,B=11,C=11,D=01m1=Mul(A,C,n/2)=Mul(10,11,2)//递归调用A=1,B=0,C=1,D=1m1=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)=0m3=Mul(B,D,n/2)=Mul(0,1,2/2)=01*(1*22+(1+0+0)*21+0)=110//返回Mul(10,11,2)=110m2=Mul(A-B,D-C,n/2)=Mul(10-11,01-11,2)=Mul(-1,-10,2)s=(-1)*(-1)=1A=0,B=1,C=1,D=0m1=Mul(A,C,n/2)=Mul(0,1,2/2)=0m2=Mul(A-B,D-C,n/2)=Mul(-1,-1,2/2)=1m3=Mul(B,D,n/2)=Mul(1,0,2/2)=01*(0*22+(0+1+0)*21+0)=10m3=Mul(B,D,n/2)=Mul(11,01,2/2)A=1,B=1,C=0,D=1m1=Mul(A,C,n/2)=Mul(1,0,2/2)=0m2=Mul(A-B,D-C,n/2)=Mul(0,1,2/2)=0m3=Mul(B,D,n/2)=Mul(1,1,2/2)=11*(0*22+(0+0+1)*21+1)=111*(110*24+(110+10+11)*22+11)=10001111//返回Mul(1011,1101,4)=10001111（2）x=3141,y=5327Mul(3141,5327,4)//整数相乘算法4.1A=31,B=41,C=53,D=27m1=Mul(A,C,n/2)=Mul(31,53,2)A=3,B=1,C=5,D=3m1=Mul(A,C,n/2)=Mul(3,5,2/2)=15m2=Mul(A-B,D-C,n/2)=Mul(2,-2,2/2)=-4m3=Mul(B,D,n/2)=Mul(1,3,2/2)=31*(15*102+(15-4+3)*10+3)=1643m2=Mul(A-B,D-C,n/2)=Mul(31-41,27-53,2)=Mul(-1,-10,2)s=(-1)*(-1)=1A=1,B=0,C=2,D=6m1=Mul(A,C,n/2)=Mul(1,2,2/2)=2m2=Mul(A-B,D-C,n/2)=Mul(1,4,2/2)=4m3=Mul(B,D,n/2)=Mul(0,6,2/2)=01*(2*102+(2+4+0)*101+0)=260m3=Mul(B,D,n/2)=Mul(41,27,2/2)A=4,B=1,C=2,D=7m1=Mul(A,C,n/2)=Mul(4,2,2/2)=8m2=Mul(A-B,D-C,n/2)=Mul(3,5,2/2)=15m3=Mul(B,D,n/2)=Mul(1,7,2/2)=71*(8*102+(8+15+7)*101+7)=11071*(1643*104+(1643+260+1107)*102+1107)=16732107//返回Mul(3141,5327,4)=167321077.修改整数乘积算法3-7，把每个整数分成：（1）三段，（2）四段，然后给出相应算法的复杂度。解答：（1）三段。假定n是3的幂。我们把n位的二进制整数看成由三个n/3位整数构成的。则有：那么，X和Y的乘积可表示为：X*Y=(A22n/3+B2n/3+C)*(D22n/3+E2n/3+F)=AD24n/3+(AE+BD)2n+(AF+BE+CD)22n/3+(BF+CE)2n/3+CF改进如下：X*Y=AD24n/3+(VW+AD+BE)2n+(MN+AD+BE+CF)22n/3+(PS+BE+CF)2n/3+CF其中，V=A-B，W=E-D，M=A-C，N=F-D，P=B-C，S=F-E时间分析：记T(n)为算法的最坏时间，则比较总次数为方程的解是算法：分三段整数乘积输入：两个n位的二进制整数X和Y。输出：整数的乘积。IntMult(X,Y,n){s=sign(X)*sign(Y);X=abs(X);Y=abs(Y);If(n==1)ReturnX*Y;Else{A=X的左边n/3位；B=X的中间n/3位；C=X的右边n/3位；D=Y的左边n/3位E=Y的中间n/3位；F=Y的右边n/3位；M1=Mult(A,D,n/3);M2=Mult(A-B,E-D,n/3);M3=Mult(A-C,F-D,n/3);M4=Mult(B,E,n/3);M5=Mult(B-C,F-E,n/3);M6=Mult(C,F,n/3);Returns*(m1*24n/3+(m1+m2+m4)*2n+(m1+m3+m4+m6)*22n/3+(m4+m6)2n/3+m6)}}（2）四段。假定n是4的幂。我们把n位的二进制整数看成由四个n/4位整数构成的。则有：那么，X和Y的乘积可表示为：X*Y=(A23n/4+B2n/2+C2n/4+D)*(E23n/4+F2n/2+G2n/4+H)=AE23n/2+(AF+BE)25n/4+(AG+BF+CE)2n+(AH+BG+CF+DE)23n/4+(BH+CG+DF)2n/2+(CH+DG)2n/4+DH改进如下：X*Y=AE23n/2+(VW+AE+BF)25n/4+(MN+AE+CG+BF)2n+(PS+RU+AE+DH+BF+CG)23n/4+(TJ+BF+DH+CG)2n/2+(OQ+CG+DH)2n/4+DH其中，V=A-B,W=F-E,M=A-C,N=G-E,P=A-D,S=H-E,R=B-C,U=G-F,T=B-D,J=H-F,O=C-D,Q=H-G时间分析：记T(n)为算法的最坏时间，则比较总次数为方程的解是算法：分四段整数乘积输入：两个n位的二进制整数X和Y。输出：整数的乘积。IntMult(X,Y,n){s=sign(X)*sign(Y);X=abs(X);Y=abs(Y);If(n==1)ReturnX*Y;Else{A=X的最左边n/4位；B=X的次左边n/4位；C=X的次右边n/4位；D=X的最右边n/4位；E=Y的最左边n/4位F=Y的次左边n/4位；G=Y的次右边n/4位；H=Y的最右边n/4位；M1=Mult(A,E,n/4);M2=Mult(B,F,n/4);M3=Mult(A-C,G-E,n/4);M4=Mult(A-B,F-E,n/4);M5=Mult(A-D,H-E,n/4);M6=Mult(B-C,G-F,n/4);M7=Mult(B-D,H-F,n/4);M8=Mult(C-D,F-E,n/4);M9=Mult(A-D,H-G,n/4);M10=Mult(C,G,n/4);Returns*(m1*23n/2+(m1+m2+m4)*25n/4+(m1+m2+m3+m10)*2n+(m1+m2+m5+m6+m9+m10)23n/4+(m2+m7+m9+m10)2n/2+(m8+m9+m10)2n/4+m9)}}8.用Strassen矩阵乘法计算乘积：解答：Strassen矩阵乘法X1=(a11+a22)*(b11+b22)=(1+4)*(5+8)=65X2=(a21+a22)*b11=(3+4)*5=35X3=a11*(b12-b22)=1*(6-8)=-2X4=a22*(b21-b11)=4*(7-5)=8X5=(a11+a12)*b22=(1+2)*8=24X6=(a21-a11)*(b11+b12)=(3-1)*(5+6)=22X7=(a12-a22)*(b21+b22)=(2-4)*(7+8)=-30c1=X1+X4-X5+X7=65+8-24-30=19c2=X3+X5=-2+24=22c3=X2+X4=35+8=43c4=X1+X3-X2+X6=65-2-35+22=509.设n=2km，用Strassen算法，求两个n×n矩阵的积，并估计复杂性。解答：对于任何非零偶数n，总可以找到基数m和正整数k，使得n=2km。为了求出两个n矩阵的积，可以把一个n矩阵分成m×m个2k×2k的子矩阵。当求解2k×2k子矩阵的积时，使用Strassen算法，其时间复杂度为O（7k）。使用传统方法求两个m阶矩阵的乘积，其时间复杂度为O（m3）。所以，算法总的间复杂度为O（7km3）。10.Strassen算法的另一种形式是用下面的恒等式计算两个2x2矩阵的乘积，如此处理共用了7次乘法和15次加法。S1=a21+a22m1=s2*s6t1=mS2=s1-a11m2=a11*b11t2=t1S3=a11-a21m3S4=a12-s2m4=sS5=b12-b11m5=s1*sS6=b22-s5m6=s4*bS7=b22-b12m7=a22*sS8=s5-b21乘积矩阵的元素是：c11=m2+m3c12=t1+m5+mc21=m2-m7c22=t2+m试证明上述等式确实计算了cij，1≤I,j≤2。证明：由于C=AxB，则有：那么，就有：c11=a11xb11+a12xb21c12=a11xb12+a12xbc21=a21xb11+a22xb21c22=a21xb12+a22xb而根据题中所给的Strassen恒等式计算，得c11=m2+m3=a11xb11+a12xb21c12=t1+m5+m6=m1+m2+m5+m6=s2*s6+a22*b11+s1*s5+s4*b22=(s1-a11)*(b22-s5)+a22*b11+(a21+a22)*(b12-b11)+(a12-s2)*b22=(a21+a22-a11)*(b22-b12+b11)+a22*b11+(a21+a22)*(b12-b11)+(a12-s1-a11)=(a21+a22-a11)*(b22-b12+b11)+a22*b11+(a21+a22)*(b12-b11)+(a12-a21-a22-a11)=a11xb12+a12xb22c21=m2-m7=a11*b11-a22*s8=a11*b11-a22*(s5-b21)=a11*b11-a22*(b12-b11-b21)=a22*b21-a22*b12c22=t2+m5=t1+m4+s1*s5=m1+m2+s3*s7+(a21+a22)*(b12-b11)=s2*s6+a22*b11+(a11-a21)*(b22-b12)+(a21+a22)*(b12-b11)=(s1-a11)*(b22-s5)+a22*b11+(a11-a21)*(b22-b12)+(a21+a22)*(b12-b11)=(a21+a22*a11)*(b22-b12+b11)+a22*b11+(a11-a21)*(b22-b12)+(a21+a22)*(b12-b11)=a21*b12+a22*b2211.对于两个n阶防阵的乘积，若n是3的幂，则用分治法可把问题归结为3×3矩阵的乘积。试设计一种算法使得仅用21次乘法而不是27次此乘积。类似地，对4×4矩阵设计一种48次乘法的算法。答案：[略]。12.设P(x)=p0+p1x+┅+p7x7。在p上执行FFT的步骤，以说明它是如何计算p的傅立叶变换的。解答：=cos(2π/n)+sin(2π/n)=cos(2π/8)+isin(2π/8)=2-1/2(1+i)，则有：开始：FFT(8,P(x),,A)N1=4;Pe(x)=p0+p2x+p4x2+p6x3;Po(x)=p1+p3x+p5x2+p7x3;=1\*GB3①FFT(4,Pe(x),2,B)N1=2;Pe(x)=p0+p4x;Po(x)=p2+p6x;=2\*GB3②FFT(2,Pe(x),4,B)N1=1Pe(x)=p0;Po(x)=p4;=3\*GB3③FFT(1,Pe(x),8,B)B[0]=p0;=3\*GB3③FFT(1,Po(x),8,C)C[0]=p4W[-1]=1/4j=0;W[0]=4*(1/4)=1;B[0]=B[0]+W[0]*C[0]=p0+p4;B[0+1]=B[0]-W[0]*C[0]=p0-p4;=2\*GB3②FFT(2,Po(x),4,C);N1=1Pe(x)=p2;Po(x)=p6;=3\*GB3③FFT(1,Pe(x),8,B)B[0]=p2;=3\*GB3③FFT(1,Po(x),8,C)C[0]=p6W[-1]=1/4j=0;W[0]=4*(1/4)=1;C[0]=B[0]+W[0]*C[0]=p2+p6;C[0+1]=B[0]-W[0]*C[0]=p2-p6;j=0W[0]=2*(1/2)=1;B[0]=B[0]+W[0]*C[0]=p0+p4+p2+p6；B[0+2]=B[0]-W[0]*C[0]=p0+p4-p2-p6；j=1W[1]=2*1=2;B[1]=B[1]+W[1]*C[1]=p0-p4+2(p2-p6)；B[1+2]=B[1]-W[1]*C[1]=p0-p4-2(p2-p6)；=1\*GB3①FFT(4,Po(x),2,C)N1=2;Pe(x)=p1+p5x;Po(x)=p3+p7x;=2\*GB3②FFT(2,Pe(x),4,B)N1=1Pe(x)=p1;Po(x)=p5;=3\*GB3③FFT(1,Pe(x),8,B)B[0]=p1;=3\*GB3③FFT(1,Po(x),8,C)C[0]=p5W[-1]=1/4j=0;W[0]=4*(1/4)=1;B[0]=B[0]+W[0]*C[0]=p1+p5;B[0+1]=B[0]-W[0]*C[0]=p1-p5;=2\*GB3②FFT(2,Po(x),4,C);N1=1Pe(x)=p3;Po(x)=p7;=3\*GB3③FFT(1,Pe(x),8,B)B[0]=p3;=3\*GB3③FFT(1,Po(x),8,C)C[0]=p7结束。13.试计算下列序列（多项式，仅给出了系数）的傅立叶变换：（1）[0，1，2，3]（2）[1，2，0，2，0，0，0，1]分析：n_向量P(p0,p1,p2,…,pn-1)的傅立叶变换Y=Fn·P，Y的第i个分量yi可以写成：，…，解答：（1）多项式P(x)=p0+p1x+┅+pn-2xn-2+pn-1xn-1=x+2x2+3x3（2）多项式P(x)=p0+p1x+┅+pn-2xn-2+pn-1xn-1=1+2x+2x3+x7第4章一、选择题1.B 2.C二、填空题1.可行解；目标函数；最优解2.最优度量标准三、简答题1.背包问题、磁带的最优存储、有期限的作业调度问题等。2.当一个问题的最优解算法的复杂度很高时，如果利用某种办法产生的算法能很快地得到较好的解（或称为次优解、满意解），可能就相当满意了。从这种愿望出发就形成了所谓启发式的算法设计方法。四、计算题1.求下面背包问题的最优解：n=6,M=20,(p1,p2,…,p6)=(11,8,15,18,12,6),(W1,W2,…,W6)=(5,3,2,10,4,2)解答：根据题义约束条件，下面确定目标函数中的xi。(P[1]/W[1],P[2]/W[2],P[3]/W[3],P[4]/W[4],P[5]/W[5],P[6]/W[6])=(2.2,8/3,7.5,1.8,3,3)按非递增次序排序：P[3]/W[3]>P[5]/W[5]≥P[6]/W[6]>P[2]/W[2]>P[1]/W[1]>P[4]/W[4]根据算法有：W[3]=2<M=20则x[3]=1;W[5]=4<20-2=18则x[5]=1;W[6]=2<18-4=14则x[6]=1;W[2]=3<14-2=12则x[2]=1;W[1]=5<12-3=9,则x[1]=1;W[4]=10>9-5=4,则x[4]=4/10;所以，（x1,x2,x3,x4,x5,x6）=(1,1,1,0.4,1,1)，。2.磁带最优存储问题：设有n=5个程序，要存放在长为L的磁带上。程序i存放在磁带上的读取概率为x=（0.71，0.46，0.9，0.73，0.35），长度p=（872，452，265，120，85），编写程序确定这n个程序的存储次序，使得平均读取时间最小。解答：要使平均读取时间最小，则应按照长度的非递减次序存放。实际上，第k个程序的读取概率为。doublegreedy(intx，int[]p){intn=p.length;int[]y=newint[n];for(inti=0;i<n;i＋＋)y[i]=x[i]*p[i];QuickSort.quickSort(y，n);for(inti=1;i<n;i＋＋)y[i]＋=y[i－l];doublem=0,t=0;for(inti=0;i<n;i＋＋){m＋=p[i];t＋=y[i];}returnt/m;}结果：85.6193。3.令n=5,(p1,p2,p3,p4,p5)=(20,15,10,5,1),(d1,d2,d3,d4,d5)=(2,2,1,3,3),,分别使用算法4.3和算法4.4，选择最大效益作业子集，请问运算结果是什么？解答：运算结果是（J[1],J[2],J[3]）=(1,2,4)，总收益是40。4.以下是一个无向图的权矩阵，根据算法4.6，求此无向图中由n条边构成的周游路线及其权。解答：（1）给各行中的最小元素及其对称元素加标记，结果见图A-3（a）。（2）扫描各行，将所在行和列加标个数多于2的元素找出即元素10，撤去该元素及其对称元素的标记。如图A-3（b）。（a）（b）图A-3（3）得到一条闭合回路，它由边(1,4),(4,3),(3,6),(6,2),(2,5),(5,1)组成，总权值数是8+7+4+12+14+9=54。第5章一、选择题D二、填空题1.分而治之思想；排队冗余策略2.最优子结构特性；子问题重叠性质3.0/1背包问题装入的物品是不可拆分的，而背包问题装入的物品是可拆分的三、简答题1.无论过程初始的状态和策略如何，其余的决策必须相对于初始决策所造成的状态构成一个最优的决策序列。2.（1）找出最优解的性质，并刻画最优解的结构特性；（2）递归定义最优解值；（3）以自底向上方式计算最优解值；（4）根据计算得到的信息构造一个最优解。3.最短路径、0/1背包问题、多矩阵相乘、货郎担问题、资源分配。四、计算题1.如图A-4给出的有向图，其中每条边均指向x轴或y轴的正向。如果OA和OB上分别具有m和n个结点，那么，若求出由O到C的一条最短路，共需多少次比较？当m=4和n=5时，求出这条最短路及其权（各边的权写在边的近旁）。图A-4带权有向图解答：先将图分级，如图A-5所示。图A-5分级有向图根据公式,有d(7,18)=a(18,20)=4,d(7,19)=a(19,20)=3}计算V7→V8的最短路径不需要比较；V6→V7的最短路径需要比较一次；V5→V6的最短路径需要比较二次；V4→V5的最短路径需要比较三次；V3→V4的最短路径需要比较三次；V2→V3的最短路径需要比较二次；d(1,1)=min{1+d(2,2),3+d(2,3)}=min{19,21}=19}计算V1→V2的最短路径需要比较一次；最短路径为1→2→4→8→12→16→18→20。比较分析：计算V7→V8的最短路径不需要比较；计算V6→V7的最短路径需要比较一次；计算V5→V6的最短路径需要比较二次；计算V4→V5的最短路径需要比较三次；计算V3→V4的最短路径需要比较三次；计算V2→V3的最短路径需要比较二次；计算V1→V2的最短路径需要比较一次；所以，总共的比较次数是12次。归纳如下：当m=2,n>2时,比较n-1次。当m>2,n=2时,比较m-1次。当m>2,n>2时,m+n（1）奇数，比较：S=1+2+…+(m+n-3)/2+(m+n-3)/2+…+3+2+1=(m+n-1)(m+n-3)/4（2）偶数，比较：S=1+2+…+(m+n-2)/2+…+3+2+1=(m+n-2)2/4当m=4,n=5时，代入公式得S=12次。2.解0/1背包问题：n=4,M=14,(W1,W2,W3,W4)=(3,6,8,4),(P1,P2,P3,P4)=(2,4,6,3).解答：便于区间的考虑，(w1,w2,w3,w4)=(3,4,6,8)=(W1,W4,W2,W3),(p1,p2,p3,p4)=(2,3,4,6)=(P1,P4,P2,P3)初始条件再根据公式fi(x)=max{fi-1(x),fi-1(x-Wi)+pi}，可递推得最优解是10，最优序列为（0，1，1，0）。解答：初始条件根据公式fi(x)=max{fi-1(x),fi-1(x-Wi)+Pi}，可递推得最优解是10，最优序列为（0，1，1，0）。3.对于以下的矩阵乘法，计算其最小的运算次数及结合方式。M=M1×M2×M3×M4[10×20][20×10][10×30][30×50]解答：由已知(r0,r1,r2,r3,r4)=(10,20,10,30,50)根据公式m11=0,m22=0,m33=0,m44=0m12=2000,m23=6000,m34=15000m13=5000,m24=25000,m14=20000最小运算次数为20000次。结合方式:(((A1*A2)*A3)*A4)4.利用动态规划法求图A-6中的一条最优的周游路线及其权。图A-6带权无向图解答：设g(i,S)是由结点i开始，通过S中的所有结点一次，然后终止于结点i的一条最短路径的权，这里是从A点出发,通过B,C,D,E,F,G,H结点一次再回到A点的最优周游路线，则根据递推关系：，可以求得最优周游路线。计算如下：g(B,Ø)=3,g(C,Ø)=∞,g(D,Ø)=∞,g(E,Ø)=∞,g(F,Ø)=5,g(G,Ø)=1,g(H,Ø)=∞g(B,{G})=aBG+g(G,Ø)=2+1=3,g(C,{B})=aCB+g(B,Ø)=1+3=4,g(B,{C})=aBC+g(C,Ø)=1+∞=∞,g(D,{C})=aDC+g(C,Ø)=2+∞=∞,g(G,{C})=aGC+g(C,Ø)=3+∞=∞,g(C,{D})=aCD+g(D,Ø)=2+∞=∞,g(G,{D})=aGD+g(D,Ø)=4+∞=∞,g(H,{D})=aHD+g(D,Ø)=1+∞=∞,g(E,{D})=aED+g(D,Ø)=3+∞=∞,g(G,{F})=aGF+g(F,Ø)=2+5=7,g(H,{F})=aHF+g(F,Ø)=2+5=7,g(E,{F})=aEF+g(F,Ø)=2+5=7,g(B,{G})=aBG+g(G,Ø)=2+1=3,g(F,{G})=aFG+g(G,Ø)=2+1=3,g(C,{G})=aCG+g(G,Ø)=3+1=4,g(H,{G})=aHG+g(G,Ø)=3+1=4,g(D,{G})=aDG+g(G,Ø)=4+1=5,g(E,{G})=aEG+g(G,Ø)=∞+1=∞,g(F,{G,B})=min{aFG+g(G,{B}),aFB+g(B,{G})}=7,g(H,{G,B})=min{aHG+g(G,{B}),aHB+g(B,{G})}=8,g(C,{G,B})=min{aCG+g(G,{B}),aCB+g(B,{G})}=4,g(D,{G,B})=min{aDG+g(G,{B}),aDB+g(B,{G})}=9,…最优的周游路线：A→G→F→E→H→D→C→B→A,权值为15。第6章一、选择题1.D 2.D二、填空题1.每个xi范围；xi