第5递归与分治策略冯.pptx

2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method1 1第第1 1章章 算法引论算法引论（6 6学时）学时）学时）学时）第第第第2 2章章章章 常用数学工具（常用数学工具（常用数学工具（常用数学工具（3 3学时）学时）学时）学时）第第3 3章章 NPNP完全性理论完全性理论（4.54.5学时）学时）学时）学时）第第4 4章章 蛮力法蛮力法（3 3学时）学时）学时）学时）第第5 5章章 递归与分治策略递归与分治策略（3 3学时）学时）学时）学时）第第6 6章章 减冶法（减冶法（3 3学时）学时）第第7 7章章 动态规划动态规划（3 3学时）学时）学时）学时）第第8 8章章 贪心算法贪心算法（4.54.5学时）学时）学时）学时）第第9 9章章 回溯法回溯法（4.54.5学时）学时）学时）学时）第第1010章章 分支限界法分支限界法（4.54.5学时）学时）学时）学时）第第1111章章 概率算法概率算法（4.54.5学时）学时）学时）学时）第第1212章章 近似算法近似算法（3 3学时）学时）学时）学时）总复习总复习总复习总复习 （3 3学时）学时）学时）学时）课程目录2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method2 2本章要点本章要点5.1 概概 述述 5.2 递递 归归5.3 排序问题中的分治法排序问题中的分治法5.4 组合问题中的分治法组合问题中的分治法5.5 几何问题中的分治法几何问题中的分治法5.6 实验项目实验项目最近对问题最近对问题2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method3 35.1.1分治法的设计思想分治法的设计思想5.1.2分治法的求解过程分治法的求解过程概概 述述2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method4 4 将一个难以直接解决的大问题，划分成将一个难以直接解决的大问题，划分成一些规模较小的一些规模较小的子问题子问题，以各个击破，以各个击破，分而治之分而治之。更一般地说，将要求解的。更一般地说，将要求解的原问题原问题划分成划分成k个较小规模的子问题个较小规模的子问题，对这，对这k个子问题分别求个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分解。如果子问题的规模仍然不够小，则再将每个子问题划分为为k个规模更小的子问题，如此分解下去，个规模更小的子问题，如此分解下去，直到问题规模足够直到问题规模足够小，很容易求出其解为止小，很容易求出其解为止，再将子问题的解合并为一个更大，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。规模的问题的解，自底向上逐步求出原问题的解。分治法的设计思想：分治法的设计思想：概述概述-分治法思想分治法思想2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method5 52.独立子问题：独立子问题：各子问题之间相互独立，这涉及到分治法的各子问题之间相互独立，这涉及到分治法的效率，如果各子问题效率，如果各子问题不是独立的不是独立的，则，则分治法需要重复地解公分治法需要重复地解公共的子问题共的子问题。1.平衡子问题：平衡子问题：最好使子问题的规模大致相同。也就是将一最好使子问题的规模大致相同。也就是将一个问题个问题划分成大小相等的划分成大小相等的k个子问题个子问题（通常（通常k2、4,），这），这种使子问题规模大致相等的做法是种使子问题规模大致相等的做法是出自一种平衡出自一种平衡（Balancing）子问题的思想）子问题的思想，它几乎，它几乎总是比总是比子问题规模不等子问题规模不等的做法要好。的做法要好。启发式规则：启发式规则：概述概述-分治法思想分治法思想2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method6 6子问题子问题1的规模是的规模是n/2子问题子问题1的解的解子问题子问题2的解的解子问题子问题2的规模是的规模是n/2原问题的解原问题的解原问题原问题的规模是的规模是n分治法的典型情况分治法的典型情况概述概述-分治法思想分治法思想2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method7 75.1.1分治法的设计思想分治法的设计思想5.1.2分治法的求解过程分治法的求解过程概概 述述2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method8 8一般来说，分治法的求解过程由以下三个阶段组成：一般来说，分治法的求解过程由以下三个阶段组成：（1 1）划划分分：既既然然是是分分治治，当当然然要要把把规规模模为为n n 的的原原问问题题划划分分为为k k 个个规规模模较较小小的的子子问问题题，并并尽尽量量使使这这k k 个个子子问问题题的的规规模大致相同。模大致相同。（2 2）求求解解子子问问题题：各各子子问问题题的的解解法法与与原原问问题题的的解解法法通通常常是是相相同同的的，可可以以用用递递归归的的方方法法求求解解各各个个子子问问题题，有有时时递递归归处理也可以用循环来实现。处理也可以用循环来实现。（3 3）合并：合并：把各个子问题的解合并起来，合并的代价因把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的情况不同有很大差异，分治算法的有效性很大程度上依赖有效性很大程度上依赖于合并的实现于合并的实现。概述概述-分治法的求解过程分治法的求解过程2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method9 9概述概述-分治法的求解过程分治法的求解过程分治法的一般过程分治法的一般过程 1DivideConquer(P)(P)/求解规模为求解规模为n的问题的问题P23if(P(P的规模足够小的规模足够小)直接求解直接求解P;分解为分解为k个子问题个子问题P1,P2,Pk;4for(i=1;i =1122naanaannn如果如果如果如果2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method1111n讨论nan的蛮力法计算复杂度为蛮力法计算复杂度为O(n)，因为，因为：a=1;For(i=1;i=n;i+)a=a*a;nAn的通用分治递推式主定理（第一章中），其的通用分治递推式主定理（第一章中），其复杂度为复杂度为O（nlog2n）概述概述-分治法的求解过程分治法的求解过程 结论：不是所有的分治法都结论：不是所有的分治法都比简单的蛮力法更有效比简单的蛮力法更有效。2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method1212本章要点本章要点5.1 概概 述述 5.2 递递 归归5.3 排序问题中的分治法排序问题中的分治法5.4 组合问题中的分治法组合问题中的分治法5.5 几何问题中的分治法几何问题中的分治法5.6 实验项目实验项目最近对问题最近对问题2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method13134.2递归递归5.2.1递归的概念递归的概念5.2.2递归函数的运行轨迹递归函数的运行轨迹5.2.3递归函数的内部执行过程递归函数的内部执行过程2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method1414递归的概念n n直接或间接地调用自身的算法称为直接或间接地调用自身的算法称为递归算法递归算法递归算法递归算法（Recursion）。用函数自身给出定义的函数称为用函数自身给出定义的函数称为递归函数递归函数递归函数递归函数。是一种描述问题是一种描述问题和解决问题的基本方法和解决问题的基本方法。n n由由分治法产生的子问题分治法产生的子问题分治法产生的子问题分治法产生的子问题往往是往往是原问题的较小模式原问题的较小模式原问题的较小模式原问题的较小模式，这就为使这就为使这就为使这就为使用递归技术提供了方便用递归技术提供了方便用递归技术提供了方便用递归技术提供了方便。在这种情况下，反复应用分治手段，。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致可以使子问题与原问题类型一致而其规模却不断缩小而其规模却不断缩小而其规模却不断缩小而其规模却不断缩小，最终最终最终最终使子问题缩小到很容易直接求出其解使子问题缩小到很容易直接求出其解使子问题缩小到很容易直接求出其解使子问题缩小到很容易直接求出其解。这自然导致递归过程。这自然导致递归过程的产生。的产生。2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method1515递归的概念n n分治与递归像一对孪生兄弟分治与递归像一对孪生兄弟分治与递归像一对孪生兄弟分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，经常同时应用在算法设计之中，并由此产生许多高效算法并由此产生许多高效算法并由此产生许多高效算法并由此产生许多高效算法。n递归有两个基本要素：递归有两个基本要素：边界条件：边界条件：确定递归到确定递归到何时终止何时终止；递归模式：递归模式：大问题是如何分解为小问题的。大问题是如何分解为小问题的。n n递归的几个实例递归的几个实例2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method1616例例例例1 1 1 1 阶乘（阶乘（阶乘（阶乘（Factorial ）函数）函数）函数）函数阶乘函数可递归地定义为：阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程递归的概念递归的概念2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method1717Factorial递归算法递归算法 1publicstaticintfactorial(int n)(int n)23if(n=0)return 1(n=0)return 1;4returnn*factorial(n-1);5递归的概念递归的概念2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method1818例例例例2 Fibonacci2 Fibonacci2 Fibonacci2 Fibonacci斐波纳契兔子数列斐波纳契兔子数列斐波纳契兔子数列斐波纳契兔子数列 无穷数列无穷数列无穷数列无穷数列1 1 1 1，1 1 1 1，2 2 2 2，3 3 3 3，5 5 5 5，8 8 8 8，13131313，21212121，34343434，55555555，被称为被称为被称为被称为FibonacciFibonacciFibonacciFibonacci数列。它可以递归地定义为：数列。它可以递归地定义为：数列。它可以递归地定义为：数列。它可以递归地定义为：边界条件边界条件递归方程递归方程第第n个个Fibonacci数可递归地计算如下：数可递归地计算如下：public static int fibonacci(int n)if(n m1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1 的划分组成。(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。前面的几个例子中，问题本身都具有比较明显的递归关系比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)p(n)为正整数为正整数n n的划分数的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n n1 1不大于m m 的划分个数记作q(n,m)q(n,m)。可以建立q(n,m)的如下递归关系。递归的概念递归的概念2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method2222例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设如果设p(n)p(n)为正整数为正整数n n的划分数的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作记作q(n,m)q(n,m)。可以建立建立q(n,m)q(n,m)的如下递归关系的如下递归关系。正整数n的划分数p(n)=q(n,n)。递归的概念递归的概念2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method2323 递归算法结构清晰，可读性强，而且容易用递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性数学归纳法来证明算法的正确性，因此，它为设，因此，它为设计算法和调试程序带来很大方便，是算法设计中计算法和调试程序带来很大方便，是算法设计中的的一种强有力的工具一种强有力的工具。但是，因为递归算法是一。但是，因为递归算法是一种自身调用自身的算法，随着种自身调用自身的算法，随着递归深度的增加递归深度的增加，工作栈所需要的空间增大工作栈所需要的空间增大，递归调用时的辅助操，递归调用时的辅助操作增多，因此，作增多，因此，递归算法的运行效率较低递归算法的运行效率较低。递归小结2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method2424递归小结优点：优点：优点：优点：结构清晰，可读性强，而且容易用数学归纳法来结构清晰，可读性强，而且容易用数学归纳法来结构清晰，可读性强，而且容易用数学归纳法来结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程证明算法的正确性，因此它为设计算法、调试程证明算法的正确性，因此它为设计算法、调试程证明算法的正确性，因此它为设计算法、调试程序带来很大方便。序带来很大方便。序带来很大方便。序带来很大方便。缺点：缺点：缺点：缺点：递归算法的运行效率较低，无论是递归算法的运行效率较低，无论是递归算法的运行效率较低，无论是递归算法的运行效率较低，无论是耗费的计算时耗费的计算时耗费的计算时耗费的计算时间还是占用的存储空间都比非递归算法要多间还是占用的存储空间都比非递归算法要多间还是占用的存储空间都比非递归算法要多间还是占用的存储空间都比非递归算法要多。2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method2525递归小结-分治法适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：n n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；n n该问题可以分解为若干个规模较小的相同问题，即该问题具该问题可以分解为若干个规模较小的相同问题，即该问题具该问题可以分解为若干个规模较小的相同问题，即该问题具该问题可以分解为若干个规模较小的相同问题，即该问题具有有有有最优子结构性质最优子结构性质最优子结构性质最优子结构性质n n利用该问题利用该问题利用该问题利用该问题分解出的子问题的解分解出的子问题的解分解出的子问题的解分解出的子问题的解可以可以可以可以合并为该问题的解合并为该问题的解合并为该问题的解合并为该问题的解；n n该问题所分解出的该问题所分解出的该问题所分解出的该问题所分解出的各个子问题是相互独立的各个子问题是相互独立的各个子问题是相互独立的各个子问题是相互独立的，即子问题之间，即子问题之间，即子问题之间，即子问题之间不包含公共的子问题。不包含公共的子问题。不包含公共的子问题。不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method2626递归小结-分治法基本步骤divide-and-conquerdivide-and-conquer(P)(P)if if(|P|=n(|P|=n0 0)adhocadhoc(P);(P);/解决小规模的问题解决小规模的问题 dividedivide P into smaller subinstances P P into smaller subinstances P1 1,P,P2 2,.,P,.,Pk k；/分解问题分解问题 forfor(i=1,i=k,i+)(i=1,i=k,i+)y yi i=divide-and-conquerdivide-and-conquer(P(Pi i);/);/递归的解各子问题递归的解各子问题 returnreturn merge(y merge(y1 1,.,y,.,yk k););/将各子问题的解合并为原问题的解将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的子问题的规模大致相同。即将一个问题分成大小相等的k k个子问个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种法是出自一种平衡平衡平衡平衡(balancing)(balancing)子问题子问题子问题子问题的思想，它几乎总是比子的思想，它几乎总是比子问题规模不等的做法要好。问题规模不等的做法要好。2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method2727本章要点本章要点5.1 概概 述述 5.2 递递 归归5.3 排序问题中的分治法排序问题中的分治法5.4 组合问题中的分治法组合问题中的分治法5.5 几何问题中的分治法几何问题中的分治法5.6 实验项目实验项目最近对问题最近对问题2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method2828排序问题中的分治法排序问题中的分治法5.3.1 5.3.1 归并排序归并排序5.3.2 5.3.2 快速排序快速排序2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method2929n归并排序归并排序二路归并排序的分治策略是：二路归并排序的分治策略是：（1）划划分分：将将待待排排序序序序列列r1,r2,rn划划分分为为两两个个长长度相等的子序列度相等的子序列r1,rn/2和和rn/21,rn；（2）求求解解子子问问题题：分分别别对对这这两两个个子子序序列列进进行行排排序序，得到两个有序子序列；得到两个有序子序列；（3）合合并并：将将这这两两个个有有序序子子序序列列合合并并成成一一个个有有序序序序列。列。排序问题中的分治法排序问题中的分治法2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method3030 r1 rn/2rn/21rn划分划分r1rn/2rn/21rn递归处理递归处理r1rn/2rn/21r n合并解合并解排序问题中的分治法排序问题中的分治法2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method3131算法算法5.3归并排序归并排序voidMergeSort(intr,intr1,ints,intt)/r原序列数组，原序列数组，r1归并后序列数组归并后序列数组if(s=t)r1s=rs;elsem=(s+t)/2;Mergesort(r,r1,s,m);/归并排序前半个子序列归并排序前半个子序列Mergesort(r,r1,m+1,t);/归并排序后半个子序列归并排序后半个子序列Merge(r1,r,s,m,t);/合并两个已排序的子序列合并两个已排序的子序列排序问题中的分治法排序问题中的分治法i jrs,rm rm+1,rt2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method3232算法算法5.4合并有序子序列合并有序子序列voidMerge(intr,intr1,ints,intm,intt)/i,j分别指向两个待合并的有序子序列，分别指向两个待合并的有序子序列，k指向最终有序序列的当前记录指向最终有序序列的当前记录i=s;j=m+1;k=s;while(i=m&j=t)if(ri=rj)r1k+=ri+;/取取ri和和rj中较小者放入中较小者放入r1kelser1k+=rj+;if(i=m)while(i=m)/若第一个子序列没处理完，则进行收尾处理若第一个子序列没处理完，则进行收尾处理r1k+=ri+;elsewhile(j+=2)2(221)(nnnTnnT排序问题中的分治法排序问题中的分治法2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method3434（2）求解子问题：求解子问题：分别对划分后的每一个子序列递分别对划分后的每一个子序列递归处理；归处理；（3）合并：合并：由于对子序列由于对子序列r1ri-1和和ri+1rn的排序的排序是就地进行的，所以合并不需要执行任何操作。是就地进行的，所以合并不需要执行任何操作。n快速排序的分治策略快速排序的分治策略（1）划划分分：选选定定一一个个记记录录作作为为轴轴值值，以以轴轴值值为为基基准准将将整整个个序序列列划划分分为为两两个个子子序序列列r1ri-1和和ri+1rn，前前一一个个子子序序列列中中记记录录的的值值均均小小于于或或等等于于轴轴值值，后后一一个个子子序序列列中记录的值均中记录的值均大于或等于轴值大于或等于轴值；排序问题中的分治法排序问题中的分治法2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method3535r1ri-1 ri ri+1rn 均均ri 轴值轴值均均ri 位于最终位置位于最终位置两种排序的区别：两种排序的区别：v归并排序归并排序按照按照记录在序列中的记录在序列中的位置位置对序列进行划分，对序列进行划分，v快速排序快速排序按照按照记录的记录的值值对序列进行划分对序列进行划分排序问题中的分治法排序问题中的分治法2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method3636以第一个记录作为轴值，对待排序序列进行划分的以第一个记录作为轴值，对待排序序列进行划分的过程过程：（1）初初始始化化：取取第第一一个个记记录录作作为为基基准准，设设置置两两个个参参数数i，j分分别别用用来来指指示示将将要要与与基基准准记记录录进进行行比比较较的的左左侧侧记记录录位位置置和和右右侧侧记录位置记录位置，也就是，也就是本次划分的区间本次划分的区间；（2）右右侧侧扫扫描描过过程程：将将基基准准记记录录与与j指指向向的的记记录录进进行行比比较较，如如果果j指指向向记记录录的的关关键键码码大大，则则j-,即即前前移移一一个个记记录录位位置置。重重复复右右侧侧扫扫描描过过程程，直直到到右右侧侧的的记记录录小小（即即反反序序），若若ij，则将基准记录与则将基准记录与j指向的记录进行交换指向的记录进行交换；（3）左左侧侧扫扫描描过过程程：将将基基准准记记录录与与i指指向向的的记记录录进进行行比比较较，如如果果i指指向向记记录录的的关关键键码码小小，则则i+，即即后后移移一一个个记记录录位位置置。重重复复左左侧侧扫扫描描过过程程，直直到到左左侧侧的的记记录录大大（即即反反序序），若若ij，则将基准记录与则将基准记录与i指向的记录交换指向的记录交换；排序问题中的分治法排序问题中的分治法2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method3737（4）重重复复（2）（3）步步，直直到到i与与j指指向向同同一一位位置置，即即基基准准记记录最终的位置。录最终的位置。排序问题中的分治法排序问题中的分治法一次划分示例一次划分示例一次划分示例一次划分示例:（1 1）i=1,j=7i=1,j=7，r1r1为基准记录为基准记录为基准记录为基准记录;（2 2）r1rj?r1rj?r1rj,j，否则交换，否则交换，否则交换，否则交换（3 3）rirj?rirj,i+,rirj?rirj,i+,否则交换否则交换否则交换否则交换（4 4）i=j?Ifi=j,theni=j?Ifi=j,then第一次划分基准记录位置找到第一次划分基准记录位置找到第一次划分基准记录位置找到第一次划分基准记录位置找到2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method38381313656527275050383849495555jijj1313656527275050383849495555jiii1313656527275050383849495555ijjj一一一一次次次次划划划划分分分分示示示示例例例例2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method3939算法算法5.5一次划分一次划分intPartition(intr,intfirst,intend)i=first;j=end;/初始化初始化while(ij)while(ij&ri=rj)j-；/右侧扫描右侧扫描if(ij)rirj;/将较小记录交换到前面将较小记录交换到前面i+;while(ij&ri=rj)i+；/左侧扫描左侧扫描if(ij)rjri;/将较大记录交换到后面将较大记录交换到后面j-;retutni;/i为轴值记录的最终位置为轴值记录的最终位置排序问题中的分治法排序问题中的分治法2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method4040以以轴轴值值(如如此此处处为为轴轴值值：38)为为基基准准将将待待排排序序序序列列划划分分为为两两个个子子序序列列后后，对对每每一一个个子子序序列列分分别别递递归归进进行行排序。排序。131327275050383849495555jiij13136565272750503838494955556565排序问题中的分治法排序问题中的分治法2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method4141算法算法5.6快速排序快速排序 void QuickSort(int r,int first,int end)if(first0)sum=aleft;elsesum=0;elsecenter=(left+right)/2;/划分划分leftsum=MaxSum(a,left,center);/对应情况对应情况，递归求解，递归求解rightsum=MaxSum(a,center+1,right);/对应情况对应情况，递归求解，递归求解最大子段和问题最大子段和问题2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method5151s1=0;lefts=0;/以下对应情况以下对应情况，先求解，先求解s1for(i=center;i=left;i-)lefts+=ai;if(leftss1)s1=lefts;s2=0;rights=0;/再求解再求解s2for(j=center+1;js2)s2=rights;sum=s1+s2;/计算情况计算情况的最大子段和的最大子段和if(sumleftsum)sum=leftsum;/合并，在合并，在sum、leftsum和和rightsum中取较大者中取较大者if(sum0时，可将时，可将2k2k的棋盘划分为的棋盘划分为4个个2k-12k-1的子棋盘，的子棋盘，这样划分后，由于这样划分后，由于原棋盘只有一个特殊方格原棋盘只有一个特殊方格，所以，这，所以，这4个个子棋盘中只有一个子子棋盘中只有一个子棋盘包含该特殊方格棋盘包含该特殊方格，其余，其余3个子棋盘个子棋盘中没有特殊方格。为了将这中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，为特殊棋盘，以便采用递归方法求解，可以用一个可以用一个L型骨牌型骨牌覆盖这覆盖这3个较小棋盘的会合处个较小棋盘的会合处，从而将原问题转化为，从而将原问题转化为4个较个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为将棋盘分割为11的子棋盘。的子棋盘。棋盘覆盖问题棋盘覆盖问题2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method56562k-12k-12k-12k-12k-12k-12k-12k-1(a)棋盘分割棋盘分割(b)构造相同子问题构造相同子问题棋盘覆盖问题棋盘覆盖问题2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method5757下面讨论棋盘覆盖问题中数据结构的设计。下面讨论棋盘覆盖问题中数据结构的设计。（1）棋盘：棋盘：可以用一个二维数组可以用一个二维数组boardsizesize表示一个棋盘，表示一个棋盘，其中，其中，size=2k。为了在递归处理的过程中使用同一个棋盘，将。为了在递归处理的过程中使用同一个棋盘，将数组数组board设为全局变量设为全局变量；（2）子棋盘：子棋盘：整个棋盘用二维数组整个棋盘用二维数组boardsizesize表示，其中表示，其中的子棋盘由棋盘左上角的下标的子棋盘由棋盘左上角的下标tr、tc和和棋盘大小棋盘大小s表示；表示；（3）特殊方格：特殊方格：用用boarddrdc表示特殊方格，表示特殊方格，dr和和dc是该特是该特殊方格在二维数组殊方格在二维数组board中的下标中的下标;（4）L型骨牌：型骨牌：一个一个2k2k的棋盘中有一个的棋盘中有一个特殊方格特殊方格，所以，所以，用到用到L型骨牌的个数型骨牌的个数为为(4k-1)/3，将所有，将所有L型骨牌从型骨牌从1开始连续开始连续编号，用一个全局变量编号，用一个全局变量t表示。表示。棋盘覆盖问题棋盘覆盖问题2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method5858dcdrtrtcsize棋盘覆盖问题中的数据结构棋盘覆盖问题中的数据结构棋盘覆盖问题棋盘覆盖问题2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method5959算法算法5.8棋盘覆盖棋盘覆盖voidChessBoard(inttr,inttc,intdr,intdc,intsize)/tr和和tc是子棋盘左上角的下标，是子棋盘左上角的下标，dr和和dc是特殊方格的下标，是特殊方格的下标，/size是棋盘的大小，是棋盘的大小，t是骨牌编号，已初始化为是骨牌编号，已初始化为0if(size=1)return;/棋盘只有一个方格且是特殊方格棋盘只有一个方格且是特殊方格t+;/L型骨牌号型骨牌号s=size/2;/划分棋盘划分棋盘/覆盖左上角子棋盘覆盖左上角子棋盘if(drtr+s&dctc+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);棋盘覆盖问题棋盘覆盖问题2024/9/6 2024/9/6 周五周五Divide and Conquer MethodDivide and Conquer Method6060 /覆盖右上角子棋盘覆盖右上角子棋盘覆盖右上角子棋盘覆盖右上角子棋盘 if(dr=tc+s)if(dr=tc+s)/特殊方格在右上角子棋盘中特殊方格在右上角子棋盘中特殊方格在右上角子棋盘中特殊方格在右上角子棋盘中 ChessBoard(tr,tc+s,dr,dc,s);ChessBoard(tr,tc+s,dr,dc,s);/递归处理子棋盘递归处理子棋盘递归处理子棋盘递归处理子棋盘 else /else /用用用用 t t 号号号号L L型骨牌覆盖左下角，再递归处理子棋盘型骨牌覆盖左下角，再递归处理子棋盘型骨牌覆盖左下角，再递归处理子棋盘型骨牌覆盖左下角，再递归处理子棋盘 board tr+s-1tc+s=t;board tr+s-1tc+s=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);ChessBoard(tr,tc+s,tr+s-1,tc+s,s);/覆盖左下角子棋盘覆盖左下角子棋盘覆盖左下角子棋盘覆盖左下角子棋盘 if(dr=tr+s&dc=tr+s&dc=tr+s&dc=tc+s)/if(dr=tr+s&dc=tc+s)/特殊方格在右下角子棋盘中特殊方格在右下角子棋盘中特殊方格在右下角子棋盘中特殊方格在右下角子棋盘中 ChessBoard