算法分析与设计实验指导书样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。算法分析与设计本书是为配合计算机算法分析与设计而编写的上机指导, 其目的是使学生消化理论知识, 加深对讲授内容的理解, 增强算法分析与设计实践动手能力。上机实验注意事项如下: ( 1) 课前认真做好预习, 准备好实验工具, 熟悉实验流程和手段。( 3) 课中根据实验指导书, 结合课本实例进行编程实验。实验时, 一人一组, 独立上机调试, 上机时出现疑问, 能够举手询问实验指导老师, 或者与周边同学小声讨论, 鼓励独立解决问题。( 4) 课后按时按质按量整理出实验报告。实验报告应独立完成, 拒绝抄袭。实验内容覆盖: 递归与分治策略、 动态规划、 贪心算法、 回溯法、 分支限界法等。实验一 递归与分治策略一 实验目的与要求（1） 理解和掌握递归与分治策略的基本原理。（2） 理解课本中的示例代码。（3） 调试代码经过。二 递归与分治的基本思想（1） 递归与分治方法。递归与分治方法的基本思想是: 将一个难以解决的大问题, 分割成一些规模较小的、 相同的子问题, 以便各个击破, 分而治之。（2） 递归。递归问题分析时, 要把握如下两个要素: l 递归出口。l 递归公式。其中: l 递归出口给出了最简单情况下问题的解。l 递归公式则给出了一般意义下大问题( 原问题) 和小问题( 子问题) 之间的递归关系。经过递归公式, 一个难以解决的大问题会随着递归不断分解为多个小问题, 小问题继续递归变为更小的小问题, 直到最后到达递归出口得到解。三 实验代码分析和说明本部分实验, 需完成”棋盘覆盖”( 课本P20) 和”快速排序”( 课本P22) 两个问题。3.1 棋盘覆盖1. 棋盘覆盖问题的思路: （1） 首先, 将原始的棋盘覆盖问题看作最初的大问题。（2） 然后, 将棋盘的行、 列一分为二, 从而将原始的大棋盘分为四个同样大小的小棋盘。（3） 接着, 采用P21的图2-5中合适的L型骨牌, 覆盖原始大棋盘的中心位置, 将四个同样大小的小棋盘都转化为特殊棋盘。（4） 最后, 对四个特殊小棋盘进行递归处理即可。以上步骤( 2) 和步骤( 3) 合起来, 完成了将大问题划分为小问题的过程, 特别需要注意的是: 小问题必须要和大问题相同或相似, 否则无法递归。具体到本例当中, 注意步骤( 3) 选取L型骨牌时, 必须要能够将原始大棋盘转化为四个小的特殊棋盘。如果不是转化为四个小的特殊棋盘, 显然L型骨牌选择是不正确, 因为此时无法进行递归处理。小问题必须和大问题相同或者相似, 是采用递归与分治方法的重要一点, 必须掌握。2. P21代码的说明。（1） ChessBoard的输入参数: tr是左上角方格的行坐标( table row) , tc是左上角方格的列坐标( table column) ; dr是特殊方格的行坐标, dc是特殊方格的列坐标; size是棋盘大小。（2） 以覆盖左上角为例, if (dr tr+s & dc tc + s)该判断条件判断特殊方格是否在左上角小棋盘中。如果在, 就直接进行递归, 即: ChessBoard( tr, tc, dr, dc, s) 。如果不在, 那么首先用t号骨牌覆盖( 具体选择P21中的哪种骨牌, 参见前述说明) 。覆盖之后, 左上角的小棋盘就变成了特殊小棋盘, 此时就能够递归处理了, 即: ChessBoard(tr, tc, tr+s-1, tc+s-1, s)。【问题】前后两次递归, ChessBoard的参数为什么这样设置? 3.2 快速排序1. 快速排序的基本思路。假设需要排序的数存储在数组”ap, ap+1, , ar”中。为了描述方便, 将上述数组简记为: ap:r。（1） 首先, 以ap为基准元素, 将ap:r划分为三段, 分别是: ap: q-1, aq, aq+1: r。其中, ap: q-1中的任何一个元素都小于等于aq; aq小于等于aq+1: r中的任何一个元素。注意: 算法工作时, 以ap为基准进行ap:r划分; aq是在划分完成时确定的。（2） 对划分得到的ap: q-1和aq+1: r类似地, 进行划分。（3） 注意到ap: q-1, aq, aq+1: r的关系, 不要任何计算, 数组ap: r就已经自动排好序。【问题】快速排序的上述思想中, 是如何体现”将大问题划分为相同或相似的小问题”的? 四 实验内容（1） 完成代码, 并调试经过。（2） 回答实验指导书中的问题。（3） 体会递归与分治策略的基本思想, 以及在编程中如何实现。实验二 动态规划一 实验目的与要求（1） 理解动态规划的基本思想。（2） 理解课本中示例代码并调试经过。（3） 根据自己的理解, 回答实验指导书中的问题。二 动态规划的基本思想（1） 动态规划问题需要满足两个特征, 分别是: l 最优子结构性质。即: 大问题的最优解当中, 包含了子问题的最优解。这是利用动态规划解决问题的最关键特征。l 重叠子问题。即: 动态规划问题中, 许多子问题被重复计算。因此, 动态规划将这些需要重复计算的子问题保存下来, 当下次需要的时候, 只需要查询即可, 从而能够提高算法的效率。（2） 动态规划本质上也是一种”递归与分治”的思想。只是, 与普通的递归与分治问题相比, 动态规划问题具有自己另外的特征, 即: 最优子结构性质+重叠子问题, 从而在递归与分治的基础上, 再采用特殊手段( 如记录重叠子问题) , 能够进一步提升效率。也就是说, 动态规划问题是一种特殊的”递归与分治”问题。（3） 动态规划方法有一种变形, 叫做备忘录方法。两者的关系是: 备忘录方法是动态规划的一种变形, 两者的思想是一致的。两者的区别是: 动态规划方法采用自底向上的方法, 备忘录方法采用自顶向下的方法。两者的适用场景是: 如果一个问题的所有子问题都需要至少求解一次时, 采用动态规划方法较好; 如果一个问题中只是部分子问题需要求解时, 采用备忘录方法较好。三 实验代码分析和说明本部分实验完成”矩阵连乘”问题( P45-P48) 和”0-1背包”问题( P71-73) 。3.1 矩阵连乘问题1. 矩阵连乘问题基本思想。假设有任意矩阵Ai*Ai+1*Aj共有( j-i+1) 个矩阵相乘。为了描述方便, 记为Ai:j。即: Ai:j= Ai*Ai+1*Aj。显然, Ai:j一定是有一个最优的计算次序的, 虽然不知道这个最优次序是多少, 可是不妨假设是从Ak处断开。换句话说, 对于Ai:j, 其最优计算次序为: (Ai*Ak) * (Ak+1*Aj)。显然, 上述计算次数由三部分构成。构成1: (Ai*Ak)的计算次数, 用X表示; 构成2: (Ak+1*Aj)的计算次数, 用Y表示; 构成3: (Ai*Ak)和(Ak+1*Aj)的乘积, 也就是( Ai的行数*Ak的列数*Aj的列数) 。用公式表示如下: Ai:j的计算次数 = X + Y + Ai的行数*Ak的列数*Aj的列数注意到: 由于已经固定从Ak处断开, 因此构成3是一个定值。因此, 要Ai:j的计算次数最少, 就需要X和Y分别是最小。这说明: 原问题Ai:j的最优解包含了子问题Ai:k和子问题Ak+1:j的最优解。因此, 能够使用动态规划算法。2. 动态规划算法的递归公式如果用mij表示Ai:j的最优值, 那么有: ( 1) 如果i=j, Ai:j是单独一个矩阵, 不需要计算, 因此, mij=0; ( 2) 如果i=w1) m1c = max (m2c, m2c-w1 + v1);上述语句和P73代码语义是一致的, 这也是赋值的含义。【问题1】理解递归公式的含义。【问题2】算法本身有没有做无用的计算, 为什么? 四 实验内容( 1) 完成代码, 并调试经过。( 2) 回答实验指导书中的问题。( 3) 理解动态规划的基本思想( 本质依然是递归与分治, 但满足最优子结构性质, 从而能够用动态规划方法进一步提升效率。最优子结构性质需要证明, 证明往往采用反证法) , 以及如何编程实现( 分为三个步骤: 首先, 证明最优子结构性质; 其次, 寻找大问题和小问题之间的递归关系; 最后, 将递归关系进行形式化表示, 并编程实现) 。