矩阵连乘和最长公共子序列问题算法设计

宁夏师范学院数学与计算机科学学院宁夏师范学院数学与计算机科学学院 算法分析与设计 实验报告实验报告 实验序号 5 实验项目名称 矩阵连乘和最长公共子序列问题算法设计 学学 号号姓姓 名名 专业 班专业 班 实验地点实验地点指导教师指导教师时时 间间 2014 年年 4 月月 28 日日 一 实验目的及要求一 实验目的及要求 1 掌握使用动态规划方法设计最优值问题的方法 2 能够使用动态规划算法设计策略设计矩阵连乘和最长公共子序列问 题的算法 二 实验设备 环境 及要求二 实验设备 环境 及要求 1 环境要求 硬件 PC PII 以上 128M 以上内存 因特网接入 软件 Windows XP 操作系统 VC 6 0 编程环境 2 实验要求 1 独立完成实验 源代码书写规范 2 程序运行结果以屏幕截图的方式粘贴在对应位置 截图必须清晰准确 3 实验完成后必须有实验结果的分析及本次实验的总结 三 实验内容与步骤三 实验内容与步骤 1 设计求解n个矩阵连乘的最优计算次序问题的程序 并将在最优计算次 序下所需的乘法次数及最优计算次序在屏幕上显示 n个矩阵的维数从键盘输入 include define N 5 此处N值为存储矩阵行列数的数组的元素个数 int matrixchain int p N int m N N int s N N int i j r t k n N 1 for i 1 i n i m i i 0 for r 2 r n r for i 1 i n r 1 i j r i 1 m i j m i 1 j p i 1 p i p j s i j i for k i 1 k j k t m i k m k 1 j p i 1 p k p j if t m i j m i j t s i j k return m i n void traceback int s N N int i int j if i j printf A d i else if i 1 j printf A dA d i j else printf traceback s i s i j traceback s s i j 1 j printf void display int a N N int i j printf for i 1 i N i printf 7d i printf n n for i 1 i N i printf 7d i for j 1 j N j printf 7d a i j printf n int main int i j p N m N N s N N printf The numbers of maxtri d n N 1 for i 0 i N i for j 0 j N j m i j 0 s i j 0 for i 0 i N i printf 请输入p d i scanf d printf 您输入的矩阵为 n for i 0 i N 1 i printf A d d d i 1 p i p i 1 matrixchain p m s printf n最优解如下 n printf m d d 矩阵 n N 1 N 1 display m printf s d d 矩阵 n N 1 N 1 display s printf n d个矩阵连乘的最优乘法次数 d N 1 m 1 N 1 printf n d个矩阵连乘的最优计算次序 N 1 traceback s 1 N 1 return 0 2 设计求解x和y两个序列的最长公共子序列问题的程序 并将最长公共子 序列的长度及最长公共子序列在屏幕上显示 include define M 8 define N 7 int lcslength char x M 1 char y N 1 int b M 1 N 1 void lcs int i int j char x M 1 int b M 1 N 1 int main char x M 1 y N 1 int b M 1 N 1 maxlen printf 输入长度为M d序列x M gets x printf 输入长度为N d序列y N gets y maxlen lcslength x y b printf 最长公共子序列的长度 d n maxlen printf 最长公共子序列 lcs M N x b printf n return 0 int lcslength char x M 1 char y N 1 int b M 1 N 1 int m M n N i j c M 1 N 1 for i 1 i m i c i 0 0 for j 1 j n j c 0 j 0 for i 1 i m i for j 1 jc i j 1 c i j c i 1 j b i j 2 else c i j c i j 1 b i j 3 return c m n void lcs int i int j char x M 1 int b M 1 N 1 if i 0 j 0 return if b i j 1 lcs i 1 j 1 x b printf c x i else if b i j 2 lcs i 1 j x b else lcs i j 1 x b 四 实验结果与数据处理四 实验结果与数据处理 1 2 最长公共子序列长度 五 分析与讨论五 分析与讨论 1 比较备忘录方法和动态规划方法求矩阵连乘问题的特点 比较备忘录方法和动态规划方法求矩阵连乘问题的特点 备忘录方法是动态规划算法的变形 与动态规划算法一样 备忘录方法用 表格保存已解决的子问题的答案 在下次需要解此子问题时 只要简单地查看 该子问题的解答 而不必重新计算 与动态规划算法不同的是 备忘录方法的 递归方式是自顶向下的 而动态规划算法则是自底向上递归的 因此 备忘录 方法的控制结构与直接递归方法的控制结构相同 区别在于备忘录方法为每个 解过的子问题建立了备忘录以备需要时查看 避免了相同子问题的重复求解 2 分析求最长公共子序列长度和构