浙江版信息技术高考总复习专题六算法的程序实现(讲解练)教学讲练

1、专题六算法的程序实现技术 浙江专用考点一解析算法及程序实现考向基础1.解析算法的基本思想用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式,并通过数学表达式的计算来实现问题的求解。如:已知圆的半径为r,求圆的面积s,则可通过公式s=3.14*r*r计算得到。2.解析算法的程序实现(1)分析问题,建立正确的数学模型,找到数学计算式或数学算法。要注意的是,有些问题能找到一个明确的公式,但是有些问题可能是一个运算过程,比如除二倒取余法求二进制,辗转相除法求最大公约数等问题。考点清单(2)将数学计算或数学算法转化为VB运算过程。考向突破解析算法一般难度不大,重点题型是各种进制之间的相互转

2、换。例1将十进制数转化为二进制数的VB 程序段如下:Dim y As Integer, s As String, r As Integery=Val(Text1.Text)输入十进制数s= Do While y 0LoopText2.Text=s显示二进制数方框中的代码由以下三部分组成:s=Str(r)+s y=y2r=y Mod 2代码顺序正确的选项是()A.B.C.D.解析本题采用“除2取余法”将十进制转换成二进制,先求余数(Mod运算)并保存,再求商(整除 ),商用来下一次求余数。重复执行该过程直到商为0。答案D例2辗转相除法是数学史中著名的算法,用于计算两个正整数a和b的最大公约数。步

3、骤如下:现编写程序,在文本框Text1和Text2中输入a和b,在文本框Text3中输出两数的最大公约数。代码如下:Private Sub Command1_Click()Dim a As Integer, b As Integer, r As Integer变量ab余数初始值24159第一次辗转1596第二次辗转963第三次辗转630余数为0时终止,最大公约数为3a=Val(Text1.Text)b=Val(Text2.Text)r=a Mod bDo Whilea=bb=rr=a Mod bLoopText3.Text=End Sub解析循环结束条件是r=0,因此循环条件是r0 或 r0。

4、退出循环后,结果存在变量b中。答案r0str(b)考点二枚举算法及程序实现考向基础1.枚举算法的基本思想将问题的可能解一一列举,逐个判断,找到所有符合条件的解。即使中途找到符合的解也要继续找下去,要将所有可能解找完才结束。设计枚举算法时要尽量减小罗列范围(提高算法的效率),不能遗漏,也不能重复。2.枚举算法的程序实现根据枚举算法的主要思想:一一列举,逐个判断。因此一般情况下枚举算法的代码具有以下特点:(1)用循环语句在一定范围内列举所有可能的解。(2)用选择语句判断和选择真正的解。枚举算法的一般格式:For(列举所有可能的解)If可能解是正确解Then输出该解或计数Next注意:循环语句不一定

5、用For语句,也可用Do语句。3.多变量列举某些枚举算法的问题比较复杂,可能有多个变量需要列举,此时就需要多重循环,也即循环嵌套。格式如下:For(列举变量1所有可能的解)For(列举变量2所有可能的解)If该组解是正确解Then输出该组解或计数NextNext如鸡兔同笼问题、百鸡百钱问题等。在设定多个变量的列举范围时,可以利用验证条件,尽可能缩小列举范围,减少列举变量,从而减少循环的嵌套。如百鸡百钱问题:100元钱买100只鸡,公鸡5元一只,母鸡3元一只,小鸡1元3只。则代码如下:For x=1 To 100For y=1 To 100For z=1 To 100If x+y+z=100 A

6、nd 5*x+3*y+z/3=100Then输出该组解或计数Next zNext yNext x利用验证条件,代码可优化为:For x=1 To 20公鸡最多不超过20只For y=1 To 33母鸡最多不超过33只z=100-x-yIf 5*x+3*y+z/3=100 Then输出该组解或计数Next yNext x例寻找3位的水仙花数。什么是水仙花数?水仙花数是指一个 n 位数(n3),它的每一位上的数字的 n 次幂之和等于它本身。例如153是水仙花数,因为13+53+33=153。解决此问题的Visual Basic程序如下,程序界面如图所示,在列表框List1中输出结果。在(1)和(2

7、)划线处,填入合适的语句或表达式,把程序补充完整。Private Sub Command1_Click()Dim i As IntegerDim a,b,c As IntegerFor(1)a=i100b=i10 Mod 10c=i Mod 10If(2) Then List1.AddItem Str(i)NextEnd Sub(1)程序中划线处(1)应填入。(2)程序中划线处(2)应填入。解析(1)枚举算法在列举的过程中,不能遗漏任何一个可能的解,寻找3位的水仙花数,100到999都是可能解。因此列举所有可能解的语句应该是For i=100 To 999。(2)If语句用于检验当前列举的可能

