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

#include using namespace std;#define N 100int n,q;int mNN,sNN,pN+1;void matrixChain() /动态规划计算最优值算法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 = r+i-1; /列的控制,找mij的最小值，先初始化一下，令k=i mij=mii+mi+1j+pi-1*pi*pj; sij=i; /k从i+1到j-1循环找mij的最小值 for(int k = i+1;kj;k+) int temp=mik+mk+1j+pi-1*pk*pj; if(tempmij) mij=temp; /s用来记录在子序列i-j段中，在k位置处断开能得到最优解 sij=k; int Recur(int i, int j) /直接递归计算最优值if (i = j)return 0; int u = Recur(i,i)+Recur(i+1,j)+pi-1*pi*pj; /递归 sij = i; for (int k=i+1; kj; k+) int t=Recur(i,k)+Recur(k+1,j)+pi-1*pk*pj;/从k处断开，分别求得每次的数乘次数 if (t0) return mij;if (i = j)return 0;int u=Look(i, i)+Look(i+1,j)+pi-1*pi*pj;sij=i;for (int k=i+1; kj;k+) int t=Look(i,k)+Look(k+1,j)+pi-1*pk*pj; /递归if (tu) u=t; /从k处断开，分别求得每次的数乘次数sij=k; /返回t,k中较小的值，并记录断点处kmij=u; return u; void Traceback(int i,int j) /输出矩阵结合方式，加括号输出 if(i = j) /只有一个矩阵，直接输出 coutAi; else if(i+1 = j) /两个矩阵，加括号输出 cout(AiAj); else cout(; Traceback(i,sij); /递归，从最得到最优解的地方sij处断开 Traceback(sij+1,j); cout); void main()coutn;cout输入第一个矩阵行数和第一个到第n个矩阵的列数：;for(int i=0;ipi;coutendl;cout请选择解决矩阵连乘问题的方法：endl;cout1.动态规划算法endl;cout2.直接递归算法endl;cout3.备忘录算法endl;cout0.退出.endl;coutendl;coutq;coutendl;while(q!=0)switch(q)case 1:matrixChain();cout动态规划算法解决矩阵连乘问题：endl;cout最优计算次序为：;Traceback(1,n);coutendl;cout矩阵连乘的最优数乘次数为：m1nendl; /最终解值为m1nbreak;case 2:Recur(0,n);cout直接递归算法解决矩阵连乘问题：endl;cout最优计算次序为：;Traceback(1,n);coutendl;cout矩阵连乘的最优数乘次数为：m1nendl; /最终解值为m1nbreak;case 3:Look(1,n);cout备忘录算法解决矩阵连乘问题：endl;cout最优计算次序为：;Traceback(1,n);coutendl;cout矩阵连乘的最优数乘次数为：m1nendl; /最终解值为m1nbreak;case 0:q=0;break;coutendl;cout请选择解决矩阵连乘问题的方法：endl;cout1.动态规划算法endl;cout2.直接递