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

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

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