分治策略

分治算法教案长沙市雅礼中学朱全民问题1：找出伪币给你一个装有16枚硬币的袋子。16枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。方法1任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。方法2将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。方法3分析上述三种方法,分别需要比较15次,8次,4次,那么形成比较次数差异的根本原因在哪里?方法1:每枚硬币都至少进行了一次比较,而有一枚硬币进行了15次比较方法2:每一枚硬币只进行了一次比较方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。问题2：金块问题有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。方法1假设袋中有n个金块。可以用函数Max通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。算法如下：max:=a[1];min:=a[1];fori:=2tondo{2n-2次比较}beginifa[i]maxthenmax:=a[i];ifa[i]minthenmin:=a[i];end;可对上述改进少1次max:=a[1];fori:=2tondo{n-1次比较，从n个元素中找到最大的}ifa[i]maxthenbeginmax:=a[i];j:=iend;fori:=j+1tondoa[i-1]:=a[i];{去掉最大的数a[j]}min:=a[1];fori:=2ton-1do{n-2次比较，从剩下的元素中找最小的}ifa[i]maxthenmin:=a[i];找金块的示例图方法2：n≤2，识别出最重和最轻的金块，一次比较就足够了。n＞2，第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA与LA，以此类推，B中最重和最轻的金块分别为HB和LB。第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法。分治过程比较过程分析从图例可以看出，当有8个金块的时候，方法1需要比较15~16次，方法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少用了25％的比较次数。证明令n=2kC(2K)=2C(2K-1)+2=2[2C(2K-2)+2]+2=22+2+22C(2K-2)=22+2+2[2C(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时的分治法又称二分法。其三个步骤如下；1.分解(Divide)：将原问题分成一系列子问题。2.解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。3.合并(combine)；将子问题的结果合并成原问题的解。分治思想问题S问题S问题SS的解问题S1……问题S2问题Si问题Sn……S1的解……S2的解Si的解Sn的解……问题的分解子集解的合并子问题求解分治思想由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n＝6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。分治策略的解题思路if问题不可分thenbegin直接求解；返回问题的解；endelsebegin对原问题进行分治；递归对每一个分治的部分求解归并整个问题，得出全问题的解；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-420输出：-2.002.005.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)0。重复执行如下的过程：(1)若a+0.0001b或f((a+b)/2)=0，则可确定根为(a+b)/2并退出过程；(2)若f(a)*f((a+b)/2)0，则由题目给出的定理可知根在区间(a,(a+b)/2)中，故对区间重复该过程；(3)若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(nlgn)基本策略－把要排序的数据数组（或向量）分成两个子数组这样：在第一个子数组中的数据比一个已知值要小在第二个数组中的数据比那个值要大－技术上来说称为“分块”已知值称为‘枢元素’－一旦我们已经分好块，枢元素将处于它最终的位置－然后我们继续把子数组分为更小的数组，直到剩余部分只有一个元素（递归！）快速排序算法1.选择一个元素作为枢元素。我们使用右边的元素2.在左边和（右-1）元素开始索引3.移除左边的索引直到我们得到一个元素枢元素4.移除右边的索引直到我们得到一个元素枢元素5.若索引不相交，则交换值并重复步骤3和46.若索引相交，则交换枢元素值和左边索引值7.在子数组调用快速排序得到枢元素左右的值实例原始值第一次交换第二次交换分块分块是快速排序的关键步骤:1.在我们的快速排序的说法里，pivot选为要排序的（子）数组的最后一个元素2.使用indexlow从左边扫描（子）数组寻找=pivot的元素3.当我们得到一个元素=pivot时，使用indexhigh从右边扫描寻找=pivot的元素4.若lowhigh，则交换它们的值，然后开始扫描另一对可交换的元素5.若low=high，则完成我们需要做的，交换low和pivot的值，该值位于两个分块之间另一个分块的实例当前pivot值原先的pivot值分块交换pivot值交换较好的快速排序pivot值的选择对快速排序具有决定性的作用。理想的pivot值是子数组的中间值，即是排序数组的中间组成。但是在排序之前我们无法得到中间值。事实证明每个子数组的第一个，中间的和最后一个元素的中间值是上面所说的中间值的很好的替代。它保证分块的每部分至少有两个元素，提供数组至少有4个，但是它的执行方式通常更好。并且没有自然的情况会产生最坏的情况。其他改进：－从递归到叠代的转化，更加有效率。总是先处理最短的子数组（有限的栈大小，pop，push）－当子数组足够小（5-25个元素）使用插入排序，在小问题上它更快快速排序算法(分块)问题5:归并排序已知某数列存储在序列A[1]，A[2]，……，A[n]，现需要采用分治策略对它们进行从大到小（从小到大）排序。例如：52462326排序后为66543222归并排序的整个过程归并过程procedureMerge(varA:ListType;P,Q,R:Integer);{将A[P..Q]和A[Q+1..R]，合并到序列A[P..R]}varI,J,{左右子序列指针}T:Integer;{合并后的序列的指针}Lt:ListType;{暂存合并的序列}beginT:=P;I:=P;J:=Q+1;whileT=Rdobegin{合并未完成}if(I=Q)and((JR)or(A[I]=A[J]))thenbeginLt[t]:=A[I];Inc(I);endelsebegin{否则右序列的首元素进入合并序列}Lt[t]:=A[J];Inc(J);end;Inc(T);{合并后的序列的指针右移}end;A:=Lt;{合并后的序列赋给A}end;二分过程procedureMerge_Sort(varA:ListType;P,R:Integer);varQ:Integer;beginifPRthenbegin{若子序列A中不止一个元素}Q:=(P+R-1)div2;{计算中间下标Q}Merge_Sort(A,P,Q);{继续对左子序列递归排序}Merge_Sort(A,Q+1,R);{继续对右子序列递归排序}Merge(A,P,Q,R){对左右子序列归并}end;end;问题6:求逆序对个数有一实数序列A[1]、A[2]、A[3]、……A[n-1]、A[n]，若ij，并且A[i]A[j]，则称A[i]与A[j]构成了一个逆序对，求数列A中逆序对的个数。n≤10000。例如，52462326，可以组成的逆序对有（52），（54），（52），（53），（52），（42），（43），（42），（62），（63），（62），（32）共：12个分析在看完试题以后，我们不难想到一个非常简单的算法——穷举算法，即对数组中任意的两个元素进行判断，看它们是不是构成“逆序对”，因此这种算法的时间复杂度为O(N2)。时间效率不尽如人意…..问题出现在哪里呢？？转换思维用分治怎么样?首先将这一序列A一分为二，分成两个不同的序列B、C如果求出了B,C的逆序对,那