Project2 动态规划实验报告
徐煜森 PB16110173
一. 实验要求
实验 1:实现矩阵链乘问题的求解算法。对 n 的取值分别为:5、
10、20、30 ,随机生成 n+1 个整数值( p
0
、p
1
、…、p
n
)代表矩
阵的规模,其中第 i 个矩阵(1≤i ≤ n)的规模为 p
i-1
× p
i
,用动态规划
法求出矩阵链乘问题的最优乘法次序,统计算法运行所需时间,画出
时间曲线,进行性能分析。
实验 2:实现最长公共子序列问题的求解算法。序列 X 的长为 m,
序列 Y 的长为 n,序列 X 和 Y 的元素从 26 个大写字母中随机生成,m
和 n 的取值:
第 1 组:(15,10),(15,20),(15,30),(15,40),(15,50),
(15,60)
第 2 组:(15,25),(30,25),(45,25),(60,25),(75,25),
(90,25)
给出算法运行所需的时间,画出时间曲线 ,进行性能分析。
二. 实验环境
1. Windows10 64 位 x86,机器内存 8G,时钟主频 2.59GHz
2. 软件环境:Visual Studio 2017
评论0