第4章分治法4.1概述将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。2.独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。子问题1的规模是n/24.1.2分治法的求解过程例：计算an，应用分治技术得到如下计算方法：4.2递归4.2.1递归的定义递归函数的经典问题——汉诺塔问题在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。算法4.2——汉诺塔算法1voidHanoi(intn,charA,charB,charC)//第一列为语句行号2{3if(n==1)Move(A,C);//Move是一个抽象操作，表示将碟子从A移到C上4else{5Hanoi(n-1,A,C,B);6Move(A,C);7Hanoi(n-1,B,A,C);8}9}4.2.2递归函数的运行轨迹Hanio(3,A,B,C)4.2.3递归函数的内部执行过程汉诺塔算法在执行过程中，工作栈的变化下图所示，其中栈元素的结构为（返回地址，n值，A值，B值，C值），返回地址对应算法中语句的行号。递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。但是，因为递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。4.3排序问题中的分治法4.3.1归并排序r1……rn/2rn/2＋1……rn划分r‘1<……<r’n/2r’n/2＋1<……<r’n递归处理r''1<……<r''n/2<r''n/2＋1<……<r''n合并解算法4.3——归并排序voidMergeSort(intr[],intr1[],ints,intt){if(s==t)r1[s]=r[s];else{m=(s+t)/2;Mergesort(r,r1,s,m);//归并排序前半个子序列Mergesort(r,r1,m+1,t);//归并排序后半个子序列Merge(r1,r,s,m,t);//合并两个已排序的子序列}}二路归并排序的合并步的时间复杂性为O(n)，所以，二路归并排序算法存在如下递推式：算法4.4——合并有序子序列voidMerge(intr[],intr1[],ints,intm,intt){i=s;j=m+1;k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中较小者放入r1[k]elser1[k++]=r[j++];}if(i<=m)while(i<=m)//若第一个子序列没处理完，则进行收尾处理r1[k++]=r[i++];elsewhile(j<=t)//若第二个子序列没处理完，则进行收尾处理r1[k++]=r[j++];}4.3.2快速排序[r1……ri-1]ri[ri+1……rn]均≤ri轴值均≥ri位于最终位置以第一个记录作为轴值，对待排序序列进行划分的过程为：（1）初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；（2）右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若i＜j，则将基准记录与j指向的记录进行交换；（3）左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若i＜j，则将基准记录与i指向的记录交换；（4）重复（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。13算法4.5——一次划分intPartition(intr[],intfirst,intend){i=first;j