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

1、算 法 设 计 技 术 与 方 法大 作 业学 院 电子工程学院 专 业 电路与系统 姓 名 学 号 导师姓名 作业1.分别实现多项式求值的四种运算，若针对不同规模的输入值 a，各算法的运行时间，问题规模 n 分别取 10，50，100，150，200，300，400，500，10000，20000，50000，100000时绘制四种算法运行时间的比较图。2.分别实现矩阵相乘的 3 种算法，比较三种算法在矩阵大小分别为 ， ，23， ， ， ， ， ， ， ，425627829101时的运行时间与 MATLAB 自带的矩阵相乘的运行时间，绘制时间对比图。13.利用遗传算法求解下面的问题： )2

2、0sin()4sin(5.2),(max111 xxf 8.4032ts1、分析题意可知，该题要用四种不同的方法实现对多项式的求值计算，每种方法取从 10-100000 不同的规模。本文采用了以下方法进行求值：直接代入法和递归法。而其中递归法分三类不同思路进行递归： ；nnnxaPx)()(1 , , ；0QQaPi, 。iniix)()(1本文对上述四种方法进行了编程，具体代码如下：程序 1.1 文件名 poly.m% 主程序：实现不同规模下多项式求值的四种运算clc;close all;clear all;n=10 50 100 150 200 300 400 500 10000 2000

3、0 50000 100000;x=2;for i=1:12a=rand(1,(n(i)+1); % 产生多项式,最高次幂为 n(i)+1tic;p1(i)=polyval(a,x); % 直接代入法t1(i)=toc;tic;p2(i)=0;for j=1:(n(i)+1)p2(i)=p2(i)+a(j)*x(j-1); % 递归法 1endt2(i)=toc; tic;p3(i)=0;q=1;for j=2:(n(i)+1)q=q*x;p3(i)=p3(i)+a(j)*q; % 递归法 2endt3(i)=toc;tic;p4(i)=0;for j=1:n(i);p4(i)=x*p4(i)+

4、a(n(i)+1-j); % 递归法 3end t4(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(The scale of the problem:n);ylabel(time for first method(s);title(the relationship between time and scale);grid on;subplot(2,2,

5、2);h=semilogx(n,t2); set(h,linestyle,-,linewidth,1.8,marker,*,color,b,markersize,6);xlabel(The scale of the problem:n);ylabel(time for second method(s);title(the relationship between time and scale);grid on;subplot(2,2,3);h=semilogx(n,t2); set(h,linestyle,-,linewidth,1.8,marker,*,color,k,markersize,

6、6);xlabel(The scale of the problem:n);ylabel(time for third method(s);title(the relationship between time and scale);grid on;subplot(2,2,4);h=semilogx(n,t2); set(h,linestyle,-,linewidth,1.8,marker,*,color,r,markersize,6);xlabel(The scale of the problem:n);ylabel(time for forth method(s);title(the re

7、lationship between time and scale);grid on;figure(2);g=semilogx(n,t1,g+,n,t2,bx,n,t3,k*,n,t4,ro);legend(the first method,the second method,the third method,the forth method);set(g,linestyle,-,linewidth,2.0,markersize,8);xlabel(n=10, 50, 100, 150, 200, 300, 400, 500, 10000, 20000, 50000, 100000);ylab

8、el(time);title(The comparison chart of four different methods for polyval);grid on;运行结果如下：图 1.1 四种方法所用时间随规模不同而变化的结果图图 2.2 四种方法所用时间随规模不同而变化的对比图由理论分析可知，四种算法的时间复杂度分别为 、 、 、 ，由)(2n2)(n图 1.2 分析可知，直接带入计算和递归法所用时间相差无几，这与理论分析一直。而第三种方法与第四种方法的差异可能是由于每次加法所用时间与每次乘法所用时间不同所导致。另外，在问题规模较小(n12.1|(x(2)5.8)f=inf;elseif

9、(x(1)=bestvbestv=fmax; % 到目前为止最优适应度值bvalxx=bval(indmax,:); % 到目前为止最佳位串optxx=xx(indmax,:); % 到目前为止最优 参数end Bestfit(k)=bestv; % 记录每代的最优适应度for i=1:(N-1)r=rand;tmp=find(r=q);newbval(i,:)=bval(tmp(1),:);endnewbval(N,:)=bvalxx; % 最优保留bval=newbval;for i=1:2:(N-1)cc=rand;if ccpcpoint=ceil(rand*(2*L-1);ch=bval(i,:);bval(i,point+1:2*L)=bval(i+1,point+1:2*L);bval(i+1,point+1:2*L)=ch(1,point+1:2*L);endend bval(N,:)=bvalxx; % 最优保留mm=rand(N,2*L)pm;bval(mm)=1-bval(mm);endplot(Bestfit); % 绘制最优适应度进化曲线xlabel(Generation); ylabel(FitnessValue);title(The relationship between FitnessValue and Generation);