第三章算法與程序?qū)崿F(xiàn)5課件-高中信息技術(shù)浙教版必修1

算法與程序設(shè)計(jì)——方衛(wèi)龍對(duì)分查找代碼（標(biāo)準(zhǔn)代碼）i=1:j=n:s=0DoWhilei<=jm=(i+j)\2Ifa(m)=keyThens=m:ExitDoElseIfkey<a(m)Thenj=m–1Elsei=m+1EndIfLoop

左邊程序?qū)崿F(xiàn)在升序數(shù)組a(1)…a(n)中查找值等于key的元素，將其下標(biāo)存儲(chǔ)在s中。如果沒有找到則s值為0，如果找到，則s存儲(chǔ)對(duì)應(yīng)元素的下標(biāo)。

對(duì)分查找前提是數(shù)組有序，對(duì)n個(gè)數(shù)據(jù)查找，最多查找次數(shù)為L(zhǎng)og2n+1（向下取整）。

例如在有序數(shù)組a(1)…a(10000)中查找某個(gè)值，最多需要查找Log210000+1，即14次。用一個(gè)行IF和一個(gè)塊IF語句實(shí)現(xiàn)i=1:j=n:s=0DoWhilei<=jm=(i+j)\2Ifa(m)=keyThens=m:ExitDoIfkey<a(m)Thenj=m–1Elsei=m+1EndIfLoop三個(gè)行If語句實(shí)現(xiàn)i=1:j=n:s=0DoWhilei<=jm=(i+j)\2Ifa(m)=keyThens=m:ExitDoIfkey<a(m)Thenj=m–1Ifkey<a(m)Theni=m+1EndIfLoop九、對(duì)分查找（二分法查找）例如在一有序序列:12,14,18,25,36,39,42,49,51,53,56,62,65存儲(chǔ)在數(shù)組a(1)到a(13)中查找特定的關(guān)鍵詞Key。九、對(duì)分查找（二分法查找）12141825363942495153566265ij假設(shè)Key=36第一次：m=(i+j)\2=(1+13)\2=7a(m)>key(j=7-1=6:i=1)第二次：m=(i+j)\2=(1+6)\2=3a(m)<key(i=3+1=4:j=6)第三次：m=(i+j)\2=(4+6)\2=5a(m)=key(找到了）m①j=m-1m②i=m+1m③假設(shè)Key=62第一次：m=(i+j)\2=(1+13)\2=7a(m)<key(i=7+1=8:j=13)第二次：m=(i+j)\2=(8+13)\2=10a(m)<key(i=10+1=11:j=13)第三次：m=(i+j)\2=(11+13)\2=12a(m)=key(找到了）m②i=m+1m③i=m+11.數(shù)組變量d(1)到d(8)的值仿效為97、86、79、68、56、41、33、13，用“標(biāo)準(zhǔn)”對(duì)分查找算法查找“13”的過程中，依次被訪問到的數(shù)據(jù)是（）A.68、13B.68、41、13C.56、41、33、13D.68、41、33、132.某數(shù)組的6個(gè)元素依次為“27、32、57、78、80、90”。若對(duì)該數(shù)組進(jìn)行順序查找，其平均查找次數(shù)為（1+2+3+4+5+6）/6=7/2；若對(duì)該數(shù)組進(jìn)行對(duì)分查找，其平均查找次數(shù)為（）A.7/2B.1/9C.5/2D.23.某校校園一卡通系統(tǒng)有4096條記錄信息（已經(jīng)索引排序），假設(shè)從中取出一條記錄并與待查找項(xiàng)進(jìn)行比較所花時(shí)間為8毫秒，則用對(duì)分法在該系統(tǒng)中查找一條指定記錄最多花費(fèi)的時(shí)間約為（）A.80毫秒B.104毫秒C.160毫秒D.240毫秒4.某對(duì)分查找算法的VB程序如下：i=1:j=8:c=0DoWhilei<=jc=c+1m=Fix(i+j)/2)Ifkey=b(m)ThenExitDoIfkey<b(m)Thenj=m–1Elsei=m+1Loop數(shù)組元素b(1)到b(8)的值依次為“22，32，39，48，71，82，96，106”。若該程序段運(yùn)行結(jié)束后，c的值為2，則key的值是（）A.48或32B.48或96C.32或82D.82或965.有以下VB程序段：i=1:j=10:x=18DoWhilei<=jm=int((i+j)/2)Ifx=f(m)ThenExitDoIfx<f(m)Thenj=m-1Elsei=m+1Loopf(1)到f(10)的值依次為：2，7，8，10，12，13，16，18，19，20該段程序運(yùn)行后,下列表達(dá)式正確的是（）A.i=m+1B.j=m-1C.j>m+1D.i>m-1九、對(duì)分查找（二分法查找）DBBCC6.某對(duì)分查找算法的VB程序如下：C=0:i=1:j=8:f=FalseKey=Val(Text1.Text)DoWhilei<=jAndNotfm=Fix((i+j)/2+0.5)c=c+1Ifkey=d(m)Thenf=TrueElseifkey>d(m)Thenj=m-1Elsei=m+1EndifLoop數(shù)組元素d(1)到d(8)的值依次為“97,79,68,48,35,23,18,10”,若運(yùn)行該程序段后，C的值為2，則Text1中輸入的值是（）

A.68或18B.68或23C.79或23D.79或187.某對(duì)分查找算法的VB程序如下：n=0:i=1:j=6:f=FalseKey=Val(Text1.Text)DoWhilei<=jAndNotfm=(i+j+1)\2n=n+1IFKey=d(m)Thenf=TrueElseIfKey>d(m)Thenj=m-1Elsei=M+1EndifLoopa(1)到a(6)的值依次為“87，72，53，41，18”,若該程序段運(yùn)行結(jié)果后，n的值為2，則key的值是（）A.87或29B.72或18C.72或29D.53或188.某對(duì)分查找算法的VB程序如下：i=1:j=7:n=0:f=FalseKey=val(Text1.Text)DoWhilei<=jAndf=Falsen=n+1m=Fix((i+j)/2)Ifkey=d(m)Thenf=TrueIFKey<d(m)Thenj=m-1Elsei=m+1Loop元素?cái)?shù)組a(1)到a(7)的值依次為:”10,20,30,40,50,60”,文本框Text1中輸入35后運(yùn)行程序段，運(yùn)行結(jié)束后下列說法正確的是（）A.變量f和True

