高中信息技術(shù)浙教課標(biāo)版選修1(2004)-選考算法教研-公開課

信息技術(shù)選考專題浙江省杭州第十一中學(xué)劉正陽算法復(fù)習(xí)解法優(yōu)化構(gòu)建模型變式遷移遵從式改良式轉(zhuǎn)化式專題1：二分查找單元設(shè)計思路：思維提升傳統(tǒng)算法在key值未知時分析繁雜，效率偏低；優(yōu)化解法，構(gòu)建二分查找判定樹模型并探究規(guī)律判定樹用于解決該類問題及拓展，提高效率。學(xué)習(xí)變化算法復(fù)習(xí)思維始于疑難板演：二分查找判定樹的構(gòu)建（以數(shù)組元素升序?yàn)槔┘僭O(shè)先有10個數(shù)據(jù)1，2，3，4，5，6，7，8，9，10①把當(dāng)前查找區(qū)間的中間位置上的結(jié)點(diǎn)（即m值）作為根，左子數(shù)組和右子數(shù)組中的結(jié)點(diǎn)分別作為根的左子樹和右子樹。②左右兩堆依次求出m值（2、8），m值保留在原位，然后把兩邊的數(shù)分別放入它的左右兩個子樹（小的放左子樹，大的放右子樹）：根結(jié)點(diǎn)左子樹右子樹構(gòu)建模型③結(jié)點(diǎn)里還有2個及以上的數(shù)的，按照上面規(guī)則求m值，m值保留在原位，其它數(shù)放入它的左右兩個子樹（小的放左子樹，大的放右子樹）：④沒有左子樹的往左畫條線，代表往左查找失敗的范圍；沒有右子樹的往右畫條線，代表往右查找失敗的范圍。原始數(shù)據(jù)1，2，3，4，5，6，7，8，9，10527316489小于1的情況1-2之間2-3之間3-4之間4-5之間5-6之間6-7之間9-10之間7-8之間大于10的情況8-9之間10<>>>>>>>>>><<<<<<<<<第一層第二層第三層第四層演練【例2的二分查找判定樹解法】有如下程序段：i=1:j=10:n=0:flag=trueKey=Val(text1.text)DoWhilei<=jandflag=truem=(i+j)\2ifa(m)=keythenflag=falseelseifkey>a(m)

theni=m+1:n=n-1elsej=m-1:n=n+1endifLoop數(shù)組元素a(1)到a(10)的值依次是：“5,16,22,28,35,43,52,67,78,89”，變量n的值最終是0，則文本框Text1輸入的數(shù)值范圍可能是（

）A.(28,35)B.(43,52)C.[52,67]D.[78,89]二叉查找判定樹的應(yīng)用：B35165222543286778小于5的情況5-16之間16-22之間22-28之間28-35之間35-43之間43-52之間78-89之間52-67之間大于89的情況67-78之間891-1-11-1-1-1-1-1-1-1-111111111繁簡、效率對比小試牛刀1【2017.11浙江】某對分査找算法的VB程序段如下:i=1:j=7:s=""key=Int(Rnd*100)DoWhilei<=jm=(i+j)\2Ifkey=a(m)Thens=s+"M":ExitDo'ExitDo表示退出循環(huán)ElseIfkey<a(m)Thenj=m-1:s=s+"L"

Elsei=m+1:s=s+"R"EndIfLoopText1.Text=sA.RL B.LMR C.RLR D.LRLM1.數(shù)組元素a(1)到a(7)的值為：“24，35，38，41，45，69，78”。若該程序段執(zhí)行后，文本框Text1中顯示的內(nèi)容可能是（）413545693878小于24的數(shù)據(jù)24-35的數(shù)據(jù)24LLLRRRRRRRLLLL35-38的數(shù)據(jù)38-41的數(shù)據(jù)41-45的數(shù)據(jù)45-69的數(shù)據(jù)69-78的數(shù)據(jù)大于78的數(shù)據(jù)C解析：由二叉判定樹可知，A項“RL”已走到數(shù)據(jù)45，是能找到，必為”RLM”B項“LM”即可找到，退出循環(huán)，不可能再有R;D項“LRL”走到了35-38之間找不到的數(shù)，其后

