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

《动态规划算法分析与设计实验报告(矩阵连乘).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、西南大学荣昌校区信息管理系算法分析与设计实验报告实验题目：动态规划算法的设计与实现1、实验目的通过本实验，掌握动态规划算法的设计的基本思想，进一步提高学生的编程能力。2、实验内容：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。3、源程序#includeusingnamespacestd;#defineN100intn,q;intm[N][N],s[N][N],p[N+1];voidmatrixChain(){//动态规划计算最优值算法

2、for(inti=1;i<=n;i++){m[i][i]=0;}for(intr=2;r<=n;r++){//对角线循环for(inti=1;i<=n-r+1;i++){//行循环intj=r+i-1;//列的控制,找m[i][j]的最小值，先初始化一下，令k=im[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(intk=i+1;k

3、){m[i][j]=temp;//s[][]用来记录在子序列i-j段中，在k位置处断开能得到最优解s[i][j]=k;}}}}}intRecur(inti,intj)//直接递归计算最优值{if(i==j){return0;}intu=Recur(i,i)+Recur(i+1,j)+p[i-1]*p[i]*p[j];//递归s[i][j]=i;for(intk=i+1;k

4、小的值，并记录断点处k{u=t;s[i][j]=k;}}returnu;}intLook(inti,intj)//备忘录计算最优值{if(m[i][j]>0){returnm[i][j];}if(i==j)return0;intu=Look(i,i)+Look(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k

5、记录断点处k}}m[i][j]=u;returnu;}voidTraceback(inti,intj){//输出矩阵结合方式，加括号输出if(i==j)//只有一个矩阵，直接输出{cout<<"A"<>p[i];}cout<>q;cout<

7、态规划算法解决矩阵连乘问题："<