2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 分治法二.doc

《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 分治法二.doc》由會員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 分治法二.doc（6頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 分治法二 課題：分治法 目標(biāo)： 知識目標(biāo)：分治的原理與分治的實(shí)現(xiàn) 能力目標(biāo)：分治的原理 重點(diǎn)：分治的應(yīng)用 難點(diǎn)：分治的理解 板書示意： 1） 分治的引入（例29） 2） 分治的應(yīng)用（例30） 授課過程： 所謂分治法就是將問題分而治之。有將問題一分為二，也有將問題一分為三或一分為N等份。對每一等份分別進(jìn)行解決后，原問題就可以很快得以解決。因此一個問題能否用分治法解決，關(guān)鍵是看該問題是否能將原問題分成n個規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題。遞歸的解決這些子問題，然后合并其結(jié)果就得到原問題的解。當(dāng)n=2時的分治法又稱二分法。 使用分治策略的問題常常要借助遞歸的結(jié)構(gòu)，逐層求解，當(dāng)問題規(guī)模達(dá)到某個簡單情況時，解容易直接得出，而不必繼續(xù)分解。其過程大致如下： if 問題不可分then begin 直接求解； 返回問題的解； end else begin 從原問題中劃出含1/n運(yùn)算對象的子問題1； 遞歸調(diào)用分治法過程，求出解1； 從原問題中劃出含1/n運(yùn)算對象的子問題2； 遞歸調(diào)用分治法過程，求出解2； ………… 從原問題中劃出含1/n運(yùn)算對象的子問題n； 遞歸調(diào)用分治法過程，求出解n； 將解1、解2、……、解n組合成整個問題的解； end; 根據(jù)分治法的分割原則，原問題應(yīng)該分為多少個子問題才較適宜？大量實(shí)踐發(fā)現(xiàn)：在用分治法設(shè)計(jì)算法時，最好是子問題的規(guī)模大致相同。通?？梢圆扇《址?，因?yàn)檫@么劃分即簡單而且均勻。使子問題規(guī)模相等的做法是出自平衡子問題的思想，一般情況下總是比子問題規(guī)模不等的做法要有效。 例29：歸并排序 某數(shù)列存儲在對序列A[1]，A[2]，……，A[n]，現(xiàn)采用歸并思想進(jìn)行排序。 分析： 這里我們采用二分法。先將n個元素分成兩個各含或（）個元素的子序列；再用歸并排序法對兩個子序列遞歸的排序；最后合并兩個已排序的子序列以得到排序結(jié)果。在對子序列排序時，當(dāng)其長度為1時遞歸結(jié)束。單個元素被視為是已經(jīng)排好的序列。 下面我們來分析一下對兩個已排好序的子序列A[P．．Q]和A[Q+1．．R]，將它們合并成一個已排好的子序列[P．．R]。 引入一個輔助過程merge（A，P，Q，R）來完成這一合并工作，其中A是數(shù)組，P，Q，R是下標(biāo)。其方法是：每次選兩個子序列中較小的一個元素加入到目標(biāo)序列中，直到某一個子序列為空，最后把另一子序列中剩下的元素加入到目標(biāo)序列中。 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{合并未完成} {若左序列剩有元素并且右序列元素全部合并或 左序列的首元素小于等于右序列的首元素，則左序列的首元素進(jìn)入合并序列} if (I <= Q) and ((J > R) or (A[I] <= A[J])) then begin Lt[t] := A[I]; Inc(I); end else begin {否則右序列的首元素進(jìn)入合并序列} Lt[t] := A[J]; Inc(J); end; Inc(T); {合并后的序列的指針右移} end; A := Lt; {合并后的序列賦給A} end; 下面我們來看看分治過程。利用merge_sort（A，P，R）對數(shù)組A[P．．R]進(jìn)行排序。若P=R, 則子序列只有一個元素，分解完畢。否則，計(jì)算出中間下標(biāo)Q,將A[P．．R]分成A[P．．Q]和A[Q+1．．R]。若數(shù)組A[P．．R]的元素個數(shù)K=R-P+1為偶數(shù)，則兩個數(shù)組各含K/2個元素；否則A[P．．Q]含個元素，A[Q+1．．R]含個元素。 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; {計(jì)算中間下標(biāo)Q} Merge_Sort(A, P, Q); {繼續(xù)對左子序列A[P．．Q]遞歸排序} Merge_Sort(A, Q + 1, R); {繼續(xù)對左子序列A[Q+1．．R]遞歸排序} Merge(A, P, Q, R) {對左子序列和右子序列歸并排序} end; end; 圖25 二分法歸并示例圖 用Merge_sort（A，1，N）便可對整個序列進(jìn)行歸并排序。如果我們自底向上來看這個過程的操作時，算法將兩個長度為1的序列合并成排好序的長度為2的序列，繼而合并成長度為4的序列……，依次類推。隨著算法自底向上執(zhí)行，被合并的排序序列長度逐漸增加，一直進(jìn)行到將兩個長度為n/2的序列合并成最終排好序的長度為n的序列。圖25列出了對序列（5，2，4，6，2，3，2，6）進(jìn)行歸并排序的過程。 例30：剔除多余括號（CTSC94-1） 鍵盤輸入一個含有括號的四則運(yùn)算表達(dá)式，可能含有多余的括號，編程整理該表達(dá)式，去掉所有多余的括號，原表達(dá)式中所有變量和運(yùn)算符相對位置保持不變，并保持與原表達(dá)式等價。 例如： 輸入表達(dá)式 應(yīng)輸出表達(dá)式 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。 表達(dá)式以字符串輸入，長度不超過255，輸入不需要判錯。 所有變量為單個小寫字母。只是要求去掉所有多余括號，不要求對表達(dá)式簡化。 分析： 對于四則運(yùn)算表達(dá)式，我們分析一下哪些括號可以去掉。 設(shè)待整理的表達(dá)式為（s1 op s2）；op為括號內(nèi)優(yōu)先級最低的運(yùn)算符（“+”，“-”或“*”，“/”）； ① 左鄰括號的運(yùn)算符為“/”，則括號必須保留，即…/（s1 op s2）…形式。 ② 左鄰括號的預(yù)算符為“*”或“-”。而op為“+”或“-”，則保留括號，即…*（s1+s2）…或…-（s1+s2）…或…*（s1-s2）…或…-（s1-s2）…。 ③ 右鄰括號的運(yùn)算符為“*”或“/”，而op為“+”或“-”，原式中的op運(yùn)算必須優(yōu)先進(jìn)行，因此括號不去除，即（s1+s2）*… 除上述情況外，可以括號去除，即…s1 op s2…等價于…（s1 op s2）… 我們從最里層嵌套的括號開始，依據(jù)上述規(guī)律逐步向外進(jìn)行括號整理，直至最外層的括號保留或去除為止。這個整理過程可以用一個遞歸過程來實(shí)現(xiàn)。 圖26 括號剔除示例圖 例如，剔除表達(dá)式“（（a+b）*f）-（i/j）”中多余的括號。依據(jù)上述算法進(jìn)行整理的過程如圖26。 最后，自底向上得到整理結(jié)果：（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串中找到下一個運(yùn)算符的位置} var Q: Byte; {Q用來記錄括號層數(shù)} begin Q := 1; repeat Inc(I); if S[I] = ( then Inc(Q) else if S[I] = ) then Dec(Q); until Q = 0; RightBracket := I; end; function Find(S: string): Byte; {找到優(yōu)先級別最低的運(yùn)算符的位置} var I, K: Byte; begin I := 1; K:= 0; while I <= Length(S) do begin if (S[I] = +) or (S[I] = -) then begin Find := I; Exit; end; if (K = 0) and ((S[I] = *) or (S[I] = /)) then K := I; if S[I] = ( then I := RightBracket(S, I); Inc(I); end; Find := K; end; function DeleteBracket(S: string; var P: Char): string; {剔除多余括號，S表示要處理的表達(dá)式；P表示表達(dá)式中最后一個運(yùn)算符} var I: Byte; Ch1, Ch2: Char; Left, Right: string; begin if Length(S) = 1 then begin {當(dāng)表達(dá)式中無運(yùn)算符} DeleteBracket := S; P := ; Exit; end; if (S[1] = () and (RightBracket(S, 1) = Length(S)) then begin {當(dāng)表達(dá)式最外層有括號} DeleteBracket := DeleteBracket(Copy(S, 2,Length(S)- 2), P); Exit; end; I := Find(S); {找到最低運(yùn)算符} P := S[I]; Left := DeleteBracket(Copy(S,1,I- 1), Ch1); {遞歸處理運(yùn)算左邊} Right := DeleteBracket(Copy(S,I+1,Length(S)-I),Ch2); {遞歸處理運(yùn)算右邊} 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.