不可能有”M”；C項“RLR”代表輸入的是45-69之間找不到的數(shù)。

變式遷移：問法變化小試牛刀2【2018.6杭州統(tǒng)測】若數(shù)組元素d(1)到d(8)的值依次為“86,75,58,46,20,18,12,5”，查找某Key值的VB程序段如下：n=0:i=1:j=8Key=Val(Text1.Text)DoWhilei<=jm=(i+j)\2

IfKey=d(m)ThenExit

IfKey>d(m)Thenj

=m-1:n=n-1Elsei=m+1:n=n+1

EndIfLoopLabel1.Caption=Str(n)1.當(dāng)輸入不同的Key值，運(yùn)行該程序段后，在標(biāo)簽Label1中

顯示的不同結(jié)果共有（）A．5種

B.6種

C.7種

D.8種二叉查找判定樹的應(yīng)用：D467520185812大于86的數(shù)據(jù)75-86的數(shù)據(jù)861111111-1-1-1-158-75的數(shù)據(jù)46-58的數(shù)據(jù)20-46的數(shù)據(jù)18-20的數(shù)據(jù)12-18的數(shù)據(jù)5-12的數(shù)據(jù)5小于5的數(shù)據(jù)1-1-1-1-1-3到4，

共8種Key=50時，m=3,i=4,j=3Key=10時，m=8,i=8,j=7m=1i=1j=0m=1i=2j=1m=3i=3j=2m=3i=4j=3m=5i=5j=4m=7i=7j=6m=5i=6j=5m=8i=8j=7m=8i=9j=82.請分別寫出當(dāng)Key=50、Key=10情況下的m,i,j值。條件、問法變化拓展【2018.11】數(shù)組a中存儲的是左右交替上升的n個正整數(shù)：a(1) a(2) a(3) …… a(n-2) a(n-1) a(n)3 25 38 …… 55 31 12

依據(jù)對分查找思想，設(shè)計一個在數(shù)組a中查找數(shù)據(jù)key的程序，其VB程序如下，但加框處代碼有錯，請改正。PrivateSubCommand1_Click()Constn=6Dima(1Ton)AsInteger,flagAsBooleanDimiAsInteger,jAsInteger,mAsInteger,keyAsInteger‘讀取一組正整數(shù)，按上述規(guī)則存入數(shù)組a中，代碼略key=Val(Text1.Text)i=1：j=(n+1)\2：flag=FalseDoWhilei<jAndNotflagm=(i+j)\2Ifkey=a(m)Thenflag=TrueElseIfkey<a(m)Thenj=m-1Elsei=m+1EndIfLoopIfNotflagAndj>0Thenm=n–iIfkey=a(m)Thenflag=TrueEndIfIfflagThenText2.Text=Str(m)ElseText2.Text="找不到"EndIfEndSub1.i<=j2.m=n-i+2或m=n-j+1考題試金框架理清拓展【2018.11】數(shù)組a中存儲的是左右交替上升的n個正整數(shù)：a(1) a(2) a(3) …… a(n-2) a(n-1) a(n)3 25 38 …… 55 31 12

依據(jù)對分查找思想，設(shè)計一個在數(shù)組a中查找數(shù)據(jù)key的程序，其VB程序如下，但加框處代碼有錯，請改正。PrivateSubCommand1_Click()Constn=6Dima(1Ton)AsInteger,flagAsBooleanDimiAsInteger,jAsInteger,mAsInteger,keyAsInteger‘讀取一組正整數(shù)，按上述規(guī)則存入數(shù)組a中，代碼略key=Val(Text1.Text)i=1：j=(n+1)\2：flag=FalseDoWhilei<=j

