第三章算法与程序实现5课件-高中信息技术浙教版必修1

算法与程序设计——方卫龙对分查找代码（标准代码）i=1:j=n:s=0DoWhilei<=jm=(i+j)\2Ifa(m)=keyThens=m:ExitDoElseIfkey<a(m)Thenj=m–1Elsei=m+1EndIfLoop

左边程序实现在升序数组a(1)…a(n)中查找值等于key的元素，将其下标存储在s中。如果没有找到则s值为0，如果找到，则s存储对应元素的下标。

对分查找前提是数组有序，对n个数据查找，最多查找次数为Log2n+1（向下取整）。

例如在有序数组a(1)…a(10000)中查找某个值，最多需要查找Log210000+1，即14次。用一个行IF和一个块IF语句实现i=1:j=n:s=0DoWhilei<=jm=(i+j)\2Ifa(m)=keyThens=m:ExitDoIfkey<a(m)Thenj=m–1Elsei=m+1EndIfLoop三个行If语句实现i=1:j=n:s=0DoWhilei<=jm=(i+j)\2Ifa(m)=keyThens=m:ExitDoIfkey<a(m)Thenj=m–1Ifkey<a(m)Theni=m+1EndIfLoop九、对分查找（二分法查找）例如在一有序序列:12,14,18,25,36,39,42,49,51,53,56,62,65存储在数组a(1)到a(13)中查找特定的关键词Key。九、对分查找（二分法查找）12141825363942495153566265ij假设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③假设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.数组变量d(1)到d(8)的值仿效为97、86、79、68、56、41、33、13，用“标准”对分查找算法查找“13”的过程中，依次被访问到的数据是（）A.68、13B.68、41、13C.56、41、33、13D.68、41、33、132.某数组的6个元素依次为“27、32、57、78、80、90”。若对该数组进行顺序查找，其平均查找次数为（1+2+3+4+5+6）/6=7/2；若对该数组进行对分查找，其平均查找次数为（）A.7/2B.1/9C.5/2D.23.某校校园一卡通系统有4096条记录信息（已经索引排序），假设从中取出一条记录并与待查找项进行比较所花时间为8毫秒，则用对分法在该系统中查找一条指定记录最多花费的时间约为（）A.80毫秒B.104毫秒C.160毫秒D.240毫秒4.某对分查找算法的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数组元素b(1)到b(8)的值依次为“22，32，39，48，71，82，96，106”。若该程序段运行结束后，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该段程序运行后,下列表达式正确的是（）A.i=m+1B.j=m-1C.j>m+1D.i>m-1九、对分查找（二分法查找）DBBCC6.某对分查找算法的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数组元素d(1)到d(8)的值依次为“97,79,68,48,35,23,18,10”,若运行该程序段后，C的值为2，则Text1中输入的值是（）

A.68或18B.68或23C.79或23D.79或187.某对分查找算法的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”,若该程序段运行结果后，n的值为2，则key的值是（）A.87或29B.72或18C.72或29D.53或188.某对分查找算法的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元素数组a(1)到a(7)的值依次为:”10,20,30,40,50,60”,文本框Text1中输入35后运行程序段，运行结束后下列说法正确的是（）A.变量f和True

B.变量i值4

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

