算法设计实验

实验三：动态规划法【实验目的】应用动态规划算法思想求解矩阵连乘的顺序问题。【实验要求】应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透Ai,j，A1,n=A1,k Ak+1,n，mij，sij各式所表达的含义并正确加以应用。mij的递归定义： 0 （ i=j ）mij= minmik mk+1j+ni-1nknj （ ij）要求完成：算法描述写出程序代码完成调试进行过程与结果分析。【实验性质】验证性实验。【实验内容】对于下列所描述的问题，给出相应的算法描述，并完成程序实现与时间复杂度的分析。该问题描述为：一般地，考虑矩阵A1，A2， ，An的连乘积，它们的维数分别为d0,d1,dn,即Ai的维数为di-1di (1in)。确定这n个矩阵的乘积结合次序，使所需的总乘法次数最少。对应于乘法次数最少的乘积结合次序为这n个矩阵的最优连乘积次序。按给定的一组测试数据对根据算法设计的程序进行调试：6个矩阵连乘积A=A1A2A3A4A5A6，各矩阵的维数分别为：A1：1020，A2：2025，A3：2515，A4：155，A5：510，A6：1025。完成测试。【注意事项】用C语言或C+实现算法。选择合适的数据结构。注意：是求解完成矩阵连乘的乘法运算次数最少的矩阵连乘次序，而不是求解矩阵连乘的结果。【调试分析和心得体会】运行依算法写出的程序并分析算法实现的时间复杂度情况。#include #include class MatrixChainpublic:MatrixChain(int mSize);/创建二维数组m和s，一维数组p，并初始化int MChain();/一般动态规划法求最优解值int LookupChain();/备忘录方法求最优解值（程序7-4）void Traceback();/构造最优解的公有函数private:void Traceback(int i, int j);/构造最优解的私有递归函数int LookupChain(int i, int j);/备忘录方法私有递归（程序7-4）int *p, *m, *s, n;int MatrixChain:MChain() /求A0:n-1的最优解值for (int i=0;in; i+) mii=0;for (int r=2; r=n; r+)for (int i=0; i=n-r; i+) int j=i+r-1;mij=mi+1j+pi*pi+1*pj+1; /mij 的初值sij=i;for (int k=i+1; kj; k+) int t=mik+mk+1j+pi*pk+1*pj+1;if (tmij) mij=t; sij=k;return m0n-1;void MatrixChain: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 MatrixChain:Traceback()cout(; Traceback(0, n-1); cout);coutendl;MatrixChain:MatrixChain(int mSize)n=mSize;p= new int n+1; m= new int *n; s=new int *n;for(int i=0;in;i+) mi=new int n;si=new intn;cout输入矩阵行列值：endl; /p0p1p2.pnfor(i=0;ipi;void main(void)int n;coutn;MatrixChain g(n);g.MChain();g.Traceback();答案