算法设计实验3.doc

《算法设计实验3.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三：动态规划法【实验目的】应用动态规划算法思想求解矩阵连乘的顺序问题。【实验要求】应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]，A[1,n]=A[1,k]×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义：0（i=j）m[i][j]=min{m[i][k]＋m[k+1][j]+ni-1nknj（i

2、进行过程与结果分析。【实验性质】验证性实验。【实验内容】对于下列所描述的问题，给出相应的算法描述，并完成程序实现与时间复杂度的分析。该问题描述为：一般地，考虑矩阵A1，A2，…，An的连乘积，它们的维数分别为d0,d1,…,dn,即Ai的维数为di-1×di(1≤i≤n)。确定这n个矩阵的乘积结合次序，使所需的总乘法次数最少。对应于乘法次数最少的乘积结合次序为这n个矩阵的最优连乘积次序。按给定的一组测试数据对根据算法设计的程序进行调试：6个矩阵连乘积A=A1×A2×A3×A4×A5×A6，各矩阵的维数分别为：A1：10

3、×20，A2：20×25，A3：25×15，A4：15×5，A5：5×10，A6：10×25。完成测试。【注意事项】用C语言或C++实现算法。选择合适的数据结构。注意：是求解完成矩阵连乘的乘法运算次数最少的矩阵连乘次序，而不是求解矩阵连乘的结果。【调试分析和心得体会】运行依算法写出的程序并分析算法实现的时间复杂度情况。#include#includeclassMatrixChain{public:MatrixChain(intmSize);//创建二维数组m和s，一维数组p

4、，并初始化intMChain();//一般动态规划法求最优解值intLookupChain();//备忘录方法求最优解值（程序7-4）voidTraceback();//构造最优解的公有函数private:voidTraceback(inti,intj);//构造最优解的私有递归函数intLookupChain(inti,intj);//备忘录方法私有递归（程序7-4）int*p,**m,**s,n;};intMatrixChain::MChain(){//求A[0:n-1]的最优解值for(inti=0;i

5、+)m[i][i]=0;for(intr=2;r<=n;r++)for(inti=0;i<=n-r;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1];//m[i][j]的初值s[i][j]=i;for(intk=i+1;k

6、aceback(inti,intj){if(i==j){cout<<'A'<

7、endl;}MatrixChain::MatrixChain(intmSize){n=mSize;p=newint[n+1];m=newint*[n];s=newint*[n];for(inti=0;i>p[i];}}voidmain(void){intn;cout<<"输入矩阵个数：";cin>>n;MatrixChaing

8、(n);g.MChain();g.Traceback();}答案：输入矩阵个数：6输入矩阵行列值：10×2020×2525×1515×55×1010×25(((A0A1)A2)(A3(A4A5)))Pressanykeytocontinue