动态规划算法分析与设计实验报告(矩阵连乘)

算法分析与设计实验报告实验题目： 动态规划算法的设计与实现 1、实验目的通过本实验，掌握动态规划算法的设计的基本思想，进一步提高学生的编程能力。2、实验内容：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。3、源程序#include using namespace std; #define N 100 int 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+) inttemp=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中较小的值，并记录断点处k mij=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; /最终解值为m1n break; case 2: Recur(0,n); cout直接递归算法解决矩阵连乘问题：endl; cout最优计算次序为：; Traceback(1,n); coutendl; cout矩阵连乘的最优数乘次数为：m1nendl; /最终解值为m1n break; case 3: Look(1,n); cout备忘录算法解决矩阵连乘问题：endl; cout最优计算次序为：; Traceback(1,n); coutendl; cout矩阵连乘的最优数乘次数为：m1nendl; /最终解值为m1n break; case 0: q=0; break; coutendl; cout请选择解决矩阵连乘问题的方法：endl; cout1.动态规划算法endl; cout2.直接递归算法endl; cout3.备忘录算法endl; cout0.退出.endl; coutq; coutendl; coutendl; 4