分治

分治算法教案长沙市雅礼中学朱全民引例：金块问题有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。方法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;例题:归并排序已知某数列存储在序列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;思考题1:求逆序对个数有一实数序列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个思考题2:导线和开关如上图是一个具有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之后，你的程序应从标准输入（standardinput）读入一行。若开关状态能使灯亮，则命令T的回答应是Y;反之，回答应是N。命令C的作用是改变开关的状态（若原来是接通则变为断开;若原来是断开则变为接通）。对C命令的回答是作为一种反馈信号。你的程序可以给出一系列命令，将T命令与C命令以任意顺序混合使用。最后给出命令D，并结束。你的程序给出的命令总数应不大于900。样例StandardOutputStandardInputC3T1T2T3C3C2T2D3133YYNYNYN思考题3：BTP职业网球赛[问题描述]N（N≤65536）—有N头奶牛（N是2P）参加网球淘汰赛。即N头奶牛分成N/2组，每组两头奶牛比赛，决出N/2位胜者；所有胜者继而分成N/4组比赛……直至剩下一头牛是冠军。Answer—现在观众们想知道，哪头奶牛是所有可能成为冠军的牛中排名最靠后的。并要求你列举出一个可能的比赛安排使该奶牛获胜。K（1≤K≤N-1）—比赛既要讲求实力，又要考虑到运气。每头奶牛都有一个BTP排名，恰为1－N。如果两头奶牛的排名相差大于给定整数K，则排名靠前的奶牛总是赢排名靠后的奶牛；否则，双方都有可能获胜。有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-10000至10000之间)，且根与根之差的绝对值=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思考题4:一元三次方程求解思考题5:关押罪犯S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。很多罪犯之间甚至积怨已久，我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c的冲突事件。应如何分配罪犯到两座监狱，才能冲突事件的影响力最小(即最大值最小)？这个最小值是多少？【数据范围】对于30%的数据有N≤15。对于70%的数据有N≤2000，M≤50000。对于100%的数据有N≤20000，M≤100000。样例：prison.inprison.out46351214253423351212283511366182418053412884思考题6:聪明的质监员小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到n逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是：1、给定m个区间[Li，Ri]；2、选出一个参数W；3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值Yi：这批矿产的检验结果Y为各个区间的检验值之和。即：若这批矿产的检验结果与所给标准值S相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W的值，让检验结果尽可能的靠近标准值S，即使得S-Y的绝对值最小。请你帮忙求出这个最小值。miiYY1是矿石编号且jWwRLjvYjjjji,],[,*1ii【数据范围】对于10%的数据，有1≤n，m≤10；对于30%的数据，有1≤n，m≤500；对于50%的数据，有1≤n，m≤5,000；对于70%的数据，有1≤n，m≤10,000；对于100%的数据，有1≤n，m≤200,000，0wi,vi≤106，0S≤1012，1≤Li≤Ri≤n。输入输出5315101525354555152433样例说明:n=5，m=3，S=10当W选4的时候，三个区间上检验值分别为:Y1=2*(5+5)=20Y2=1*5=5Y3=0Y=20+5+0=25,此时与标准值S相差最小为10。