中科院计算机算法分析和设计习题答案市公开课一等奖百校联赛获奖课件.pptx

第一章 复杂性分析初步 习题 语 句 s/e 频率 总步数template void Mult(T*a,T*b,int m,int n,int p)0 0 0for(int i=0;im;i+)1 m+1 m+1for(int j=0;jp;j+)1 m*(p+1)m*p+m T sum=0;1 m*p m*p for(int k=0;kn;k+)1 m*p*(n+1)m*p*n+m*p Sum+=aik*bkj;1 m*p*n m*p*n Cij=sum;1 m*p m*p 总总 计计 2*m*p*n+4*m*p+2*m+11.试确定下述程序执行步数，该函数实现一个mn矩阵与一个np矩阵之间乘法:s/e 表示每次执行该语句所要执行程序步数,频率是指该语句总执行次数。第1页2 函数MinMax用来查找数组a0:n-1中最大元素和最小元素，以下给出两个程序。令n为实例特征。试问：在各个程序中，a中元素之间比较次数在最坏情况下各是多少？6.按照渐进阶从低到高次序排列以下表示式:templatebool MinMax(T a,int n,int&Min,int&Max)if(n1)return false;Min=Max=0;/初始化 for(int i=1;iai)Min=i;if(aMaxai)Max=i;return true;最好，最坏，平均比较次数都是最好，最坏，平均比较次数都是 2*（n-1）templatebool MinMax(T a,int n,int&Min,int&Max)if(n1)return false;Min=Max=0;/初始化 for(int i=1;iai)Min=i;else if(aMaxB-E|0B-A-C|0C-B-D-E|0D-C|0E-A-C-F-G|0F-E-G|0G-E-F|0第10页ABEDGCF11234756111554A-B-E|0B-A-C|0C-B-D-E|0D-C|0E-A-C-F-G|0F-E-G|0G-E-F|0初始化 DFN:=0，num:=1；DFNL(A,null)，DFN(A):=num=1;L(A):=num=1;num+:=2。DFN(B)=0,DFNL(B,A)DFN(B):=num=2,L(B):=num=2,num+:=3;DFN(A)=10,A=A,无操作。DFN(C)=0 DFNL(C,B)DFN(C):=num=3,L(C):=num=3,num+:=4;DFN(B)=10,B=B,无操作.DFN(D)=0,DFNL(D,C)，DFN(D):=num=4;L(D):=num=4;num+:=5;DFN(C)=30,C=C，无操作.DFNL(D,C)结束结束。DFN(E)=0,DFNL(E,C),DFN(E):=5;L(E):=5;num+:=6;DFN(A)=10,AC,L(E)=min(L(E),DFN(A)=1。DFN(C)=30，C=C，无操作。DFN(F)=0，DFNL(F,E)，DFN(F):=num=6;L(F):=num=6;num+:=7;DFN(E)=50，E=E，无操作。DFN(G)=0，DFNL(G,F)，DFN(G):=num=7;L(G):=num=7;num+:=8；DFN(E)=50,EF，L(G)=min(L(G),DFN(E)=5;DFN(F)=60,F=F,无操作。DFNL(G,F)结束结束 L(F):=min(L(F)，L(G)=min(6,5)=5 DFNL(F,E)结束。结束。L(E):=min(L(E),L(F)=min(1,5)=1 DFNL(E,C)结束。结束。L(C):=min(L(C),L(E)=min(3,1)=1 DFNL(C,B)结束。结束。L(B):=min(L(B),L(C)=min(2,1)=1 DFNL(B,A)结束。L(A):=min(L(A),L(B)=1 因DFN(E)=0，E null,则L(A)=min(L(A),DFN(E)=1DFNL(A,null)结束。第11页序号顶点DFNL栈顶栈底2-连通割点1A1(1,0,0,0,0,0,0)(A,B)2B2(1,2,0,0,0,0,0)(B,C),(A,B)3C3(1,2,3,0,0,0,0)(C,D),(B,C),(A,B)4D4(1,2,3,4,0,0,0)(B,C),(A,B)(C,D);C5E5(1,1,1,4,1,0,0)(E,F),(E,A),(B,C),(A,B)6F6(1,1,1,4,1,6,0)(F,G),(E,F),(E,A),(B,C),(A,B)7G7(1,1,1,4,1,5,5)(E,A),(B,C),(A,B)(G,E),(F,G),(E,F)E8(1,1,1,4,1,5,5)(E,A),(B,C),(A,B)第12页7.对图另一个检索方法是 D-Search。该方法与 BFS 不一样之处于于将队列换成栈，即下一个要检测结点是最新加到未检测结点表那个结点。1）写一个D-Search算法；2）证实由结点v开始D-Search能够访问v可抵达全部结点；3）你算法时、空复杂度是什么？（类比BFS算法）（类比定理2.2.1证实）第13页proc DBFS(v)/PushS(v,S);/将S初始化为只含有一个元素v栈 while S非空 do u:=PullHead(S);count:=count+1;visitedu:=count;for 邻接于u全部顶点w do if sw=0 then PushS(w,S);/将w压入栈中 sw:=1;endif endfor endwhile endDBFS图D搜索算法伪代码：proc DBFT(G,)/count、s同DBFS中说明，branch是统计图G连通分支数 count:=0;branch:=0;for i to n do si:=0;/将全部顶点标识为未被访问 endfor for i to do if si=0 then DBFS(i);branch:=branch+1;endif endfor endDBFT第14页2）证实：除结点v外，只有当结点w满足sw=0时才被压入栈中，所以每个结点至多有一次被压入栈中，搜索不会出现重合和死循环现象，对于每一个v可抵达节点，要么直接被访问，要么被压入栈中，只有栈内节点全部弹出被访问后，搜索才会结束，所以由结点v开始D-Search能够访问v可抵达全部结点。3）除结点v外，只有当结点w满足sw=0时才被压入栈中，所以每个结点至多有一次被压入栈中。需要栈 空间至多是-1；visited数组变量所需要空间为；其余变量所用空间为O(1)，所以s(,)=()。假如使用邻接链表，for循环要做d(u)次，而while循环需要做次，又visited、s和count赋值都需要次操作，因而t(,)=(+)。假如采取邻接矩阵，则while循环总共需要做2次操作，visited、s和count赋值都需要次操作，因而t(,)=(2)。第15页8.考虑下面这棵假想对策树：1）使用最大最小方法(2-4-2)式获取各结点值；2）弈者A为获胜应该什么棋着？3）列出算法VEB计算这棵对策树结点值时各结点被计算次序4）对树中每个结点X，用(2-4-3)式计算V(X)；5）在取X根，l=10,LB=-,D=情况下，用算法AB计算此树根值期间，这棵树那些结点没有计算？841551030592050 1861510520第16页2064205481562030550841520510305920 50 186151055201）使用最大最小方法(2-4-2)式获取各结点值maxmaxmaxminmin第17页2）弈者A为获胜应该什么棋着？2064205481562030550841520510305920 50 18615105520XX1X2X3X4X1.1X1.2X2.1X2.2X3.1X3.2X4.1X4.2X1.1.1X1.1.2X1.1.3X1.2.1X2.1.1X2.2.1X3.1.1X3.1.2X1.1.1.1X3.1.2.1X3.2.1X3.2.2X3.2.3X4.1.1X4.2.1X4.4.2X4.2.3X4.2.4第18页3）列出算法VEB计算这棵对策树结点值时各结点被计算次序46151051-523469-10-1515-66578-6-441011-4第19页3）列出算法VEB计算这棵对策树结点值时各结点被计算次序20-6-4-20-5415620305-4-15-20-5-10-30-5-6-15-10-55202420231519223412 141618 211711312695781011第20页4）对树中每个结点X，用(2-4-3)式计算V(X)；20-6-4-20-5481562030550-8-4-15-20-5-10-30-5-9-20-50-18-6-15-10-5520第21页5）在取X根，l=10,LB=-,D=情况下，用算法AB计算此树根值期间，这棵树那些结点没有计算？20-6-6-20-206156203020-4-15-20-5-10-30-5-6-15-10-5520第22页5）在取X根，l=10,LB=-,D=情况下，用算法AB计算此树根值期间，这棵树那些结点没有计算？20-6-6-20-206156203020-4-15-20-5-10-30-5-6-15-10-5520第23页5）在取X根，l=10,LB=-,D=情况下，用算法AB计算此树根值期间，这棵树那些结点没有计算？20-6-6-20-206156203020-4-15-20-5-10-30-5-6-15-10-5520第24页