8、解i是不是正确解。水仙花数的验证条件:它的每一位上的数字的n次幂之和等于它本身,本程序要求找出3位的水仙花数,因此n=3,变量a、b、c是i的百位、十位和个位上的数字,因此验证条件是a3+b3+c3=i。答案(1)i=100 To 999(2)a3+b3+c3=i考向突破从目前出现的真题看,直接考枚举算法的不多,常考字符串的处理,一般题型为:输入一串字符串,字符串中有一些特殊字符做为间隔符号,利用该间隔符号,将字符串中的字符提取,并作进一步的数据分析或处理。从代码特点和思想方法上分析,该类问题也利用了枚举算法的思想。一、字符串问题相关知识1.字符大小的比较字符(包括字符串)在计算机中存储的是每

9、个字符的内码值。字符比大小实际上是比较字符的ASCII码值。如“a”“b”,“ab”“abc”,“abc”“abd”,“acde”=“a” And ch=“A” And ch=“0” And ch=“A” And ch=“a” And ch=“A” And ch=“a” And ch=“z”)4.字符转换二、字符串基本操作1.判断是否对称f=truen=Len(s)For i=1 To n2If Mid(s,i,1)Mid(s,n-i+1,1) Then功能表达式大写转小写Chr(Asc(ch)+32)小写转大写Chr(Asc(ch)-32)求字母的字母序小写字母:Asc(ch)-96或Asc

10、(ch)- Asc(“a”)+1大写字母:Asc(ch)-64或 Asc(ch)- Asc(“A”)+1f=false:Exit ForEnd IfNext i最后判断f的值,如果是true,则对称,否则不对称。2.字符串反转n=Len(s)For i=1 To ns1=Mid(s,i,1)+s1Next i得到的字符串s1是s的反串。3.插入字符串在字符串s中,在第n个位置插入字符串c:s1=Mid(s,1,n-1)+c+Mid(s,n,Len(s)-n+1)如s=“hppynewyear”,n=2,c=“aa”,则s1=“haappynewyear”。4.删除字符串在字符串s中,删除子串s

11、1:i=1Do While i=A And ch=a And ch=0 And ch = 9 Thenp =Elset=p = 0If ch = - Thenflag = -1Else If ch = + Thenflag = 1End IfEnd IfNext iLabel1.Caption = Str(t)End Sub(3)若文本框Text1中输入内容的结束符“=”缺失(即输入内容为12+28-15+50),单击“计算”按钮后, 标签Label1上显示的内容是。解析本题的解题关键在于理解非数字字符的操作。For语句遍历字符串值,If语句判断字符类型。(1)略。(2)分析判断条件可知,要执

12、行数字相连。原值p乘10加新出现的值Val(ch)组成新值。非数字符号出现,要把前值放入累加器t中,flag存放前值符号,因此要累加flag*p。(3)由于“=”缺失,造成最后一个数50没有被累加。答案(1)C (2)p*10 + Val(ch) t + flag*p(3)25考点三排序算法及程序实现考向基础1.冒泡排序的基本思想把待排序的n个元素的数组看成是垂直堆放的一列数据,从最下面的一个元素起,自下而上地比较相邻的两个元素中的数据,将较小的数据换到上面。重复这一过程,直到处理完最后两个元素中的数据,称为一遍加工。第一遍加工完成后,最小的数据已经上升到第一个元素的位置。然后对余下的n-1个

13、元素重复上述处理过程,直至最后进行余下两个数据的比较和交换。n个数需要n-1遍排序。以数据130,20,98,15,67,3为例,从小到大冒泡排序的操作过程如下:原始数据130209815673第1遍排序后313020981567第2遍排序后315130209867第3遍排序后315201306798第4遍排序后315206713098第5遍排序后3152067981302.冒泡排序的程序实现For i=1 To n-1n个数需要n-1遍排序For j=n To i+1 Step -1从后往前,两两比较,直到a(i+1)和a(i)比较完If a(j)a(j-1) Then比较相邻的两个数tem

14、p=a(j-1):a(j-1)=a(j):a(j)=temp小的数在后面,则交换End IfNext jNext i外循环“For i=1 To n-1”中的变量i表示第i遍冒泡排序,n个数需要n-1遍排序。由内循环“For j=n To i+1 Step -1”可看出,冒泡比较的方向是从后往前,两两比较,第i遍的比较次数是n-i次,交换次数最多是n-i次,交换次数最少是0次。从小到大排序(升序),If语句中条件表达式为:a(j)a(j-1)。例1有如下程序段:For i=1 To 2For j=5 To i+1 Step -1If a(j)a(j-1) Then t=a(j):a(j)=a(

15、j-1):a(j-1)=tNext jNext i数组元素a(1)到a(5)的值依次为“95,88,66,80,75”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为()A.66,75,95,88,80B.66,75,80,95,88C.95,88,66,80,75D.95,88,80,75,66解析此题为冒泡排序,升序排序,排序两遍。答案为A。答案A3.选择排序的基本思想在所有的元素中选出最小(大)的数据,把它与第一个数据交换,然后在其余的元素中再选出最小(大)的数据与第二个数据交换。以此类推,直至所有数据排序完成。n个数需要n-1遍排序。以数据130,20,98,15,67,

