算法实验动态规划----矩阵连乘

实验三 动态规划法实验三 动态规划法 实验目的实验目的 深入理解动态规划算法的算法思想 应用动态规划算法解决实际的算法问题 实验性质实验性质 验证性实验 实验要求实验要求 对于下列所描述的问题 给出相应的算法描述 并完成程序实现与时间复杂度的分析 该问题描述为 一般地 考虑矩阵 A1 A2 An 的连乘积 它们的维数分别为 d0 d1 dn 即 Ai 的维数为 di 1 di 1 i n 确定这 n 个矩阵的乘积结合次序 使所需 的总乘法次数最少 对应于乘法次数最少的乘积结合次序为这 n 个矩阵的最优连乘积次序 按给定的一组测试数据对根据算法设计的程序进行调试 6 个矩阵连乘积 A A1 A2 A3 A4 A5 A6 各矩阵的维数分别为 A1 10 20 A2 20 25 A3 25 15 A4 15 5 A5 5 10 A6 10 25 完成测试 算法思想及处理过程算法思想及处理过程 Main 函 数 定义 二维数组 m 用来存放最优解 定义 二维数组 s 用来 存放最优解的断开点 定义 一维数组 p 用来存放矩阵维数 MatrixChain 函数 首先通过 for 循环 给二维数组 M 和 S 的对角线赋值为 0 表示只有一个矩阵 没有相乘的 然后通过 for 循环 求出 最优解 这只是假定的最优解 和 断开点 这只是假定的最完 美的断开点 再通过双重 for 循环在后面找到了一个最优解 判断后一个最优解是不是比前一个最优解小 也就是更优 更好 如果小 则将前最优解改为后一个的最优解 并且将前 断开点改为后一个的断开点 然后重复此操作 程序代码程序代码 include void MatrixChain int p int m 6 int s 6 int n 求最优解和断开点 void print1 int m 6 int s 6 int p 打印矩阵 最优解 断开点 void print2 int i int n int s 6 打印加括号的断开矩阵 int main int p 7 10 20 25 15 5 10 25 int m 6 6 s 6 6 MatrixChain p m s 6 print1 m s p printf n n 矩阵连乘次数的最优值为 n printf n print2 0 6 1 s printf n n n return 0 void MatrixChain int p int m 6 int s 6 int n int i j k z t for i 0 i n i m i i 0 s i i 0 for z 2 z n z for i 0 i n z i j i z 1 m i j m i 1 j p i p i 1 p j 1 s i j i for k i 1 k j k t m i k m k 1 j p i p k 1 p j 1 if t m i j m i j t s i j k void print1 int m 6 int s 6 int p int i j printf n n 程序所给矩阵如下 n printf n for i 0 i 6 i printf A d 矩阵 2d X 2d n i 1 p i p i 1 printf n n n printf 矩阵的最少计算次数为 d n m 0 5 printf n printf n n 数乘次数 n printf n for i 0 i 6 i for j 0 j i j printf for j i j 6 j printf 7d m i j printf n printf n printf n n 中间断点 n printf n for i 0 i 6 i for j 0 j i j printf for j i j 6 j printf 7d s i j printf n printf n void print2 int i int n int s 6 if i n printf A d i else if i 1 n printf A d A d i n else printf print2 i s i n s print2 s i n 1 n s printf 运行