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):分治的理解 板書(shū)示意: 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) 鍵盤(pán)輸入一個(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è)小寫(xiě)字母。只是要求去掉所有多余括號(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.- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 分治法二 2019 2020 年高 信息技術(shù) 全國(guó)青少年 奧林匹克 聯(lián)賽 教案 分治
鏈接地址:http://www.hcyjhs8.com/p-2595525.html