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

'参考答案61参考答案第1章一、选择题1.C2.A3.C4.CADB5.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）数据模型和该模型上的运算统一在抽象数据类型中，反映它们之间内在的互相依赖和互相制约的关系，便于空间和时间耗费的折衷，灵活地满足用户要求。 参考答案61（4）由于顶层设计和底层实现局部化，在设计中出现的差错也是局部的，因而容易查找也容易纠正，在设计中常常要做的增、删、改也都是局部的，因而也都容易进行。因此，用抽象数据类型表述的算法具有很好的可维护性。（5）算法自然呈现模块化，抽象数据类型的表示和实现可以封装，便于移植和重用。（6）为自顶向下逐步求精和模块化提供有效途径和工具。（7）算法结构清晰，层次分明，便于算法正确的证明和复杂性的分析。3.算法的复杂度是算法运行所需要的计算机资源的量。4.当问题的规模递增时，将复杂度的极限称为渐进复杂度。5.采用复杂性渐近性态替代算法复杂度，使得在数量级上估计一个算法的执行时间成为可能。四、计算题1.验证下面的关系：O（1）.#defneN50intbsearch(int*a,intn,intx)//参数为数组、元素个数和被查找的值{intk=0,m=n-1,mid;//k，m，mid为被查找区间的最小、最大和中间元素下标　　while(k<=m)//若最小下标超过最大下标则终止循环，说明不存在　　{mid=(k+m)/2;//取中间下标，注意整数相除取整　　if(x==a[mid];　　　retummid;//相等时绔束，返回元求下标　　else　　　if(xë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时，则2k0。用数学归纳法证明命题：当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。②∵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的非递归形式的表达式。解答：原方程所对应的特征方程为： 参考答案61a2-a-6=0为齐次方程，则齐次解:q1=3,q2=-2,重数均为1。记通解的形式为:an=Aq1n+Bq2n=A3n+B(-2)n将a0=1,a1=1代入上式，得A+B=13A-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+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)-5C=14(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,当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=5解得：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 参考答案61令，则有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)=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）假设当n≤k时成立,既有T(k)=kélogkù–2élogkù+1是原递归方程的解。那么当n=k+1时，下面证明T(k+1)=(k+1)élog(k+1)ù–2élog(k+1)ù+1是原递归方程的解。当n≤k时,T(ëk/2û)+T(ék/2ù)+k-1=kélogkù–2élogkù+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ù·élogék/2ùù–2élogék/2ùù+1]+k=(k+1)·élogék/2ùù–2élogék/2ùù+1+2+k 参考答案61=(k+1)(élog（k+1）/2+1ù)–2élog（k＋1）/2+log2ù+1=(k+1)élog(k+1)－1+1ù–2élog(k+1)ù+1=(k+1)élog(k+1)ù–2élog(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)ù－2élog(k/2)ù+1+[(k/2+1)élog(k/2+1)ù－2élog(k/2+1)ù+1]+k=(k/2+k/2+1)élog(k/2)ù–(2élog(k/2)ù+2élog(k/2+1)ù)+2+k=(k+1)élog(k/2)ù–2élog(k/2)ù+1+2+k=T(k+1)即当n=k+1时，命题成立。所以，原命题成立。五、上机题1．计算Hermite多项式Voidmain(){Printf(“n%f“,H(2,2.0));//输出结果76.000000}DobuleH(intn,floatx){Switch(n){Case0:return1;Case1:2*x;}Return2*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）汉诺塔问题的递归算法如下：publicstaticvoidHanoi(intn,intA,intB,intC){ 参考答案61if(n>O){Hanoi(n-1,A,C,B)"Move(n,A,B);Hanoi(n-l,C,B,A);}}（2）汉诺塔问题的非递归算法。教材中所述非递归算法的目的塔座不确定。当n为奇数时，目的塔座是B，按顺时针方向移动；而当n为偶数时，目的塔座为C，按反时针方向移动。为确定起见，规定目的塔座为B。汉诺塔问题的非递归算法可描述如下：publicstaticvoidHanoi(intn){int[]top={0，0，0}int　［］［］tower=newint[n+1][3];intx,y,min=O;Booleanb,bb;for(inti=0;i<=n;i++){tower[i][0]=n-i+1;tower[i][1]=n+l;tower[i][2]=n+l;}top[0]=n;b=odd(n);bb=true;;while(top[1]tower[top[y]]|y]){inttmp=x;x=y;y_tmp;}}move(tower[top[x]][x],x+1,y+l);tower[top[y]+1][y]=tower[top[x]][x];top[x]--;top[y]++;}}下面用数学归纳法证明递归算法和非递归算法产生相同的移动序列。当n＝1和n＝2时容易直接验证。设当k≤n－1时，递归算法和非递归算法产生完全相同的移动序列。考察k＝n的情形。将移动分为顺时针移动（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（n－1，A，C，B）产生的移动序列，O，Hanoi（n－1，C，B，A）产生的移动序列。Hanoi（n－1，A，C，B）和Hanoi（n－1，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（n－1，A，C，B）产生的移动序列，O，Hanoi（n－1，C，B，A）产生的移动序列。Hanoi（n－1，A，C，B）和Hanoi（n－1，C，B，A 参考答案61）均为奇数圆盘逆时针移动问题。由数学归纳法知，产生的移动序列均为：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（n－1，A，C，B）；②Move（A，B）；③Hanoi（n－1，C，B，A）。按归纳假设，步骤①不违反规则（3），且在移动过程中，塔座C上最底圆盘的编号与n-1具有相同奇偶性，塔座B上最底圆盘的编号与n-1具有不同奇偶性，从而塔座B上最底圆盘的编号与n具有相同奇偶性，塔座C上最底圆盘的编号与n具有不同奇偶性。步骤②也不违反规则（3），且塔座B上最底圆盘的编号与n相同。按归纳假设，步骤③不违反规则（3），且在移动过程中，塔座B上倒数第2个圆盘的编号与n－1具有相同奇偶性，塔座A上最底圆盘的编号与n－1具有不同奇偶性，从而塔座B 参考答案61上倒数第2个圆盘的编号与n具有不同奇偶性，塔座A上最底圆盘的编号与n具有相同奇偶性。因此在移动过程中，塔座B上圆盘不违反规则（3），而且塔座B上最底圆盘的编号与n具有相同奇偶性，塔座C上最底圆盘的编号与n具有不同奇偶性。由数学归纳法即知，Hanoi（n，A，B，C）不违反规则（3）。第3章一、选择题1.B2.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(X2时，则需要进行两次递归调用及之后的比较。故有：T(n)=5n/24.求解最接近中位数的k个数：给定由n个互不相同的数组成的集合A以及正整数k≤n，设计一个O（n）时间复杂度的查找A中最接近A的中位数的k个数的算法。在采用分治法进行查找时，为了满足分治法的平衡原则，需要将数组分成两个大小基本相同的子数组，其中的那个划分点就是中位数。所以，中位数是指数组中能将数组划分成两个大小基本相同的两个子数组的那个元素，即中位数是第én／2ù小的数。 参考答案61解析：（1）找出A中的中位数mid；（2）计算T={|a-mid|，aÎA}；（3）找出T的第k小元素b；（4）根据b找出所要的解{|a-mid|≤b，aÎA}。由于在最坏情况想选择的时间复杂度为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|，aÎA}：T={20，13，50，0，24，3，5}。（3）找出T的第k小元素b：T的第k小元素b=5。（4）根据b找出所要的解{a，|a-mid|≤b，aÎA}：{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)满足递归式： 参考答案61解此速归方程可得：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}的中位数＝606.利用整数相乘算法3-7计算两个二进制数1011和1101及两个十进制数3141和5327的乘积。解答：（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)=1 参考答案611*(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; 参考答案61Else{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位； 参考答案61M1=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=m1+m2S2=s1-a11m2=a11*b11t2=t1+m4S3=a11-a21m3=a12*b21S4=a12-s2m4=s3*s7S5=b12-b11m5=s1*s5S6=b22-s5m6=s4*b22S7=b22-b12m7=a22*s8 参考答案61S8=s5-b21乘积矩阵的元素是：c11=m2+m3c12=t1+m5+m6c21=m2-m7c22=t2+m5试证明上述等式确实计算了cij，1≤I,j≤2。证明：由于C=AxB，则有：那么，就有：c11=a11xb11+a12xb21c12=a11xb12+a12xb22c21=a21xb11+a22xb21c22=a21xb12+a22xb22而根据题中所给的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) 参考答案61N1=4;Pe(x)=p0+p2x+p4x2+p6x3;Po(x)=p1+p3x+p5x2+p7x3;①FFT(4,Pe(x),2,B)N1=2;Pe(x)=p0+p4x;Po(x)=p2+p6x;②FFT(2,Pe(x),4,B)N1=1Pe(x)=p0;Po(x)=p4;③FFT(1,Pe(x),8,B)B[0]=p0;③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;②FFT(2,Po(x),4,C);N1=1Pe(x)=p2;Po(x)=p6;③FFT(1,Pe(x),8,B)B[0]=p2;③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)；①FFT(4,Po(x),2,C)N1=2; 参考答案61Pe(x)=p1+p5x;Po(x)=p3+p7x;②FFT(2,Pe(x),4,B)N1=1Pe(x)=p1;Po(x)=p5;③FFT(1,Pe(x),8,B)B[0]=p1;③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;②FFT(2,Po(x),4,C);N1=1Pe(x)=p3;Po(x)=p7;③FFT(1,Pe(x),8,B)B[0]=p3;③FFT(1,Po(x),8,C)C[0]=p7 参考答案61结束。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可以写成：yi=p0+p1(i)+p2(i)2+┅+pn-2(i)n-2+pn-1(i)n-1，i=1，2，…，n。其中，是1的n次主根。解答：（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 参考答案61五、上机题＃include＃include＃include＃include＃includeusingnamespacestd;constintN=100005;constdoubleMAX=10e100;constdoubleeps=0.00001;typedefstructTYPE{doublex,y;   intindex;}Point;Pointa[N],b[N],c[N];doubleclosest(Point*,Point*,Point*,int,int);doubledis(Point,Point);intcmp_x(constvoid*,constvoid*);intcmp_y(constvoid*,constvoid*);intmerge(Point*,Point*,int,int,int);inlinedoublemin(double,double);intmain(){   intn,i;   doubled;   scanf("%d",&n);   while(n)   {       for(i=0;iq[j].y)           p[k++]=q[j],j++;       else           p[k++]=q[i],i++;   }   while(i<=m)       p[k++]=q[i++];   while(j<=t)       p[k++]=q[j++];   memcpy(q+s,p+s,(t-s+1)*sizeof(p[0]));   return0;}intcmp_x(constvoid*p,constvoid*q){   doubletemp=((Point*)p)->x-((Point*)q)->x;   if(temp>0)       return1;   elseif(fabs(temp)y-((Point*)q)->y;   if(temp>0)       return1;   elseif(fabs(temp)q)?(q):(p);第4章一、选择题1.B2.C 参考答案61二、填空题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]=29-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;icode="";p->letter=c;p->parent=0;p->sigh=none;p->weight=w;p++;getchar();}for(;i<=m;i++,p++){p->code="";p->letter="";p->parent=0;p->sigh=none;p->weight=0;}}//INITTREENODEvoidSelect(HuffmanTreeHT,intend,int*s1,int*s2){//在0~END之间,找出最小和次小的两个结点序号,返回S1,S2inti;intmin1=INT_MAX;intmin2;for(i=0;i<=end;i++){//找最小的结点序号if(HT[i].parent==0&&HT[i].weightHT[i].weight){*s2=i;min2=HT[i].weight;}}}voidHuffmanTreeCreat(HuffmanTree&HT){//建立HUFFMAN树inti;intm=2*n-1;ints1,s2;for(i=n;i2时,比较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)初始条件 参考答案61再根据公式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}，可递推得 参考答案61最优解是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+∞=∞, 参考答案61g(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。五、上机题1．实现数字三角形问题#includeints[100][100]={0};intfun(intx,inty,inta,intb){    if(s[x][y]==-1)    {      b=a>b?a:b;      returnb;    }    a=s[x][y]+a;    b=fun(x+1,y,a,b);    b=fun(x+1,y+1,a,b);    b=a>b?a:b;    returnb;}main(){    intn,i,j;    scanf("%d",&n);    for(i=0;i0)returna[m][n];if(m==0)returna[0][n]=n+1;if(n==0)returna[m][0]=ack(m+1,l).returna[m][n]=ack(m−l,ack(m,n−l));}另外还可用消去递归的方法，将上述算法非递归化如下。publicstaticintackm(intm,intn){inttop=1;s[l][l]=m;s[1][2]=n;while(top>0){m=s[top][1];n=s[top][2];top−−;if(top==0&&m==0)returnn+1;if(m==0)s[top][2]=n+1;elseif(n==0){s++top][1]=m−l;s[top][2]=l;}else{s[++top][l]=m−1;s[++top][1]=m;s[top][2]=n−1;}}returns[0][l];}实际上，还有一个稍简单的递归算法。publicstaticintack(intm,intn){for(inti=m;i>0;i−−){if(n==0)n=1;elsen=ack(i,n−1);}returnn+l;}同样也可将其改造为备忘录算法。这些算法都是自顶向下的递归算法。下面考察自底向上的动态规划算法，如表A-1所示。表A-1Ackermann函数A（m，n）值的变化nm01234567891001234567891011123456789101112235791113151719212335132961125253509102120454093818941365533565533首先对于较小的仍和n考察Ackermann函数A（m，n）的值的变化。从表13-2容易看出，当m＝0时，第0行对应于A（0，n）的值。当n＝0时，第0列对应于A（m，0）的值，其值恰好是第m－1行第1列的值。A（m，n）的值等于第m－1行第A（m，n－1）列的值。据此，可从第1行的值依次递推出各行的值。为此，用两个数组val［0：m］和ind［0：m］分别记录当前第i行计算到第ind［i］列的值，即已计算到A（i，ind［i］）的值，这个值存储于val［i］中。当计算到A（m，n）时，算法结束。按此思想设计的动态规划算法如下：publicstaticintack（intm，intn）{inti,val[],ind[];if(m==0)returnn+1; 参考答案61va1=newint[m+1];ind=newint[m+1];for(i=0;i<=m;i++)(val[i]=−1;ind[i]=−2;}val[0]=1;ind[0]=0;while(ind[m]#include//以time()结果做种子#include//优先队列（priority_queue）usingnamespacestd;constintN=8;//作业的数量constintTIME=99;//每个作业的时间被控制在两位数内constintNUM=1000;//测试次数classFlowshop1{private:int**M,   //各作业所需处理时间      n;     //作业数量   int*bestx,//当前的最优作业调度      *x,    //当前的作业调度      *f2,   //机器2完成的处理时间      f1,    //机器1完成的处理时间      f,     //完成的时间和      bestf; //当前的最优值   voidBacktrack(inti);   voidSwap(int&x,int&y);public:   Flowshop1(int**M,intn);   ~Flowshop1();   intgetBestf();   int*getBestx();};structMinHeapNode{   ints,  //已经安装作业数      f1, //机器1上最后完成的时间      f2, //机器2上最后完成的时间      sf2,//当前机器2上完成时间和      bb, //当前完成的时间和下界      *x; //当前作业的调度   MinHeapNode(intn){      x=newint[n];      for(inti=0;ib.bb);   }};classFlowshop2{private: 参考答案61   intn,  **M;   //作业数n，各作业所需处理时间M   int**b,   //各作业所需处理时间排序数组      **a,   //数组M和b对应关系数组      *bestx,//最优解      bestc; //最小完成的时间和   voidBBFlow(void);   intBound(MinHeapNode&E,int&f1,int&f2);   voidSort(void);   voidSwap(int&x,int&y);public:   Flowshop2(int**M,intn);   ~Flowshop2();   intgetBestf();   int*getBestx();};intmain(){   int*M[N],i;      srand(time(0));   for(intnum=1;num<=NUM;num++)   {      for(i=0;igetBestf(),my2->getBestf());      for(i=0,putchar("t");igetBestf()!=my2->getBestf()){         printf("tNotEqual");         getchar();//最优值不等，有错，等待...      }            for(i=0;igetBestx()[i]);      putchar("n");      for(i=0;igetBestx()[i]);      putchar("n");      for(i=0;igetBestx()[i]!=my2->getBestx()[i]){            putchar(7);//最优作业调度方案不同（允许不同），响铃            break;         }      }            deletemy1;      deletemy2;   }      for(i=0;iM=M;   this->n=n;   this->bestx=newint[n];   this->x=newint[n];   this->f2=newint[n]; 参考答案61   this->f1=0;   this->f=0;   this->bestf=(~(unsignedint)0)>>1;   for(inti=0;ix[i]=i;   this->Backtrack(0);}Flowshop1::~Flowshop1(){   delete[]bestx;   delete[]x;   delete[]f2;}intFlowshop1::getBestf(){   returnbestf;}int*Flowshop1::getBestx(){   returnbestx;}voidFlowshop1::Backtrack(inti){   if(i==n){      for(intj=0;jf1)?f2[i-1]:f1)+M[x[j]][1];            f+=f2[i];         }         if(fM=M;   this->n=n;   b=newint*[n]; //各作业所需处理时间排序数组   a=newint*[n]; //数组M和b对应关系数组 参考答案61   bestc=(~(unsignedint)0)>>1;//最小完成的时间和   for(inti=0;iSort();   this->BBFlow();}Flowshop2::~Flowshop2(){   for(inti=0;i,cmp>H;      MinHeapNodeE(n);   while(true)   {      if(E.s==n){//叶结点         if(E.sf2E.f2)?f1:E.f2)+M[E.x[E.s]][1];   intsf2=E.sf2+f2;      //机器1和机器2的作业顺序同，假设它们可以运行，分别都先运行时间短的,   //s1:假设机器2很快很快，s2:假设机器1很快很快   //原则是使估计得到的下界尽可能的大   ints1=0,k1=n-E.s,f3;   for(j=0;jf1+b[j][0])?f2:f1+b[j][0];         s1+=f1+k1*b[j][0];//假设作业在机器1上顺序执行并无时间间隔      }   }   ints2=0,k2=n-E.s;   for(j=0;js2)?s1:s2);}voidFlowshop2::Sort(void){//对各作业在机器1和2上所需时间排序   int*c=newint[n];   inti,j,k;      for(j=0;j<2;j++){      for(i=0;ii;k--){            if(b[k-1][j]>b[k][j]){//结果为从小到大排序               Swap(b[k-1][j],b[k][j]);               Swap(c[k-1],c[k]);            }         }      }      for(i=0;i1)factor(i);If(n>i)factor(n/i);}第9章一、选择题1.B2.B二、填空题1.单值；多值2.多项式时间；难解 参考答案61三、简答题1.用机器来模拟人们用纸笔进行数学运算的过程，它把这样的过程看作下列两种简单的动作：在纸上写上或擦除某个符号和把注意力从纸上的一个位置移动到另一个位置。2.随机存取机RAM、随机存取存储程序机RASP以及RAM模型的变形与简化和图灵机。四、计算题（略）第10章一、选择题1.B，A，C2.B二、填空题1.近似算法2.绝对性能保证，相对性能保证三、简答题1.使用AVC存储顶点覆盖中的各顶点。初始时AVC为空，然后在算法的循环中不断从图G的边集E中选取一边（u，v），将边的端点加入AVC中，并将E中已被u和v覆盖的边删去，直到AVC已覆盖所有边，即E为空时为止。2.集合覆盖问题是求F的一个最小规模子集C（CÍF），使得C中元素包含X的所有元素，称为C覆盖了X。比如，假设x是完成一项工作所需技能的集合。现有一组工作人员，其中每个人掌握若干种技能。问题是要求一个由尽可能少的人员组成的工程组，其中的工作人员具备该项工程所需的全部技能。四、计算题{①，②，③，④}。五、上机题见程序10-5近似子集和问题算法ApproxSubsetSum(S，r，ε)。第11章一、选择题1.C2.D二、填空题1.对称密码机制；非对称密码机制；2.明文；密文；密钥；加密算法；解密算法。三、简答题1.（1）使用两个密钥进行三次加密，定义成：C=EK1（DK2（EK1（P）））；（2）三密钥3DES的密钥长度为168位，定义成：C=EK3（DK2（EK1（P）））。2.（l）即使是纯粹的软件实现，AES也是很快的。例如，用C++在奔腾200的的电脑上实现的AES的加密速度可达到70M位／秒。Rijndael的非常低的内存需求也使它很适合用于受限环境中。 参考答案61（2）DES的S一盒的选择是人为的，从而可能包含后门；AES的S一盒具有一定的代数结构，并且能够抗击差分密码分析及线性密码分析。四、计算题1．解答：M=2´3´5=30M1=3´5=15，M2=2´5=10，M3=2´3=615y1≡1mod2，y1=110y2≡1mod3，y2=16y3≡1mod5，y3=1x=15+20+18=53≡23mod30。2．分析与解答：这里分组的列数为Nb，Nb=分组长度/32=128/32=4。Nk为密钥k的列数，Nk=密钥长度/32=128/32=4。加密算法输入的是明文，转换为状态字节，依次为b00，b10，b20，b30，b01，b11，b21，b31，b02，b12，b22，b32，b03，b13，b23，b33。加密结束时，输出也是从状态字节中按相同的顺序提取。下面给出以矩阵表示的状态字节：0004080C0105090D02060A0E03070B0FB[i,j]=子密钥是由密钥导出的，包括两部分，一是密钥膨胀，另一个是轮子密钥的选取。膨胀密钥是4字节的数组，用下式表示：W[Nb*（Nr+1）]那么，在这里有：W0=00010203W1=04050607W2=08090A0BW3=0C0D0E0F第i轮子密钥是由W[Nb*i]到W[Nb*（i+1）]间的位构成。第一个子密钥，为：K0=（W0，W1，W2，W3）0004080C0105090D02060A0E03070B0FK0=或者写成：第一步计算子密钥：W(i–)⊕tempt,imodNk=0W(i–)⊕Wi-1,imodNk≠0Wi= 参考答案61其中：tempt=ByteSub[S1（Wi-1）]⊕Rconk；Rconk=（RCk，00，00，00）；RC1=1；RCi=x*RCi-1=xi-1。W5=W1⊕W4=（04,05,06,07）⊕（D6,AA,74,FD）=（D2,AF,72,FA）W6=(DA,A6,78,F1)W7=(D6,AB,76,FE)所以，子密钥K1为：K1=（W4,W5,W6,W7）=（D6,AA,74,FD,D2,AF,72,FA,DA,A6,78,F1,D6,AB,76,FE）D6D2DAD6AAAFA6AB74727876FDFAF1FEK1=或者写成：W8=W4⊕ByteSub（S1W7）=（B6,92,CF,0B）W9=(64,3D,BD,F1)W10=(BE,9B,C5,00)W11=(68,30,B3,FE)所以，子密钥K2为：K2=（W4,W5,W6,W7）=（B6,92,CF,0B,64,3D,BD,F1,BE,9B,C5,00,68,30,B3,FE）或者写成：同理可得： 参考答案61第二步做变换。0004080C0105090D02060A0E03070B0F=B[i,j]0004080C0105090D02060A0E03070B0F00000000000000000000000000000000⊕=（1）初始轮B[i,j]⊕K[i,j]。（2）第1轮。①做ByteSub运算。00000000000000000000000000000000由于00和00对应，故第一步对bij做求乘法的逆，得做变换： 参考答案61得：63636363636363636363636363636363②ShiftRow变换。第0行保持不变，其他行内的字节循环移位，第l行移动Cl字节，第2行移动C2字节，第3行移动C3字节。Cl、C2、C3依赖于分组长度Nb。当Nb＝4或6时，取（Cl，C2，C3）＝（1，2，3）。如图和表所示。6363636363636363636363636363636363636363636363636363636363636363ShiftRow③MixColumn变换。每一列作为GF（28）上多项式乘以多项式c（x），模M（x）＝x4＋l。多项式MixColumn变换6363636363636363636363636363636363636363636363636363636363636363MixColumn④KeyAddition。63636363636363636363636363636363D6D2DAD6AAAFA6AB74727876FDFAF1FEB5B1B9B5C9CCC5C817111B159E99929D⊕=经过第一轮的加密得到密文为：C1=B5,C9,17,9E,B1,CC,11,99,B9,C5,1B,92,B5,C8,15,9D或者写成：B5B1B9B5C9CCC5C817111B159E99929D（3）第2轮。①Bytesub变换。ByteSub（S－盒）非线性、可逆，作用在状态的每个字节上表示为ByteSub（State）。该变换由两个子变换合成：首先，将字节看成GF（28）上的元素，按模m（x）映射到自己的乘法逆，0映射到自身。其次，做如下的GF（2）的仿射变换（可逆的）。可以预先将GF（28）上的每个元素做ByteSub变换，从而形成S一盒，进行ByteSub变换时只需要查表操作。见表A-2。可以看出该S一盒具有一定的代数结构，而DES中S一盒是人为构造的。 参考答案61表A-2Rijndael的S置换结果表ByteSubXY0123456789ABCDEF0637C777BF26B6FC53001672BFED7AB761CA82C97DFA5947F0ADD4A2AF9CA472C02B7FD9326363FF7CC34A5E5F171D83115304C723C31896059A071280E2EB27B275409832C1A1B6E5AA0523BD6B329E32F84553D100ED20FCB15B6ACBBE394A4C58CF6D0EFAAFB434D338545F9027F503C9FA8751A3408F929D38F5BCB6DA2110FFF3D28CD0C13EC5F974417C4A77E3D645D1973960814FDC222A908846EEB814DE5E0BDBAE0323A0A4906245CC2D3AC629195E479BE7C8376D8DD54EA96C56F4EA657AAE08CBA78252E1CA6B4C6E8DD741F4BBD8B8AD703EB5664803F60E613557B986C11D9EEE1F8981169D98E949B1E87E9CE5528DFF8CA1890DBFE6426841992D0FB054BB16在C1的基础上，查找ByteSub表，可得B5B1B9B5C9CCC5C817111B159E99929D查找表ByteSubD5C856D5DD4BA6E8F082AF590BEE4F5EByteSub（B5）=D5ByteSub（C9）=DDByteSub（17）=F0ByteSub（9E）=0B②ShiftRow变换。D5C856D5DD4BA6E8F082AF590BEE4F5ED5C856D54BA6E8DDAF59F0825E0BEE4FShiftRow③MixColumn变换。D5C856D54BA6E8DDAF59F0825E0BEE4F9D289100F77F78A639C16CC63CAA25A5MixColumn假如第一列对应一系数在GF（28）的多项式D5x3+48x2+AFx+5E做（D5x3+48x2+AFx+5E）（03x3+01x2+01x+02）mod（x4+1）≡9Dx3+F7x2+39x+3C 参考答案61同理，处理其他列。④AddRoundKey变换。9D289100F77F78A639C16CC63CAA25A5B664BE68923D9B30CFBDC5B30BF100FE2B4C2F686542E396F67CA975375B255B⊕=所以，第2轮加密的结果是：C2=2B65F6374C427C5B2FE3A9256896755B或者写成2B4C2F686542E396F67CA975375B255B（4）第3轮。①Bytesub变换。2B4C2F686542E396F67CA975375B255B查找表ByteSubF12915454D2C11904210D39D9A393F39②ShiftRow变换。F12915454D2C11904210D39D9A393F39F12915452C11904DD39D4210399A393FShiftRow③MixColumn变换。F12915452C11904DD39D4210399A393F6766FA72FE2DD1D02BAC4A6985D89FECMixColumn④AddRoundKey变换。6766FA72FE2DD1D02BAC4A6985D89FECB6D26C04FFC2596974C90CBF4EBFBF41D1B4967601EF88B95F6546D6CB6720AD⊕=所以，第3轮加密的结果是：C3=D1015FCBB4EF65679688462076B9D6AD第4轮到第9轮的结果是： 参考答案61C4=8E17064A2A35A183729FE59FF3A591F1C5=D7557DD55999DB3259E2183D558DCDD2C6=73A96A5D7799A5F3111D2B63684B1F7FC7=1B6B853069EEFC749AFEFD7B57A04CD1C8=107EEADFB6F77933B5457A6F08FD46B2C9=8EC166481A677AA96A14FF6ECE88C010（5）最后一轮。①Bytesub变换。8E1A6ACEC1671488667AFFC048A96E10查找表ByteSub19A2028B7885FAC433DA16BA52D39FCA②ShiftRow变换。19A2028B7885FAC433DA16BA52D39FCA19A2028B85FAC47816BA33DACA52D39FShiftRow③AddRoundKey变换。19A2028B85FAC47816BA33DACA52D39F13E3F34D1194072B1D4AA7307F178BC50A41F1C6946EC3530BF094EAB545585A⊕=所以，最后加密的结果是：C=0A940BB5416EF045F1C39458C653EA5A五、上机题1.用C语言编程实现中国剩余定理。#defineN3＃includelongshengyu(intb[],intm[]){/*正常来讲，应首先判断是否有解，即m[N]中的数是否互素，读者可以自己加上*/ longproduct=1; longx=0; int M[N],y[N],i; for(i=0;iintIsPrime(longn){ longi; for(i=2;i#include#include 参考答案61#defineINIT_TYPE10#defineALLTOONE_TYPE100#defineONETOALL_TYPE200#defineMULTI_TYPE300#defineRESULT_TYPE400#defineRESULT_LEN500#defineMULTI_LEN600intSpt;longDataSize;int*arr,*arr1;intmylength;int*index;int*temp1;main(intargc,char*argv[]){longBaseNum=1;intPlusNum;intMyID;MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&MyID);PlusNum=60;DataSize=BaseNum*PlusNum;if(MyID==0)printf("TheDataSizeis:%lun",PlusNum);Psrs_Main();if(MyID==0)printf("n");MPI_Finalize();}Psrs_Main(){inti,j;intMyID,SumID;intn,c1,c2,c3,c4,k,l;FILE*fp;intready;MPI_Statusstatus[32*32*2];MPI_Requestrequest[32*32*2];MPI_Comm_rank(MPI_COMM_WORLD,&MyID);MPI_Comm_size(MPI_COMM_WORLD,&SumID);Spt=SumID-1;/*初始化参数*/arr=(int*)malloc(2*DataSize*sizeof(int));if(arr==0)merror("mallocmemoryforarrerror!");arr1=&arr[DataSize];if(SumID>1){temp1=(int*)malloc(sizeof(int)*SumID*Spt);if(temp1==0)merror("mallocmemoryfortemp1error!");index=(int*)malloc(sizeof(int)*2*SumID);if(index==0)merror("mallocmemoryforindexerror!");}MPI_Barrier(MPI_COMM_WORLD);mylength=DataSize/SumID; 参考答案61srand(MyID);printf("Thisisnode%dn",MyID);printf("Onnode%dtheinputdatais:n",MyID);for(i=0;i1){MPI_Barrier(MPI_COMM_WORLD);n=(int)(mylength/(Spt+1));for(i=0;i=temp1[i])&&(ic4){c3=c2-1;c2=(int)((c1+c3)/2);}else{c1=c2+1;c2=(int)((c1+c3)/2);}}while((arr[c2]<=c4)&&(c2datas[i]))i++;if(i0){ind[j++]=ind[i];if(j1){n=0;for(i=0;idata1[m])data2[i]=data1[m++];elsedata2[i]=data1[l++];}}（2）运行实例。编译：mpiccpsrs_sort.c–opsrs运行：可以使用命令mpirun-npSIZEpsrs来运行该串匹配程序，其中SIZE是所使用的处理器个数，本实例中使用了SlZE=3个处理器。mpirun-np3psrs运行结果：TheDataSizeis：60Thisisnode00nnode0theinputdatais：0：21468：9988：22117：3498：16927：16045：19741：12122：8410：12261：27052：5659：9758：21087：25875：32368：26233：15212：17661：0nnode0thesorteddatais：0：2749：3498：4086：56Z7：5659：5758：7419：8410：9084：9758：9988：703：908：2294：9212：Thisisnode10nnodeltheinputdatais：16838：5758：10113：17515：31051：5627：23010：7419：16212：4086：2749：12767：9084：12060：32225：17543：25089：21183：25137：25566：0nnodelthesorteddatais：10113；12060；12122：12767：15212：16045：l6212：16838：16927：17515：l0239：10595：12508：12914：14363：16134Thisisnode20nnode2theinputdatais：908：22817：10239：12914：25837：27085：299766：27865：20302：32531：26005：31251：12308：14363：10595：92l2：17811：16134：2294：703：0nnode2thesorteddatais：17543：17661：19741：21087：21183：21468：22117：230l0：23089：25l37：25566：25875：26233：27052：3l051：32225：32368：17811：20302：22817：25837：26005：27095：27865：29976：3125l：32531：说明：本程序中通过变量DataSize指定了待排序序列的长度为60，顺序输出各个处理器的局部数据就可以得到全局有序的序列。2.（略）。'