矩阵连乘问题C++代码加注释.doc

#include iostream using namespace std; #define N 100 int n,q; int m[N][N],s[N][N],p[N+1]; void matrixChain() { //动态规划计算最优值算法 for(int i=1;i=n;i++) { m[i][i]=0; } for(int r=2;r=n;r++) { //对角线循环 for(int i=1;i=n-r+1;i++) { //行循环 int j = r+i-1; //列的控制,找m[i][j]的最小值，先初始化一下，令k=i m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; //k从i+1到j-1循环找m[i][j]的最小值 for(int k = i+1;kj;k++) { int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(tempm[i][j]) { m[i][j]=temp; //s[][]用来记录在子序列i-j段中，在k位置处断开能得到最优解 s[i][j]=k; } } } } } int Recur(int i, int j) //直接递归计算最优值 { if (i == j){ return 0; } int u = Recur(i,i)+Recur(i+1,j)+p[i-1]*p[i]*p[j]; //递归 s[i][j] = i; for (int k=i+1; kj; k++) { int t=Recur(i,k)+Recur(k+1,j)+p[i-1]*p[k]*p[j];//从k处断开，分别求得每次的数乘次数 if (tu) //返回t,k中较小的值，并记录断点处k { u=t; s[i][j]=k; } } return u; } int Look(int i,int j) //备忘录计算最优值 { if (m[i][j]0) { return m[i][j]; } if (i == j) return 0; int u=Look(i, i)+Look(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i; for (int k=i+1; kj;k++) { int t=Look(i,k)+Look(k+1,j)+p[i-1]*p[k]*p[j]; //递归 if (tu) { u=t; //从k处断开，分别求得每次的数乘次数 s[i][j]=k; //返回t,k中较小的值，并记录断点处k } } m[i][j]=u; return u; } void Traceback(int i,int j) { //输出矩阵结合方式，加括号输出 if(i == j) //只有一个矩阵，直接输出 { coutAi; } else if(i+1 == j) //两个矩阵，加括号输出 { cout(AiAj); } else { cout(; Traceback(i,s[i][j]); //递归，从最得到最优解的地方s[i][j]处断开 Traceback(s[i][j]