算法设计技术与方法
大作业
 
                     
      学    院          电子工程学院         
      专    业            电路与系统           
      姓    名                                
      学    号                                
      导师姓名                              
作业
1.分别实现多项式求值的四种运算，若针对不同规模的输入值a，各算法的运行时间，问题
规模n分别取10，50，100，150，200，300，400，500，10000，20000，50000，100000时绘制四种算法运行时间的比较图。
2.分别实现矩阵相乘的3种算法，比较三种算法在矩阵大小分别为，，，，，，，，，，时的运行时间与MATLAB自带的矩阵相乘的运行时间，绘制时间对比图。
3.利用遗传算法求解下面的问题：
1、分析题意可知，该题要用四种不同的方法实现对多项式的求值计算，每种方法取从10-100000不同的规模。本文采用了以下方法进行求值：直接代入法和递归法。而其中递归法分三类不同思路进行递归：
    ；
    ,,；
    。
本文对上述四种方法进行了编程，具体代码如下：
html网页设计大作业
程序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;        % 递归法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;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。