AndNotflagm=(i+j)\2Ifkey=a(m)Thenflag=TrueElseIfkey<a(m)Thenj=m-1Elsei=m+1EndIfLoopIfNotflagAndj>0Thenm=m=n-i+2或m=n-j+1

Ifkey=a(m)Thenflag=TrueEndIfIfflagThenText2.Text=Str(m)ElseText2.Text="找不到"EndIfEndSub以key=31為例子1.第一次m=2，則i=2+1=32.第二次m=3，則j=3-1=2退出循環(huán)，沒有找到3.然后在第二個區(qū)塊中找鏡像部分的那個值，注意當(dāng)前i和j的值考題試金527316489m=1i=1j=0真的找不到m=1i=2j=1還要判斷是否在位置nm=3i=3j=2還要判斷是否在位置n-1m=4i=4j=3還要判斷是否在位置n-2m=4i=5j=4還要判斷是否在位置n-3m=6i=6j=5還要判斷是否在位置n-4m=7i=7j=6還要判斷是否在位置n-5m=10i=10j=9還要判斷是否在位置n-8m=7i=8j=7還要判斷是否在位置n-6m=10i=11j=10還要判斷是否在位置n-9m=9i=9j=8還要判斷是否在位置n-710解析：假設(shè)n=20，對左邊一半進(jìn)行二分查找，畫出查找判定樹，可得出左半查找不到時退出Do

循環(huán)時的m對應(yīng)到右半部分位置，將其賦值給新的m即可。a(1) a(2) a(3) …… a(n-2) a(n-1) a(n)3 25 38 …… 55 31 12原理不清語法不透知識碎片單元設(shè)計思路：意義建構(gòu)思維可視深入理解變式遷移知識碎片領(lǐng)悟內(nèi)化串珠成鏈系統(tǒng)整合專題2：插入排序讓學(xué)生親歷將實(shí)際問題抽象成結(jié)構(gòu)模型；將結(jié)構(gòu)模型分解，主動學(xué)習(xí)，各個擊破；深入理解并內(nèi)化，讓學(xué)習(xí)在課堂真正發(fā)生。實(shí)際問題模型：每次從桌子上拿走一張牌并將它插入到左手中正確的位置意義建構(gòu)：其建構(gòu)的意義是指事物的性質(zhì)，規(guī)律以及事物之間的內(nèi)在聯(lián)系。重要的前提：手里的牌已經(jīng)是排好序的。插入排序問題分解step1.查找位置step2.移位騰出step3.數(shù)據(jù)插入1.從前往后查找位置：a(1)a(2)a(3)a(n)a(n+1)i=1DoWhilekey>=a(i)andi<=n

i=i+1Loopwz=iFori=1ton

ifkey<a(i)thenexitforNextiwz=i2.從后往前查找位置：(約定：若數(shù)據(jù)相同則順接插入)i=nDoWhilekey<=a(i)andi>=1

i=i-1Loopwz=i+1Fori=nto1step-1

ifkey>a(i)thenexitforNextiwz=i+13.二分查找定位:(用于數(shù)據(jù)量大)有重復(fù)數(shù)據(jù)，可用對分并看后一位，或微增量近似替代查找抽象模型：先研究插入一個數(shù)據(jù)：step1.查找位置意義建構(gòu)問題分解2.從定位wz到最后，數(shù)據(jù)逐個移位2.從末位置n到定位wz，數(shù)據(jù)逐個移位 j=wz’wz=6.

Dowhilej<=n

a(j+1)=a(j)

j=j+1Loop“將錯就錯” j=n.

Dowhilej>=wz

a(j+1)=a(j)

j=j-1Loopa(wz)=keystep2.位置騰出（數(shù)據(jù)移位，疑難點(diǎn)）step3.數(shù)據(jù)插入深入理解Key=14Key=14綜合：邊尋址邊移位j=nDowhile