B.變量i值4

C.變量m值是3.5D.變量n值4

9.某對(duì)分查找算法的VB程序如下：Key=Val(Text1.Text)i=1:j=10:flag=FalseDoWhilei<=jandflag=Falsem=Fix((i+j)/2)Ifa(m)=KeyThenflag=TrueIfKey>a(m)Thenj=m-1Elsei=m+1Loop元素?cái)?shù)組a(1)到a(10)的值依次為:”95,82,76,70,68,50,41,9,3,1”,文本框Text1中輸入的值是32，運(yùn)行程序段后，以下變更的值正確的是（）A.flag=TrueB.m=8C.i=8D.j=8ABBC九、對(duì)分查找（二分法查找）10.有10個(gè)數(shù)據(jù)：83,80,66,46,44,36,21,16,15,12依次存放在數(shù)組元素d(1)到d(10)中，部分VB程序段如下所示：Key=Val(Text1.Text)i=1:j=10:Text2.Text=“”DoWhilei<=jm=(i+j+1)\2c=c+1Ifkey=a(m)ThenExitDoIfkey>a(m)Thenj=m-1Elsei=m+1Text2.Text=Text2.Text+Str(a(m))Loop文本框Text1中輸入80,執(zhí)行程序段,文本框Text2中顯示的是(

)A.3666B.4480C.3645D.446611.某對(duì)分查找算法的VB程序如下：n=0:i=1:j=6:Key=Val(Text1.Text)DoWhilei<=jm=(i+j+1)\2n=n+1Ifkey=a(m)ThenExitDoIfkey>a(m)Thenj=m-1Elsei=m+1LoopIfi<=jThens=Str(m-n)Elses=Str(n)a(1)到a(6)的值依次為“88，77，53，47，39,28”,輸入某個(gè)key值后，運(yùn)行程序段后，變量s的值為1，則key的值是（）A.89B.77C.47D.3912.某對(duì)分查找算法的VB程序如下：i=1:j=7:s=“”DoWhilei<=jm=(i+j)\2Ifkey=a(m)Thens=“E”:ExitDoElseIfKey<a(m)Thenj=m-1s=“L”Elsei=m+1s=“R”EndifLoop元素?cái)?shù)組a(1)到a(7)的值依次為:”25,42,53,66,77,83,98”,若key=60,運(yùn)行程序段后,下列條件表達(dá)式成立的是（）A.s=“E”B.s=“L”C.s=“R”D.s=“LRR”13.某對(duì)分查找算法的VB程序如下：t=“”:i=1:j=9:key=62:f=FalseDoWhilei<=jandNotfm=Fix((i+j)/2)t=t+Str(m)Ifa(m)=KeyThenf=TrueElseIfKey<a(m)Theni=m+1:t=t+”→”Elsej=m-1:t=t+”←”EndifLoop元素?cái)?shù)組a(0)到a(9)的值依次為:”99,94,90,87,78,70,63,56,45,36”執(zhí)行該程序段后，t的值是（）A.“4→7←5→”B.“4→7←5→6→”C.“4→7←5→6”D.“4→7←5”九、對(duì)分查找（二分法查找）ACCB1.編寫一個(gè)技術(shù)成績(jī)查詢的VB程序。程序功能如下：在文本框Text1中輸入分?jǐn)?shù)key（0-50的整數(shù)），單擊“查詢”按鈕Command1,查詢出信息成績(jī)大于key的所有記錄，并以“信息”為主要關(guān)鍵字、“通用”為次要關(guān)鍵字均進(jìn)行降序排序，結(jié)果輸出在列表框List2中，運(yùn)行界面如下圖所示。實(shí)現(xiàn)上述功能的VB程序如下，請(qǐng)回答下問題:（1）觀察上圖，排序后第5位的學(xué)生姓名是______________.Dimxm(1to600)asString,xx(1to600)asinteger,ty(1to600)asinteger,nasintegerPrivateSubForm_Load()‘從數(shù)據(jù)庫中讀取學(xué)生數(shù)據(jù)，存儲(chǔ)在相應(yīng)的變量中，代碼略EndSubPrivateSubCommand1_Click()Dimkeyasinteger,midasinteger,iasinteger,kasintegerDimtmp1asString,tmp2asString,Lasinteger,Rasinteger’以“信息”為主要關(guān)鍵字、“通用”為次要關(guān)鍵字排序Fori=1ton-1k=iForj=i+1tonIfxx(k)<xx(j)or________________________Thenk=jEndIfNextjIFk<>iThentmp1=xm(k):xm(k)=xm(i):xm(i)=tmp1tmp2=xx(k):xx(k)=xx(i):xx(i)=tmp2tmp2=ty(k):ty(k)=ty(i):ty(i)=tmp2EndIfNexti九、對(duì)分查找（二分法查找）‘查詢記錄Key=Val(Text1.text)L=1:R=nDoWhile

