信息技术 算法的程序实现

第四章算法的程序实现,第四章算法的程序实现,本节掌握枚举算法的基本思想、程序实现方法、多重循环的程序实现方法，难点是理解内循环与外循环的概念，并能根据算法编写简单的多重循环代码。掌握常见素数问题算法与最大公约数问题算法。考查方式为选择题与非选择题。,第一节枚举算法及程序实现,1枚举算法的基本思想枚举，就是将问题的可能解一个个地列举，逐一判断，即使中途找到符合的解也要继续找下去，将所有可能都找完才结束。枚举算法又叫穷举算法，其基本思想是把问题所有的解一一地罗列出来，并对每一个可能解进行判断，以确定这个可能解是否是问题的真正解。若是，就采纳这个解，否则就抛弃它。2枚举算法的实现要点(1)列举与检验过程既不重复也不遗漏；(2)尽可能地使可能解的罗列范围最小，以提高解决问题的效率；(3)用循环语句(For语句)在一定范围内列举所有可能的解；(4)用选择语句(If语句)判断和选择真正的解。3枚举算法的一般格式,4双重循环某些枚举算法的问题比较复杂，需要通过复杂的双重循环来实现。双重循环就是循环的嵌套，在一层循环结构内部又是另一层循环，其结构如下所示：,此结构由两个For循环构成，外循环是循环变量为i的循环，内循环是循环变量为j的循环，这两个循环之间的关系是嵌套关系，循环变量为i的循环将循环变量为j的循环包含在内，在循环执行时，外循环变量i每变化一次，都要执行一次完整的内循环。在枚举算法中，有很多时候用到循环的嵌套来解决问题。5循环嵌套循环嵌套的层数没有具体限定，选考时的多重循环结构一般只要求到双重循环。多重循环在使用时，每个循环必须只有一个唯一的变量名作为循环变量；在Next语句结束循环时，必须内循环先结束，不得出现互相交叉。6编写枚举算法的程序要注意两个要点(1)For循环的范围要尽可能的小，这决定可能解的范围是否已经尽可能的小；(2)条件表达式必须要正确无误，这决定哪些解才是真正的解。,7素数问题(1)素数的概念素数(质数)就是一个大于等于2的整数，并且只能被1和本身整除，而不能被其他整数整除的数。(2)算法说明判别某数n是否是素数的经典算法是，对于n，从i2,3,4，n1依次判别能否被i整除，只要有一个能整除，n就不是素数，否则n是素数。(3)代码实现,8最大公约数问题(1)最大公约数：就是几个数共同最大的约数。(2)算法说明：用辗转相除法求两自然数m、n的最大公约数，再由最大公约数求出最小公倍数。首先，对于已知两数m、n，比较并使得mn；m除以n得余数r；若r0，则n为求得的最大公约数，算法结束；否则执行步骤；使mn，nr再重复执行。(3)代码实现：,【例1】下列问题中适合使用枚举算法解决的是()A计算两个电阻的并联值B计算五个同学的平均身高C查找100以内所有能被6整除的数D超市的促销方案,【例1解题】本题考查枚举算法的特点。选项A、B和D都适用_算法，用数学公式求解。选项C的解决方法符合_算法的基本思想，先列举再验证。【答案1】_,解析,枚举,C,【例2】浙江高考某工厂购入100千克原材料，每4千克原材料可以生产一件A产品，每5千克原材料可以生产一件B产品。下列VB程序的功能是：计算恰好用尽这些原材料时，生产A产品和B产品数量的各种可能，并在列表框中输出。请在划线处填入合适代码。PrivateSubCommand1_Click()DimxAsInteger,yAsIntegerx为A产品数量，y为B产品数量Forx0To25Fory0To20If_(1)_ThenList1.AddItem”A产品”Str(x)”件，”B产品”Str(y)”件”EndIf_(2)_NextxEndSub,【例2解题】本题考查枚举算法的程序实现。设100千克原材料产生了x件A产品、y件B产品，它们必须满足等式4x+5y=100。当y取最小值0时，x可以取到最大值25，同样，当x取最小值0时，y可以取到最大值20。本题中程序采用嵌套循环的方法来进行枚举，执行时，外层的For循环当x的取值为0时，内层的For循环完整执行一次，即y取值为020之间的整数，然后判断这些数y与x的组合能否满足条件4x+5y=100，若满足，则在对象List1列表框中输出一组x、y，一次循环结束后，外循环变量x增加1，再次执行一次完整的内层For循环，还是y取值为020之间的整数依此类推，可把x取值为025与y取值为020的所有可能组合（共有2621=546种组合）都判断是否满足条件4x+5y=100，若条件成立则在列表框List1输出一组x、y。故题中（1）就是条件表达式4*x+5*y=100，内层For循环语句的循环变量是y，它应先结束；（2）为Nexty，放在外层循环的Nextx语句之前。【答案2】(1)_(2)_,4*x+5*y=100,Nexty,【例3】2016金华模拟平面上有N(3N100)个房间围成一圈，按顺时针方向分别编号为1.N，相邻的两个房间之间均有一扇门，第i个房间居住人数为a(i)。初始时选择一个房间，将所有人都聚集在该房间，接着每个人都按顺时针方向走到相邻的房间，直到走到居住的房间。一个人每经过一扇门花费1的能量，请确定初始房间，使得所有人花费的能量和最小。例如：N=5，a(1)=4，a(2)=7，a(3)=8，a(4)=6，a(5)=4最佳方案：初始时所有人聚集在2号房间，花费的能量和：7*0+8*1+6*2+4*3+4*4=48。为了解决这个问题，小明编写了一个VB程序。在窗体加载时，从数据库中读取N的值和编号为1到N的房间的居住人数，人数存储在数组a中。点击窗体上的按钮Command1，程序枚举每一种方案（不同的初始房间），计算该方案下的能量和，在文本框Text1中输出最优方案的初始房间编号，在文本框Text2中输出最小能量和。实现上述功能的VB代码如下，但加框处代码有错，请改正。Dima(1To100)AsInteger依次存储编号为1到100的房间的最多居住人数PrivateSubForm_Load()本过程从数据库中读取N的值和编号为1到N的房间的居住人数，存储在数组a中代码略EndSub,PrivateSubCommand1_Click()DimiAsInteger,jAsInteger,wAsInteger,kAsIntegerDimtAsLong,ansAsLongk=0:ans=32767Fori=1Tont=0Forj=0Ton-1w=（1）Ifw=0Thenw=nt=（2）NextjIft100,yf(x),【例4】浙江高考用辗转相除法求最大公约数。已知用辗转相除法求两个正整数m、n的最大公约数的算法如下：(用num1，num2，r分别表示被除数m、除数n和余数)求num1/num2的余数r；若r0，则执行第步；将num2的值放在num1中，将r的值放在num2中；重新执行第步；,Functiontemp(num1AsInteger,num2AsInteger)AsIntegerDimrasInteger此函数用于计算两个正整数的最大公约数rnum1Modnum2DoWhile_num1num2num2rrnum1Modnum2Looptempnum2EndFunctionPrivateSubCommand1_Click()DimaAsInteger,bAsInteger,cAsInteger,xAsInteger,yAsIntegeraVal(Text1.Text)bVal(Text2.Text)cVal(Text3.Text)x_ytemp(x,c)Text4.TextStr(y)EndSub(1)解决此问题的算法是_(选填：解析算法/枚举算法)。在程序和划线处，填入适当的语句或表达式，把程序补充完整：(2)程序中划线处应填入_。(3)程序中划线处应填入_。,【例4解题】本题考查解析算法的基本思想及其程序实现。(1)本题求三个整数的最大公约数，主要采用数学上的辗转相除法，符合解析算法的思想方法。(2)函数temp的功能是求两个正整数的最大公约数，方法是辗转相除法，通过辗转相除法的算法描述(步骤到)可知，如果r0，则跳出循环，因此Do语句的条件表达式应该是r0。(3)Command1_Click事件的功能是求a、b、c三个数的最大公约数，函数temp是求两个数的最大公约数，因此需要两次调用该函数，先求出a和b的最大公约数x，再求出x和c的最大公约数y，那么y就是a、b、c三个数的最大公约数，因此xtemp(a，b)。【答案4】(1)_(2)_(3)_,解析法,r0,temp(a，b),微专题二枚举算法与解析算法的辨析,本节理解冒泡排序算法的基本思想，能根据冒泡排序的思想，对一组数据进行冒泡排序。掌握冒泡排序算法的程序实现，能根据给出的题目自行编写冒泡程序。考查方式为选择题与非选择题。,第三节冒泡排序算法及程序实现,1冒泡排序算法的基本思想冒泡排序是在一列数据中把较小(大)的数据逐次向上推移的一种排序技术。该算法的基本思想是把待排序的n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小(大)的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一趟加工。当第一趟加工完成时，最小(大)的数据已经上升到第一个元素的位置。然后对余下的n1个元素重复上述处理过程，直至最后余下两个数据的比较和交换。由于每一趟加工都是将本趟最小(大)的数元素像气泡一样浮至本趟的顶端位置，所以称作冒泡排序。但冒泡也有变式，即将数组元素进行两两比较，若相邻两个元素中的数据不符合排序，就交换位置。某数组c共由4个元素构成，每个元素的值如下表所示：,采用冒泡排序思想进行升序排序，从最下面的一个元素起，自下而上的比较相邻两个元素中的数据，整个排序过程如下所示：第一趟加工处理过程：,第一趟加工共比较3次，处理完成后，最小的元素15存储在了c(1)中。第二趟加工处理过程：,第二趟加工共比较2次，处理完成后，第2个最小的元素23存储在了c(2)中。第三趟加工处理过程：,第三趟加工共比较1次，处理完成后，第3个小的元素32存储在了c(3)中。4个元素共需进行3趟加工处理，总的比较次数为3216次。对n个元素的数组，用冒泡法进行排序时，共需比较n(n1)/2次。2冒泡排序算法的程序实现冒泡排序程序的实现可用双重For循环来实现，外层For循环控制是第几遍加工，内层For循环控制进行排序的数组元素下标的变化范围。由于每趟加工完成后，进行排序的范围会发生变化(每趟减少一个)，故内层For循环变量的下界由外层循环变量决定。现有n个数据，分别存放在数组变量a(1Ton)当中，用冒泡排序算法表示结构如下：,用冒泡排序算法程序实现的片段如下：,Fori1Ton1ForjnToi1Step1Ifa(j)a(j1)、a(j)h(j)Thenth(i)：h(i)h(j)：h(j)tEndIfNextjNexti,【例1】浙江高考下表记录了6个数据的排序过程。分析表中数据可知，该排序采用的算法与排序方式分别为(),A.冒泡排序，降序B选择排序，降序C冒泡排序，升序D选择排序，升序,【例1解题】本题考查冒泡排序的基本思想。【答案1】_,C,【例2】2016浙江模拟对16,12,14,7,10这5个数进行冒泡从小到大排序，则完成第二遍时的结果是()A7,12,14,16,10B7,10,14,16,12C7,10,16,12,14D16,14,12,10,7,【例2解题】第一趟冒泡固定_，第二趟冒泡固定_，注意冒泡比较的是相邻两个元素。【答案2】_,7,10,C,【例3】2016金华模拟有如下程序段：tot0Fori1To4yesFalseForj5Toi1Step1Ifa(j)a(i)ThenyesTruetottot1ta(j):a(j)a(i):a(i)tEndIfNextjIfyesFalseThenExitForNexti数组元素a(1)到a(5)的值依次为“33,24,4,16,77”，经过该程序段“加工”后，变量tot的值为()A2B3C4D5,【例3解题】本题考查程序阅读能力，程序中Fori语句控制外层循环，Forj语句控制内层循环，第i趟处理时，在数组a中a(j)从后向前逐个与a(i)比较，tot记录交换次数。i1时，a(5)与a(1)交换，数组a变为77,24,4,16,33；i2时，a(2)与a(5)交换，数组a变为77,33,4,16,24；i3时，_与_交换，数组a变为_；i4时，由于没有发生交换，直接退出循环。总交换次数为_次。【答案3】_,B,a(3),a(5),77,24,33,16,4,3,【例4】2016.10浙江选考小吴为了探究冒泡排序过程中数据的“移动”情况，编写了一个VB程序，功能如下：在列表框List1中显示排序前数据(存储在数组a中)，在文本框Text1中输入初始位置(即下标值)，单击“排序”按钮Command1后，在标签Label1中显示指定初始位置的数据在排序过程中的位置变化情况，排序后的数据显示在列表框List2中。程序运行界面如图所示。,实现上述功能的VB程序如下，但加框处代码有错，请改正。Dima(1To8)AsIntegerDimnAsIntegerPrivateSubForm_Load()n8，排序前的8个数据存储在数组a中，并在列表框Listl中显示代码略EndSub,PrivateSubCommand1_Click()DimiAsInteger,jAsInteger,kAsIntegerDimposAsInteger变量pos存储指定数据的位置(即下标值)DimsAsString变量s存储pos变化情况sText1.TextposVal(Text1.Text)Fori1Ton1ForjnToi1Step1Ifa(j)a(j1)Then(1)a(j1)a(j)a(j)k如果pos位置的数据参与交换，则更新pos值，记录pos变化情况IfposjThenposj1s=s+”Str(pos)(2),k=a(j),Else,posjs=s+”Str(pos)EndIfEndIfNextjNextiLabel1.Caption”位置变化情况：”sFori1TonList2.AddItemStr(a(i)NextiEndSub,【例4解题】本题考查冒泡排序，其算法核心是：n个数排序就是寻找n1个最值的过程，寻找最值的过程就是从最后一个位置开始，逐个往前，相邻的两个数依次比较，让最值自动冒上来，比较规则就是，如果后面的数大就交换两者的值。识记口诀：(1)交换算法，易知应该改为ka(j1)。(2)以pos值为5、第一趟排序为例：,排序n1趟，每趟从后往前比，相邻两个比，大小不对就交换。,至此，第一趟排序结束，我们看到最小值23已经位于第一个位置了，同时经过第一趟排序，pos的值被更新为6。其它排序趟，可比照进行。程序错误第二处，因为Else是除posj的所有情况都包括进来，每次j变化(即每次比较)都重新将pos赋值为j，显然违背题意。故应该改为ElseIfposj1Then。【答案4】(1)_(2)_,(1)ka(j1),Elselfposj1Then(其中posj1可用其他等价表达式),【例5】2015.10浙江选考n个数据的冒泡排序需要经过n1遍加工，每一遍加工自下而上比较相邻两个数据，把较小者交换到上面。小刘发现：当某一遍加工过程中没有数据交换，说明数据已经有序，无需进一步加工。为此，小刘对算法进行优化，编写了一个VB程序，功能如下：运行程序时，在列表框List1中显示排序前数据，单击“排序”按钮Command1，在列表框List2中显示这些数据按升序排序后的结果，在标签Label3中显示排序过程的加工遍数。运行效果如图所示：,实现上述功能的VB代码如下，但加框处代码有错，请改正。Dima(1To8)AsIntegerDimnAsIntegerPrivateSubForm_Load()n8，排序前数据存储在数组a中，并在列表框Listl中显示代码略,EndSubPrivateSubCommand1_Click()DimflagAsBooleanflag值为True表示一遍加工中发生过交换i1flagTrueDoWhile(1)flagFalseForjnToi1Step1Ifa(j)a(j1)Thenka(j)：a(j)a(j1)：a(j1)kflagTrueEndIfNextjii1LoopLabel3.Caption”排序过程的加工遍数为”(2)Fori1TonList2.AddItemStr(a(i)NextiEndSub,ia(p)Thenpm,【例3解题】本题考查选择排序的核心代码：寻找最小值或最大值。题中要求是_排序，即从小到大排序，因此每一遍选择排序找的都是剩下元素里的最_值。变量p记录当前找到的最小值的位置，即数组元素的下标，则a(p)就是当前找到的最小的数组元素。它的思想方法是先假设数组的第m项是最小的(第m遍排序)，因此p记为m，然后把从第m1项开始的所有数组元素跟a(p)进行比较，如果比a(p)小，则用p记录该元素的下标。这样循环结束后，变量p中存储的就是数组中从第m项至第8项的最小元素的下标，a(p)就是第m项至第8项中的最小元素。【答案3】_,B,升序,小,【例4】浙江高考下列VB程序段是选择法排序程序的主要部分。其中虚线框内代码用于寻找数组元素d(i)到d(n)的最小值。Fori1Ton1IfikThenktd(i):d(i)d(k):d(k)ktEndIfNextI框内代码运行结束时，保存最小值的数组元素一定是()Ad(n)Bd(j)Cd(i)Dd(k),k=1Fprj=i+1TonIfd(j)maxThenmax=a(i),【例5解题】本题考查选择排序的核心代码：寻找最小值或最大值。它的思想方法是先假设数组的第一项是最大的，并赋值给变量max，然后把从第二项开始的所有数组元素跟变量max进行比较，如果比max大，则把该元素赋值给max。这样循环结束后，变量max中存储的就是该数组中的最大值。循环6次以后，也就是比较了6次，max中存储的应该是前7个数中的最大值，也即78。【答案5】_,C,【例6】编写VB程序，实现如下功能：单击“排序数组a”按钮Command1时，对已有数组a的数据进行升序排列，并显示在文本框Label1中；单击“显示数组b”按钮Command2时，将升序数组b的数据显示在文本框Label2中；再单击“合并a和b”按钮Command3时，对数组a和数组b升序合并到字符串中，将合并后的数据在文本框Label3中显示。(运行效果如图所示)。实现上述功能的VB代码如下，请在划线处填入合适代码。,Dima(1To6)AsIntegerDimb(1To6)AsIntegerPrivateSubCommand1_Click()对数组a中的数据进行排序DimiAsInteger,jAsInteger，kAsIntegera(1)53：a(2)18：a(3)62：a(4)22：a(5)6：a(6)25s”Fori1To5,kiForji1To6Ifa(k)a(j)Then_NextjIfikThenta(k):a(k)a(i):a(i)tEndIfNextiFori1To6ssStr(a(i)NextiLabel1.CaptionsEndSubPrivateSubCommand2_Click()b(1)3:b(2)8:b(3)15:b(4)27:b(5)38:b(6)49此处部分代码省略EndSubPrivateSubCommand3_Click(),将数组a和b中的数据逐个比较后添加到新的字符串s中，并将s在Label3中显示i1:j1:s”DoWhilei6_j6如果两数组都还有数据未合并If_ThenssStr(a(i):ii1ElsessStr(b(j):jj1EndIfLoopDoWhilei6只有数组a还有数据未合并ssStr(a(i):ii1LoopDoWhilej6只有数组b还有数据未合并ssStr(b(j):jj1LoopLabel3.CaptionsEndSub,【例6解题】本题考查选择排序的思想方法和程序实现。【答案6】_,kj,And,a(i)aAndcAAndcaAndcAAndcZ)r_(2)_cMid(s，r,1)Looppr,EndIfList1.AddItemMid(s,1，p)totaltotal1s_(3)_LoopList1.AddItemstotaltotal1Label1.Caption共Str(total)行EndSub,【例3解题】本题考查对字符串的处理能力及自然语言到程序语言的转换能力。解题技巧是大致阅读程序语言，把程序语言与自然语言描述的算法步骤一一对应起来，再把相关步骤转换成VB语言。对应算法的第(1)步即“将文本框中的字符串保存到变量s中”。从定义可知s是String字符串类型，Text1中英文文本也是字符串，所以可以直接赋值，而不需要Val()函数转换。对应算法的第(2)步第点的后半部，即“否则，向左逐个查找，直至找到第一个非英文字母，将其位置作为分行位置p”。所以r控制向左逐个查找，即rr1。对应算法的第(2)步第点，即“将s中未分行部分重新赋值给变量s”。从前一句List1.AddItemMid(s,1，p)可知，已经把字符串s中1p号字符作为一行输出到列表框中，所以未分行部分应该是从p1开始到最后的。【答案3】(1)_(2)_(3)_,Text1.Text,r1,Mid(s，p1，Len(s)p)或Mid(s，p1)或Right(s，Len(s)p),【例4】浙江高考要求从某一字符串中删除指定的字符(假设所含的英文字母均为小写字母)，并将处理后的字符串重新输出。程序界面如图所示，在文本框Text_1中输入原始字符串，在文本框Text_2中输入需要删除的字符，单击“删除此字符”按钮(Command1)后，在文本框Text_3中输出处理后的结果。,解决此问题的算法流程图如图所示，相应的VisualBasic程序如下：DimpAsString,kAsStringPrivateSubCommand1_Click()DimsAsInteger,resultAsString,flagAsBooleanresult”pText_1.TextkText_2.TextFors1ToLen(p)flagf(s)IfNotflagThen,resultresult_EndIfNexts_EndSubFunctionf(sAsInteger)AsBooleanIfMid(p,s,1)kThenfTrueEndFunction(1)解决此问题的算法是_(选填：顺序查找/对分查找)。在程序和划线处，填入适当的语句或表达式，把程序补充完整。(2)程序中划线处应填入_。(3)程序中划线处应填入_。,【例4解题】本题考查顺序查找的思想方法和程序实现。顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定值相等，则查找成功；反之，查找不成功。(1)本题中的查找范围是字符串p中的所有字符，查找关键字是字符k，通过顺序查找的方法(Fors1ToLen(p)，逐个比较字符k和字符串p中的字符。(2)函数f(s)是判断字符串p中第s个字符是不是要找的字符k，如果是则返回True，不是则返回False，如果notflagTrue，即当前查到的第s个字符不等于k，则将该字符加入字符串变量result中。因此程序中划线处应填当前查到的第s个字符即Mid(p，s,1)。(3)根据流程图所示，循环结束时应该输出result，在文本框Text_3中输出，因此该处填Text_3.Textresult。【答案4】(1)_(2)_(3)_,顺序查找,Mid(p，s，l),Text_3.Textresult,微专题四枚举算法与顺序查找的辨析,本节要求掌握对分查找算法的基本思想，掌握对分查找算法的程序实现要点，学会编写简单的对分查找的程序。掌握对顺序查找与对分查找次数的估算。对分查找算法在历次考试中出现的概率为90%以上，考查方式为选择题与非选择题。,第六节对分查找算法及程序实现,1对分查找的概念对分查找又称二分查找，是一种高效的查找方法。对分查找的前提是，被查找的数据序列是有序的(升序或降序)。对分查找的基本思想是在有序的数列中，首先将要查找的数据与有序数列内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则就根据数据的有序性，再确定该数据的范围应该在数列的前半部分还是后半部分；在新确定的缩少范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，如果要查找的数据不存在，即查找不成功。2对分查找的过程若key为查找键，数组d存放n个已按升序排序的数据。在使用对分查找时，把查找范围i，j的中间位置上的数据d(m)与查找键key进行比较，结果必然是如下三种情况之一：(1)若keyd(m)，由与(1)相同的理由，必须在新的范围(m1，j)中继续查找。这样，除了出现情况(2)，在通过一次比较后，新的查找范围将不超过上次查找范围的一半。,中间位置数据d(m)的下标m的计算方法：,m=(i+j)2或m=Fix(i+j)/2),以规模为16的递增数组d为例，观察对分查找的过程。要查找的数据key为37。,3对分查找算法的表示使用对分查找在数组变量d中查找key，用自然语言描述的算法如下：(1)(确定初始查找范围)i1，jn。(2)(是否能继续查找？)如果ij，那么转到(4)。(3)(找不到)输入出结果0，算法结束。(4)(计算中点位置)m(ij)2。(5)(相等？)如果d(m)key，那么转到(7)。(6)(修改查找范围)如果keyd(m)，那么jm1；否则im1，转到(2)。(7)(找到)输出结果m，算法结束。使用流程图描述对分查找的算法如图所示：,4对分查找算法程序的实现要点(1)由于比较次数难以确定，所以用Do语句来实现循环；(2)在Do循环体中用If语句来判断查找是否成功；(3)若查找成功则输出查找结果，并结束循环(ExitDo)；(4)若查找不成功，则判断查找键在数组的左半区间还是右半区间，从而缩小范围。对分查找的程序结构如下(升序序列)：,对分查找程序的基本框架：,PrivateSubCommand1_Click()i1:jnDoWhileijm(ij)2Ifd(m)KeyThen输出结果，退出查找(代码略)ElseIfKeyd(m)Thenjm1Elseim1EndIfLoopEndSub,5查找次数的估算对规模为n的数组进行对分查找时，无论是否找到，至多进行log2n1(log2n表示大于或等于log2n的最小整数)次查找就能得到结果，而使用顺序查找算法，在最坏的情况下(查找键在最后一个或没找到)，需要进行n次查找，最好的情况是一次查找(查找键在第一个)，平均查找次数是。,【例1】浙江高考下列有关查找的说法，正确的是()A顺序查找时，被查找的数据必须有序B对分查找时，被查找的数据不一定有序C顺序查找总能找到要查找的关键字D一般情况下，对分查找的效率较高,【例1解题】本题考查顺序查找和对分查找算法的辨析。顺序查找算法对被查找数据没有要求，也就是说数据有序无序均可；对分查找算法要求被查找数据必须有序，这个有序既包括升序也包括降序；在被查找数据量非常大的情况下，一般是对分查找比顺序查找效率高，但是在特殊情况下，如果要查找的关键字恰好排在被查找数据的首位，那么利用顺序查找速度要快。【答案1】_,D,【例2】2016浙江模拟某数组有10个元素，依次为11、21、35、44、51、64、78、81、92、98，若采用对分查找法在该数组中查找数据92，依次被访问的数据为()A51、81、92B51、78、81、92C64、81、92D64、81、98、92,【例2解题】共有10个数，首先查找到的是第5个数51，其次分别是81、92。【答案2】_,A,【例3】2016.4浙江选考已知一无序数组a(下标1到n)，通过引入数组b(下标1到n)，使得a(b(1)a(b(2)a(b(3)a(b(n)(示例如图所示)，对这些有序数据可进行对分查找。则第一次查找时，中点位置m与中点值分别是(),Am的值是Fix(1n)/2)，中点值是a(m)Bm的值是Fix(1n)/2)，中点值是a(b(m)Cm的值是Fix(b(1)b(n)/2)，中点值是a(m)Dm的值是Fix(b(1)b(n)/2)，中点值是a(b(m),【答案3】_,【例3解题】本题考查对分查找的灵活运用及变化。理解对分查找的两个要素：对分查找仅仅是查找数据而不是改变数组中元素位置，因此和前面排序不同，没有数据交换；对分查找的前提条件是“数据是有序”的，因此，在这个前提下进行的对分查找，每次查找可以“缩小一半的数据区域排查范围”。这两点是理解此题关键，也是对分查找的核心。由题图可知：,B,下面模拟一下第1次查找：由题中数据可知，使用对分查找第1次查找时，对下标而言：kFix(15)/2)(或(15)2)，其中k3，b(k)5，a(b(k)67，因此中点值为67。,【例4】2015.10浙江选考已知单调函数f(x)在0,1区间存在一个x0，使f(x0)0。现用对分查找法搜索x0的值，开始搜索区间为0,1，若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为()A1/2B1/10C1/102D1/210,【例4解题】本题考查对分查找区间长度。在0,1区间内查找一个数，第一次取0,1区间中间0.5，如果f(0.5)0，则第二次区间为0.5,1；如果f(0.5)0，则第二次区间为0，0.5，每次都减少为原来的1/2。第三次查找的区间长度为原来的1/4，依次类推，第11次查找的区间长度为1/210。【答案4】_,D,【例5】2016.10浙江选考某对分査找算法的VB程序段如下：i1：j9：n0keyVal(Textl.Text)DoWhileijnn1mFix(ij)/2)Ifkeyd(m)ThenExitDoExitDo表示退出循环Ifkeyd(m)Thenjm1Elseim1Loop数组元素d(1)到d(9)的值依次为“7,12,18,25,39,58,61,72,86”。若该程序段运行结束后，n的值为2，则key的值是()A39B18或61C18或72D12或61,【例5解题】本题考查对分查找。本题中9个数据，i的初值为1，j的初值为9，第一次找到的数必定是m5时，即d(5)39，现因n2，说明循环了2次即成功。那么第一次查找d(5)39肯定不是key的值，进行第二次查找，有两种可能，其一，当key值小于39时，那么i1不变，j514，那么mFix(ij)/2)2。(注意，Fix函数是截掉小数部分，保留整数部分，与Int函数功能不同！)，所以d(2)12为key值。其二，当key值大于39时，那么im16，j9不变，那么新的mFix(69)/2)7，所以d(7)61为key值。【答案5】_,D,【例6】2015.9浙江模拟编写VB程序，实现如下功能：在文本框Text1中输入一个整数，单击“查找删除”按钮Command1，采用对分查找法在数组A(从小到大排列，并显示在标签Label1中)中查找该数。若找到，则从数组A中删除该数(该数后面的数组元素都前移一位)，并在标签Label2中显示删除后的结果(运行效果如图所示)；否则，在标签Label2中显示“该数没有找到”。,实现上述功能的VB代码如下，但加框处代码有错，请改正。DimA(1To10)AsInteger用于保存10个按从小到大顺序排列的整数Form_Load事件过程产生10个整数，按升序保存在数组A中，并在标签Label1中显示