算法设计与分析大作业答案

算法设计技术与方法大作业学院电子工程学院专业电路与系统姓名学号导师姓名作业1.分别实现多项式求值的四种运算，若针对不同规模的输入值a，各算法的运行时间，问题规模n分别取10，50，100，150，200，300，400，500，10000，20000，50000，100000时绘制四种算法运行时间的比较图。2.分别实现矩阵相乘的3种算法，比较三种算法在矩阵大小分别为2222，3322，4422，5522，6622，7722，8822，9922，101022，111122，121222时的运行时间与MATLAB自带的矩阵相乘的运行时间，绘制时间对比图。3.利用遗传算法求解下面的问题：)20sin()4sin(5.21),(max221121xxxxxxf8.51.41.120.3..21xxts1、分析题意可知，该题要用四种不同的方法实现对多项式的求值计算，每种方法取从10-100000不同的规模。本文采用了以下方法进行求值：直接代入法和递归法。而其中递归法分三类不同思路进行递归：①nnnnxaxPxP)()(1；②0aP,1Q,QaPPQxQi,；③iniiaxxPxP)()(1。本文对上述四种方法进行了编程，具体代码如下：程序1.1文件名poly.m%主程序：实现不同规模下多项式求值的四种运算clc;closeall;clearall;n=[1050100150200300400500100002000050000100000];x=2;fori=1:12a=rand(1,(n(i)+1));%产生多项式,最高次幂为n(i)+1tic;p1(i)=polyval(a,x);%直接代入法t1(i)=toc;tic;p2(i)=0;forj=1:(n(i)+1)p2(i)=p2(i)+a(j)*x^(j-1);%递归法1endt2(i)=toc;tic;p3(i)=0;q=1;forj=2:(n(i)+1)q=q*x;p3(i)=p3(i)+a(j)*q;%递归法2endt3(i)=toc;tic;p4(i)=0;forj=1:n(i);p4(i)=x*p4(i)+a(n(i)+1-j);%递归法3endt4(i)=toc;endfigure(1);subplot(2,2,1);h=semilogx(n,t1);%这里不能用plot，横轴需要取对数，下同set(h,'linestyle','-','linewidth',1.8,'marker','*','color','g','markersize',6);xlabel('Thescaleoftheproblem:n');ylabel('timeforfirstmethod(s)');title('therelationshipbetweentimeandscale');gridon;subplot(2,2,2);h=semilogx(n,t2);set(h,'linestyle','-','linewidth',1.8,'marker','*','color','b','markersize',6);xlabel('Thescaleoftheproblem:n');ylabel('timeforsecondmethod(s)');title('therelationshipbetweentimeandscale');gridon;subplot(2,2,3);h=semilogx(n,t2);set(h,'linestyle','-','linewidth',1.8,'marker','*','color','k','markersize',6);xlabel('Thescaleoftheproblem:n');ylabel('timeforthirdmethod(s)');title('therelationshipbetweentimeandscale');gridon;subplot(2,2,4);h=semilogx(n,t2);set(h,'linestyle','-','linewidth',1.8,'marker','*','color','r','markersize',6);xlabel('Thescaleoftheproblem:n');ylabel('timeforforthmethod(s)');title('therelationshipbetweentimeandscale');gridon;figure(2);g=semilogx(n,t1,'g+',n,t2,'bx',n,t3,'k*',n,t4,'ro');legend('thefirstmethod','thesecondmethod','thethirdmethod','theforthmethod');set(g,'linestyle','-','linewidth',2.0,'markersize',8);xlabel('n=10,50,100,150,200,300,400,500,10000,20000,50000,100000');ylabel('time');title('Thecomparisonchartoffourdifferentmethodsforpolyval');gridon;运行结果如下：图1.1四种方法所用时间随规模不同而变化的结果图图2.2四种方法所用时间随规模不同而变化的对比图由理论分析可知，四种算法的时间复杂度分别为)(2n、)(2n、)(n、)(n，由图1.2分析可知，直接带入计算和递归法所用时间相差无几，这与理论分析一直。而第三种方法与第四种方法的差异可能是由于每次加法所用时间与每次乘法所用时间不同所导致。另外，在问题规模较小(n1000)时，在图上几乎看不出区别，更精细的分析需要更深入地讨论，本文不做讨论。2、分析题意可知，要利用四种方法计算矩阵相乘，每种方法取矩阵大小从2222~121222不同的规模。本文采用了以下方法进行求值：矩阵计算法、定义法、分治法和Strassen方法。详细程序如下：程序2.1文件名matrix.m%比较三种算法的运行时间与MATLAB自带的矩阵相乘的运行时间clc;closeall;clearall;n=[2^22^32^42^52^62^72^82^92^102^112^12];form=1:11A=round(rand(n(m)));%随机生成矩阵B=round(rand(n(m)));tic;C1=A*B;%MATLAB自带的矩阵相乘t1(m)=toc;tic;C2=zeros(n(m));fori=1:n(m)fork=1:n(m)forj=1:n(m)C2(i,j)=C2(i,j)+A(i,k)*B(k,j);%按照定义进行计算endendendt2(m)=toc;A11=A(1:n(m)/2,1:n(m)/2);A12=A(1:n(m)/2,n(m)/2+1:n(m));A21=A(n(m)/2+1:n(m),1:n(m)/2);A22=A(n(m)/2+1:n(m),n(m)/2+1:n(m));B11=B(1:n(m)/2,1:n(m)/2);B12=B(1:n(m)/2,n(m)/2+1:n(m));B21=B(n(m)/2+1:n(m),1:n(m)/2);B22=B(n(m)/2+1:n(m),n(m)/2+1:n(m));tic;C3=zeros(n(m));C11=A11*B11+A12*B21;%分治法C12=A11*B12+A12*B22;C21=A21*B11+A22*B21;C22=A21*B12+A22*B22;C3=[C11C12;C21C22];t3(m)=toc;tic;C4=zeros(n(m));M1=A11*(B12-B22);M2=(A11+A12)*B22;M3=(A21+A22)*B11;M4=A22*(B21-B11);M5=(A11+A22)*(B11+B22);M6=(A12-A22)*(B21+B22);M7=(A11-A21)*(B11+B12);C11=M5+M4-M2+M6;%Strassen方法C12=M1+M2;C21=M3+M4;C22=M5+M1-M3-M7;C4=[C11C12;C21C22];t4(m)=toc;endfigure(1);subplot(2,2,1);h=semilogx(n,t1);%这里不能用plot，横轴需要取对数，下同set(h,'linestyle','-','linewidth',1.8,'marker','*','color','g','markersize',6);xlabel('Thescaleofthematrix:n');ylabel('timeforfirstmethod(s)');title('therelationshipbetweentimeandscale');gridon;subplot(2,2,2);h=semilogx(n,t2);set(h,'linestyle','-','linewidth',1.8,'marker','*','color','b','markersize',6);xlabel('Thescaleofthematrix:n');ylabel('timeforsecondmethod(s)');title('therelationshipbetweentimeandscale');gridon;subplot(2,2,3);h=semilogx(n,t2);set(h,'linestyle','-','linewidth',1.8,'marker','*','color','k','markersize',6);xlabel('Thescaleofthematrix:n');ylabel('timeforthirdmethod(s)');title('therelationshipbetweentimeandscale');gridon;subplot(2,2,4);h=semilogx(n,t2);set(h,'linestyle','-','linewidth',1.8,'marker','*','color','r','markersize',6);xlabel('Thescaleofthematrix:n');ylabel('timeforforthmethod(s)');title('therelationshipbetweentimeandscale');gridon;figure(2);g=semilogx(n,t1,'g+',n,t2,'bx',n,t3,'k*',n,t4,'ro');legend('theMATLABmethod','thedefinitionmethod','分治法','theStrassenmethod');set(g,'linestyle','-','linewidth',2.0,'markersize',8);xlabel('n=2^22^32^42^52^62^72^82^92^102^112^12');ylabel('time');title('Thecomparisonchartoffourdifferentmethodsformatrixmultiplication');gridon;实验结果如下：图2.1四种方法所用时间随规模不同而变化的结果图3、方法1：将原函数取负，求),(21xxf的最小值即得原函数的最大值。程序采用MATLAB自带的工具箱实现，程序如下：程序3.1文件名main_function.m%主程序：用遗传算法求解带约束二元函数的最大值clc;closeall;clearall;G=100;%进化的代数optionsOrigin=gaoptimset('Generation',G/2)