矩阵连乘重叠和备忘录.doc

#include#include/预设宽度setw()函数using namespace std;int m1010,s1010;int p10=30,35,15,5,10,20,25,;/数据预设/函数申明void MatrixMultiply(int a10,int b10,int c10,int ra,int ca,int rb,int cb);void MatrixChain(int p,int n,int m10,int s10);void Traceback(int i,int j,int s10);void Output(int n,int m10,int s10);int RecurMatrixChain(int i,int j);int MemoizedMatrixChain(int n,int m10,int s10);int LookupChain(int i,int j);int main() int ch,c=1;/ch用来标记排序方法的序号 int n=6;/设置为6个矩阵连乘 while(c!=0) coutendl; cout选择解决最优计算次序的方法： endl; cout- 1 动态规划endl; cout- 2 递归直接endl; cout- 3 备忘录endl; coutendlch; coutendl; switch(ch) case 1:MatrixChain(p,n,m,s);/动态规划 Output(n,m,s);/mij和sij Traceback(1,n,s);/最优计算次序 break; case 2:RecurMatrixChain(1,n);/递归直接 /Output(n,m,s); Traceback(1,n,s); break; case 3:MemoizedMatrixChain(n,m,s);/备忘录 /Output(n,m,s); Traceback(1,n,s); break; default: cout选择范围是13,重新输入:endl; return 0;void MatrixMultiply(int a10,int b10,int c10,int ra,int ca,int rb,int cb)if(ca!=rb)/Ai的列Ai+1的行cout矩阵不可乘!;for(int i=0;ira;i+)for(int j=0;jcb;j+)int sum=ai0*b0j;for(int k=1;kca;k+)sum+=aik*bkj;cij=sum;/动态规划void MatrixChain(int p,int n,int m10,int s10)for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+)int t=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k;void Traceback(int i,int j,int s10)/最优计算次序if(i=j)return;/单个矩阵Traceback(i,sij,s);Traceback(sij+1,j,s);coutMultiply Ai,sij;cout and A(sij+1),jendl;/递归式直接计算int RecurMatrixChain(int i,int j)if(i=j)return 0;int u=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+)int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+pi-1*pk*pj;if(tu)u=t;sij=k;return u;/备忘录int MemoizedMatrixChain(int n,int m10,int s10)for(int i=1;i=n;i+)for(int j=i;j0)return mij;if(i=j)return 0;int u=LookupChain(i,i)+LookupChain(i+1,j)+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+)int t=LookupChain(i,k)+LookupChain(k+1,j)+pi-1*pk*pj;if(tu)u=t;sij=k;mij=u;return u;void Output(int n,int m10,int s10)for(int i=1;i=n;i+)for(int j=1;j=n;j+)coutsetw