9.某对分查找算法的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元素数组a(1)到a(10)的值依次为:”95,82,76,70,68,50,41,9,3,1”,文本框Text1中输入的值是32，运行程序段后，以下变更的值正确的是（）A.flag=TrueB.m=8C.i=8D.j=8ABBC九、对分查找（二分法查找）10.有10个数据：83,80,66,46,44,36,21,16,15,12依次存放在数组元素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,执行程序段,文本框Text2中显示的是(

)A.3666B.4480C.3645D.446611.某对分查找算法的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”,输入某个key值后，运行程序段后，变量s的值为1，则key的值是（）A.89B.77C.47D.3912.某对分查找算法的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元素数组a(1)到a(7)的值依次为:”25,42,53,66,77,83,98”,若key=60,运行程序段后,下列条件表达式成立的是（）A.s=“E”B.s=“L”C.s=“R”D.s=“LRR”13.某对分查找算法的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元素数组a(0)到a(9)的值依次为:”99,94,90,87,78,70,63,56,45,36”执行该程序段后，t的值是（）A.“4→7←5→”B.“4→7←5→6→”C.“4→7←5→6”D.“4→7←5”九、对分查找（二分法查找）ACCB1.编写一个技术成绩查询的VB程序。程序功能如下：在文本框Text1中输入分数key（0-50的整数），单击“查询”按钮Command1,查询出信息成绩大于key的所有记录，并以“信息”为主要关键字、“通用”为次要关键字均进行降序排序，结果输出在列表框List2中，运行界面如下图所示。实现上述功能的VB程序如下，请回答下问题:（1）观察上图，排序后第5位的学生姓名是______________.Dimxm(1to600)asString,xx(1to600)asinteger,ty(1to600)asinteger,nasintegerPrivateSubForm_Load()‘从数据库中读取学生数据，存储在相应的变量中，代码略EndSubPrivateSubCommand1_Click()Dimkeyasinteger,midasinteger,iasinteger,kasintegerDimtmp1asString,tmp2asString,Lasinteger,Rasinteger’以“信息”为主要关键字、“通用”为次要关键字排序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九、对分查找（二分法查找）‘查询记录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.查找最接近的数。编写一个查找最接近数的VB程序：程序运行时，在文本框Text1中输入产生随机数的个数（1到100之间），单击命令按钮“产生随机数并升序排列”后，在列表框List1中显示已经按升序排列后的随机整数。然后在文本框Text2中输入要查找的整数，单击命令按钮“查找”后，在标签L中显示随机整数序列中与待查找数最接近的整数（当最接近的数有2个时，输出较大的一个）。程序运行效果如图所示。实现上述功能的VB代码如下，请在划线处填入合适的代码。Dimnasinteger,f(1to100)asBoolean,a(1to100)asinteger‘f(i)为true时表示随机整数I已经产生过PrivateSubCommand1_Click()

