查找算法課件

第三單元查找算法第三單元查找算法考點(diǎn)與典例考點(diǎn)1順序查找1.查找算法所謂查找就是在指定的數(shù)據(jù)中尋找某一特定的數(shù)據(jù)。查找結(jié)果有兩種:找到(查找成功)和未找到(查找失敗)。2.順序查找的基本思想從第一個(gè)數(shù)據(jù)開(kāi)始,從左往右(或從上到下)將數(shù)據(jù)按順序逐個(gè)與給定的關(guān)鍵字進(jìn)行比較,若某個(gè)數(shù)據(jù)和給定的關(guān)鍵字相等,則查找成功,找到并輸出第一個(gè)與關(guān)鍵字相等的數(shù)據(jù)的位置;反之,查找失敗。若有n個(gè)數(shù),則可能的最多查找次數(shù)為n?？键c(diǎn)與典例考點(diǎn)1順序查找1.查找算法3.順序查找算法基本框架假設(shè):要查找的數(shù)為key,待查找的數(shù)存放在數(shù)組d中。For語(yǔ)句框架:

Fori=1Ton若d(i)=key,則表示找到,做相應(yīng)處理

Nexti若i>n表示未找到DoWhile語(yǔ)句框架:

i=1

DoWhilei<=n若d(i)=key,則表示找到,做相應(yīng)處理

i=i+1

Loop若i>n表示未找到3.順序查找算法基本框架4.順序查找的程序?qū)崿F(xiàn)在n個(gè)數(shù)組元素中依次查找,找到第1個(gè)滿足條件的值,查找即結(jié)束,輸出找到元素所在的位置;若找不到,輸出“未找到”。程序?qū)崿F(xiàn):設(shè):(1)要查找的數(shù)據(jù)是key(在文本框Text1中輸入),查找的數(shù)據(jù)存放在數(shù)組d中。(2)pos為找到數(shù)的位置,pos=0表示未找到。(3)p記錄查找的次數(shù)。key=Val(Text1.Text)

′Val要根據(jù)實(shí)際情況決定是否要添加

p=0

pos=04.順序查找的程序?qū)崿F(xiàn)

find=False

′find=False表示未找到,find=True表示找到

i=1

DoWhilei<=nAndfind=False

′表示還沒(méi)找完并且還未找到,則繼續(xù)查找,notfind也可表示為find=False

p=p+1

Ifkey=d(i)Then

pos=i

find=True

EndIf

i=i+1

Loop

IffindThen′也可表示為Iffind=TrueThen

Text2.Text="在d("+Str(pos)+")中"

Else

Text2.Text="未找到"

EndIffind=False′find=False表示未找到,f【典例1】某查找算法的部分VB代碼如下:t=Falsei=0DoWhilei<7Andt=False

i=i+1

Ifa(i)=keyThent=TrueLoopIft=FalseTheni=0數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次為“3,5,1,5,8,9,5”,當(dāng)變量key值為5時(shí),運(yùn)用該算法處理后,變量i的值是(

)A.0 B.2 C.4 D.7【典例1】某查找算法的部分VB代碼如下:解析:本題主要考查的是順序查找的實(shí)現(xiàn)過(guò)程。本程序的功能是查找數(shù)組中第一個(gè)與目標(biāo)數(shù)據(jù)相等的數(shù),若找到將其在數(shù)組中的位置賦給變量i,結(jié)束查找;若找不到,變量i=0。因?yàn)槟繕?biāo)值key=5,它和數(shù)組中第二個(gè)數(shù)正好相等,因此i=2。

答案:B解析:本題主要考查的是順序查找的實(shí)現(xiàn)過(guò)程。本程序的功能是查找【典例2】(2017·浙江省4月選考)小王編寫(xiě)了一個(gè)實(shí)現(xiàn)文字查找替換功能的VB程序,運(yùn)行界面如圖4-3-1所示。文本框Text1顯示原文內(nèi)容,Text2中輸入查找內(nèi)容,Text3中輸入替換內(nèi)容,單擊“全部替換”按鈕Command1后,Text4顯示查找替換的結(jié)果,Text5中顯示替換的次數(shù),Text6顯示“查找內(nèi)容”在原文中的起始位置?！镜淅?】(2017·浙江省4月選考)小王編寫(xiě)了一個(gè)實(shí)現(xiàn)文實(shí)現(xiàn)上述功能的VB程序如下,但加框處代碼有錯(cuò),請(qǐng)改正。PrivateSubCommand1_Click()

DimsAsString,resuleAsString,posAsString

DimcountAsInteger,iAsInteger

i=1:count=0

resule="":pos=""

DoWhilei<=Len(Text1.Text)

s=Mid(Text1.Text,i,Len(Text2.Text))

