动态规划算法解矩阵连乘问题的源代码(共3页).docx

《动态规划算法解矩阵连乘问题的源代码(共3页).docx》由会员分享，可在线阅读，更多相关《动态规划算法解矩阵连乘问题的源代码(共3页).docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上#include #include #include using std:cout;using std:endl;int main()int p=30,35,15,5,10,20,25; /p0,p1确定A1行列数，p1,p2确定A2行列数，依次类推int n=sizeof(p)/sizeof(int)-1; /自动计算矩阵个数，增加程序灵活性int i,j,k,r;long *m=new long*n+1; int *s=new int*n+1; for(i=0;i=n;i+) mi=new longn+1; /m 行列数n*n，下标都从1开始 for(i=0;i=

2、n;i+) si=new intn+1; /s 行列数n*n，下标都从1开始for(i=0;i=n;i+) mii=sii=0; / 矩阵初始化 / 给以下程序加上注解 for (r = 2; r = n; r+) /* 数组相乘个数 */ for (i = 1; i = n - r+1; i+) /* n行里每行要求得的值的个数 */ j=i+r-1; /* 相乘数组中最后数组的列指针 */ mij = mi+1j+ pi-1*pi*pj; /* 得到两个数组相乘的运算量 */ sij = i; for (k = i+1; k j; k+) /* 加括号方法得到的组数 */ long t =

3、 mik + mk+1j + pi-1*pk*pj; /* 得到每组运算量 */ if (t mij) mij = t; /* 最小运算量 */ sij = k; /* 括号分割的位置 */ /输出矩阵m与s的上三角阵，结果应与图（b）、（c）一致,你的代码写在下面！ /此处为你的输出矩阵m与s的上三角阵的代码！cout图(b)显示结果如下：endl;for(i=0;i=n;i+)if (i=0)coutt;elsecoutit;coutendl;for (i=1;i=n;i+)coutit;for (int j=1;j=0)coutmijt;elsecoutt;coutendl;cout图(c)显示结果如下：endl;for(i=0;i=n;i+)if (i=0)coutt;elsecoutit;coutendl;for (i=1;i=n;i+)coutit;for (int j=1;j=0)coutsijt;elsecoutt;coutendl;return 0;专心-专注-专业