算法设计与分析实验二

《算法设计与分析实验二》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验二：分治法实验一、实验目的（1）掌握设计有效算法的分治策略。（2）通过快速排序学习分治策略设计技巧二、实验要求（1）熟练掌握分治法的基本思想及其应用实现。（2）理解所给出的算法，并对其加以改进。三、分治法的介绍任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分

2、割成k个子问题，1

3、有最优子结构性质。（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则

4、分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。分治法的基本步骤：分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。它的一般的算法设计模式如下：Divide-and-Conquer(P)1. if

5、P

6、≤n02.   thenreturn(ADHOC(P))3. 将P分解为较小的子问题P1,P2,...,Pk4. fori←

7、1tok5.   doyi←Divide-and-Conquer(Pi)   △递归解决Pi6. T←MERGE(y1,y2,...,yk)            △合并子问题7. return(T)其中

8、P

9、表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,

10、...,Pk的相应的解y1,y2,...,yk合并为P的解。根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并

11、方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。四、实验内容1、编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。输入10组相同的数据，验证排序结果和完成排序的比较次数。用表格列出比较结果。给出文字分析。2、汉诺塔（hanoi）问题。3、棋盘覆盖问题。4、循环赛日程安排问题。五、算法设计1、归并排序算法procedureMERGESORT(low，high)//A(low；high)是一个全程数组，它含有high-low+1≥

12、0个待排序的元素//integerlow，high；iflow