《算法分析与设计》实验指导书.docxVIP

算法分析与设计 本书是为配合《计算机算法分析与设计》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，增强算法分析与设计实践动手能力。 上机实验注意事项如下： （1）课前认真做好预习，准备好实验工具，熟悉实验流程和手段。 （3）课中根据实验指导书，结合课本实例进行编程实验。实验时，一人一组，独立上机调试，上机时出现疑问，可以举手询问实验指导老师，或者与周边同学小声讨论，鼓励独立解决问题。 （4）课后按时按质按量整理出实验报告。实验报告应独立完成，拒绝抄袭。 实验内容覆盖：递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等。 实验一 递归与分治策略 一． 实验目的与要求 （1） 理解和掌握递归与分治策略的基本原理。 （2） 理解课本中的示例代码。 （3） 调试代码通过。 二． 递归与分治的基本思想 （1） 递归与分治方法。 递归与分治方法的基本思想是：将一个难以解决的大问题，分割成一些规模较小的、相同的子问题，以便各个击破，分而治之。 （2） 递归。 递归问题分析时，要把握如下两个要素： ● 递归出口。 ● 递归公式。 其中： ● 递归出口给出了最简单情况下问题的解。 ● 递归公式则给出了一般意义下大问题（原问题）和小问题（子问题）之间的递归关系。通过递归公式，一个难以解决的大问题会随着递归不断分解为多个小问题，小问题继续递归变为更小的小问题，直到最后到达递归出口得到解。 三． 实验代码分析和说明 本部分实验，需完成“棋盘覆盖”（课本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. 快速排序的基本思路。 假设需要排序的数存储在数组“a[p], a[p+1], ……, a[r]”中。为了描述方便，将上述数组简记为：a[p:r]。 （1） 首先，以a[p]为基准元素，将a[p:r]划分为三段，分别是：a[p: q-1], a[q], a[q+1: r]。其中，a[p: q-1]中的任何一个元素都小于等于a[q]；a[q]小于等于a[q+1: r]中的任何一个元素。注意：算法工作时，以a[p]为基准进行a[p:r]划分；a[q]是在划分完成时确定的。 （2） 对划分得到的a[p: q-1]和a[q+1: r]类似地，进行划分。 （3） 注意到a[p: q-1], a[q], a[q+1: r]的关系，不要任何计算，数组a[p: r]就已经自动排好序。 【问题】快速排序的上述思想中，是如何体现“将大问题划分为相同或相似的小问题”的？ 四． 实验内容 （1） 完成代码，并调试通过。 （2） 回答实验指导书中的问题。 （3） 体会递归与分治策略的基本思想，以及在编程中如何实现。 实验二 动态规划 一． 实验目的与要求 （1） 理解动态规划的基本思想。 （2） 理解课本中示例代码并调试通过。 （3） 根据自己的理解，回答实验指导书中的问题。 二． 动态规划的基本思想 （1） 动态规划问题需要满足两个特征，分别是： ● 最优子结构性质。即：大问