Ifs=Text2.TextThen

result=result+Text3.Text

count=count+1

pos=pos+Str(count)′(1)實(shí)現(xiàn)上述功能的VB程序如下,但加框處代碼有錯(cuò),請(qǐng)改正。

i=i+Len(Text2.Text)

Else

result=result+Text2.Text′(2)

i=i+1

EndIf

Loop

Text4.Text=result

Text5.Text=Str(count)

Text6.Text=posEndSubi=i+Len(Text2.Text)解析:本題利用順序查找算法實(shí)現(xiàn)查找替換的功能。語(yǔ)句“Ifs=Text2.TextThen”表示在原文中找到了所要的查找內(nèi)容時(shí)的情況,此時(shí)需要做的是:①將查找內(nèi)容用替換內(nèi)容代替(result=result+Text3.Text);②替換次數(shù)計(jì)數(shù)(count=count+1);③記錄起始位置i(pos=pos+Str(i),添加在字符串pos中);④查找位置從當(dāng)前位置前進(jìn)Len(Text1.Text)個(gè)位置(i=i+Len(Text1.Text))。否則,將當(dāng)前位置上的字符添加到字符串result中,因此(2)處語(yǔ)句修改為result=result+mid(Text1.Text,i,1)。答案:(1)pos+Str(i)

(2)result=result+mid(Text1.Text,i,1)解析:本題利用順序查找算法實(shí)現(xiàn)查找替換的功能。語(yǔ)句“Ifs【典例3】某8位男生的肺活量數(shù)據(jù)放在數(shù)組元素a(1)到a(8)中,其數(shù)據(jù)依次為“3104,3700,3058,3222,3621,3329,4233,4540”。使用順序查找算法查找數(shù)據(jù)3339,則共需查找次數(shù)為(

)A.0 B.1 C.8 D.9解析:本題考查的是順序查找算法的實(shí)現(xiàn)過(guò)程。由于給定的數(shù)列中沒(méi)有數(shù)據(jù)3339,因此需要與數(shù)列中每個(gè)數(shù)進(jìn)行比較,全部比較完后才知道查找失敗,因此共需查找次數(shù)為8次。答案:C【典例3】某8位男生的肺活量數(shù)據(jù)放在數(shù)組元素a(1)到a(8考點(diǎn)2對(duì)分查找1.對(duì)分查找的基本思想在有序的數(shù)據(jù)序列中(一般存放在數(shù)組中),首先把要查找的數(shù)據(jù)與數(shù)組中間位置的元素進(jìn)行比較,如果相等,則查找成功并退出查找;否則,根據(jù)數(shù)組元素的有序性,確定數(shù)據(jù)應(yīng)在數(shù)組的前半部分還是在后半部分查找;在確定了新的查找范圍后,重復(fù)進(jìn)行以上比較,直到找到或未找到為止。重難點(diǎn)剖析①對(duì)分查找的前提是被查找的數(shù)據(jù)序列必須是有序。②“未找到”是指當(dāng)指定范圍內(nèi)的起點(diǎn)大于終點(diǎn)仍未找到該數(shù)據(jù)。考點(diǎn)2對(duì)分查找1.對(duì)分查找的基本思想2.對(duì)分查找算法基本框架說(shuō)明:要查找的數(shù)為key,待查找的數(shù)存放在數(shù)組d中。

i為查找范圍的起點(diǎn),j為查找范圍的終點(diǎn),m為范圍[i,j]的中間位置。

i=1

j=n

DoWhilei<=j計(jì)算中點(diǎn)位置m比較key與d(m),并做相應(yīng)處理

Loop若i>j,則表示未找到2.對(duì)分查找算法基本框架3.對(duì)分查找程序?qū)崿F(xiàn)在n個(gè)數(shù)組元素中依次查找,找到第1個(gè)滿足條件的值,查找就結(jié)束,輸出找到元素所在的位置;若找不到,輸出“未找到”。程序?qū)崿F(xiàn):設(shè)要查找的數(shù)據(jù)是key(在文本框Text1中輸入),查找的數(shù)據(jù)存放在數(shù)組d中。在文本框Text2中輸出查找結(jié)果,若找到輸出“找到!位置為:X”,否則輸出“未找到!”在文本框Text3中輸出共查找的次數(shù)。p表示查找的次數(shù)。核心代碼為(以升序?yàn)槔?:

key=Val(Text1.Text)

′表示要查找的數(shù)

p=0

′表示查找的次數(shù)3.對(duì)分查找程序?qū)崿F(xiàn)

find=False

′查找的結(jié)果,若find=True表示找到,find=False表示未找到

i=1

′查找范圍的起點(diǎn)

j=n

′查找范圍的終點(diǎn)

DoWhilei<=jAndNotfind

