算法设计与分析实验二.doc

实验二：分治法实验一、实验目的 （1）掌握设计有效算法的分治策略。 （2）通过快速排序学习分治策略设计技巧二、实验要求 （1）熟练掌握分治法的基本思想及其应用实现。 （2）理解所给出的算法，并对其加以改进。三、分治法的介绍 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。 而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1kn ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。分治法的适用条件：（1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 （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为一阈值，表示当问题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+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)计算时间。如果我们能设计一个需要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进行排序。 合并(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,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 /划分元素在位置p/ End PARTITION 3、汉诺塔（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(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;typedef int ElemType;struct recKeyType 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) 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+;elser2k=rj;j+;output(r2,M);while(jh)r2k=rj;j+;k+;while(i=m)r2k=ri;i+;k+;output(r2,M);private: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#define MAXI 10typedef int KeyType;typedef int ElemType;struct recKeyType 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(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;srand(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; / 分割棋盘 / 覆盖左上角子棋盘 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型骨牌覆盖左下角boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoa