5.4 对分查找程序应用 导学案 -2021-2022学年高中信息技术浙教版选修1
高二信息技术导学案 VB模块 班级 姓名
《 对分查找程序应用》导学案
[考试要求]
1.对分查找程序实现 (c)
[学习目标]
1. 对比顺序查找,掌握对分查找的算法思想。
2. 分解对分查找的算法思想,构建对分查找的代码
3. 充分解读和理解对分查找的程序代码
[自主学习]
一、 知识梳理
1、 对分查找继续重复进行查找的条件是
2、 对分查找最多的查找次数(n个数据)
3、 key与d(mid)的大小比较影响i,j在后续查找中的取值变化:①若d(mid)<key,则i= ,j不变;②若d(mid)>key,则j=mid-1,i
二、自我检测
1.完善下方对分查找基本代码,并在空白处对横线所填代码进行注释。
i=1:j=n
x=0
Do While__________
m=______________
If d(m)=key Then
x=m
Exit Do
End If
If d(m)>key Then
_________
Else
_________
End If
Loop
If x<>0 Then
list1.additem “查找成功下标为”+str(x)
Else
list1.additem “查找失败”
End If
2.某算法程序段如下:
Key=Val (Textl. Text)
Text2. Text=""
i=1:j=9:f= False
Do While i<=j And Not f
m=(i+j)\2
If a(m) Mod 10=Key Then
search=m
f= True
Elself a(m) Mod 10>Key Then
i=m+1
Else
j=m-1
End If
高二信息技术导学案 VB模块 班级 姓名
Text2. Text=Text2. Text+Str(m)
Loop
现数组元素a(1)至a(9)的值依次为19, 28, 37,46, 55, 64, 73, 82, 91,若在文本框Text1中输入29,执行以上程序段后,文本框Text2中显示的内容是( )
A. 5 7 8 B. 55 73 82 C. 55 28 37 D. 5 21
[课堂练习]
1.某对分查找算法的VB程序段如下:
i=1:j=9:n=0
key=Val(Text1.Text)
Do While i<=j
n=n+1
m=Fix((i+j)/2)
If key=d(m) Then Exit do 'Exit Do 表示退出循环
If key<d(m) Then j=m-1 Else i=m+1
Loop
数组元素d(1)到d(9)的值依次为“7,12,18,25,39,58,61,72,86”,若该程序段运行结果后,n的值为2,则key的值是( )
A.39 B.18或61 C.18或72 D.12或61
2.数组元素a(0)到a(9)的值依次为“13,20,22,25,30,33,40,52,65,100”,文本框Text1中输入的值是33,执行该程序段,下列描述正确的是( )
key = Val(Text1.Text)
i = 0: j = 9: s = 0
Do While i <= j
m = Fix((i + j) \ 2 + 0.5)
s = s + 1
If key = a(m) Then
Label1.Caption = Label1.Caption + "→" + Str(m)
Exit Do 'Exit Do表示退出循环
End If
If key < a(m) Then j = m - 1 Else i = m + 1
Label1.Caption = Label1.Caption + "→" + Str(m)
Loop
Label2.Caption = "历经" + CStr(s) + "步"
A.标签Label1显示内容为“→4→7→5”
B.标签Label2显示内容为“历经1步”
C.该程序为顺序查找,查找次数为3
D.该程序为对分查找,查找次数为4
3.数组a中依次存放6个有序数据“23 33 44 55 66 77”
Dim a(1 To 10) As Integer
Dim s As String ,n ,key As Integer
a(1)=23:a(2)=33:a(3)=44:a(4)=55:a(5)=66:a(6)=77
i=1:j=6:c=0:key=35
Do While i<=j
c=c+1
m=(i+j)\2
If (j-i+1) mod 2=0 Then m=m+1
If a(m)=key Then Exit Do
If key<a(m) Then j=m-1 Else i=m+1
Loop
高二信息技术导学案 VB模块 班级 姓名
该程序运行后,下列各变量的值不正确的是( )
A.i=3 B.j=2 C.c=3 D.m=2
4.某查找算法的VB程序段如下:
Key=VaI(Text1. Text)
i=1
j= 10
Do While i<=j
mid1=i+(j-i)\3
mid2=j- (j-i)\3
If a(mid1)=Key Or a(mid2)=Key Then
Exit Do
Elself Key<a(mid1) Then
j= mid1 -1
Elself Key>a(mid1) And Key<a(mid2) Then
i= mid1+1
j= mid2 -1
Else
i= mid2+1
End If
Text2. Text=Text2. Text+Str(a(mid1))+Str(a (mid2))
Loop
数组元素a(1)到a(10)的值依次为“15, 19, 23, 25, 27,32, 33, 38, 43, 48",若在文本框Text1中输入38,执行垓程序段,文本框Text2中显示的是( )
A.25 33 B.23 32 C.38 48 D.25 32
[课后练习]
1.已知一无序数组a(下标1到n),通过引入数组b(下标1到n),使得a(b(1))≤a(b(2)) ≤a(b(3))……≤a(b(n))(示例如图所示),对这些有序数据可进行对分查找。则第一次查找时,中点位置m与中点值分别是( )
A. m的值是Fix((1+n)/2),中点值是 a(m)
B. m的值是Fix((1+n)/2),中点值是 a(b(m))
C. m的值是Fix((b(1))+b(n))/2),中点值是 a(m)
D. m的值是Fix((b(1))+b(n))/2),中点值是 a(b(m))
2.采用如下对分查找算法对数组a中7个有序数据“15,38,51,66,77,81,99”进行查找,查找数据为“55”
i = 1: j = 7: x = 55
Do While i <= j
m = (i + j) \ 2
If a(m) = x Then Exit Do
If a(m) > x Then j = m - 1 Else i = m + 1
Loop