16、3为例,从小到大选择排序的操作过程如下:原始数据130209815673第1遍排序后320981567130第2遍排序后315982067130第3遍排序后315209867130第4遍排序后315206798130第5遍排序后3152067981304.选择排序的程序实现选择排序的代码如下:For i=1 To n-1k=iFor j=i+1 To nIf a(j)a(k) Then k=jNext jIf ki Thentemp=a(i):a(i)=a(k):a(k)=tempEnd IfNext i外循环“For i=1 To n-1”中的变量i表示第i遍选择排序,n个数需要n-1遍排序

17、。矩形框内代码用于寻找数据元素a(i)到a(n)的最小值,变量k记录当前找到的最小值的位置,即数组元素的下标,则a(k)就是当前找到的最小的数组元素。它的思想方法是先假设数组的第i项是最小的(第i遍排序),因此k记为i,然后把从第i+1项开始的所有数组元素跟a(k)进行比较,如果比a(k)小,则用k记录该元素的下标。这样循环结束后,变量k中存储的就是数组中从第i项至第n项的最小元素的下标,a(k)就是第i项至第n项中的最小元素。从小到大排序(升序),If语句中条件表达式为:a(j)a(k)。例2对下列一组原始数组:13,15,2,11,8,18 进行选择排序,第一遍排序结束,数组的状态不可能是

18、()A.2,15,13,11,8,18B.18,15,2,11,8,13C.13,15,2,11,18,8D.13,15,18,11,8,2解析本题考查选择排序的思想方法。选择排序算法第一遍一定会把最大或最小的数交换到最前或最后,其他数据不动。因此答案为C。答案C例3用选择排序法对一组学生的身高数据进行升序排序,已知第一遍排序结束后的数据序列为165,168,178,175,171,则下列选项中可能是原始数据序列的是()A.175,178,168,165,171B.178,168,165,175,171C.165,178,168,175,171D.165,168,171,175,178解析第一

19、遍排序后排第一位的165有5种可能的来源,原来就在第一位,不需要数据互换,那么原始数据就是165,168,178,175,171;从第二位换来,那么原始数据就是168,165,178,175,171;从第三位换来,那么原始数据就是178,168,165,175,171;从第四位换来,那么原始数据就是175,168,178,165,171;从第五位换来,那么原始数据就是171,168,178,175,165。答案B5.冒泡排序与选择排序的比较 冒泡排序选择排序思想方法一边比较,一边交换先选出最大值或最小值,再交换相同点n个数都需要n-1遍排序,其中变量i控制排序的遍数比较的次数一样多,都是(n-

20、1)+(n-2)+3+2+1次最好的情况下,交换的次数一样,都是0次不同点边比较边交换,最坏的情况下交换的次数是(n-1)+(n-2)+3+2+1次先选择再交换,最坏的情况下交换的次数是n-1次如何区分交换两个变量的代码在内层循环内交换两个变量的代码在内层循环后,外层循环内例4某校通过政府招投标中心采购一套多媒体教学设备,有5家单位参加竞标,竞标价分别为19万、15万、21万、13万、12万元人民币。若采用选择排序算法对标价从大到小排序,需要进行数据互换的次数是()A.1B.2C.3D.4解析原始数据为19、15、21、13、12,第一遍排序19与21互换,得到21,15,19,13,12;第

21、二遍排序15与19互换,得到21,19,15,13,12;第三遍排序与第四遍排序都不需要数据互换。因此总共是2次数据互换。答案B例5有如下VB程序段:a(1)=44: a(2)=36: a(3)=58: a(4)=65: a(5)=12b=0:c=0For i=1 To 4k=iFor j=i+1 To 5If a(j) a(k) Then k=j: b=b+1Next jIf k i Thent=a(i): a(i)=a(k): a(k)=t:c=c+1End IfNext iText1.Text=Str(b)+Str(c)该程序段执行后,文本框Text1显示的内容是()A.53B.44C.

