分治算法讲解

分治算法一：基本概念（分而治之）分治就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成 更小的子问题.直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 比如：二分查找，归并排序，快速排序，树的遍历等等任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小， 越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=l 时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，。 而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较犬的问题，有时是相当 困难的。二：基本思想分治设计思想：将一个人的问题，分解成一个个小的，相同类型的问题，然后逐个 击破各个小问题，最后将小问题逐步合并，得到最终的解。（可能会用到递归，犬问题里包 含小问题，找到规律然后解决）分治基本策略：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n 较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问 题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。三：分治使用情况1）该问题的规模缩小到一定的程度就可以容易地解决2）该问题可以分解为相同类型的小问题（前提）3）利用该问题分解出的子问题的解可以合并为该问题的解；（关键）4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。四：基本步骤（1）划分：把问题的实例划分成子问题（2）求解：若是子问题比较简单，就直接解决，否则递归求解子问题（3）合并：合并子问题的解得到原问题的解课前引导：一：分段函数例如：高中数学中的分段函数也是类似分治思想的体现，如看图求y关于 x的表达式。一个分段函数，反映的是x与y的关系，简单來说，就是在R的范 围内将y的表达式表示出來，那么这时候利用分治的思想，将R区间划分为小区 间，然后分别求出各个小区间的表达式，最后合并起來，完成y关于x的表达式 的求解二：大整数乘法123 345 678 * 3 = 370 037 034在这里我们可以这样写：123 * 3 = 369345 * 3 = 1035678 * 3=2034组合在一起是369 1035 2034o对比发现，当使用进制的时候结果变成了 370037034首先他满足：第一条件：分解到一定小规模的时候可以解决第二条件：每个小规模都具有最佳子结构（在变量范围内，可以用來表示）第三条件：每个小问题可以通过合并在一起形成大问题的解第四条件：每个小问题相互独立专题一：分治算法之二分査找思考题：找假币：有一堆个数为32的硬币，和一个天平，己知其中有一个假币，且假币 比真硬币轻，找出这个假币1. 普通方法：两两比较，轻的那个是假币，最多比较16次2. 二分法：将硬币分为两份，假币在轻的那份中，然后继续分，直到 找出假币，最多用5次哪种方法好？课题：二分査找（折半査找）知识目标：理解二分查找算法的概念以及执行过程。 重点：掌握二分查找算法的常规写法以及递归写法。 边界错误造成的问题2. 死循坏3. 溢出I.算法介绍：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好;其缺点是要 求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的 有序列表。II. 思路分析：二分查找的基本思想是：（1）先确定一组顺序排列的数据存储到数组中，输入要查找的数据（2）将数组元素的中值与查找的数据相比较，如呆两者相等，则子函数返回相应的结 果后终止；（3）否则利用中间位置缩小数据查找的范圉。如果中间位置的数组元素人于查找数值,则进一步查找中值之前的数组元素，否则进一步查找中值之后的数组元素。（4）重复上述过程，直到在数组中找到相同的数字。（5）若在数组中找不到这个数据，则显示查找不成功III. 算法框架：按照分治算法三步骤，将二分算法作如下介绍：（1）二分算法代码设计模式：/arr表示要进行二分査找的顺序排列对象数组,low表示数组下标的最小值,high 表示数组下表的最大值，key表示要査找的元素int erfen（int arr,int low.int highjnt key） 如果数组下标的最小值大于最大值则返回结果为-1至主函数；/表明在数组中不存在要查找的元素 确定数组的中间位置mid 若查找的元素等于数组的中间元素，则进行相应的步骤 若查找的元素大于数组（指定范围内）的中间元素则将查找范围缩小至数组（指定范围内）中间元素右边； 若查找的元素小于数组指定范围内的中间元素则将查找范闱缩小至数组（指定范I制内）中间元素左边；例题1：输入一个整数n,然后按升序输入n个整数，将它们存入数组a中，再输入一个数x撚后在数组中查找x,如果找到，输出相应的最小下标，否则，输出Not Found.普通写法：# includeusing namespace std;int main()int i,s100,n;cinn;for(i=0;i si;int x;cinx;for(i=0;i n;i+)if(si=x)coutie ndl; break;if(i=n)coutnNot foundHendl; return 0;二分写法：# includeusing namespace std;void erfen(int a,int n,int key)int low=0,high=n-l,mid; while(low=high)nmide ndl;mid=(low+high)/2; if(amid=key) coutkey) high=mid-l;elseIow=mid+1;if(lowhigh)coutHNot Found! endl;int main()int a100;int n,keyzi;cinn;for(i=0;i ai;cin key;erfen(a,n,key);return 0;二分递归：#include using namespace std;int search(int a,int left,int right,int key)if(leftright)coutNot found!endl;exit(0);elseint middle二(left+right)/2;if (amiddle=key)return middle;else if(keyleft=O;right=n-l;cinx;cout这个数的下标是:search(ajeftzright,x)endl;专题二：分治算法之归并排序归并排序是分治算法的一个非常典型的应用。归并排序原理：归并排序具体工作原理如下(假设序列共有n个元素)：将序列每相邻两个数字进行归并操作(merge),形成floor (n/2)个序列，排序 后每个序列包含两个元素将上述序列再次归并，形成floor (n/4)个序列，每个序列包含四个元素重复步骤2,直到所有元素排序完毕归并操作：归并操作(merge),也叫归并算法，指的是将两个顺序序列合并成一个顺序序列 的方法。如 设有数列6, 202, 100, 301, 38, 8, 1初始状态:6, 202, 100, 301, 38, 8, 1第一次归并后:6,202, 100,301, 8, 38, 1,比较次数:3；第二次归并后:6, 100, 202, 301, 1,8, 38,比较次数：4；第三次归并后：1,6, 8, 3& 100, 202, 301,比较次数:4；总的比较次数为：3+4+4二11；归并基本算法:卩合并例稈工作的例子见下面各图。|2152738TBptr113 24 26Aptr如果数组A含有1. 13、24. 26,数组B含有2. 15、27、38那么该算法进行如下:首174“原血2进“匕较先，比较在1和2之阊进hTTbTw工一枷这样-直进行到26和27进行比较它2被添嗣C中然后】3和15进行比较AprrBP13被添加到C中，接下来比较M和15,i订旳|26AprrBprr1 71 1 13 24 %27 |1 12|13 15 11 11 一TAptrtBptrCpr1 1 13 24 262 IS27 38 |I213 15241厂TTBptrCptrAptr将26添加到C中.数组A已经用完。2152738BptrAptr可2426 27 38|Ap“1J合并两个已排序的表的时间竝然足 索的总数。为了看清这一点，汁亠疋女件的，将数殂B的其余部分拷贝到C中ADptrCptr注意每次比较都體为警进行了 N-1次比较, 输入两个整数，作为两个数组的长度，输入两个按升序排列好的数组，将两个已排序的数组 合并后存放在另一个数组中，且合并后的数组也是有序排列(要求不能合并后再排序)，再 输出合并后的数组。【样例输入】45123456789【样例输出】123456789代码：#in cludeusing namespace std;int main()int m,n,i,j/k=0/a100/b100,c200;cinmn;for(i=0;i ai;for(j=0;jn;j+)cinbj；i=O;j=O;while(im&jn)当数组a和数组b都没有完全赋值到数组c中时if(aibj)如果a数组里的元素比b数组的小ck=ai;/就把数组a的元素赋给数组ci+;k+;且将数组a和数组c的下标都往后移一位else/要是数组b的元素比数组a的元素人时ck=bj;就把数组b的元素赋值到数组c中j+;k+;且将数组b和数组c的下标往后移一位if(i=m)当数组a己经被完全赋值到数组c中while(jn)/当数组b还没有完全赋值ck=bj;此时，只需要把b数组中剩余的数全部赋值到数组c接卞去的位置j+；k+;else/当数组b己经被完全赋值到数组c中while(im)当数组a还没有完全赋值ck=ai;此时，只需要把a数组中剩余的数全部赋值到数组c接下去的位置 i+；k+;for(i=0;im+n;i+)coutci归并函数：所涉及知识过多，目前只需要了解思想【例题三】设有n=2k个运动员要进行网球循坏赛。现要设计一个满足以卜要求的比 赛日程表：(1) 每个选手必须与其他n-1个选手各赛一次；(2) 每个选手一天只能参赛一次；(3) 循坏赛在n-1天内结束请按此要求将比赛口程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处 填入第i个选手在第j天所遇到的选手。其中1in, 1jn-1假设有8位参赛选手，8个 选手的比赛日程表如下图：1323%56722214扣658133心412卩785322876异舁672123*58732143心7385234128心765Q4322【思路】按分治的实现过程，可以先找到上面所示口程表的规律，即对角线相等，那么所要完成 的操作就是对角线填充。实现过程：用一个for循坏输出口程表的第一行for(int i=1;i=N;i+) a1i = iIp2p4a5卩6卩7p8卩(2) 然后定义一个m值，m初始化为1, m用来控制每一次填充表格时i (i表示行)和 j (j表示列)的起始填充位置。(3) 用一个for循环将问题分成几部分，对于k=3, 28,将问题分成3人部分，第一部 分为，根据已经填充的第一行，填写第二行，第二部分为，根据已经填充好的第一部分，填 写第三四行，第三部分为，根据已经填充好的前四行，填写最后四行。for(ints=1 ;s=k;s+) N/=2;(4) 用一个for循坏对中提到的每一部分进行划分for(int t=1 ;t=N;t+)对于第一部分， 将其划分为四个小的单元，即对第二行进行如下划分222同理，对第二部分(即三四行),划分为两部分，第三部分同理。(5) 最后，根据以上for循坏对整体的划分和分治法的思想，进行每一个单元格的填充。 填充原则是：对角线填充for(int i=m+1;i=2*m;i+)/i 控制行for(int j=m+1 ;j=2*m;j+) j 控制列ai0+(t-1)*m*2= ai-m0+(t-1)*m*2-m;/*右下角的值等于左上角的值 7 aij+(t-1)*m*2-m =ai-mg+(t-1)*m*2;/*左下角的值等于右上角的值 */ 实例过程：(1) 由初始化的第一行填充第二行la3a4a5卩58“2u!4p3“6p5p80J(2) 由s控制的第一部分填完。然后是s+,进行第二部分的填充1卩2卩5卩6卩7匸2。36。XX7.3pX、2 二7。X6q432p!8“J66,7e乂2卩34卩6q5。x81c2u屉3u7q5p6a3a!2q8p6i*54卩3p2。1卩