′如果還未找完并且未找到

p=p+1

′查找次數(shù)計(jì)數(shù)

m=(i+j)\2

′計(jì)算中點(diǎn)位置m

Ifkey=d(m)Then

′表示找到的情況

find=True

Text2.Text="找到!位置為:"+Str(m)find=False′查找的結(jié)果,若find=T

EndIf

Ifkey>d(m)Then

′表示查找的數(shù)比中間位置上的數(shù)大時(shí)

i=m+1

Else

′表示查找的數(shù)比中間位置上的數(shù)小時(shí)

j=m-1

EndIf

Loop

IfNotfindThenText2.Text="未找到!"

Text3.Text="共查找的次數(shù)為:"+Str(p)重難點(diǎn)剖析計(jì)算中點(diǎn)位置的語(yǔ)句還可以寫(xiě)成:m=Int((i+j)/2)或m=Fix((i+j)/2)。EndIf解析:本題主要考查的是對(duì)分查找算法。在[0,1]區(qū)間內(nèi)查找一個(gè)數(shù),第一次取[0,1]區(qū)間中間值0.5,每次都減少為原來(lái)的1/2,所以答案為D。答案:D

【典例4】已知單調(diào)函數(shù)在[0,1]區(qū)間存在一個(gè)x0,使f(x0)=0。現(xiàn)用對(duì)分查找算法搜索x0的值,開(kāi)始搜索區(qū)間為[0,1],若經(jīng)過(guò)10次對(duì)分查找后還需繼續(xù)搜索,則第11次搜索區(qū)間的長(zhǎng)度為(

)A.1/2 B.1/10 C.1/102 D.1/210解析:本題主要考查的是對(duì)分查找算法。在[0,1]區(qū)間內(nèi)查找一【典例5】(2017·浙江11月選考)某算法的VB程序段如下:i=1:j=7:s=""key=Int(Rnd*100)DoWhilei<=j

m=(i+j)\2

Ifkey=a(m)Then

s=s+"M":ExitDo

′ExitDo表示退出循環(huán)

ElseIfkey<a(m)Then

j=m-1:s=s+"L"

Else

i=m+1:s=s+"R"【典例5】(2017·浙江11月選考)某算法的VB程序段如下

EndIfLoopText1.Text=s數(shù)組元素a(1)到a(7)的值依次為“24,35,38,41,45,69,78”。若該程序段執(zhí)行后,文本框Text1中顯示的內(nèi)容可能是(

)A.RL B.LMR C.RLR D.LRLMC解析:本題主要考查的是對(duì)分查找算法。查找的結(jié)果有成功和不成功兩種,若查找成功,則最后輸出"M",如果查找不成功,則不會(huì)出現(xiàn)"M",因此"M"不可能出現(xiàn)在中間,故B選項(xiàng)錯(cuò)誤。對(duì)n個(gè)數(shù)據(jù)查找,最多查找次數(shù)為log2n+1(向下取整),7個(gè)元素最多查找3次,因此可排除D選項(xiàng)。如果查找失敗,則需要查找3次,即不可能查找2次就結(jié)束,因此A選項(xiàng)也錯(cuò)誤。故答案為C。EndIfC解析:本題主要考查的是對(duì)分查找算法。查找的結(jié)【典例6】(2017·浙江省4月選考)某對(duì)分查找算法的VB程序段如下:Key=Val(Text1.Text)i=1:j=10Text2.Text=""DoWhilei<=j

m=Int((i+j)/2+0.5)

IfKey=a(m)ThenExitDo

′ExitDo表示退出循環(huán)

IfKey<a(m)Thenj=m-1Elsei=m+1

Text2.Text=Text2.Text+Str(a(m))Loop數(shù)組元素a(1)到a(10)的值依次為“8,17,24,30,36,40,55,58,61,66”,文本框Text1中輸入的值是30,執(zhí)行該程序段,文本框Text2中顯示的是(

)A.40

24 B.40

24

36 C.36

24 D.36

17

24【典例6】(2017·浙江省4月選考)某對(duì)分查找算法的VB程解析:本題主要考查對(duì)分查找代碼執(zhí)行過(guò)程。具體查找過(guò)程如表所示:Key=30由此可知,共查找了4次,最后一次滿足Key=a(m),執(zhí)行ExitDo退出循環(huán),其他幾次的a(m)按次序依次顯示在Text2中。答案:B

