动态规划算法分析与设计实验报告 矩阵连乘.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];voidmatrix

2、Chain(){//动态规划计算最优值算法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[k+1][j]+p[i-1]*p[k]*p[j];if(temp

4、-1]*p[k]*p[j];//从k处断开，分别求得每次的数乘次数3西南大学荣昌校区信息管理系if(t0){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+1,j)+p[i-1]*p[k]*p[j];//递归if(t

6、,s[i][j]);//递归，从最得到最优解的地方s[i][j]处断开Traceback(s[i][j]+1,j);cout<<")";}}voidmain(){cout<<"输入矩阵个数：n=";cin>>n;cout<<"输入第一个矩阵行数和第一个到第n个矩阵的列数：";for(inti=0;i<=n;i++){cin>>p[i];}cout<

7、算法"<>q;cout<

8、<<"直接递归算法解决矩阵连乘问题："<