L<=Rmid=(L+R)\2If______________ThenL=mid+1ElseR=mid-1EndifLoopList2.ClearList2.additem“姓名”&“”&“信息”&“”&“通用”Fori=1to__________List2.additemxm(i)&“”&xx(i)&“”&ty(i)NextiEndSub李白xx(k)=xx(j)andty(k)<ty(j)xx(mid)>=keyR或L-12.查找最接近的數(shù)。編寫一個(gè)查找最接近數(shù)的VB程序：程序運(yùn)行時(shí)，在文本框Text1中輸入產(chǎn)生隨機(jī)數(shù)的個(gè)數(shù)（1到100之間），單擊命令按鈕“產(chǎn)生隨機(jī)數(shù)并升序排列”后，在列表框List1中顯示已經(jīng)按升序排列后的隨機(jī)整數(shù)。然后在文本框Text2中輸入要查找的整數(shù)，單擊命令按鈕“查找”后，在標(biāo)簽L中顯示隨機(jī)整數(shù)序列中與待查找數(shù)最接近的整數(shù)（當(dāng)最接近的數(shù)有2個(gè)時(shí)，輸出較大的一個(gè)）。程序運(yùn)行效果如圖所示。實(shí)現(xiàn)上述功能的VB代碼如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。Dimnasinteger,f(1to100)asBoolean,a(1to100)asinteger‘f(i)為true時(shí)表示隨機(jī)整數(shù)I已經(jīng)產(chǎn)生過PrivateSubCommand1_Click()

