矩阵连乘 《算法设计与分析》实验报告

《矩阵连乘 《算法设计与分析》实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》实验报告矩阵连乘问题：给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A1,A2,…,An。实验基本思想：由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。设计求解矩阵连乘问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在Ak和Ak+1之间将矩阵链断开，,则其相应的完全加括号方式为((A1…Ak)(Ak+1…An))。依此次序，先计算A[1:k]和A[k+1:n],然后将计

2、算结果相乘得到A[1:n]。一．实验环境VC++6.0一．实验内容C语言代码如下：#includeusingnamespacestd;constintL=7;intMatrixChain(intn,int**m,int**s,int*p);voidTraceback(inti,intj,int**s);//构造最优解intmain(){intp[L]={28,17,15,30,10,30,28};//A1为28*17A2为17*15A3为15*30A4为30*10A5为10*30A6为30*28int**s=newint*[L];int**m=newint*

3、[L];for(inti=0;i

4、i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k

5、[j];cout<<"andA"<<(s[i][j]+1)<<","<