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