分治策略ppt课件

1、分治算法教案长沙市雅礼中学 朱全民问题1：找出伪币给他一个装有1 6枚硬币的袋子。1 6枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。他的义务是找出这枚伪造的硬币。为了协助他完成这一义务，将提供一台可用来比较两组硬币分量的仪器，比如天平。利用这台仪器，可以知道两组硬币的分量能否一样。 方法1恣意取1枚硬币，与其他硬币进展比较，假设发现轻者，这那枚为伪币。最多能够有15次比较。 方法2将硬币分为8组，每组2个，每组比较一次，假设发现轻的，那么为伪币。最多能够有8次比较。 方法3分析上述三种方法,分别需求比较15次,8次,4次,那么构成比较次数差别的根本缘由在哪里?方法1:每枚硬币

2、都至少进展了一次比较,而有一枚硬币进展了15次比较方法2:每一枚硬币只进展了一次比较方法3:将硬币分为两组后一次比较可以将硬币的范围减少到了原来的一半,这样充分地利用了只需1枚伪币的根本性质。问题2：金块问题有一个老板有一袋金块。每个月将有两名雇员会因其优良的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块参与袋中，否那么第一名雇员所得到的金块总是比第二名雇员所得到的金块重。假设有新的金块周期性的参与袋中，那么每个月都必需找出最轻和最重的金块。假设有一台比较分量的仪器，我们希望用最少的比较次数找出最轻和最重的金

3、块。方法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 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 a

4、imax 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次,那么构成比较次数差别的根本缘由在哪里?其缘由在于方法

5、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)=

6、3n/2 -2分治思想分治(divide-and-conquer)就是“分而治之的意思，其本质就是将原问题分成n个规模较小而构造与原问题类似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。当n=2时的分治法又称二分法。其三个步骤如下；分解(Divide)：将原问题分成一系列子问题。处理(Conquer)：递归地解各子问题。假设子问题足够小，那么可直接求解。合并(combine)；将子问题的结果合并成原问题的解。 分治思想问题S问题S问题SS的解问题S1问题S2问题Si问题SnS1的解S2的解Si的解Sn的解问题的分解子集解的合并子问题求解分治思想由分治法所得到的子问题与原问题

7、具有一样的类型。假设得到的子问题相对来说还太大，那么可反复运用分治战略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高，关键在于如何分割？普通地，出于一种平衡原那么，总是把大问题分成K个规模尽能够相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n6时，等分定量成两个规模为3的子表L1和L2不是最正确分割。分治战略的解题思绪 if 问题不可分then begin 直接求解； 前往问题的解；end else begin 对原问题进展分治； 递归对每一个分治的部分求解 归并整个问题，得出全问题的解；end;有形

8、如：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.0

9、0步长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)=1。因此可知：在-100,-99、-99,-98、99，100

10、、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)枢元素4. 移除右边的索引直到我们得到一个元素=pivot的元素当我们得到一个元素=pivot时，运用index high从右边扫描寻觅=pivot的元素假设low=high，那么完成我们需求做的，交换low和pivot的值，该值位于两个分块之间另一个分块的实例当前pivot值原先的pivot值分块交换pivot值交换较好的快速排序pivot值的选择对快速排序具有决

11、议性的作用。 理想的pivot值是子数组的中间值，即是排序数组的中间组成。但是在排序之前我们无法得到中间值。 现实证明每个子数组的第一个，中间的和最后一个元素的中间值是上面所说的中间值的很好的替代。它保证分块的每部分至少有两个元素，提供数组至少有4个，但是它的执行方式通常更好。并且没有自然的情况会产生最坏的情况。其他改良： 从递归到叠代的转化，更加有效率。总是先处置最短的子数组有限的栈大小，pop，push 当子数组足够小5-25个元素运用插入排序，在小问题上它更快快速排序算法(分块)问题5: 归并排序知某数列存储在序列A1，A2，An，现需求采用分治战略对它们进展从大到小从小到大排序。例如：

12、 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 do begin合并未完成 if (I R) or (AI = AJ) then begin Ltt := AI; Inc(I); end

13、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); 继

14、续对右子序列递归排序 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)。 时间效率不尽如人意.问题

15、出如今哪里呢？ 转换思想用分治怎样样?首先将这一序列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两个数组曾经进

