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

... .. 算 法 设 计 技 术 与 方 法大 作 业学院电子工程学院专业电路与系统姓名学号导师姓名... .. 作业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),(max221121xxxxxxf8.51.41.120.3..21xxts1、分析题意可知，该题要用四种不同的方法实现对多项式的求值计算，每种方法取从10-100000 不同的规模。本文采用了以下方法进行求值：直接代入法和递归法。而其中递归法分三类不同思路进行递归：①nnnnxaxPxP)()(1；②0aP,1Q,QaPPQxQi,；③iniiaxxPxP)()(1。本文对上述四种方法进行了编程，具体代码如下：程序 1.1 文件名 poly.m % 主程序：实现不同规模下多项式求值的四种运算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... .. 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; % 递归法 2end t3(i)=toc; tic; p4(i)=0;for j=1:n(i); p4(i)=x*p4(i)+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,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 ...