1、算法设计方案与分析验实验二：分治法实验一、实验目的（1）掌握设计有效算法的分治策略。（2）通过快速排序学习分治策略设计技巧二、实验要求（1）熟练掌握分治法的基本思想及其应用实现。（2）理解所给出的算法，并对其加以改进。三、分治法的介绍任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。 而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1kn ，且这些子问题都可
2、解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。分治法的适用条件：（1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子
3、问题是相互独立的，即子问题之间不包含公共的子问题。 上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。分治法的基本步骤：分治法在每一层递归上都有三个步骤：分解：将原问题分解
4、为若干个规模较小，相互独立，与原问题形式相同的子问题； 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 合并：将各个子问题的解合并为原问题的解。 它的一般的算法设计模式如下：Divide-and-Conquer(P)1. if |P|n0 2. then return(ADHOC(P)3. 将P分解为较小的子问题 P1 ,P2 ,.,Pk4. for i1 to k 5. do yi Divide-and-Conquer(Pi) 递归解决Pi6. T MERGE(y1,y2,.,yk) 合并子问题7. return(T)其中|P|表示问题P的规模；n0为一阈值，表示当问题
5、P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC(P)求解。算法MERGE(y1,y2,.,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,.,Pk的相应的解y1,y2,.,yk合并为P的解。根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许
6、多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。四、实验内容 1、编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。输入10组相同的数据，验证排序结果和完成排序的比较次数。用表格列出比较结果。给出文字分析。 2、汉诺塔（hanoi）问题。 3、棋盘覆盖问题。 4、循环赛日程安排问题
7、。五、算法设计1、归并排序算法procedure MERGESORT(low，high) /A(low；high)是一个全程数组，它含有high-low+10个待排序的元素/ integer low，high； if lowmid then for kj to high do /处理剩余的元素/ B(i) A(k)；ii+1 repeat else for kh to mid do B(i) A(k)；ii+1 repeat endif 将已归并的集合复制到A end MERGE 2、快速排序算法我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要(nlogn
8、)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。算法的基本思想：快速排序的基本思想是基于分治策略的。对于输入的子序列Lp.r，如果规模足够小则直接进行排序，否则分三步处理：分解(Divide)：将输入的序列Lp.r划分成两个非空子序列Lp.q和Lq+1.r，使Lp.q中任一元素的值不大于Lq+1.r中任一元素的值。 递归求解(Conquer)：通过递归调用快速排序算法分别对Lp.q和Lq+1.r进行排序
9、。 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在Lp.q和Lq+1.r都排好序后不需要执行任何计算Lp.r就已排好序。 这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。QuickSort(p,q) /将数组A1:n中的元素 Ap, Ap+1, , Aq按不降次序排列， 并假定An+1是一个确定的、且大于 A1:n中所有的数。/ int p,q。 global n, A1:n。 if pq then j=Partition(p, q+1)。 / 划分后j成为划分元素的位置 QuickSort(p,j-1)。 QuickSort(j+1,
10、q)。 endif end QuickSortprocedure PARTITION(m，p) /退出过程时，p带着划分元素所在的下标位置。/ integer m，p，i；global A(m：p-1) vA(m)；im /A(m)是划分元素/ loop loop ii+1 until A(i)v repeat /i由左向右移/ loop pp-1 until A(p)v repeat /p由右向左移/ if ip then call INTERCHANGE(A(i)，A(p) /A(i)和A(p)换位/ else exit endif repeat A(m) A(p)；A(p) v /划分元
11、素在位置p/ End PARTITION3、汉诺塔（hanoi）问题。设有 A、B、 C 共 3 根塔座， 在塔座 A 上堆叠 n个金盘， 每个盘大小不同， 只允许小盘在大盘之上，最底层的盘最大，如下图 所示。现在要求将 A 上的盘全都移到 C 上，在移的过程中要遵循以下原则：每次只能移动 一个盘；圆盘可以插在 A、B 和 C 任一个塔座上；在任何时刻，大盘不能放在小盘的上面。hanoi问题递归求解思想： 我们把一个规模为n的hanoi问题：1到n号盘按照移动规则从A上借助B移到C上表示为H(A,B,C,n)；原问题划分成如下三个子问题：（1）将1到n-1号盘按照移动规则从A上借助C移到B上H
12、(A,C,B,n-1)。（2）将n号盘从A上直接移到C上；（3）将1到n-1号盘按照移动规则从B上借助A移到C上H(B,A,C,n-1)。经过三个子问题求解，原问题的也即求解完成。 4、盘覆盖问题。在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。六、参考程序代码1、归并排序#include#include#include#include#define M 11typedef int KeyType。type
13、def int ElemType。struct rec KeyType key。 ElemType data。 。typedef rec sqlistM。class guibingpublic: guibing(sqlist b) for(int i=0。iM。i+) ri=bi。 void output(sqlist r,int n) for(int i=0。in。i+) coutsetw(4)ri.key。 coutendl。 void xuanze(sqlist b,int m,int n) int i,j,k。 for(i=m。in-1。i+) k=i。 for(j=i。jbj.key
14、) k=j。 if(k!=i) rec temp=bk。 bk=bi。 bi=temp。 void merge(int l,int m,int h,sqlist r2) xuanze(r,l,m)。 xuanze(r,m,h)。 output(r,M)。 int i,j,k。 k=i=l。 for(j=m。im&jh。k+) if(ri.key=rj.key) r2k=ri。 i+。 else r2k=rj。 j+。 output(r2,M)。 while(jh) r2k=rj。 j+。 k+。 while(i=m) r2k=ri。 i+。 k+。 output(r2,M)。 private:
15、 sqlist r。 。 void main() coutguibingfa1运行结果:n。 sqlist a,b。 int i,j=0,k=M/2,n=M。 srand(time(0)。 for(i=0。iM。i+) ai.key=rand()%80。bi.key=0。 guibing gx(a)。 cout排序前数组:n。 gx.output(a,M)。 cout数组排序过程演示:n。 gx.merge(j,k,n,b)。 cout排序后数组:n。 gx.output(b,M)。 cin.get()。 2、快速排序#include#include#include#include#defin
16、e MAXI 10typedef int KeyType。typedef int ElemType。struct rec KeyType key。 ElemType data。 。typedef rec sqlistMAXI。class kuaisupublic: kuaisu(sqlist a,int m):n(m) for(int i=0。in。i+) bi=ai。 void quicksort(int s,int t) int i。 if(st) i=part(s,t)。 quicksort(s,i-1)。 quicksort(i+1,t)。 else return。 int part(
17、int s,int t) int i,j。 rec p。 i=s。j=t。p=bs。 while(ij) while(i=p.key)j-。 bi=bj。 while(ij&bi.key=p.key)i+。 bj=bi。 bi=p。 output()。 return i。 void output() for(int i=0。in。i+) coutsetw(4)bi.key。 coutendl。 private: sqlist b。 int n。void main() coutkuaisu1.cpp运行结果:n。 sqlist a1。 int i,n=MAXI,low=0,high=9。 sra
18、nd(time(0)。 for(i=0。in。i+) a1i.key=rand()%80。 kuaisu px(a1,n)。 cout数组排序过程演示:n。 px.quicksort(low,high)。 cout0) H(A,C,B,n-1)。 printf(“%d from %c to %c”,n,A,C)。 H(B,A,C,n-1)。 4、棋盘覆盖问题。void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return。 int t = tile+, / L型骨牌号 s = size/2。 / 分割
19、棋盘 / 覆盖左上角子棋盘 if (dr tr + s & dc tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s)。 else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t。 / 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s)。 / 覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s)。 else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖
20、左下角boardtr + s - 1tc + s = t。 / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s)。 / 覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s)。 else / 用 t 号L型骨牌覆盖左上角 boardtr + stc + s = t。 / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s)。 5、循环赛日程安排问题#includestdio.h
21、void Table(int k,int a9) int n=1。 for(int i=1。i=k。i+)n*=2。 for(i=1。i=n。i+)a1i=i。 int m=1。 for(int s=1。s=k。s+) n/=2。 for(int t=1。t=n。t+) for( i=m+1。i=2*m。i+) for(int j=m+1。j=2*m。j+) aij+(t-1)*m*2=ai-mj+(t-1)*m*2-m。 aij+(t-1)*m*2-m=ai-mj+(t-1)*m*2。 m*=2。 main() int k=3。 int a99=0。 Table(k,a)。 for(int i=1。i=8。i+) for(int j=1。j=8。j+) printf(%3d,aij)。 printf(n)。 思考问题：1、递归的关键问题在哪里？ 2、递归与非递归之间程序的转换？
