算法设计与分析大作业答案
算法设计技术与方法
大作业
学 院 电子工程学院
专 业 电路与系统
姓 名
学 号
导师姓名
作业
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 四种方法所用时间随规模不同而变化的结果图
图 2.2 四种方法所用时间随规模不同而变化的对比图
由理论分析可知，四种算法的时间复杂度分别为O(n)、O(n)、O(n)、O(n)，由图1.2分析可知，直接带入计算和递归法所用时间相差无几，这与理论分析一直。而第三种方法与第四种方法的差异可能是由于每次加法所用时间与每次乘法所用时间不同所导致。 另外，在问题规模较小(n
222、分析题意可知，要利用四种方法计算矩阵相乘，每种方法取矩阵大小从2⨯2~ 22
212⨯212不同的规模。本文采用了以下方法进行求值：矩阵计算法、定义法、分治法和Strassen方法。
实验结果如下：
图 2.1 四种方法所用时间随规模不同而变化的结果图
3、
方法1：将原函数取负，求 f(x1,x2)的最小值即得原函数的最大值。
程序采用MATLAB自带的工具箱实现，程序如下：
运行后的结果：
Bestx =
11.6184 5.7273
BestFval =
-38.7478
从而可知原函数在(11.6184,5.7273)取得最大值38.7478。
方法2：按照遗传算法的思路编程，程序如下：
运行结果如下：
optxx =
11.[**************] 5.[**************]
bestv =
38.[**************]
从而可知原函数在(11.[**************],5.[**************])取得最大值38.[**************]。