j=j-1loopa(

)=keykey<a(j)andj>=1a(j+1)=a(j)j+1效果：數(shù)據(jù)待插入位置更明確

元素移位賦值原理掌握a(1)3a(2)4a(3)8a(4)9a(5)11a(6)key=61198j6動畫輔助理解推廣：插入多個數(shù)據(jù)排序模塊語句：Fori=2Ton’變量i表示第i個待排序數(shù)據(jù)

key=a(i)

j=i-1

DoWhile

key

<a(j)andj>0

j=j-1

Loop

NextiFori=1Ton

List2.AddItemStr(a(i))Nextia(j+1)=a(j)a(j+1)=key2.輪轉(zhuǎn)有序序列中插入或刪除數(shù)據(jù)數(shù)形結(jié)合變式拓展1.二分查找結(jié)合插入排序（見2019.2溫州卷）專題3“桶”&“統(tǒng)”2.

數(shù)組可理解為存儲數(shù)據(jù)的容器。1.桶數(shù)據(jù)元素序列，用于存儲多個相同類型數(shù)據(jù)的集合（多個“桶”）。數(shù)組元素訪問：數(shù)組名（下標(biāo)）。三步走模型：“洗桶”、“裝桶”、“數(shù)桶”Fori=1Tona(i)=0Nextis=Text1.TextFori=1ToLen(s)c=Mid(s,i,1)

’數(shù)據(jù)處理NextiFori=1TonIfa(i)>0ThenList1.AddItem

’輸出

EndIfNext初始化：“洗桶”處理：“裝桶”輸出：“數(shù)桶”單元設(shè)計思路：實(shí)際問題模型：如某班技術(shù)成績排序(范圍確定，重復(fù)率高)將結(jié)構(gòu)模型分解，串珠成鏈；以算法鞏固語法（如常見函數(shù)，for、Do循環(huán)，字符串，數(shù)組）。模型積累“桶”應(yīng)用1：桶排序

若有11個桶，編號從0～10，每出現(xiàn)一個數(shù)時，就在以該數(shù)編號的桶中放一面小旗子，最后只要按順序數(shù)每個桶中有幾面小旗子，就能得到這幾個整數(shù)的有序排列。例如2號桶中有1個小旗子，表示2出現(xiàn)了一次；3號桶中有1個小旗子，表示3出現(xiàn)了一次；5號桶中有2個小旗子，表示5出現(xiàn)了兩次；8號桶中有1個小旗子，表示8出現(xiàn)了一次，最后只要按桶的編號順序逐次輸出非空的桶的編號即可實(shí)現(xiàn)排序功能，為“2,3,5,5,8”。算法實(shí)現(xiàn)在[0,10]產(chǎn)生5個隨機(jī)整數(shù)的升序排序過程。Dima(4)AsInteger’數(shù)組a存儲產(chǎn)生的隨機(jī)整數(shù)Dimb(10)AsInteger

’數(shù)組b即桶Fori=0To10 '將數(shù)組初始化為0a(i)=0NextiFori=0To4

'產(chǎn)生5個[0,10]的隨機(jī)數(shù)

a(i)=Int(Rnd*10)

①b(a(i))=b(a(i))+1’第a(i)號桶中小旗子數(shù)量加1

List1.AddItemCStr(a(i))

NextiFori=0To10

Forj=1To②

b(i)

List2.AddItemCStr(i)

Nextj

Nexti’內(nèi)循環(huán)是因?yàn)榭赡苣硞€桶有多個重復(fù)數(shù)據(jù)“洗桶”“裝桶”“數(shù)桶”“桶”應(yīng)用2：統(tǒng)計無序數(shù)字出現(xiàn)次數(shù)

例2：在Text1中輸入一串單個數(shù)字（范圍[0,9]），統(tǒng)計并升序輸出出現(xiàn)的數(shù)字和次數(shù)。Fori=0TonIfa(i)>0ThenList1.AddItemStr(i)+"出現(xiàn)："+Str(a(i))+"次"EndIfNextiFori=0Tona(i)=0Nextis=Text1.TextFori=1ToLen(s)

