《分治策略朱全民》PPT课件.ppt

分治算法教案,长沙市雅礼中学 朱全民,问题1：找出伪币,给你一个装有1 6枚硬币的袋子。1 6枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。,方法1,任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。,方法2,将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。,方法3,分析,上述三种方法,分别需要比较15次,8次,4次,那么形成比较次数差异的根本原因在哪里?方法1:每枚硬币都至少进行了一次比较,而有一枚硬币进行了15次比较方法2:每一枚硬币只进行了一次比较方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。,问题2：金块问题,有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。,方法1,假设袋中有n 个金块。可以用函数M a x通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。算法如下：max:=a1;min:=a1;for i:=2 to n do 2n-2次比较begin if aimax then max:=ai;if aimin then min:=ai;end;,可对上述改进少1次,max:=a1;for i:=2 to n do n-1次比较，从n个元素中找到最大的if aimax then begin max:=ai;j:=i end;for i:=j+1 to n do ai-1:=ai;去掉最大的数ajmin:=a1;for i:=2 to n-1 do n-2次比较，从剩下的元素中找最小的if aimax then min:=ai;,找金块的示例图,方法2：,n2，识别出最重和最轻的金块，一次比较就足够了。n2，第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n2，则递归地应用分而治之方法。,分治过程,比较过程,分析,从图例可以看出，当有8个金块的时候，方法1需要比较1516次，方法2只需要比较10次,那么形成比较次数差异的根本原因在哪里?其原因在于方法2对金块实行了分组比较。对于N枚金块，我们可以推出比较次数的公式：假设n是2的次幂，c(n)为所需要的比较次数。方法1：c(n)=2n-1方法2：c(n)=2c(n/2)+2。由c(2)=1,使用迭代方法可知c(n)=3n/2-2。在本例中，使用方法2比方法1少用了2 5的比较次数。,证明,令n=2kC(2K)=2C(2K-1)+2=22C(2K-2)+2+2=22+2+22C(2K-2)=22+2+22C(2K-3)+2=23+22+2+23C(2K-3)=2K-1+2K-2+2+2K-1C(2)=2K-1+2K-2+2+2K-1=2K-2+2K-1C(n)=3n/2-2,分治思想,分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。当n=2时的分治法又称二分法。其三个步骤如下；分解(Divide)：将原问题分成一系列子问题。解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。合并(combine)；将子问题的结果合并成原问题的解。,分治思想,分治思想,由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。,分治策略的解题思路,if 问题不可分then begin 直接求解；返回问题的解；end else begin 对原问题进行分治；递归对每一个分治的部分求解 归并整个问题，得出全问题的解；end;,有形如：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,问题3:一元三次方程求解,分析,如果精确到小数点后两位，可用简单的枚举法：将x从-100.00 到100.00（步长0.01）逐一枚举，得到20000个 f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值,分析,A、当已知区间(a,b)内有一个根时，用二分法求根，若区间(a,b)内有根，则必有f(a)f(b)b或f(a+b)/2)=0，则可确定根为(a+b)/2并退出过程；(2)若f(a)*f(a+b)/2)0，则必然有f(a+b)/2)*f(b)0，根在(a+b)/2,b)中，对此区间重复该过程。执行完毕，就可以得到精确到0.0001的根。,思路分析,B、求方程的所有三个实根所有的根的范围都在-100至100之间，且根与根之差的绝对值=1。因此可知：在-100,-99、-99,-98、99，100、100，100这201个区间内，每个区间内至多只能有一个根。即：除区间100，100外，其余区间a,a+1，只有当f(a)=0或f(a)f(a+1)0时，方程在此区间内才有解。若f(a)=0，解即为a；若f(a)f(a+1)0，则可以利用A中所述的二分法迅速出找出解。,问题4:快速排序,最有效的一般目的的排序，O(n lg n)基本策略 把要排序的数据数组（或向量）分成两个子数组这样：在第一个子数组中的数据比一个已知值要小 在第二个数组中的数据比那个值要大 技术上来说称为“分块”已知值称为枢元素 一旦我们已经分好块，枢元素将处于它最终的位置 然后我们继续把子数组分为更小的数组，直到剩余部分只有一个元素（递归！）,快速排序算法,1.选择一个元素作为枢元素。我们使用右边的元素2.在左边和（右-1）元素开始索引3.移除左边的索引直到我们得到一个元素枢元素4.移除右边的索引直到我们得到一个元素枢元素5.若索引不相交，则交换值并重复步骤3和46.若索引相交，则交换枢元素值和左边索引值7.在子数组调用快速排序得到枢元素左右的值,实例,原始值,第一次交换,第二次交换,分块,分块是快速排序的关键步骤:在我们的快速排序的说法里，pivot选为要排序的（子）数组的最后一个元素使用index low从左边扫描（子）数组寻找=pivot的元素当我们得到一个元素=pivot时，使用index high从右边扫描寻找=high，则完成我们需要做的，交换low和pivot的值，该值位于两个分块之间,另一个分块的实例,当前pivot值,原先的pivot值,分块交换,pivot值交换,较好的快速排序,pivot值的选择对快速排序具有决定性的作用。理想的pivot值是子数组的中间值，即是排序数组的中间组成。但是在排序之前我们无法得到中间值。事实证明每个子数组的第一个，中间的和最后一个元素的中间值是上面所说的中间值的很好的替代。它保证分块的每部分至少有两个元素，提供数组至少有4个，但是它的执行方式通常更好。并且没有自然的情况会产生最坏的情况。其他改进：从递归到叠代的转化，更加有效率。总是先处理最短的子数组（有限的栈大小，pop，push）当子数组足够小（5-25个元素）使用插入排序，在小问题上它更快,快速排序算法(分块),问题5:归并排序,已知某数列存储在序列A1，A2，An，现需要采用分治策略对它们进行从大到小（从小到大）排序。例如：5 2 4 6 2 3 2 6排序后为 6 6 5 4 3 2 2 2,归并排序的整个过程,归并过程,procedure Merge(var A:ListType;P,Q,R:Integer);将AP.Q和AQ+1.R，合并到序列AP.R var I,J,左右子序列指针 T:Integer;合并后的序列的指针 Lt:ListType;暂存合并的序列 begin T:=P;I:=P;J:=Q+1;while T R)or(AI=AJ)then begin Ltt:=AI;Inc(I);end else begin否则右序列的首元素进入合并序列 Ltt:=AJ;Inc(J);end;Inc(T);合并后的序列的指针右移 end;A:=Lt;合并后的序列赋给A end;,二分过程,procedure Merge_Sort(var A:ListType;P,R:Integer);var Q:Integer;begin if P R then begin 若子序列A中不止一个元素 Q:=(P+R-1)div 2;计算中间下标Q Merge_Sort(A,P,Q);继续对左子序列递归排序 Merge_Sort(A,Q+1,R);继续对右子序列递归排序 Merge(A,P,Q,R)对左右子序列归并 end;end;,问题6:求逆序对个数,有一实数序列A1、A2、A3、An-1、An，若iAj，则称Ai与Aj构成了一个逆序对，求数列A中逆序对的个数。n10000。例如，5 2 4 6 2 3 2 6，可以组成的逆序对有（5 2），（5 4），（5 2），（5 3），（5 2），（4 2），（4 3），（4 2），（6 2），（6 3），（6 2），（3 2）共：12个,分析,在看完试题以后，我们不难想到一个非常简单的算法穷举算法，即对数组中任意的两个元素进行判断，看它们是不是构成“逆序对”，因此这种算法的时间复杂度为O(N2)。时间效率不尽如人意.问题出现在哪里呢？,转换思维,用分治怎么样?首先将这一序列A一分为二，分成两个不同的序列B、C如果求出了B,C的逆序对,那么可由B,C求出A的逆序对.如何来统计序列B和序列C之间的“逆序对”呢？如果还按照穷举的思想来统计的话，那么我们采用分治法就没有什么意义!,提示,在递归的求解B、C两个序列中的逆序对的个数以后，如果对B、C两个序列当中的元素进行排序的话，要统计B、C两个序列之间的“逆序对”是非常容易的.如图排序前排序后,在B数组当中，首先，B中的6，5，4都与C数组当中的3，2，2都构成了“逆序对”，而2不会构成逆序对，因此B、C两个数组之间构成的逆序对的个数为3+3+3=9。,结论,由于B、C两个数组已经进行了排序，因此可以设置两个指针进行操作，有效的统计B、C两个数组之间的“逆序对”的个数。而且这一统计步骤是能够在线性时间内完成的。考虑到我们设计的二分模型本身是递归定义的，所以可以将我们所建立的二分模型完全与归并排序联系起来。因为排序的过程是可以在递归求解子问题时就能够完成的，算法的时间复杂度就降到了O(nlogn)。在这里，虽然对B、C两个序列当中的元素进行了排序，使得序列A当中某一部分元素的顺序被打乱了，但由于求解过程是递归定义的，在排序之前B、C两个序列各自其中的元素之间的“逆序对”个数已经被统计过了，并且排不排序对统计B、C两个数组之间的“逆序对”的个数不会产生影响。所以这个排序过程对整个问题的求解的正确性是没有任何影响的。,总结归纳,分治是一种解题的策略，它的基本思想是：“如果整个问题比较复杂，可以将问题分化，各个击破。”分治包含“分”和“治”两层含义，如何分，分后如何“治”成为解决问题的关键所在不是所有的问题都可以采用分治，只有那些能将问题分成与原问题类似的子问题，并且归并后符合原问题的性质的问题，才能进行分治分治可进行二分，三分等等，具体怎么分，需看问题的性质和分治后的效果。只有深刻地领会分治的思想，认真分析分治后可能产生的预期效率，才能灵活地运用分治思想解决实际问题。,问题7：剔除多余括号,输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。表达式以字符串输入，长度不超过255，输入不需要判错。所有变量为单个小写字母。只是要求去掉所有多余括号，不要求对表达式简化。样例:,分析,对于四则运算表达式，我们分析一下哪些括号可以去掉。设待整理的表达式为（s1 op s2）；op为括号内优先级最低的运算符（“+”，“-”或“*”，“/”）；左邻括号的运算符为“/”，则括号必须保留，即/（s1 op s2）形式。左邻括号的预算符为“*”或“-”。而op为“+”或“-”，则保留括号，即*（s1+s2）或-（s1+s2）或*（s1-s2）或-（s1-s2）右邻括号的运算符为“*”或“/”，而op为“+”或“-”，原式中的op运算必须优先进行，因此括号不去除，即（s1+s2）*除上述情况外，可以括号去除，即 s1 op s2 等价于（s1 op s2）我们从最里层嵌套的括号开始，依据上述规律逐步向外进行括号整理，直至最外层的括号保留或去除为止。这个整理过程可以用一个递归过程来实现。,剔除“(a+b)*f)-(i/j)”中多余的括号,问题8：导线和开关,如上图是一个具有3根导线的电缆把A区和B区连接起来。在A区3根导线标以1，2，3;在B区导线1和被连到开关3，导线2连到开关1。一般说来，电缆含(1 90)根导线，在A区标以1,2,m。在B 区有个开关，标为1，2，。每一根导线都被严格地连到这些开关中的某一个上;每一个开关上可以连有0根或多根导线。,问题描述,测量你的程序应作某些测量来确定，导线和开关怎样连。每个开关或处于接通或处于断开状态，开关的初始状态为断开。我们可用一个探头P在A区进行测试:如果探头点到某根导线上，当且仅当该导线连到处接通状态的开关时，灯L才会点亮。你的程序从标准输入读入一行以得到数字;然后可以通过向标准输出写入一行以发出命令(共3种命令)。每种命令的开头是一个大写字母:测试导线命令T:T后面跟一个导线标号;改变开关状态命令C:C后面跟一个开关标号;完成命令D:D后面跟的是一个表列（LIST），该表列中的第个元素代表与导线相连的开关号。在命令T和C之后，你的程序应从标准输入（standard input）读入一行。若开关状态能使灯亮，则命令T的回答应是Y;反之，回答应是N。命令C的作用是改变开关的状态（若原来是接通则变为断开;若原来是断开则变为接通）。对C命令的回答是作为一种反馈信号。你的程序可以给出一系列命令，将T命令与C命令以任意顺序混合使用。最后给出命令D，并结束。你的程序给出的命令总数应不大于900。,样例,分析,为了使导线和开关的连接工作有规律地进行，我们不妨采用二分法。1.分解设当前待接的开关为head.tail,初始时为1.m,则左区间head.(head+tail-1)/2,开关集合为p1=1.m右区间(head+tail-1)/2+1.tail,开关集合为p2=导线的连接状态state=(0,1)，分别表示断开和连接对区间进行检测，对p1中的每根导线发出T命令，若开关状态为闭合，且回答N,或者开关状态为断开，且回答Y,则移到p22.递归过程check(p1,左区间,1-state)check(p2,右区间,state)3.合并当区间近近剩下一个开关(head=tail)且与之相连的导线集合p1非空，则p1中所有的导线与head相连,并使得ANSi=head,i属于p1,算法框架,Procedure check(p1,head,tail,state);Begin if p1 then if head=tail then begin 计算左区间p1；通过c命令和用户应答，将左区间开关状态取反；右区间p2=；对p1中的每根导线发出T命令，若开关状态为闭合，且回答N,或者开关状态为断开，且回答Y,则移到p2；end;i:=trunc(head+tail)/2);check(p1,head,i,state);check(p2,i+1,tail,state);End;,