22、43D.34解析本题首先要理解变量 b和变量 c的含义。变量 b 表示每遍排序a(j)值比a(k)小的次数,变量 c 表示数据交换的次数。第一遍排序 k=1,a(2)a(k),k=2;a(5)a(k),k=5;然后a(1)与a(5)交换。b=2,c=1。第二遍排序 k=2,后面没有数比a(k)小,也没有数据交换。第三、四遍排序同理,最终b=4,c=3。答案C考向突破1.冒泡排序算法的变形标准写法:For i=1 To n-1n个数需要n-1遍排序For j=n To i+1 Step -1从后往前,两两比较,一直到第i+1个数If a(j)a(j-1) Then比较相邻的两个数temp=a(j

23、-1):a(j-1)=a(j):a(j)=temp小的数在后面,则交换End IfNext jNext i排序思想解析:n个数需要n-1遍排序;每一遍排序都是从最后一个数开始,两两比较,小的数换到前面,大的数换到后面;第一遍把最小数推到了第一个位置,第二遍把第二小的数推到了第二个位置,。因此排序过程中,数据是从前往后依次排好的。(1)变形一For i=1 To n-1For j=n-1 To i Step -1If a(j+1)a(j) Thentemp=a(j+1):a(j+1)=a(j):a(j)=temp End IfNext jNext i排序思想解析:与标准形唯一的差异就是两个比较项

24、从a(j-1)和a(j)变成a(j+1)和a(j),因此循环语句也从“For j=n To i+1 Step -1”变成了“For j=n-1 To i Step -1”,而程序在执行过程中没有任何差别,与标准形是完全一样的。(2)变形二For i=1 To n-1For j=1 To n-iIf a(j+1)a(j) Thentemp=a(j+1):a(j+1)=a(j):a(j)=temp End IfNext jNext i排序思想解析:跟标准形不一样的是本代码中每一遍冒泡是从前往后两两比较的,因此每一遍排序达到的效果是把最大值推到了最后面。第一遍排序后,最大值就到了最后位置,第二遍后,

25、次大值就到了倒数第二个位置,。因此排序过程中,数据是从后往前依次排好的。(3)变形三For i=1 To n-1For j=i+1 To 2 Step -1If a(j)a(j-1) Thentemp=a(j):a(j)=a(j-1):a(j-1)=temp End IfNext jNext i排序思想解析:第一遍,2号和1号元素比较并交换;第二遍,从3号元素开始往前比较并交换,直到1号元素;第三遍,从4号元素开始往前比较并交换,直到1号元素;。最后同样达到排序效果。如有5个数:4、3、1、5、2,第一遍后为:3、4、1、5、2;第二遍后为:1、3、4、5、2;第三遍后为:1、3、4、5、2;

26、第四遍后为:1、2、3、4、5。需要注意的是,当某一遍排序过程中没有数据交换时,不代表所有数据已经有序,这点跟标准冒泡排序不同。(4)变形四For i=1 To n-1For j=i+1 To nIf a(j)a(i) Thentemp=a(j):a(j)=a(i):a(i)=temp End IfNext j Next i排序思想解析:在第i遍排序中,把第i+1到第n个数依次与a(i)比较,如果比a(i)小,则交换。它的最大特点是:所有数据跟某个位置上的数去比较。如第1遍排序时,所有数都跟a(1)比较;第2遍排序时,所有数都跟a(2)比较;以此类推。排序过程中,数据是从前往后依次排好。(5)

27、冒泡排序的错误变形For i=1 To n-1For j=i To n-1If a(j+1)= 2 And Not flagIf a(j) a(j - 1) Thent = a(j): a(j) = a(j - 1): a(j - 1) = tflag = TrueEnd Ifj = j - 1LoopNext i数组元素 a(1)到 a(8)的初值依次为“8,2,7,10,6,9,5,3”,则程序运行后,元素 a(1)到 a(8)的值依次为()A.2,7,8,10,6,9,5,3B.10,8,7,2,6,9,5,3C.2,3,5,8,6,7,10,9D.2,3,5,6,7,8,9,10解析程

28、序用了第3种冒泡排序的变形,数组中只有前4个数参与了排序,从小到大升序,后4个数不动,程序运行后元素为:2,7,8,10,6,9,5,3。答案A2.选择排序算法的变形选择排序的变形考法较少。选择排序的变形:For i=1 To n-1k=IFor j=n To i+1 Step -1If a(j)a(k) Then k=jNext jIf ki Thentemp=a(i):a(i)=a(k):a(k)=tempEnd IfNext i排序思想解释:在每一遍找最小值时,从前往后的比较改为从后往前的比较,其他没有变化。选择排序的错误变形:For i=1 To n-1k=iFor j=i+1 To

29、nIf a(j)a(i) Then k=jNext jIf ki Thentemp=a(i):a(i)=a(k):a(k)=tempEnd IfNext i错误原因分析:在选择最小值的过程中把第i+1到第n个数依次与a(i)比较,“If a(j)a(i) Then k=j”,如果a(j)比a(i)小,则用变量k记录j的位置,但是a(j)与a(i)并未交换。这种方法是找不到最小值的位置的。比如有如下数据:5,2,1,3,4,第一遍排序i=1时比较过程如下:a(2)a(1),因此k=2;a(3)a(1),因此k=3;a(4)a(1),因此k=4;a(5)a(1),因此k=5。这一遍循环的结果是k=