ch=Mid(s,i,1)

a(Val(ch))=a(Val(ch))+1Nexti初始化：“洗桶”輸入并處理：“裝桶”輸出：“數(shù)桶”“桶”應(yīng)用2變式：統(tǒng)計無序字母出現(xiàn)次數(shù)

例3：在Text1中輸入一串大寫字母（范圍[A,Z]），統(tǒng)計并按字典序輸出出現(xiàn)的字母和次數(shù)。Fori=0TonIfa(i)>0Then

List1.AddItemChr(i+97)+"出現(xiàn)："+Str(a(i))+"次"EndIfNextiFori=0Tona(i)=0Nextis=Text1.TextFori=1ToLen(s)

ch=Mid(s,i,1)

a(Asc(ch)-65)=a(Asc(ch)-65)+1Nexti“洗桶”“裝桶”“數(shù)桶”變式1：若統(tǒng)計小寫字母：將65改為97即可變式2：若統(tǒng)計大小寫字母：用分支語句分別“裝桶”與“數(shù)桶”Ifch>="A"Andch<="Z"Then

i=Asc(ch)-65

a(i)=a(i)+1ElseIfc>="a"Andc<="z"Theni=Asc(ch)-97a(n)=a(n)+1EndIf“桶”應(yīng)用3：數(shù)據(jù)存在性分析

例3：在給定區(qū)間[1,500]中尋找完全數(shù)。。。利用數(shù)組下標(biāo)和數(shù)值之間的對應(yīng)關(guān)系，用數(shù)組存儲狀態(tài)--數(shù)值是否出現(xiàn)。完全數(shù)：一個數(shù)恰好等于它的因子（真約數(shù)）之和，如6=1+2+3專題4：字符串研究歷次考題，屬于高頻考點(diǎn)，?？汲Ｐ?；研究學(xué)生常見錯誤，對比學(xué)習(xí)；以算法鞏固語法（如常見函數(shù)mid/len/val/str/asc/chr）；掰取，處理，初始化模型，匹配，插入，刪除，移位、替換等。①得串②量串③取串串處理①逐位處理？②逐串（如單詞）處理？③邊取邊處理？④全取好再逐一處理？如何處理①匹配②插入③刪除④移位（循環(huán)移位）⑤替換（1換1，1換n，n換n）s=Text1.Textn=len(s)Fori=1Ton

ch=Mid(s,i,1)

Nexti’數(shù)據(jù)處理“取”一個fori=1tolen(s)ch=mid(s,i,1)if

條件滿足thent=t+chelse’處理t’初始化t

endifnexti“取”一串程序模塊：Dimt

Asstring“得”串“量”串sum=0s=Text1.Text

Fori=1ToLen(s)

ch=Mid(s,i,1)Ifch>="0"Andc<="9“Then

t=t

*10+Val(ch)

Else

sum=sum+t

t=0EndIfNextiDimsumAsInteger,t

AsInteger,chAsstring

Ifch>="0"Andch<="9"Then

t

=t+chElsesum=sum+

val(t)

t

=""EndIf若：Dimt

Asstring？

疑難一：變量類型不清比較學(xué)習(xí)疑難二：子串長度計算字符匹配長度計算s=Text1.Textn=Len(s)j=0:k=1:i=1DoWhilei<=n‘將所有的單詞都取出來，不論長度

c=Mid(s,i,1)IfNot(c>="a"Andc<="z"Orc>="A"Andc<="Z")Then

w(k)=mid(s,i-j,j)k=k+1j=0Elsej=j+1EndIf

i=i+1Loop子串長度：(i-j+1)子串長度：j畫圖，數(shù)形結(jié)合數(shù)缺形時少直觀形少數(shù)時難入微數(shù)形結(jié)合百般好隔離分家萬事休