16、展了排序，因此可以设置两个指针进展操作，有效的统计B、C两个数组之间的“逆序对的个数。而且这一统计步骤是可以在线性时间内完成的。思索到我们设计的二分模型本身是递归定义的，所以可以将我们所建立的二分模型完全与归并排序联络起来。由于排序的过程是可以在递归求解子问题时就可以完成的，算法的时间复杂度就降到了O(nlogn)。在这里，虽然对B、C两个序列当中的元素进展了排序，使得序列A当中某一部分元素的顺序被打乱了，但由于求解过程是递归定义的，在排序之前B、C两个序列各自其中的元素之间的“逆序对个数曾经被统计过了，并且排不排序对统计B、C两个数组之间的“逆序对的个数不会产生影响。所以这个排序过程对整个问

17、题的求解的正确性是没有任何影响的。总结归纳分治是一种解题的战略，它的根本思想是：“假设整个问题比较复杂，可以将问题分化，各个击破。分治包含“分和“治两层含义，如何分，分后如何“治成为处理问题的关键所在不是一切的问题都可以采用分治，只需那些能将问题分成与原问题类似的子问题，并且归并后符合原问题的性质的问题，才干进展分治分治可进展二分，三分等等，详细怎样分，需看问题的性质和分治后的效果。只需深化地领会分治的思想，仔细分析分治后能够产生的预期效率，才干灵敏地运用分治思想处理实践问题。思索题1: 剔除多余括号 输入一个含有括号的四那么运算表达式，能够含有多余的括号，编程整理该表达式，去掉一切多余的括号

18、，原表达式中一切变量和运算符相对位置坚持不变，并坚持与原表达式等价。表达式以字符串输入，长度不超越255，输入不需求判错。一切变量为单个小写字母。只是要求去掉一切多余括号，不要求对表达式简化。样例:输入表达式应输出表达式a+b(+c)a+b+c(a*b)+c/(d*e)a*b+a/(d*e)a+b/(c-d)a+b/(c-d)分析对于四那么运算表达式，我们分析一下哪些括号可以去掉。设待整理的表达式为s1 op s2；op为括号内优先级最低的运算符“+，“-或“*，“/；左邻括号的运算符为“/，那么括号必需保管，即 /s1 op s2 方式。左邻括号的预算符为“*或“-。而op为“+或“-，那么

19、保管括号，即*s1+s2 或 -s1+s2 或 *s1-s2 或 -s1-s2右邻括号的运算符为“*或“/，而op为“+或“-，原式中的op运算必需优先进展，因此括号不去除，即s1+s2* 除上述情况外，可以括号去除，即 s1 op s2 等价于s1 op s2我们从最里层嵌套的括号开场，根据上述规律逐渐向外进展括号整理，直至最外层的括号保管或去除为止。这个整理过程可以用一个递归过程来实现。剔除“(a+b)*f)-(i/j)中多余的括号 思索题2:导线和开关如上图是一个具有3根导线的电缆把A区和B区衔接起来。在A区3根导线标以1，2，3;在B区导线1和被连到开关3，导线2连到开关1。 普通说来

20、，电缆含(1 90)根导线，在A区标以1,2,m。在B 区有个开关，标为1，2， ，。每一根导线都被严厉地连到这些开关中的某一个上; 每一个开关上可以连有0根或多根导线。问题描画丈量他的程序应作某些丈量来确定，导线和开关怎样连。 每个开关或处于接通或处于断开形状，开关的初始形状为断开。我们可用一个探头P在A区进展测试:假设探头点到某根导线上，当且仅当该导线连四处接通形状的开关时，灯L才会点亮。他的程序从规范输入读入一行以得到数字;然后可以经过向规范输出写入一行以发出命令(共3种命令)。每种命令的开头是一个大写字母:测试导线命令T:T后面跟一个导线标号;改动开关形状命令C:C后面跟一个开关标号;

21、完成命令D:D后面跟的是一个表列LIST，该表列中的第个元素代表与导线相连的开关号。在命令T和C之后，他的程序应从规范输入standard input读入一行。 假设开关形状能使灯亮，那么命令T的回答应是Y;反之，回答应是N。命令C的作用是改动开关的形状假设原来是接通那么变为断开;假设原来是断开那么变为接通。对C命令的回答是作为一种反响信号。他的程序可以给出一系列命令，将T命令与C命令以恣意顺序混合运用。最后给出命令D，并终了。他的程序给出的命令总数应不大于900。样例Standard OutputStandard InputC 3 T 1 T 2 T 3 C 3 C 2 T 2 D 3 1

22、33YYNYNYN分析为了使导线和开关的衔接任务有规律地进展，我们无妨采用二分法。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,