30、5,没有找到最小值所在的位置(最小值位置应该是3),原因就是a(1)的值没有变过。3.冒泡排序算法的优化当某一遍排序过程中没有数据交换,说明数据已经有序,无需进行下一遍排序。代码如下:Dim flag As Booleanflag值为True表示某遍排序中发生过交换i = 1flag = TrueDo Whilei = n - 1 Or flag = True flag = False For j = n To i + 1 Step -1If a(j) a(j - 1) Then k = a(j): a(j) = a(j - 1): a(j - 1) = k flag = TrueEnd If

31、Next ji = i + 1Loop思想解析:用一个逻辑变量flag标记某一遍排序过程中是否有数据交换,如果没有,则无需再进行下一遍排序。排序遍数是i-1遍。另一种写法:Dim flag As BooleanFor i=1 To n-1flag=FalseFor j=n To i+1 Step -1If a(j)a(j-1) Thenk=a(j):a(j)=a(j-1):a(j-1)=kflag=TrueEnd IfNext jIf flag=False Then Exit ForNext i注意这种写法的排序遍数是i,因为程序从中间跳出循环,不执行“Next i”指令,因此没有多加一次。4

32、.选择排序算法的优化在数组的所有元素中同时找出最小和最大的元素,然后将这两个元素分别与第一个和最后一个元素交换数据,在余下的元素中找出最小和最大数据的元素,分别与第二个和倒数第二个元素交换数据,以此类推,直到所有元素的数据按升序排列。代码如下:p = 1: q = 10Do While p qiMin = p:iMax = pFor i = p + 1 To qIf a(i) a(iMax) Then iMax = iNext it = a(iMin): a(iMin) = a(p): a(p) = tIf iMax = p Then iMax = iMint = a(iMax): a(iMa

33、x) = a(q): a(q) = tp = p + 1q = q - 1Loop普通的选择排序是从头到尾一个方向的,优化后的排序是从两端往中间同时进行,一端从小到大排,另一端从大到小排,变量p和q表示本次排序的范围(p前和q后的数据已经完成排序)。For语句找出本次排序的最小数a(iMin)和最大数a(iMax),然后将a(iMin)与a(p)交换,将a(iMax)与a(q)交换。由于找最小数和最大数时,一开始都假定了p位置上的数是最小值和最大值,如果本次找到的最大值在p位置,那么当a(p)和a(iMin)交换以后,最大值a(p)就被换到iMin的位置。因此当iMax=p时,在最小值交换完毕

34、后,再给i-Max赋值iMin。5.奇数偶数分开排序、素数合数分开排序、男生女生分开排序等问题解决这类排序问题的关键点是分析出需要交换的情况有哪些,比如要求奇数在前升序,偶数在后升序,则需要交换的情况有:小奇数在大奇数的后面;奇数在偶数的后面;小偶数在大偶数的后面。其他类似的排序问题也是同样的思路。例2(2018稽阳联谊学校联考,16,3分)有一组正整数,基于冒泡排序对其中的数进行升序排序。排序后奇数在前,偶数在后。排序示例如下:实现上述功能的VB程序如下,但加框处代码有误,请改正。Const n=10Dim d(1 To n) As IntegerPrivate Sub Command1_C

35、lick()Dim i As Integer, j As Integer, t As Integer读取一组正整数,存储在数组d中,代码略i=1Do While i d(i)Then(1)t=d(j): d(j) =d(j - 1): d(j - 1)=tEnd IfElse(2)t=d(j): d(j) =d(j - 1): d(j - 1)=tEnd IfNext ji=i + 1Loop依次输出排序后的数据,代码略End Sub解析本题考查冒泡排序的应用。与普通的冒泡排序不同之处在于,本题把奇数偶数分开从小到大升序排序。(1) If d(j) Mod 2=d(j-1) Mod 2表示d(

36、j)和d(j-1)的奇偶性相同,此时如果d(j)d(j-1),则交换两数。(2)此处说明d(j)和d(j-1)的奇偶性不相同,由于奇数偶数分开排序,奇数在前,偶数在后,因此只有当 d(j-1)是偶数而d(j)是奇数时,才需要交换两数的位置。因此此处条件设置为ElseIf d(j) Mod 2=1 And d(j-1) Mod 2=0 Then。当d(j-1)是奇数而d(j)是偶数时是不需要交换的。答案(1)d(j) d(j-1)(2)ElseIf d(j) Mod 2=1 And d(j-1) Mod 2=0 Then或其他等价的答案6.隔位排序偶数位置和奇数位置上的元素分别排序。例3有如下程