‘命令按鈕“產(chǎn)生隨機(jī)數(shù)并升序排列”DimiasintegerRandomizeFori=1to100f(i)=FalseNextin=Val(Text1.Text)Fori=1tont=int(Rnd*100+1)DoWhilef(i)=Truet=Int(Rnd*100+1)Loop_________________j=0Fori=1to100’實(shí)現(xiàn)排序并輸出Iff(i)=TrueThen_______________a(j)=iList1.additemStr(i)EndifNextiEndSubPrivateSubCommand2_Click()‘命令按鈕”查找“Dimkeyasintegerkey=Val(Text2.Text)Ifkey<=a(1)ThenLabel3.Caption=Str(a(1)):ExitSubIfkey>=a(n)ThenLabel3.Caption=Str(a(n)):ExitSubL=1:R=nDoWhileL<=R’找到與key較為接近的兩個(gè)數(shù)a(R)和a(L)m=(L+R)\2Ifkey<=a(m)ThenR=m–1ElseL=m+1EndifLoopIf__________________Then‘在a(R)和a(L)中選出更接近key的數(shù)Label3.Caption=Str(a(R))ElseLabel3.Caption=Str(a(L))EndifEndSubf(t)=Turej=j+1Abs(a(R)-key)<Abs(a(L)-key)九、對(duì)分查找（二分法查找）3.對(duì)于無序數(shù)組a(下標(biāo)1到n），通過引入數(shù)組b（下標(biāo)1到n），使得a(b(1))≤a(b(2))

≤a(b(3))

…≤a(b(n))。小王編寫了一個(gè)VB程序,功能如下：在列表框List1中顯示i,a(i),b(i),a(b(i))，在文本框Text1輸入要查找的數(shù)據(jù)，單擊“查找”按鈕Command1后，在標(biāo)簽Label3中顯示該數(shù)據(jù)在a數(shù)組中的位置。程序運(yùn)行界面如圖所示。實(shí)現(xiàn)上述功能的VB程序如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。Dima(1to8)asinteger,b(1to8)asinteger,nasintegerPrivateSubForm_Load()‘n=8對(duì)分查找前的8個(gè)數(shù)據(jù)存儲(chǔ)在a數(shù)組中，每個(gè)數(shù)據(jù)的位次存儲(chǔ)在b數(shù)組中,在列表框List1中顯示數(shù)組下標(biāo),a數(shù)組，b數(shù)組，a(b(i))EndSubPrivateSubCommand1_Click()Dimiasinteger,jasinteger,kasintegerDimmasinteger,keyasintegerkey=Val(Text1.Text)i=1:j=nDoWhilei<=jm=(i+j)\2_________________Ifkey=kThenExitDoElseIfkey>kTheni=m+1Elsej=m–1EndifLoopIF______________ThenLabel3.Caption=“該數(shù)據(jù)不存在”ElseLabel3.Caption=__________________EndifEndSubk=a(b(m))i>jb(m)九、對(duì)分查找（二分法查找）1.某一過程算法的VB程序段如下：PrivateSubCommand1_Click()Dimnasintegern=Val(Text1.Text)Callprsj(n)‘調(diào)用自定義過程EndSubSubprsj(casinteger)’自定義過程，可以用Call語句來調(diào)用該過程Dimiasinteger,jasinteger,kasStringList1.ClearFori=1tock=“”Forj=1toik=k+“*”NextjList1.additemkNextiEndSub在文本框Text1輸入3，執(zhí)行程序段后，在列表框List1中顯示的是（）

A.B.C.D.十、自定義函數(shù)和過程***********************************C2.數(shù)字游戲：將1到9這個(gè)9個(gè)數(shù)字分成3個(gè)三位數(shù)，數(shù)字不能重復(fù)，且3個(gè)數(shù)的比例為1：2：3，求出滿足條件的所有三位數(shù)分組。用VB編寫了程序?qū)崿F(xiàn)上述功能。界面如圖所示。請(qǐng)?jiān)趧澗€處填入合適代碼。Dima(0to9)asintegerPrivateSubCommand1_Click()Dimiasinteger,jasinteger,sasintegerFori=123to333Forj=1to9a(j)=0Nextj_____________Calljs(2*i)Calljs(3*i)_____________Forj=1to9s=s+a(j)NextjIf___________ThenList1.additemStr(i)+””+Str(2*i)+“”+Str(3*i)NextiEndSub十、自定義函數(shù)和過程Subjs(xasinteger)a(xmod10)=1a(x\10Mod10)=1________________EndSubCalljs(i)S=0S=9a(x\100)=13.一個(gè)整數(shù)n(n≥11)從左向右和從右向左讀其結(jié)果相同，且是素?cái)?shù)，則稱n為回文素?cái)?shù)，例如133020331是回文素?cái)?shù)。小張?jiān)O(shè)計(jì)一個(gè)VB程序用于找出1000以內(nèi)的所有回文素?cái)?shù)，程序運(yùn)行界面如圖所示。提示：如果不能被[2,n-1]內(nèi)的任何一個(gè)整數(shù)整除，則肯定是素?cái)?shù)。實(shí)現(xiàn)上述功能的VB程序如下，請(qǐng)?jiān)趧澗€處填入合適代碼。PrivateSubCommand1_Click()Dimnasinteger,jasinteger,masintegern=11DoWhilen<1000m=int(Sqr(n))Forj=2tomIf____________ThenExitForNextjIfj>mThenIfhws(n)=TrueThenList1.AdditemStr(n)Endifn=n+2LoopEndSub十、自定義函數(shù)和過程Functionhws(nasinteger)asBoolean‘判斷所給n是不是回文數(shù)Dimjasinteger,kasinteger,masintegerDimaasinteger,basinteger_____________m=CStr(n)‘將數(shù)值n轉(zhuǎn)成字符類型去除空格k=len(m)Forj=1tok\2a=Val(Mid(m,j,1))________________IFa<>bThenhws=FalseExitForEndifNextjEndFunctionnmodj=0hws=Trueb=mid(m,k-j+1,1)4.哥德巴赫1742年給歐拉的信中提出了以下猜想：任一大于2的偶數(shù)都可寫成兩個(gè)質(zhì)數(shù)之和，是為著名的哥德巴赫猜想。程序運(yùn)行時(shí)在文本框Text1輸入一個(gè)偶數(shù)n，單擊按鈕后在列表框List1上顯示驗(yàn)證結(jié)果?；卮鹣旅鎲栴}：(1)根據(jù)運(yùn)行界面和程序代碼，用來輸入偶數(shù)的對(duì)象所屬類名為__________.(2)請(qǐng)完善下列程序代碼Functionprime(xasinteger)asBooleanprime=TrueFori=2toint(Sqr(x))If__________Thenprime=False:ExitForNextiEndFunctionPrivateSubCommand1_Click()Dimaasinteger,basinteger,nasintegerList1.Clear_____________Fora=2ton\2b=n–aIf________________________ThenList1.additem(Str(a)+“”+Str(b)+“”+Str(n))EndifNextaEndSub十、自定義函數(shù)和過程TextBoxxmodi=0n=Val(Text1.Text)prime(a)andprime(b)5.設(shè)計(jì)一個(gè)二進(jìn)制數(shù)、十進(jìn)制數(shù)、十六進(jìn)制數(shù)混合加法計(jì)算的VB程序。在文本框Text2中輸入由數(shù)字、大寫字母、“+”和“=”組成的加法運(yùn)算式子，其中每一個(gè)數(shù)的最后一個(gè)大寫字母表示它的進(jìn)制，B表示二進(jìn)制數(shù)、D表示十進(jìn)制數(shù)、H表示十六進(jìn)制數(shù)，運(yùn)算式子以“=”結(jié)束，點(diǎn)擊“計(jì)算”按鈕Command1，在標(biāo)簽Label1中輸出十進(jìn)制表示的計(jì)算結(jié)果，程序運(yùn)行結(jié)果如圖所示。實(shí)現(xiàn)上述功能的VB程序如下，請(qǐng)回答下列問題，請(qǐng)?jiān)趧澗€處填入合適的代碼。PrivateSubCommand1_Click()Dimsasstring,casstring,s1asstringDimiasinteger,resultasintegers=Text1.Textresult=0s1=““Fori=1tolen(s)c=Mid(s,I,1)Ifc=“+”orc=“=“Then__________________s1=““Elses1=_______________EndifNextILabel1.Caption=Str(result)+“D”EndSub(2)若在輸入運(yùn)算式子“10B+10D+10H=”，則輸出結(jié)果___________。十、自定義函數(shù)和過程Functionxtod(s2asstring)asintegerDimleasinteger,fasstring,casstringDimnasinteger,masinteger,Iasintege,aasintegerle=len(s2)f=Mid(s2,le,1)Iff=“B”Thenn=2Elseiff=“D”Thenn=10ElseIff=“H”Thenn=16EndIFm=0Fori=1tole-1c=Mid(s2,i,1)Ifc>=“A”andc<=“9”Thena=Asc(c)-Asc(“0”)EsleIfc>=“A”andc<=“F”Thena=_________________Endifm=m*n+aNexIxtod=mEndFunctionresult=result+xtod(s1)s1+cAsc(c)-Asc(“A”)+1028D6.張勇想在學(xué)校里請(qǐng)一些同學(xué)做項(xiàng)問卷調(diào)查，為了實(shí)驗(yàn)客觀性，想由計(jì)算機(jī)隨機(jī)生成調(diào)查的學(xué)號(hào)，并由小到大排好。學(xué)校學(xué)號(hào)為1-1000，調(diào)查的人數(shù)<100，產(chǎn)生的隨機(jī)學(xué)號(hào)不能重復(fù),顯示在列表框List1中，第一列為序號(hào)，第2列為隨機(jī)學(xué)號(hào)，如下圖所示。請(qǐng)?jiān)趧澗€處填入合適代碼。Dimmasinteger,a(1000)asintegerPrivateSubCommand1_Click()Dimnasinteger,ppasinteger,kasinteger,tasinteger,jasintegerRandomize:List1.Clearn=Val(Text1.Text):m=1DoWhilem<=npp=Int(Rnd*1000)+1Ifflag(pp)Then________________m=m+1EndifLoopFori=1ton-1k=iForj=i+1ton_____________________NextjIfk<>iThent=a(k):a(k)=a(i):a(i)=tNextiFori=1tonList1.additemStr(i)+“”+Str(a(i))NextiEndSub十、自定義函數(shù)和過程Functionflag(nnasinteger)asBooleanflag=TrueForj=1tomIf_______________Thenflag=FalseExitFunctionEndifNextjEndFunctiona(m)=ppIfa(k)>a(j)Thenk=jnn=a(j)7.小王編寫一個(gè)VB程序模擬數(shù)據(jù)篩選,功能如下：程序運(yùn)行時(shí)從數(shù)據(jù)庫中讀取成績(jī)數(shù)據(jù),按升序排序后在列表框List1

