2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 分治法二.doc

2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 分治法二课题：分治法目标：知识目标：分治的原理与分治的实现能力目标：分治的原理重点：分治的应用难点：分治的理解板书示意：1） 分治的引入（例29）2） 分治的应用（例30）授课过程：所谓分治法就是将问题分而治之。有将问题一分为二，也有将问题一分为三或一分为N等份。对每一等份分别进行解决后，原问题就可以很快得以解决。因此一个问题能否用分治法解决，关键是看该问题是否能将原问题分成n个规模较小而结构与原问题相似的子问题。递归的解决这些子问题，然后合并其结果就得到原问题的解。当n=2时的分治法又称二分法。使用分治策略的问题常常要借助递归的结构，逐层求解，当问题规模达到某个简单情况时，解容易直接得出，而不必继续分解。其过程大致如下： if 问题不可分then begin 直接求解； 返回问题的解； end else begin 从原问题中划出含1/n运算对象的子问题1； 递归调用分治法过程，求出解1； 从原问题中划出含1/n运算对象的子问题2； 递归调用分治法过程，求出解2； 从原问题中划出含1/n运算对象的子问题n； 递归调用分治法过程，求出解n； 将解1、解2、解n组合成整个问题的解； end;根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？大量实践发现：在用分治法设计算法时，最好是子问题的规模大致相同。通常可以采取二分法，因为这么划分即简单而且均匀。使子问题规模相等的做法是出自平衡子问题的思想，一般情况下总是比子问题规模不等的做法要有效。例29：归并排序某数列存储在对序列A1，A2，An，现采用归并思想进行排序。分析：这里我们采用二分法。先将n个元素分成两个各含或（）个元素的子序列；再用归并排序法对两个子序列递归的排序；最后合并两个已排序的子序列以得到排序结果。在对子序列排序时，当其长度为1时递归结束。单个元素被视为是已经排好的序列。下面我们来分析一下对两个已排好序的子序列APQ和AQ+1R，将它们合并成一个已排好的子序列PR。引入一个辅助过程merge（A，P，Q，R）来完成这一合并工作，其中A是数组，P，Q，R是下标。其方法是：每次选两个子序列中较小的一个元素加入到目标序列中，直到某一个子序列为空，最后把另一子序列中剩下的元素加入到目标序列中。procedure Merge(var A: ListType; P, Q, R: Integer); 将APQ和AQ+1R，合并到序列APR 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 else begin否则右序列的首元素进入合并序列 Ltt := AJ; Inc(J); end; Inc(T);合并后的序列的指针右移 end; A := Lt;合并后的序列赋给A end;下面我们来看看分治过程。利用merge_sort（A，P，R）对数组APR进行排序。若P=R, 则子序列只有一个元素，分解完毕。否则，计算出中间下标Q,将APR分成APQ和AQ+1R。若数组APR的元素个数K=R-P+1为偶数，则两个数组各含K/2个元素；否则APQ含个元素，AQ+1R含个元素。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);继续对左子序列APQ递归排序 Merge_Sort(A, Q + 1, R);继续对左子序列AQ+1R递归排序 Merge(A, P, Q, R)对左子序列和右子序列归并排序 end;end;图25 二分法归并示例图用Merge_sort（A，1，N）便可对整个序列进行归并排序。如果我们自底向上来看这个过程的操作时，算法将两个长度为1的序列合并成排好序的长度为2的序列，继而合并成长度为4的序列，依次类推。随着算法自底向上执行，被合并的排序序列长度逐渐增加，一直进行到将两个长度为n/2的序列合并成最终排好序的长度为n的序列。图25列出了对序列（5，2，4，6，2，3，2，6）进行归并排序的过程。例30：剔除多余括号（CTSC94-1）键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。例如：输入表达式应输出表达式A+b(+c)A+b+c(a*b)+c/(d*e)A*b+a/(d*e)A+b/(c-d)A+b/(c-d)注意输入a+b时不能输出b+a。表达式以字符串输入，长度不超过255，输入不需要判错。所有变量为单个小写字母。只是要求去掉所有多余括号，不要求对表达式简化。分析：对于四则运算表达式，我们分析一下哪些括号可以去掉。设待整理的表达式为（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）我们从最里层嵌套的括号开始，依据上述规律逐步向外进行括号整理，直至最外层的括号保留或去除为止。这个整理过程可以用一个递归过程来实现。图26 括号剔除示例图例如，剔除表达式“（a+b）*f）-（i/j）”中多余的括号。依据上述算法进行整理的过程如图26。最后，自底向上得到整理结果：（a+b）*f-i/j。程序如下：program CTSC94_1; const Inp = input.txt; Outp = output.txt; var Ch: Char; Expr: string;function RightBracket(S:string;I:Byte):Byte;在S串中找到下一个运算符的位置 var Q: Byte;Q用来记录括号层数 begin Q := 1; repeat Inc(I); if SI = ( then Inc(Q) else if SI = ) then Dec(Q); until Q = 0; RightBracket := I; end; function Find(S: string): Byte;找到优先级别最低的运算符的位置 var I, K: Byte; begin I := 1; K:= 0; while I = Length(S) do begin if (SI = +) or (SI = -) then begin Find := I; Exit; end; if (K = 0) and (SI = *) or (SI = /) then K := I; if SI = ( then I := RightBracket(S, I); Inc(I); end; Find := K; end; function DeleteBracket(S: string; var P: Char): string;剔除多余括号，S表示要处理的表达式；P表示表达式中最后一个运算符 var I: Byte; Ch1, Ch2: Char; Left, Right: string; begin if Length(S) = 1 then begin 当表达式中无运算符 DeleteBracket := S; P := ; Exit; end; if (S1 = () and (RightBracket(S, 1) = Length(S) then begin 当表达式最外层有括号 DeleteBracket := DeleteBracket(Copy(S, 2,Length(S)- 2), P); Exit; end; I := Find(S); 找到最低运算符 P := SI; Left := DeleteBracket(Copy(S,1,I- 1), Ch1); 递归处理运算左边 Right := DeleteBracket(Copy(S,I+1,Length(S)-I),Ch2); 递归处理运算右边 if (P in *, /) and (Ch1 in +, -) then Left := ( + Left + ); if (P in *,/)and(Ch2 in +,-) or (P =/)and(Ch2 ) then Right := ( + Right + ); DeleteBracket := Left + P + Right; end; Begin Assign(Input, Inp); Reset(Input); Readln(Expr); Close(Input); Assign(Output, Outp); Rewrite(Output); Writeln(DeleteBracket(Expr, Ch); Close(Output); End.