查找次數(shù)ijm=Int((i+j)/2+0.5)a(m)比較結(jié)果1110640Key<a(m)215324Key>a(m)345536Key<a(m)444430Key=a(m)解析:本題主要考查對(duì)分查找代碼執(zhí)行過(guò)程。具體查找過(guò)程如表所示【典例7】小明編寫(xiě)了一個(gè)查詢學(xué)生的選考組合的VB程序。程序運(yùn)行時(shí),在列表框List1中顯示所有學(xué)生的選考組合信息,在文本框Text1中輸入學(xué)號(hào),單擊“開(kāi)始查詢”按鈕(Command1),就開(kāi)始查找該學(xué)號(hào),如果找到,則在標(biāo)簽Label4中顯示此學(xué)號(hào)對(duì)應(yīng)的學(xué)生姓名和選考組合;如果沒(méi)有找到,則顯示信息“找不到此學(xué)號(hào)!”。程序的運(yùn)行效果如圖4-3-2所示?！镜淅?】小明編寫(xiě)了一個(gè)查詢學(xué)生的選考組合的VB程序。程序運(yùn)說(shuō)明:(1)共有n名學(xué)生,其學(xué)號(hào)、姓名和選考組合信息分別存儲(chǔ)在數(shù)組a,b,c中。(2)數(shù)據(jù)已按學(xué)生學(xué)號(hào)從小到大排列,第i個(gè)學(xué)生的學(xué)號(hào)保存在a(i),對(duì)應(yīng)的姓名保存在b(i),選考組合保存在c(i)。實(shí)現(xiàn)上述功能的VB程序如下,在程序劃線處填入適當(dāng)?shù)拇a,把程序補(bǔ)充完整。DimnAsInteger′考生數(shù)Dima(1000)AsString,b(1000)AsString,c(1000)AsStringPrivateSubForm_Load()

′此過(guò)程用于輸入n個(gè)學(xué)生的學(xué)號(hào)、姓名和選考組合,并分別存儲(chǔ)在數(shù)組a、b、c中

′對(duì)學(xué)生信息按學(xué)號(hào)升序排序′將學(xué)生信息顯示在列表框List1中說(shuō)明:′代碼略EndSubPrivateSubCommand1_Click()

DimxAsString:DimposAsInteger

x=Text1.Text①

Ifpos>0ThenLabel4.Caption=b(pos)+"∶"+c(pos)

ElseLabel4.Caption="找不到此學(xué)號(hào)!"

EndIfEndSubFunctionSearch(KeyAsString)AsInteger′代碼略DimiAsInteger,jAsInteger,mAsInteger

i=1:j=n

DoWhilei<=j

m=Fix((i+j)/2)

IfKey=a(m)Then②

ExitFunction

′退出search函數(shù)ElseIf③

Then

j=m-1

Else

i=m+1

EndIf

Loop

Search=0EndFunctionDimiAsInteger,jAsInteger解析:本題主要考查的是對(duì)分查找算法。程序劃線①處代碼為調(diào)用函數(shù),如果能找到該學(xué)號(hào),則返回該學(xué)號(hào)在數(shù)組a中位置,根據(jù)“Ifpos>0Then”可知,將函數(shù)的返回值保存在變量pos中,因此劃線①處的代碼為pos=Search(x);函數(shù)的函數(shù)值是通過(guò)函數(shù)名來(lái)返回的,劃線②處表示找到的情況,因此將返回該學(xué)號(hào)在數(shù)組a中的位置m,即劃線②處代碼為Search=m;數(shù)據(jù)已按學(xué)號(hào)升序排序,根據(jù)代碼“j=m-1”可知,劃線③處代碼表示學(xué)號(hào)小于a(m)的情況,因此③處代碼為a(m)>Key。答案:①pos=Search(x)②Search=m③a(m)>Key解析:本題主要考查的是對(duì)分查找算法。程序劃線①處代碼為調(diào)用函【典例8】編寫(xiě)VB程序,實(shí)現(xiàn)如下功能:在文本框Text1中輸入一個(gè)整數(shù),單擊“查找刪除”按鈕Command1,采用對(duì)分查找法在數(shù)組A(從小到大排列,并顯示在標(biāo)簽Label1中)中查找該數(shù)。若找到,則從數(shù)組A中刪除該數(shù)(該數(shù)后面的數(shù)組元素都前移一位),并在標(biāo)簽Label2中顯示刪除后的結(jié)果,否則,在標(biāo)簽Label2中顯示“該數(shù)沒(méi)有找到”。程序運(yùn)行效果如圖4-3-3所示?！镜淅?】編寫(xiě)VB程序,實(shí)現(xiàn)如下功能:在文本框Text1中輸實(shí)現(xiàn)上述功能的VB代碼如下,但加框處代碼有錯(cuò),請(qǐng)改正。DimA(1To10)AsInteger′用于保存10個(gè)按從小到大順序排列的整數(shù)Form_Load事件過(guò)程產(chǎn)生10個(gè)整數(shù),按升序保存在數(shù)組A中,并在標(biāo)簽Labe