中顯示，在文本框Text1中輸入成績(jī)1，在文本框Text2中輸入成績(jī)2，單擊“篩選”按鈕Command1，篩選出大于等于成績(jī)1且小于等于成績(jī)2的記錄，并顯示在列表框List2中，程序運(yùn)行界面如圖所示。(1)運(yùn)行上述程序,若文本框Text1中輸入75，Text2中輸入85，單擊“篩選”按鈕，則篩選到的記錄有條__________(填數(shù)字)。（2）填寫合適代碼。Constn=20Dimscore(1ton)asSinglePrivateSubForm_Load()EndSubFunctionadj(sasstring,nasinteger)EndFunctionFunctionsearch_left(keyasinteger)EndFunctionFunctionsearch_right(keyasinteger)Dimiasinteger,jasinteger,masintegeri=1:j=nDoWhilei<=j____________Ifkey>=score(m)Theni=m+1Elsej=m-1Loop______________EndFuction十、自定義函數(shù)和過程PrivateSubCommand1_Click()Dimnum1asinteger,num2asintegeDimfirstasinteger,lastasintegerList2.Clearnum1=Val(Text1.Text):num2=Val(Text2.Text)first=search_left(num1):last=search_right(num2)_____________________Iftotal<=0ThenList2.additem“無篩選到的記錄!”