分治算法PPT讲稿.ppt

分治算法第1页，共16页，编辑于2022年，星期五例：找出伪币例：找出伪币给你一个装有给你一个装有n枚硬币的袋子。枚硬币的袋子。n枚硬币中有一个枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。器，可以知道两组硬币的重量是否相同。对对n=2,3,4,5,6,7,8,9?N=80?第2页，共16页，编辑于2022年，星期五分治思想分治思想【分治思想分治思想分治思想分治思想】：分治就是：分治就是：分治就是：分治就是“分而治之分而治之分而治之分而治之”的意思，其实质就是将原问的意思，其实质就是将原问的意思，其实质就是将原问的意思，其实质就是将原问题分成题分成题分成题分成n n个规模较小而结构与原问题相似的子问题；然后递归地解这些个规模较小而结构与原问题相似的子问题；然后递归地解这些个规模较小而结构与原问题相似的子问题；然后递归地解这些个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。当子问题，最后合并其结果就得到原问题的解。当子问题，最后合并其结果就得到原问题的解。当子问题，最后合并其结果就得到原问题的解。当n=2n=2时的分治法又称二时的分治法又称二时的分治法又称二时的分治法又称二分法。分法。分法。分法。分治步骤：分治步骤：分治步骤：分治步骤：1.1.分解分解分解分解(Divide)(Divide)：将原问题分成一系列子问题。：将原问题分成一系列子问题。：将原问题分成一系列子问题。：将原问题分成一系列子问题。2.2.解决解决解决解决(Conquer)(Conquer)：递归地解各子问题。若子问题足够小，则：递归地解各子问题。若子问题足够小，则：递归地解各子问题。若子问题足够小，则：递归地解各子问题。若子问题足够小，则可直接求解。可直接求解。可直接求解。可直接求解。3.3.合并合并合并合并(combine)(combine)；将子问题的结果合并成原问题的解。；将子问题的结果合并成原问题的解。；将子问题的结果合并成原问题的解。；将子问题的结果合并成原问题的解。第3页，共16页，编辑于2022年，星期五分治思想分治思想问题问题S问题问题S问题问题SS的解的解问题问题S1问题问题S2问题问题Si问题问题SnS1的解的解S2的解的解Si的解的解Sn的解的解问题的分解问题的分解子集解的合并子集解的合并子问题求子问题求解解第4页，共16页，编辑于2022年，星期五分治策略的解题思路分治策略的解题思路 if(问题不可分问题不可分)直接求解；直接求解；返回问题的解；返回问题的解；else 对原问题进行分治；对原问题进行分治；递归对每一个分治的部分求解递归对每一个分治的部分求解;归并整个问题，得出全问题的解；归并整个问题，得出全问题的解；第5页，共16页，编辑于2022年，星期五应用举例应用举例:一元三次方程求解一元三次方程求解【问题描述问题描述】：有形如：有形如：ax3+bx2+cx+d=0这样的一个一元三次这样的一个一元三次方程。给出该方程中各项的系数方程。给出该方程中各项的系数(a，b，c，d均为实数均为实数)，并约定该，并约定该方程存在三个不同实根方程存在三个不同实根(根的范围在根的范围在-100至至100之间之间)，且根与根之差，且根与根之差的绝对值的绝对值=1。要求由小到大依次在同一行输出这三个实根。要求由小到大依次在同一行输出这三个实根(根与根根与根之间留有空格之间留有空格)，并精确到小数点后，并精确到小数点后4位。位。提示：记方程提示：记方程f(x)=ax3+bx2+cx+d，若存在，若存在2个数个数x1和和x2，且，且x1x2，f(x1)*f(x2)0，则在，则在(x1，x2)之间一定有一个根。之间一定有一个根。【样例输入样例输入】：1 -5 -4 20【样例输出样例输出】：-2.00 2.00 5.00第6页，共16页，编辑于2022年，星期五分分 析析如果精确到小数点后两位，可用简单的枚举法：将如果精确到小数点后两位，可用简单的枚举法：将x从从-100.00 到到100.00（步长（步长0.01）逐一枚举，得到逐一枚举，得到20000个个 f(x)，取其值与，取其值与0最接近的三个最接近的三个f(x)，对应的，对应的x即为答即为答案。而题目已改成精度为小数点后案。而题目已改成精度为小数点后4位，枚举算法时间位，枚举算法时间复杂度将达不到要求。复杂度将达不到要求。直接使用求根公式，极为复杂。加上本题的提示给直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值得到根的某精度的数值第7页，共16页，编辑于2022年，星期五分分 析析u当已知区间当已知区间(a,b)内有一个根时，用二分法求根，若区间内有一个根时，用二分法求根，若区间(a,b)内有根，内有根，则必有则必有f(a)*f(b)b或或f(a+b)/2)=0，则可确定根为，则可确定根为(a+b)/2并退出并退出过程；过程；u(2).若若f(a)*f(a+b)/2)0,则必然有则必然有f(a+b)/2)*f(b)0,根在根在(a+b)/2,b)中中,对此区间重复该过程。对此区间重复该过程。u执行完毕执行完毕,就可以得到精确到就可以得到精确到0.0001的根。的根。第8页，共16页，编辑于2022年，星期五应用举例应用举例-二分查找二分查找 在一个从小到大排序好的表里搜索关键码在一个从小到大排序好的表里搜索关键码在一个从小到大排序好的表里搜索关键码在一个从小到大排序好的表里搜索关键码x x 顺序查找：最坏情况下要比较所有元素顺序查找：最坏情况下要比较所有元素顺序查找：最坏情况下要比较所有元素顺序查找：最坏情况下要比较所有元素 二分查找：只需要比较二分查找：只需要比较二分查找：只需要比较二分查找：只需要比较log2nlog2n个元素个元素个元素个元素 Divide:Divide:检查中间元素检查中间元素检查中间元素检查中间元素 Conquer:Conquer:递归在其中一个区间内搜索递归在其中一个区间内搜索递归在其中一个区间内搜索递归在其中一个区间内搜索 Combine:Combine:平凡的平凡的平凡的平凡的2.2.2.2.折半查找折半查找折半查找折半查找：是在一列升序（或降序）的数中查找目的数。将这一列数存储：是在一列升序（或降序）的数中查找目的数。将这一列数存储：是在一列升序（或降序）的数中查找目的数。将这一列数存储：是在一列升序（或降序）的数中查找目的数。将这一列数存储在数组在数组在数组在数组a a a a中中中中,目的是寻找目的是寻找目的是寻找目的是寻找x,x,x,x,用用用用toptoptoptop指向低端指向低端指向低端指向低端,bot,bot,bot,bot指向高端指向高端指向高端指向高端,mid,mid,mid,mid指向中间指向中间指向中间指向中间,然后进然后进然后进然后进行以下三种比较：行以下三种比较：行以下三种比较：行以下三种比较：（1 1 1 1）若）若）若）若x=amid,x=amid,x=amid,x=amid,则表示找到；则表示找到；则表示找到；则表示找到；（2 2 2 2）若）若）若）若xamid,xamid,xamid,xamid,xamid,xamid,xamid,则进行下一步查找则进行下一步查找则进行下一步查找则进行下一步查找,top:=mid-1;bot,top:=mid-1;bot,top:=mid-1;bot,top:=mid-1;bot不变不变不变不变,假如有已按由小到大排好序的假如有已按由小到大排好序的假如有已按由小到大排好序的假如有已按由小到大排好序的9 9 9 9个数个数个数个数,a1-a9,a1-a9,a1-a9,a1-a9 其值分别为：其值分别为：其值分别为：其值分别为：1 3 5 7 9 11 13 15 171 3 5 7 9 11 13 15 171 3 5 7 9 11 13 15 171 3 5 7 9 11 13 15 17第9页，共16页，编辑于2022年，星期五int erfind(int low,int high,int x)int erfind(int low,int high,int x)/在在在在alowalow与与与与ahighahigh之间查找是否有值为之间查找是否有值为之间查找是否有值为之间查找是否有值为x x的元素的元素的元素的元素 int mid;int mid;while(low=high)while(low=high)mid=(low+high)/2;mid=(low+high)/2;if(amid=x)return mid;/if(amid=x)return mid;/查找成功查找成功查找成功查找成功 if(x amid)high=mid1;if(x amid)high=mid1;else low=mid+1;else low=mid+1;return-1;/return-1;/查找不成功查找不成功查找不成功查找不成功 代码代码第10页，共16页，编辑于2022年，星期五应用举例应用举例-归并排序归并排序 problem problem：给：给：给：给n n个数个数个数个数,要求从小到大排序要求从小到大排序要求从小到大排序要求从小到大排序 divide divide：将：将：将：将n n个元素分成各含个元素分成各含个元素分成各含个元素分成各含n/2n/2个元素的子序列个元素的子序列个元素的子序列个元素的子序列;conquer conquer：用合并排序法对这两个子序列递归地排序：用合并排序法对这两个子序列递归地排序：用合并排序法对这两个子序列递归地排序：用合并排序法对这两个子序列递归地排序;combine combine：合并两个已排序的子序列得到排序结果：合并两个已排序的子序列得到排序结果：合并两个已排序的子序列得到排序结果：合并两个已排序的子序列得到排序结果;【基本思想基本思想基本思想基本思想】：在对子序列排序时：在对子序列排序时：在对子序列排序时：在对子序列排序时,当其长度为当其长度为当其长度为当其长度为1 1时递归结束。单个元素被视时递归结束。单个元素被视时递归结束。单个元素被视时递归结束。单个元素被视为是已排好序的。合并排序的关键步骤在于合并步骤中产生的两个已为是已排好序的。合并排序的关键步骤在于合并步骤中产生的两个已为是已排好序的。合并排序的关键步骤在于合并步骤中产生的两个已为是已排好序的。合并排序的关键步骤在于合并步骤中产生的两个已排好序的子序列排好序的子序列排好序的子序列排好序的子序列 ap.q ap.q 和和和和 aq+1.raq+1.r 将它们合并成一个已排好序的子序列将它们合并成一个已排好序的子序列将它们合并成一个已排好序的子序列将它们合并成一个已排好序的子序列p.rp.r。这一合并过程如果用玩。这一合并过程如果用玩。这一合并过程如果用玩。这一合并过程如果用玩扑克来比喻扑克来比喻扑克来比喻扑克来比喻,就可以看作桌上有两堆牌就可以看作桌上有两堆牌就可以看作桌上有两堆牌就可以看作桌上有两堆牌,每一堆都是排好序的每一堆都是排好序的每一堆都是排好序的每一堆都是排好序的,最小的牌在最上面最小的牌在最上面最小的牌在最上面最小的牌在最上面,我们希望把这两堆牌合并成排好序的一堆加以输出。我们希望把这两堆牌合并成排好序的一堆加以输出。我们希望把这两堆牌合并成排好序的一堆加以输出。我们希望把这两堆牌合并成排好序的一堆加以输出。基本步骤：先取面朝上的两堆牌的顶上两张中较小的一张基本步骤：先取面朝上的两堆牌的顶上两张中较小的一张基本步骤：先取面朝上的两堆牌的顶上两张中较小的一张基本步骤：先取面朝上的两堆牌的顶上两张中较小的一张,将它取出将它取出将它取出将它取出面朝下地放到输出堆中。重复这个步骤直到某一输入堆为空。这时把另一个面朝下地放到输出堆中。重复这个步骤直到某一输入堆为空。这时把另一个面朝下地放到输出堆中。重复这个步骤直到某一输入堆为空。这时把另一个面朝下地放到输出堆中。重复这个步骤直到某一输入堆为空。这时把另一个输入堆中余下的牌面朝下放入即可。输入堆中余下的牌面朝下放入即可。输入堆中余下的牌面朝下放入即可。输入堆中余下的牌面朝下放入即可。第11页，共16页，编辑于2022年，星期五10 4 6 3 8 2 5 710 4 6 3 8 2 5 710 4 6 310 4 6 38 2 5 78 2 5 710 410 46 36 3 10104 4 3 4 6 103 4 6 102 5 8 72 5 8 72 3 4 5 6 7 8 102 3 4 5 6 7 8 10分分分分解解解解合合合合并并并并第12页，共16页，编辑于2022年，星期五void MergeSort(int left,int right)void MergeSort(int left,int right)/对区间对区间对区间对区间left-rightleft-right进行归并排序进行归并排序进行归并排序进行归并排序 if(left=right)return;/if(left=right)return;/只有一个元素只有一个元素只有一个元素只有一个元素 mid=(left+right)/2;/mid=(left+right)/2;/找中间位找中间位找中间位找中间位 MergeSort(left,mid);/MergeSort(left,mid);/对左边归并对左边归并对左边归并对左边归并 MergeSort(mid+1,right);/MergeSort(mid+1,right);/对右边归并对右边归并对右边归并对右边归并 i=left,j=mid+1,p=left;/i=left,j=mid+1,p=left;/合并左右合并左右合并左右合并左右 while(i=mid&j=right)while(i=mid&j=right)if(aiaj)tempp+=ai+;if(aiaj)tempp+=ai+;else tempp+=aj+;else tempp+=aj+;while(i=mid)tempp+=ai+;/while(i=mid)tempp+=ai+;/左边多余左边多余左边多余左边多余 while(j=right)tempp+=aj+;/while(j=right)tempp+=aj+;/右边多余右边多余右边多余右边多余 for(i=left;i=right;i+)ai=tempi;for(i=left;i=right;i+)ai=tempi;核心代码核心代码第13页，共16页，编辑于2022年，星期五应用举例应用举例-快速幂快速幂 问题问题问题问题:计算计算计算计算a an n,其中其中其中其中n n是自然数是自然数是自然数是自然数 朴素算法朴素算法朴素算法朴素算法:每次乘以每次乘以每次乘以每次乘以a,O(n)a,O(n)例题：计算例题：计算例题：计算例题：计算x xn n。分分分分析：如果析：如果析：如果析：如果N N为偶数，则为偶数，则为偶数，则为偶数，则X XN N=（X X2 2）N/2N/2；如果；如果；如果；如果N N为奇数，则为奇数，则为奇数，则为奇数，则X XN N=X=X2P2P*X*X1 1，（，（，（，（2P+1=N2P+1=N）转化成了偶数次方。这样递归地做下去，直）转化成了偶数次方。这样递归地做下去，直）转化成了偶数次方。这样递归地做下去，直）转化成了偶数次方。这样递归地做下去，直到计算到计算到计算到计算X X0 0为止。为止。为止。为止。分治算法分治算法分治算法分治算法:第14页，共16页，编辑于2022年，星期五Description:Description:输入输入输入输入b b，p p，k k的值，求的值，求的值，求的值，求bp%kbp%k的值。其中的值。其中的值。其中的值。其中b b，p p，k*kk*k为长整型为长整型为长整型为长整型数。数。数。数。Input:Input:输入输入输入输入b b，p p，k k。Output:Output:输出输出输出输出bp%kbp%k的值。的值。的值。的值。Sample Input:Sample Input:2 10 9 2 10 9Sample Output:Sample Output:7 7取余运算取余运算第15页，共16页，编辑于2022年，星期五下面先介绍一个原理：下面先介绍一个原理：下面先介绍一个原理：下面先介绍一个原理：a*b%ka*b%k(a%k)*(b%k)%k(a%k)*(b%k)%k。显然有了这个原理，就。显然有了这个原理，就。显然有了这个原理，就。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢么怎样分解最有效呢么怎样分解最有效呢么怎样分解最有效呢?显然对于任何一个自然数显然对于任何一个自然数显然对于任何一个自然数显然对于任何一个自然数P P，有，有，有，有p p2*p/2+p%22*p/2+p%2，如如如如19192*19/22*19/2十十十十19%219%22*9+12*9+1，利用上述原理就可以把，利用上述原理就可以把，利用上述原理就可以把，利用上述原理就可以把b b的的的的1919次方除以次方除以次方除以次方除以k k的余数转换为求的余数转换为求的余数转换为求的余数转换为求b b的的的的9 9次方除以次方除以次方除以次方除以k k的余数，即的余数，即的余数，即的余数，即b19=b(2*9+1)b19=b(2*9+1)b*b9*b9b*b9*b9，再进一步分解下去就不难求得整个问题的解。再进一步分解下去就不难求得整个问题的解。再进一步分解下去就不难求得整个问题的解。再进一步分解下去就不难求得整个问题的解。这是一个典型的分治问题，具体实现的时候是用这是一个典型的分治问题，具体实现的时候是用这是一个典型的分治问题，具体实现的时候是用这是一个典型的分治问题，具体实现的时候是用递推递推递推递推的方法来处理的，的方法来处理的，的方法来处理的，的方法来处理的，如如如如p=19p=19，有，有，有，有19=2*9+119=2*9+1，9=2*4+19=2*4+1，4=2*2+04=2*2+0，2=2*1+02=2*1+0，1 12*0+12*0+1，反过，反过，反过，反过来，我们可以从来，我们可以从来，我们可以从来，我们可以从0 0出发，通过乘以出发，通过乘以出发，通过乘以出发，通过乘以2 2再加上一个再加上一个再加上一个再加上一个0 0或或或或1 1而推出而推出而推出而推出1 1，2 2，4 4，9 9，1919，这样就逐步得到了原来的指数，进而递推出以，这样就逐步得到了原来的指数，进而递推出以，这样就逐步得到了原来的指数，进而递推出以，这样就逐步得到了原来的指数，进而递推出以b b为底，依次以这些数为指为底，依次以这些数为指为底，依次以这些数为指为底，依次以这些数为指数的自然数除以数的自然数除以数的自然数除以数的自然数除以k k的余数。不难看出这里每一次乘以的余数。不难看出这里每一次乘以的余数。不难看出这里每一次乘以的余数。不难看出这里每一次乘以2 2后要加的数就是后要加的数就是后要加的数就是后要加的数就是1919对对对对应的二进制数的各位数字，即应的二进制数的各位数字，即应的二进制数的各位数字，即应的二进制数的各位数字，即1 1，0 0，0 0，1 1，1 1，而，而，而，而1919(10011)2(10011)2，求解的过，求解的过，求解的过，求解的过程也就是将二进制数还原为十进制数的过程。程也就是将二进制数还原为十进制数的过程。程也就是将二进制数还原为十进制数的过程。程也就是将二进制数还原为十进制数的过程。分析分析倍增法倍增法第16页，共16页，编辑于2022年，星期五