‘命令按钮“产生随机数并升序排列”DimiasintegerRandomizeFori=1to100f(i)=FalseNextin=Val(Text1.Text)Fori=1tont=int(Rnd*100+1)DoWhilef(i)=Truet=Int(Rnd*100+1)Loop_________________j=0Fori=1to100’实现排序并输出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较为接近的两个数a(R)和a(L)m=(L+R)\2Ifkey<=a(m)ThenR=m–1ElseL=m+1EndifLoopIf__________________Then‘在a(R)和a(L)中选出更接近key的数Label3.Caption=Str(a(R))ElseLabel3.Caption=Str(a(L))EndifEndSubf(t)=Turej=j+1Abs(a(R)-key)<Abs(a(L)-key)九、对分查找（二分法查找）3.对于无序数组a(下标1到n），通过引入数组b（下标1到n），使得a(b(1))≤a(b(2))

≤a(b(3))

…≤a(b(n))。小王编写了一个VB程序,功能如下：在列表框List1中显示i,a(i),b(i),a(b(i))，在文本框Text1输入要查找的数据，单击“查找”按钮Command1后，在标签Label3中显示该数据在a数组中的位置。程序运行界面如图所示。实现上述功能的VB程序如下，请在划线处填入合适的代码。Dima(1to8)asinteger,b(1to8)asinteger,nasintegerPrivateSubForm_Load()‘n=8对分查找前的8个数据存储在a数组中，每个数据的位次存储在b数组中,在列表框List1中显示数组下标,a数组，b数组，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=“该数据不存在”ElseLabel3.Caption=__________________EndifEndSubk=a(b(m))i>jb(m)九、对分查找（二分法查找）1.某一过程算法的VB程序段如下：PrivateSubCommand1_Click()Dimnasintegern=Val(Text1.Text)Callprsj(n)‘调用自定义过程EndSubSubprsj(casinteger)’自定义过程，可以用Call语句来调用该过程Dimiasinteger,jasinteger,kasStringList1.ClearFori=1tock=“”Forj=1toik=k+“*”NextjList1.additemkNextiEndSub在文本框Text1输入3，执行程序段后，在列表框List1中显示的是（）

A.B.C.D.十、自定义函数和过程***********************************C2.数字游戏：将1到9这个9个数字分成3个三位数，数字不能重复，且3个数的比例为1：2：3，求出满足条件的所有三位数分组。用VB编写了程序实现上述功能。界面如图所示。请在划线处填入合适代码。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十、自定义函数和过程Subjs(xasinteger)a(xmod10)=1a(x\10Mod10)=1________________EndSubCalljs(i)S=0S=9a(x\100)=13.一个整数n(n≥11)从左向右和从右向左读其结果相同，且是素数，则称n为回文素数，例如133020331是回文素数。小张设计一个VB程序用于找出1000以内的所有回文素数，程序运行界面如图所示。提示：如果不能被[2,n-1]内的任何一个整数整除，则肯定是素数。实现上述功能的VB程序如下，请在划线处填入合适代码。PrivateSubCommand1_Click()Dimnasinteger,jasinteger,masintegern=11DoWhilen<1000m=int(Sqr(n))Forj=2tomIf____________ThenExitForNextjIfj>mThenIfhws(n)=TrueThenList1.AdditemStr(n)Endifn=n+2LoopEndSub十、自定义函数和过程Functionhws(nasinteger)asBoolean‘判断所给n是不是回文数Dimjasinteger,kasinteger,masintegerDimaasinteger,basinteger_____________m=CStr(n)‘将数值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的偶数都可写成两个质数之和，是为著名的哥德巴赫猜想。程序运行时在文本框Text1输入一个偶数n，单击按钮后在列表框List1上显示验证结果。回答下面问题：(1)根据运行界面和程序代码，用来输入偶数的对象所属类名为__________.(2)请完善下列程序代码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十、自定义函数和过程TextBoxxmodi=0n=Val(Text1.Text)prime(a)andprime(b)5.设计一个二进制数、十进制数、十六进制数混合加法计算的VB程序。在文本框Text2中输入由数字、大写字母、“+”和“=”组成的加法运算式子，其中每一个数的最后一个大写字母表示它的进制，B表示二进制数、D表示十进制数、H表示十六进制数，运算式子以“=”结束，点击“计算”按钮Command1，在标签Label1中输出十进制表示的计算结果，程序运行结果如图所示。实现上述功能的VB程序如下，请回答下列问题，请在划线处填入合适的代码。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)若在输入运算式子“10B+10D+10H=”，则输出结果___________。十、自定义函数和过程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.张勇想在学校里请一些同学做项问卷调查，为了实验客观性，想由计算机随机生成调查的学号，并由小到大排好。学校学号为1-1000，调查的人数<100，产生的随机学号不能重复,显示在列表框List1中，第一列为序号，第2列为随机学号，如下图所示。请在划线处填入合适代码。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十、自定义函数和过程Functionflag(nnasinteger)asBooleanflag=TrueForj=1tomIf_______________Thenflag=FalseExitFunctionEndifNextjEndFunctiona(m)=ppIfa(k)>a(j)Thenk=jnn=a(j)7.小王编写一个VB程序模拟数据筛选,功能如下：程序运行时从数据库中读取成绩数据,按升序排序后在列表框List1

中显示，在文本框Text1中输入成绩1，在文本框Text2中输入成绩2，单击“筛选”按钮Command1，筛选出大于等于成绩1且小于等于成绩2的记录，并显示在列表框List2中，程序运行界面如图所示。(1)运行上述程序,若文本框Text1中输入75，Text2中输入85，单击“筛选”按钮，则筛选到的记录有条__________(填数字)。（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十、自定义函数和过程PrivateSubCommand1_Click()Dimnum1asinteger,num2asintegeDimfirstasinteger,lastasintegerList2.Clearnum1=Val(Text1.Text):num2=Val(Text2.Text)first=search_left(num1):last=search_right(num2)_____________________Iftotal<=0ThenList2.additem“无筛选到的记录!”