...
算法设计技术与方法
大作业
学 院 电子工程学院
专 业 电路与系统
姓 名
学 号
导师姓名
..
...
作业
1.分别实现多项式求值的四种运算，若针对不同规模的输入值a，各算法的运行时间，问题 规模n分别取10，50，100，150，200，300，400，500，10000，20000，50000，100000时绘制四种算法运行时间的比较图。 2.分别实现矩阵相乘的3种算法，比较三种算法在矩阵大小分别为2?2，2?2，223324?24，25?25，26?26，27?27，28?28，29?29，210?210，211?211，212?212时的运行时间与MATLAB自带的矩阵相乘的运行时间，绘制时间对比图。 3.利用遗传算法求解下面的问题： maxf(x1,x2)?21.5?x1?sin(4?x1)?x2?sin(20?x2) ??3.0?x1?12.1s.t.? 4.1?x?5.82?
1、分析题意可知，该题要用四种不同的方法实现对多项式的求值计算，每种方法取从10-100000不同的规模。本文采用了以下方法进行求值：直接代入法和递归法。而其中递归法分三类不同思路进行递归：
n ① Pn(x)?Pn?1(x)?anx；
② P?a0,Q?1,Q?Qx,P?P?aiQ； ③ Pi?(x)?Pi??1(x)x?an?i。
本文对上述四种方法进行了编程，具体代码如下：
程序1.1 % 主程序：实现不同规模下多项式求值的四种运算 clc; close all; clear all; n=[10 50 100 150 200 300 400 500 10000 20000 50000 100000]; x=2; for i=1:12 a=rand(1,(n(i)+1)); % 产生多项式,最高次幂为n(i)+1 tic; 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); % 递归法1 ..
文件名poly.m ...
end t2(i)=toc; tic; p3(i)=0; q=1; for j=2:(n(i)+1) q=q*x; p3(i)=p3(i)+a(j)*q; % 递归法2 end t3(i)=toc; tic; p4(i)=0; for j=1:n(i); p4(i)=x*p4(i)+a(n(i)+1-j); % 递归法3 end t4(i)=toc; end figure(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,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); 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 relationship 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'); ylabel('time'); title('The comparison chart of four different methods for polyval'); grid on;
运行结果如下：
图 1.1 四种方法所用时间随规模不同而变化的结果图
..
...
图 2.2 四种方法所用时间随规模不同而变化的对比图
22 由理论分析可知，四种算法的时间复杂度分别为?(n)、?(n)、?(n)、?(n)，由
图1.2分析可知，直接带入计算和递归法所用时间相差无几，这与理论分析一直。而第三种方法与第四种方法的差异可能是由于每次加法所用时间与每次乘法所用时间不同所导致。 另外，在问题规模较小(n<1000)时，在图上几乎看不出区别，更精细的分析需要更深入地讨论，本文不做讨论。
2、分析题意可知，要利用四种方法计算矩阵相乘，每种方法取矩阵大小从2?2~
22212?212不同的规模。本文采用了以下方法进行求值：矩阵计算法、定义法、分治法和
Strassen方法。 详细程序如下： 文件名matrix.m % 比较三种算法的运行时间与MATLAB自带的矩阵相乘的运行时间 clc; close all; clear all; n=[2^2 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10 2^11 2^12]; for m=1:11 ..
程序2.1
算法设计与分析大作业答案 - 图文
