算法设计方案与分析验.docx

实验二:分治法实验一、实验目的(1)掌握设计有效算法的分治策略。(2)通过快速排序学****分治策略设计技巧二、实验要求(1)熟练掌握分治法的基本思想及其应用实现。(2)理解所给出的算法,并对其加以改进。三、分治法的介绍任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。 而当 n 较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。如果原问题可分割成 k 个子问题,1<k≤n ,且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。分治法的适用条件:(1)该问题的规模缩小到一定的程度就可以容易地解决;(2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。(3)利用该问题分解出的子问题的解可以合并为该问题的解;(4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。分治法的基本步骤:分治法在每一层递归上都有三个步骤:分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;合并:将各个子问题的解合并为原问题的解。它的一般的算法设计模式如下:Divide-and-Conquer(P)1. if |P|≤n02. then return(ADHOC(P))3. 将 P 分解为较小的子问题 P1 ,P2 ,...,Pk4. for i←1 to k5. do yi ← Divide-and-Conquer(Pi) △ 递归解决 Pi6. T ← MERGE(y1,y2,...,yk) △ 合并子问题7. return(T)其中|P|表示问题 P 的规模;n0 为一阈值,表示当问题 P 的规模不超过 n0 时,问题已容易直接解出,不必再继续分解。ADHOC(P)是该分治法中的基本子算法,用于直接解小规模的问题 P。因此,当 P 的规模不超过 n0 时,直接用算法 ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法,用于将 P 的子问题 P1 ,P2 ,...,Pk 的相应的解 y1,y2,...,yk 合并为 P 的解。根据分治法的分割原则,原问题应该分为多少个子问题才较适宜?各个子问题的规模应该怎样才为适当?这些问题很难予以肯定的回答。但人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。换句话说,将一个问题分成大小相等的 k 个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显,有些问题合并方法比较复杂,或者是有多种合并方案;或者是合并方案不明显。究竟应该怎样合并,没有统一的模式,需要具体问题具体分析。四、实验内容1、编程实现归并排序算法和快速排序算法,程序中加入比较次数的计数功能,输出排序结果和比较次数。输入 10 组相同的数据,验证排序结果和完成排序的比较次数。用表格列出比较结果。给出文字分析。2、汉诺塔(hanoi)问题。3、棋盘覆盖问题。4、循环赛日程安排问题。五、算法设计1、归并排序算法procedure MERGESORT(low,high)//A(low;high)是一个全程数组,它含有high-low+1≥0个待排序的元素//integer low,high;if low<high;then mid← , //求这个集合的分割点//call MERGESORT(low,mid) /