37、序段:For i=1 To 9For j=10 To i+2 Step -1If a(j) a(j-2) Thent=a(j): a(j)=a(j-2): a(j-2)=tEnd IfNext jNext i数组元素a(1)到a(10)的值依次为“10,9,8,7,6,5,4,3,2,1”,执行该程序段后,数组元素a(8)中的值为()A.7B.8C.9D.10解析本题考查冒泡排序。排序时隔位比较并交换,由“If a(j) a(j-2) Then”可知程序实现隔位递增排序,也即奇数位置的数和偶数位置的数分别从小到大排序,排序结果为“2,1,4,3,6,5,8,7,10,9”,答案为A。答案A考点

38、四查找算法及程序实现考向基础1.顺序查找的基本思想顺序查找的基本思想是从第一个数据开始,按顺序逐个将数据与查找关键词进行比较。若某个数据和关键词相等,则查找成功;如果所有的数据都比较过,没有一个数据和关键词相等,则查找不成功。2.顺序查找的程序实现假定在数组a中有n个数据,查找关键词是key。则顺序查找的代码如下:For i = 1 To nIf a(i)=key Then Exit ForNext i说明:For语句用于遍历整个数据源,从开始位置到结束位置。If 语句用于判断当前访问的元素是不是等于关键词。一旦某个位置的数据等于关键词,查找任务结束,通常用语句 Exit For 退出循环。退

39、出循环后,如果i的值大于n,则表示未找到。i=n是找到的情况,i的值就是关键词所在的位置。顺序查找不要求数据源是有序的。3.对分查找的基本思想在有序的数据列中,首先将要查找的数据与有序数组内处于中间位置的数据进行比较,如果两者相等,则查找成功;否则根据数组元素的有序性,可确定该数据在数组的前半部分还是后半部分。在新确定的范围内,继续按上述方法进行查找,直到找到要查找的数据,则查找成功,或直到子表不存在,则查找不成功。对分查找要求数据源必须是有序的。4.对分查找的程序实现对分查找的代码如下:key=Text1.Text输入关键词i=1:j=n设置首次查找的范围f=Falsef标志是否已经找到关键

40、词Do While(i=j)And Not f未找到并且查找范围还存在m=Fix(i+j)/2)计算中间位置If key=a(m) Thenf=True 相等表示找到了,将f设为TrueElseIf keya(m) Thenj=m-1下一次查找范围是前半部分Elsei=m+1下一次查找范围是后半部分End IfLoop说明:变量i和j记录每一次查找的起始位置和结束位置,变量m记录中间位置。如果keya(m),则下一次查找的范围是后半部分,因此j不变,i=m+1。退出Do循环有两种可能:第一种是f为True,说明已经找到关键词,此时结束查找;第二种是ij,查找的起始位置超过结束位置,说明已经找遍

41、数据源,但是找不到关键词,此时结束查找。例7位学生的身高(单位:cm)从高到低依次为:178,177,175,172,170,165,162。用对分查找法找到178的过程中,依次被访问到的数据是()A.178B.172,175,178C.172,177,178D.172,175,177,178解析本题主要考查对对分查找算法基本思想的理解。将7个数据从1到7进行编号。第一次访问到的数据是第4个,即172(中间位置m=Fix(1+7)/2)=4),178172,因此下一次查找的范围是前半部分,即第1个到第3个。因此第二次访问的数据应该是第2个,即177(中间位置m=Fix(1+3)/2)=2),1

42、78177,因此下一次查找的范围是前半部分,即第1个,因此第三次访问的数据是178。答案C考向突破1.对分查找的效率问题(1)对分查找的每一次查找,要么找到了目标,结束任务;要么通过比较中间值与关键词,将下一次的查找范围缩小一半,因此对分查找的效率往往高于顺序查找。对n个数据查找某个值,最多需要查找Int(log2n)+1次。(2)找不到关键词的情况下,最后一遍查找时,i=j=m,若keya(m),则i=m+1;若keya(m), 则j=m-1。这两种情况都得到i=j+1,即起始位置超过结束位置,则该遍查找结束后会退出循环。(3)计算中间值位置的式子有多种写法,不同写法,查找过程可能不同。实例

43、:a(1)到a(10)的值依次为2,7,8,10,12,13,16,18,19,20。公式查找过程m=(i+j)2 m=Int(i+j)/2)m=Fix(i+j)/2)m=Int(i+j+1)/2) m=Int(i+j)/2+0.5)m=(i+j)2If (i+j) Mod 2=1 Then m=m+1表中序号表示第几次找到该数。如果“If (i+j) Mod 2=1 Then m=m+1”写成“If j Mod 2=0 Then m=m+1”,查找过程可能也不同,要根据实际情况分析。例1有一个由4000个整数构成的顺序表,假定表中的元素已经按升序排列,采用对分查找查找一个元素,则最多需要次比

