第4章分治法.pptx

第4章 分治法 ;4.1 概 述 ; 将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。 ;2. 独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。 ;;4.1.2 分治法的求解过程 ; 例：计算an，应用分治技术得到如下计算方法：;4.2 递 归 ;4.2.1 递归的定义 ;;;;递归函数的经典问题——汉诺塔问题 在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。 ;;? 李志欣;算法4.2——汉诺塔算法 1 void Hanoi(int n, char A, char B, char C) //第一列为语句行号 2 { 3 if (n==1) Move(A, C); //Move是一个抽象操作，表示将碟子从A移到C上 4 else { 5 Hanoi(n-1, A, C, B); 6 Move(A, C); 7 Hanoi(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/2 rn/2＋1 … … rn 划分 r‘1… …r’n/2 r’n/2＋1… …r’n 递归处理 r1……rn/2rn/2＋1 ……r n 合并解 ; 算法4.3——归并排序 void MergeSort(int r[ ], int r1[ ], int s, int t) { 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——合并有序子序列 void Merge(int r[ ], int r1[ ], int s, int m, int t) { 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] else r1[k++]=r[j++]; } if (i=m) while (i=m)