第三单元-查找算法

技术第三单元查找算法技术夯实考点考点1顺序查找1.查找算法所谓查找就是在指定的数据中寻找某一特定的数据。查找结果有两种,找到(查找成功)和未找到(查找失败)。2.顺序查找的基本思想从第一个数据开始,从左往右(或从上到下)将数据按顺序逐个与给定的关键字进行比较,若某个数据和给定的关键字相等,则查找成功,找到并输出第一个与关键字相等的数据的位置;反之,查找失败。若有n个数,则可能的最多查找次数为n。技术3.顺序查找算法基本框架假设:要查找的数为key,待查找的数存放在数组d中。For语句框架:Fori=1ton若d(i)=key,则表示找到,做相应处理Nexti若in表示未找到DoWhile语句框架:i=1Dowhilei=n若d(i)=key,则表示找到,做相应处理i=i+1Loop若in表示未找到技术4.顺序查找的程序实现在n个数组元素中依次查找,找到第1个满足条件的值,查找即结束,输出找到元素所在的位置;若找不到,输出“未找到”。程序实现:设:(1)要查找的数据是key(在文本框Text1中输入),查找的数据存放在数组d中。(2)pos为找到数的位置,pos=0表示未找到。(3)p记录查找的次数。key=Val(Text1.Text)'Val要根据实际情况决定是否要添加p=0pos=0find=False'find=False表示未找到,find=True表示找到i=1技术DoWhilei=nAndfind=False'表示还没找完并且还未找到,则继续查找,notfind也可表示为find=Falsep=p+1Ifkey=d(i)Thenpos=ifind=TrueEndIfi=i+1LoopIffindThen'也可表示为Iffind=TrueThenText2.Text=在d(+Str(pos)+)中ElseText2.Text=未找到EndIf技术典例1某查找算法的部分VB代码如下:t=Falsei=0DoWhilei7Andt=Falsei=i+1Ifa(i)=keyThent=TrueLoopIft=FalseTheni=0数组元素a(1)到a(7)的数据依次为“3,5,1,5,8,9,5”,当变量key值为5时,运用该算法处理后,变量i的值是()A.0B.2C.4D.7技术解析:本题主要考查的是顺序查找的实现过程。本程序的功能是查找数组中第一个与目标数据相等的数,若找到将其在数组中的位置赋给变量i,结束查找;若找不到,变量i=0。因为目标值key=5,它和数组中第二个数正好相等,因此i=2。答案:B技术典例2编写一个VB程序,实现如下功能:在列表框List1中显示十个字符串,十个字符串存放在数组s中,在文本框Text1中输入一个字符串,单击“统计”按钮,统计字符串出现的次数,若出现次数大于0,则在文本框Text2中显示实际次数,若出现次数为0,则在文本框Text2中显示“找不到”。程序运行效果如图3-1所示。技术Dims(1to10)AsStringPrivateSubForm_Load()'给数组s赋值,并显示在列表框List1中EndSubPrivateSubCommand1_Click()DimstAsString,iAsInteger,numAsIntegerst=①num=0Fori=1To10If②Thennum=num+1NextiIf③ThenText2.Text=Str(num)ElseText2.Text=找不到EndIfEndSub技术为实现上述功能,请在程序划线处填入合适的语句:程序①处语句为;程序②处语句为;程序③处语句为。解析:要查找的字符为st,st通过文本框Text1中输入得到,因此①处语句为Text1.Text;将要查找的字符串按顺序与数组s中元素比较,如果相等,则进行计数,因此②处语句为s(i)=st;根据题目“若出现次数大于0,则在文本框Text2中显示实际次数,若出现次数为0,则在文本框Text2中显示“找不到”。可知③处的语句为num0或num0。答案:①Text1.Text②s(i)=st③num0或num0技术典例3某6位学生的学号存储在数组元素a(1)到a(6)中,其数据依次为“2015001,2015003,2015078,2015010,2015788,2015666”。使用顺序查找算法查找学号2015700,则共需查找次数为()A.0B.5C.6D.7解析:本题考查的是顺序查找算法的实现过程。由于给定的数组中没有数据2015700,因此需要与数组中每个数进行比较,因此共需查找次数为6次。答案:C技术考点2对分查找1.对分查找的基本思想在有序的数据序列中(一般存放在数组中),首先把要查找的数据与数组中间位置的元素进行比较,如果相等,则查找成功并退出查找;否则,根据数组元素的有序性,确定数据应在数组的前半部分还是在后半部分查找;在确定了新的查找范围后,重复进行以上比较,直到找到或未找到为止。【重难点剖析】①对分查找的前提是被查找的数据序列必须是有序。②“未找到”是指当指定范围内的起点大于终点仍未找到该数据。技术2.对分查找算法基本框架说明:要查找的数为key,待查找的数存放在数组d中。i为查找范围的起点,j为查找范围的终点,m为范围[i,j]的中间位置。i=1j=nDoWhilei=j计算中点位置m比较key与d(m),并做相应处理Loop若ij,则表示未找到技术3.对分查找程序实现在n个数组元素中依次查找,找到第1个满足条件的值,查找就结束,输出找到元素所在的位置;若找不到,输出“未找到”。程序实现:设要查找的数据是key(在文本框Text1中输入),查找的数据存放在数组d中。在文本框Text2中输出查找结果,若找到输出“找到!位置为:X”,否则输出“未找到!”在文本框Text3中输出共查找的次数。p表示查找的次数。核心代码为(以升序为例):key=Val(Text1.Text)′表示要查找的数p=0′表示查找的次数技术find=False′查找的结果,若find=True表示找到,find=False表示未找到i=1′查找范围的起点j=n′查找范围的终点DoWhilei=jAndNotfind′如果还未找完并且未找到p=p+1′查找次数计数m=(i+j)/2′计算中点位置mIfkey=d(m)Then′表示找到的情况find=TrueText2.Text=找到!位置为:+Str(m)EndIfIfkeyd(m)Then′表示查找的数比中间位置上的数大时i=m+1Else′表示查找的数比中间位置上的数小时j=m-1EndIfLoopIfNotfindThenText2.Text=未找到!Text3.Text=共查找的次数为:+Str(p)技术【重难点剖析】计算中点位置的语句还可以写成:m=Int((i+j)/2)或m=Fix((i+j)/2)。典例4(2015浙江省10月选考题)已知单调函数在[0,1]区间存在一个x0,使f(x0)=0。现用对分查找算法搜索x0的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为()A.1/2B.1/10C.1/102D.1/210解析:本题主要考查的是对分查找算法。在[0,1]区间内查找一个数,第一次取[0,1]区间中间值0.5,如果f(0.5)0,则第二次区间为[0.5,1],如果f(0.5)0,则第二次区间为[0,0.5],每次都减少为原来的1/2,所以答案为D。答案:D技术典例5a数组(a(1)～a(8))中存储了8本图书的价格,其数据依次为“105,98,95,60,55,35,12,8”。现使用对分查找数据8,需要查找的次数是()A.1B.2C.3D.4解析:本题主要考查的是对分查找算法的实现过程。根据计算公式m=(i+j)/2可知,第一次访问的数据为60(第4个),第二次访问的数据为35(第6个),第三次访问的数据为12(第7个),第四次访问的数据为8(第8个),因此答案为D。答案:D技术典例6某数组有10个数据,依次为1,2,3,4,5,6,7,8,9,10,现要查找某一数据,若使用对分查找目标数据,需查找两次,若用顺序查找需查找8次,则要查找的目标数据为()A.2B.3C.7D.8解析:本题考查的是两种查找算法。根据顺序查找次数即可判定目标数据为8,我们再用对分查找进行验证,第一次查找的位置是m=(1+10)/2=5,第二次查找的位置是m=(6+10)/2=8,第8个位置上的数就是8,因此答案为D。答案:D技术典例7小明编写了一个学生IC卡余额查询系统,其功能是在文本框Text1中输入学生的IC卡号,单击“查询余额”按钮Command1后,在标签Label3中输出查找结果。程序运行效果如图3-2所示。程序说明:(1)学生的IC卡号保存在数组card中,并已按升序排序好;卡中金额保存在数组money中。例:第i个学生的卡号保存在card(i)中,其对应的金额保存在money(i)中。(2)如果在数据库中找到此卡号,则在标签Label3中显示“此卡号余额为”及对应的余额,如果未找到则显示“查无此号!”。技术(3)程序运行,将在左边列表框List1中显示学生的卡号和金额。技术解决此问题的部分程序段如下:Constn=1500′设共有n张卡Dimcard(1Ton)AsLongDimmoney(1Ton)AsSinglePrivateSubForm_Load()′此过程用于输入卡号及金额,并存储在数组card和money中代码略EndSubPrivateSubCommand1_Click()DimxAsLong,iAsLong,jAsLong,mAsLong,findAsBooleanx=Val(Text1.Text)i=1①find=FalseDoWhile②技术m=(i+j)/2Ifx=card(m)Then③ElseIfxcard(m)Thenj=m-1Elsei=m+1EndIfLoopIffind=TrueThenLabel3.Caption=此卡号余额为+④+元ElseLabel3.Caption=查无此号!EndIfEndSub技术(1)解决此问题的算法是。(选填:对分查找或顺序查找)(2)在程序①,②,③,④划线处填入适当的语句或表达式,将程序补充完整:程序中①划线处应填入。程序中②划线处应填入。程序中③划线处应填入。程序中④划线处应填入。技术解析:本题考查的是对分查找算法的程序实现。对分查找的关键在于确定每次查找的范围,程序用变量i,j表示查找的范围,根据划线①处前面的语句可以确定①处的语句应表示首次查找范围的终点,即j=n;划线②处的语句表示查找的条件,如果还没找完并且还没找到,则继续查找,因此,划线②处应填入的语句为(i=j)Andfind=False;划线③处的语句表示找到后的情况,找到对应的卡号表示查找结束,因此划线③处应填入find=True;最后是显示查找结果,找到则显示卡中金额,因此划线④处应填入的语句为Str(money(m)),需注意的是要加转换函数Str。答案:(1)对分查找(2)①j=n②(i=j)Andfind=False③find=True④Str(money(m))技术点击进入课后训练技术谢谢观赏Thanks!