44、较就能确定是否存在所查找的元素。()A.11B.12C.13D.14解析本题主要考查对分查找的效率问题。根据对分查找的思想方法,每一次查找的结果要么是找到,要么是找不到,如果找不到则将下一次的查找范围缩小一半。最差的情况是数据源中没有查找对象,每次查找都将查找范围缩小一半。规模为n个数的数据源,使用对分查找时,最多经过Int(log2n)+1次查找。Int(log24000)+1=11+1=12。答案B例2使用对分查找算法在包含某个有序元素的数组中查找某值,下列说法错误的是(中括号表示向下取整)()A.第一次查找的位置一般是(1+n)/2B.在某连续的三次查找中,不可能是三个相邻的元素C.如果

45、找不到,那么最少需要查找log2n次D.如果找得到,那么最多需要查找log2n+1次解析比如5个元素的查找,第一次查找3号位置,第二、三次分别查找1号和2号位置,三者相邻。对分查找在找不到的情况下,最少也需要log2n次查找,相当于每次都在元素个数较少的一半中查找;选项D刚好相反,每次都在元素个数较多的一半中查找,但总次数不会超过log2n+1次。答案B2.对分查找中各个变量值的变化规律例3对数组a 中6 个有序数据“11,22,33,44,55,66”,用下面的程序代码查找数据“23”,程序执行完毕后,下列各变量值正确的是()Dim a(1 To 6)As IntegerDim i As I

46、nteger,j As Integer,Key As Integer,m As Integera(1)= 11:a(2)= 22:a(3)= 33: a(4)= 44:a(5)= 55:a(6)= 66i= 1:j= 6:p= 0:Key= 23Do While i=jp=p+1m=(i+j) 2If j Mod 2=0 Then m=m+1If a(m)= Key Then Exit DoIf Keya(m) Then j=m-1 Else i=m+1LoopA.i=5B.j=4C.m=3D.p=2解析本题主要考查对分查找。变量p是查找次数。第一次查找,i=1,j=6,m=(i+j)2=3,

47、而j Mod 2=0,因此m=m+1=4,2322因此i=m+1=3;第三次查找,m=(i+j)2=3,23j,整个查找过程结束,故C正确。答案C例4用对分查找算法在含有100个元素的无重复有序数组中查找某元素,已知第3次查找位置是62号元素,则第4次查找不可能是()A.第43号元素B.第56号元素C.第68号元素D.无需第4次查找解析本题考查对分查找算法的原理。100个有序元素中,第1次查找位置是50,第2次查找位置是25或75,根据题意第3次查找位置是62,说明关键词大于第50号元素,因此第4次不可能再去找50之前的元素,A不可能。第4次查找位置是62左右两段区间:51,61或63,74,

48、因此B和C可能。如果第3次找到的第62号元素就是关键词,则无需第4次查找,因此D可能。答案A3.在有相同项的数据源中找关键字找到最先出现的位置,代码如下:i = 1: j = nDo While ia(m) Theni = m + 1Elsej = m - 1End IfLoop说明:当keya(m)时,往后半部分查找;当keya(m)时,往前半部分查找;当key=a(m)时,仍然往前半部分查找,因此可以理解成是找到最先出现key的位置。退出循环时,如果key在序列中,则key等于最后一次的a(m),此时i=j=m,然后执行j=m-1,因此退出循环后,最先出现key的位置是i。如果key不在序

49、列中,则退出循环时a(j)keya(m)写成key=a(m),则当key=a(m)时,仍然往后半部分查找,因此是找到最后出现key的位置,退出循环时,j的位置是最后出现的位置。例5(2018 浙江“七彩阳光 ”联盟期初联考,11,2分)某对分查找算法的 VB 程序段如下:L = 1: R = 10: Key = 21Do While L = Rm = (L + R) 2If a(m) = Key ThenL = m + 1ElseR = m - 1End IfLoop数组元素 a(1)到 a(10)的值依次为“3,9,21,21,21,21,27,28,39,40”,执行该程序段,变量 R、a

50、(R)的值分别是()A.2,9B.3,21C.6,21D.7,27答案C本题考查对分查找。由于数列中有相同项,代码If a(m) = Key Then L=m+1,也即往后找相同项,直到找到最后一个相同项,因此Key=21时,找到第6项a(6)。例6有序(非降序)数组a有n个元素,用对分查找算法在数组a中查找key值所在的位置,如果有重复的元素,则显示最早出现该key值的位置。相应的VB程序段如下:key =Val(Text1.Text)i=1:j=nDo While i key Thenj = m-1Elself a(m) j Then s =找不到+ Str(key)Label2.Capt

51、ion=s要使程序实现上述算法,划线处的语句是()A.a(m -1) = keyB.a(m) = keyC.m-1 = 0 And a(m-1) = keyD.m-1 = 0 And a(m) = key解析Else这一支隐含的条件是:a(m)=key,因此此处判断的是当a(m)=key时,是否前面有重复值,同时要保证m-1=0,如果成立则继续往前找,所以答案为 C。答案C4.非简单有序序列的对分查找例7循环升序数组指的是将一个升序数组循环向右移动若干距离之后变成的数组。如1,2,3,4,5循环右移1位,就成为5,1,2,3,4,再右移1位,就成为4,5,1,2,3,其中5,1,2,3,4和4

