算法设计与分析(作业三).doc

算法设计与分析实验报告学 院 信息科学与技术学院 专业班级 软件工程3班 学 号 20122668 姓 名 王建君 指导教师 尹治本 2014年10月 实验四 矩阵相乘次序一、 问题提出用动态规划算法解矩阵连乘问题。给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,n-1。要算出这n个矩阵的连乘积A1A2An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1） 单个矩阵是完全加括号的； （2） 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4），（A1（A2A3）A4），（A1A2）（A3A4），（A1（A2A3）A4），（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个pq矩阵，B是一个qr矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。 （3） 为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵A1,A2,A3连乘的情况。设这三个矩阵的维数分别为10100，1005，550。加括号的方式只有两种：（A1A2）A3），（A1（A2A3），第一种方式需要的数乘次数为101005105507500，第二种方式需要的数乘次数为100550101005075000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵A1,A2,An（其中矩阵Ai的维数为pi-1pi，i1,2,n），如何确定计算矩阵连乘积A1A2An的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。二、 求解思路本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的*m和*s，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为。四、 实验源代码#include using namespace std; const int MAX = 100; /p用来记录矩阵的行列，main函数中有说明 /mij用来记录第i个矩阵至第j个矩阵的最优解 /s用来记录从哪里断开的才可得到该最优解 int pMAX+1,mMAXMAX,sMAXMAX; int n;/矩阵个数 int matrixChain() for(int i=0;i=n;i+) mii=0; for(int r=2;r=n;r+)/对角线循环 for(int i=0;i=n-r;i+)/行循环 int j = r+i-1;/列的控制 /找mij的最小值，先初始化一下，令k=i mij=mi+1j+pi+1*pi*pj +1; sij=i; /k从i+1到j-1循环找mij的最小值 for(int k = i+1;kj;k+) int temp=mik+mk+1j+pi*pk+1*pj+1; if(tempmij) mij=temp; /s用来记录在子序列i-j段中，在k位置处 /断开能得到最优解 sij=k; return m0n-1; /根据s记录的各个子段的最优解，将其输出 void traceback(int i,int j) if(i=j) coutAi; return; if(isij) cout(; traceback(i,sij); if(isij) cout); if(sij+1j) cout(; traceback(sij+1,j); if(sij+1j) cout); void traceback() cout(; traceback(0,n-1); cout); coutendl; int main() system(title 软件3班 王建君 20122668 动态规划求矩阵连乘次序);cout请输入矩阵的个数：n; cout输入矩阵（形如a*b,中间用空格隔开）:endl; for(int i=0;ipi; /测试数据可以设为8个矩阵分别为 /A110*15,A215*20,A320*5,A45*25,A525*20,A620*5,A75*23,A823,8 /则p0-8=10,15,20,5,25,20,5,23,8 cout输出结果如下：endl; matrixChain(); traceback(0,n-1); /最终解值为m0n-1;coutendl; return 0; 五、 结果分析测试数据可以设为8个矩阵分别为 /A010*15,A115*20,A220*5,A35*25,A425*20,A520*5,A65*23,A723,8 则p0-8=10,15,20,5,25,20,5,23,8，的最佳相乘次序为(A0(A1A2)(A3A4)A5)(A6A7)。 实验五、找零问题一、 问题提出 设有n种不同面值的硬币，各硬币的面值存于数组t1:n中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值t1,t2,ti时，可找出钱数M的最少硬币个数记为bij。若只用这些硬币面值，找不出钱数M时，记bij=。二、 求解思路 令bi,j表示前i(1im)种硬币，总额为j(0jn)的最小硬币数。目标为求bm,n。由于对第i种硬币，存在可选1个或者不选两种可能，故容易建立递推关系：bi,jmin bi-1,j, 1+bi,j-vi, for 1im, 0jn显然，bi,0=0, 1im如果无解，令bi,j=+。特别的，如果i=1，令b-1,j=+；如果j-vi0，bi,j-vi=+三、 算法复杂度n-钞票面额的个数 M-要找的钱数，子问题不重复计算，时间复杂度降低，时间复杂度O(nM)。四、 实验源代码#include #include #define INFINITY 32767/无穷大#define MAX 100/*bij=-1 子问题未计算，递归计算 bij!=-1 子问题已计算，直接取计算结果 另外,也可从bij算出各种面额的钞票数*/int DynamicMemory(int t, int i ,int j,int bMAX) if(i=1) if(j%t1=0) bij=j/t1; else bij=INFINITY; return bij; else int x; if(bi-1j=-1) x=DynamicMemory(t,i-1,j,b); else x=bi-1j; if(jy+1)?(y+1):x; return bij; void main() system(title 软件3班 王建君 20122668 动态规划实现找零问题); int t10,n,M;/n-钞票面额的个数 M-要找的钱数 t0=0; printf(请输入钞票面额的种数:n); scanf(%d,&n); printf(请依次输入%d种钞票的面额:n,n); for(int i=1;i=n;i+) scanf(%d,&ti); printf(请输入要找零的钱的总数:n); scanf(%d,&M); int bMAXMAX; int pMAX=0; for(i=0;iMAX;i+)for(int j=0;j0) if(r=1;k-)if(pk!=0)printf(面额为%d的钞票数：%dn,tk,pk); 五、 结果分析