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