52、,5,1,2,3都是循环升序数组。该数组的特点是:将循环升序数组从中间分开,肯定有一边是有序数组,另外一边是循环有序数组。小杜研究发现对分查找算法适当优化后也适用于循环升序数组。在文本框输入被查找的数据Key,查找循环升序数组a中是否有相同的元素存在。编写的VB程序段如下:i=1: j = n 数组a下标从1到nKey = Val(Text1.Text)Do While i = jm = (i + j) 2If a(m) = Key Then Exit DoIf a(i) a(m) And Key = a(j) Then i = m + 1 Else j = m - 1End IfLoopIf

53、 i = a(i) And Key a(m)B.Key a(m)C.Key = a(i) And Key a(i) And Key = a(m)解析本题考查对分查找。a(i)a(m),说明i,m这一段数据是有序的,此时如果Key处于这一段,并且Key=a(i) And Keya(m),则j=m-1。答案A5.随机数与可能性问题例8有以下VB程序段:i = 1:j=10 : flag=True : cs=0Key = Int(Rnd()* 10) + 28Do While i = j And flag = Truem =(i+ j)2:cs=cs+lIf a(m)=Key Thenflag=Fa

54、lseElseIf a(m) Key Theni= m+1Elsej=m-1End IfLoop数组元素a(1)到a(10)依次是3,10,17,23,27,30,35,40,45,50,变量cs的值可能是()A.1 或 2B.2或3C.3或4D.4或5解析本题考查对分查找。Key = Int(Rnd() * 10) + 28 即产生28,37的随机整数,cs表示查找次数,10个数,最多查找4次,D错。第1次查找,m=5,a(5)=27,而Key的范围是28,37,因此1次是不可能的,A错。第2次查找,m=8,a(8)=40,因此2次也是不可能的,B错。答案C考点五递归算法及程序实现考向基础1

55、.递归算法的基本思想函数或过程调用它本身,称为递归。递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题,规模较小的问题又变成规模更小的问题,当问题小到一定程度时,可以直接得出它的解,从而得到原来问题的解。即采用“大事化小、小事化无”的基本思想。比如著名的汉诺塔问题、八皇后问题、斐波那契数列、猴子吃桃问题等。在自定义函数中调用自己,这样的函数叫递归函数。2.递归算法的前提条件(1)每一步解决问题的方法要一致;(2)在使用递归策略时,必须有一个明确的结束条件(也称边界条件),称为递归出口。示例:年龄问题1有A、B、C、D四个人,问A的年龄,A说:我的年龄是B的两倍;

56、问B的年龄,B说:我比C大3岁;问C的年龄,C说:我的年龄是D的两倍减15岁;问D的年龄,D说:我17岁。请问A的年龄是多少?在这个问题中,虽然有递归出口(D的年龄),但是每一步解决问题的方法不一致,因此不能使用递归算法。示例:年龄问题2有A、B、C、D四个人,问A的年龄,A说:我比B大5岁;问B的年龄,B说:我比C大5岁;问C的年龄,C说:我比D大5岁;问D的年龄,D说:我17岁。请问A的年龄是多少?在这个问题中,不但有递归出口(D的年龄),而且每一步解决问题的方法是相同的(前一人比后一个大5岁),因此可以用递归算法。3.递归算法的程序实现求阶乘(n!)的代码。Private Sub Com

57、mand1_Click()Dim n As IntegerDim m As Longn = Val(Text1.Text)m = f(n)Text2.Text = Str(m)End SubFunction f(a As Integer)If a = 1 Then边界条件f = 1递归出口Elsef = f(a - 1) * a递归调用End IfEnd Function注:递归算法的代码通常比较简洁,但事实上递归算法的运行效率较低。4.递归算法的设计难点(1)找到边界条件,设置递归出口。(2)推导递归公式。如阶乘问题的递归公式是:n!=(n-1)!*n。斐波那契数列的递归公式是:f(n)=f

58、(n-1)+f(n-2)。5.递归算法的调用过程例有以下程序段:Dim a(4) As IntegerPrivate Sub Command1_Click()Dim s As Stringa(1)= 10:a(2)= 30:a(3)= 20:a(4)= 40s = doit(4)Label1.Caption = sEnd SubFunction doit(k As Integer) As StringIf k = 1 Thendoit = Str(a(1)Elsedoit = doit(k - 1) & Str(a(k)End IfEnd Function程序运行后,标签Label1 中显示的内容是()A.10 20 30 40B.10 30 20 40C.40 30 20 10D.40 20 30 10解析本题的递归调用过程如下: 答案B考点六算法在数据管理中的应用考向基础在VB程序中使用ADO对象,必须先引