教科版 信息技术 必修 3.3 第三章　查找算法的程序实现课件（共36张ppt)

课件36张PPT。第三章　查找算法的程序实现-2--3-考点1考点2顺序查找
查找是一种能以比较少的步骤或较短的时间找到所需对象的一种查询技术。常见的查找方法有顺序查找和对分查找。
顺序查找的基本思想:从第一个数据开始,按照数据的顺序逐个将数据与给定的值进行比较,若某个数据与给定值相等,则查找成功,找到所查数据的位置;反之,则查找不成功。顺序查找算法简单,对数据表中的元素是否有序没有要求,N个元素的顺序查找过程中数据比较的次数最多是N次。
顺序查找的程序结构:
k=0(k用来保存与要查找数据key相等的元素的下标)-4-考点1考点2如果k≠0,则输出查找成功,否则输出查找不成功。
顺序查找程序段
k=0
for i=1 to n
if a(i)=key then k=i
next i
if k<>0 then
输出查找成功
else
输出查找失败
end if-5-考点1考点2【例1】 在数组元素a(1)到a(8)中查找键值为key的数,其顺序查找的VB程序段如下,请在划线处填写正确的语句。
for i=1 to 8
if ①　　　　　　　　then?
　　Text1.text=str(i)
　　exit for
end if
next i
if ②　　　　　　　　then?
text1.text=″在数组中没有找到″+str(key)
end if-6-考点1考点2答案:①a(i)=key　② i>8
解析:根据顺序查找的基本思想,依次将数组元素a(1)到a(8)跟查找键值key比较,若相等,显示找到结果并退出循环,否则继续查找。程序实现时,变量i用来表示第几次查找,而a(i)则是第i次查找时被访问到的数组元素。如果某个数组元素a(i)的值等于key则将该数组元素的下标值i显示在text1文本框中,并通过exit for来结束查找。若没有找到key,则i的值必定大于8,故划线①处的条件表达式为“a(i)=key”,划线②处的条件表达式为“i>8”。-7-考点1考点2对分查找
对分查找又名二分查找,是一种高效的查找方法,但前提是被查找的数据必须是有序的。
1.对分查找的基本思想
首先将查找键与有序数组内处于中间位置的元素进行比较,如果相等表明查找成功;否则根据数据的有序性,确定应该在数组的前半部分还是后半部分继续查找,在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。对分查找最多进行[log2N]+1次查找。[log2N]表示小于等于log2N的最大整数。
2.对分查找实现的要点
(1)由于比较次数不确定,所以一般用do语句实现。
(2)在do的循环体中用if语句来判断是否查找成功。
(3)若查找成功则输出查找结果,并用exit for语句提前结束循环。-8-考点1考点23.对分查找的程序结构(以查找升序序列为例) -9-考点1考点24.常用对分查找程序段
i=1:j=n
do while i<=j
m=(i+j)2
if a(m)=key then
　　'找到目标,退出查找
else if key　　j=m-1
else
　　i=m+1
end if
loop
if　i>j then
　'未找到目标
end if-10-考点1考点2【例2】 小金设计了一个按原子量找元素名称和符号的VB程序。程序运行时,先将26种元素原子量按从小到大保存在数组a中,对应的元素名称和元素符号保存在数组b和c中,并在列表框List1中显示。然后在文本框Text1中输入一个原子量数值,单击“查找”按钮Command1,Label3中显示查找到的元素名称和符号,程序运行界面如图所示。-11-考点1考点2查找26个元素的程序代码如下,请在画线处填入合适代码:
Dim a(1 To 26) As Single,b(1 To 26) As String,c(1 To 26) As String
Private Sub Command1_Click()
Dim i As Integer,j As Integer,m As Integer
Dim k As Single,f As Booleam
i=1:j=26:f=False
k=Val(Text1.Text)
Do While i<=j And Not f
m=　①　?
If k=a(m) Then-12-考点1考点2　　Label3.Caption=″元素:″+b(m)+″　″+　②　?
　　f=True
Else
　　If k　　　　j=　③　?
　　Else
　　　　i=m+1
　　End If
End If
Loop
If Not f Then
Label3.Caption=″元素不存在表里!″
End If
End Sub-13-考点1考点2答案:①Int((i+j)/2)或Fix((i+j)/2)或(i+j)2　②c(m)　③m-1
解析:程序采用典型的对分查找算法,循环中首先计算中间位置m=(i+j)2。如果a(m)=k,说明找到了元素,则显示元素名称和符号,元素名称和元素符号保存在数组b和c中。如果ka(m),则下次在右区间找,即j不变,i=m+1-14-12345678 答案解析1.某数组的6个元素依次为“27,32,57,78,80,90”。若对该数组进行顺序查找,其平均查找次数为(1+2+3+4+5+6)/6=7/2;若对该数组进行对分查找,其平均查找次数为 (　　)
A.7/2 B.7/3
C.5/2 D.2-15-123456782.某对分查找算法的VB程序段如下:
i=1:j=8:c=0
Do While i<=j
c=c+1
m=Fix((i+j)/2)
If key=b(m) Then Exit Do
If keyLoop
数组元素b(1)到b(8)的值依次为“22,32,39,48,71,82,96,106”。若该程序段运行结束后,c的值为2,则key的值是(　　)
A.48或32 B.48或96
C.32或82 D.82或96 答案解析-16-123456783.某对分查找算法的VB程序段如下:
t=″ ″:i=0:j=9:key=62:f=False
Do While i<=j And Not f
m=Fix((i+j)/2)
t=t+Str(m)
If a(m)=key Then
f=True
ElseIf a(m)>key Then
i=m+1
t=t+″→″
Else
j=m-1
t=t+″←″
End If
Loop-17-12345678数组元素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″ 答案解析-18-123456784.(2018·4浙江学考)数组a为一组正整数,奇数在前,偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想:设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下:
i=1:j=10
Key=Val(Text1.Text)
Do While i<=j
m=(i+j)2
If a(m)=Key Then Exit Do　'Exit Do 表示退出循环
If Key Mod 2=1 And a(m) Mod 2=0 Then
　　　　(1)?
ElseIf Key Mod 2=0 And a(m) Mod 2=1 Then
　　　　(2)?-19-12345678Else
　　　　(3)?
End If
Loop
If i>j Then s=″没有找到!″ Else s=″位置:″+Str(m)
Text2.Text=s
上述程序中划线处可选语句为:
①i=m+1
②j=m-1
③If Key则(1)、(2)、(3)处语句依次是(　　)
A.①、②、③ B.①、③、②
C.②、①、③ D.③、②、① 答案解析-20-123456785.有如下VB程序段:
i=1:j=10:flag=False:s=″ ″
Do While i<=j And Not flag
mid1=Int(i+(j-i)/3)
mid2=Int(j-(j-i)/3)
If Key=a (mid1) Then
flag=True
Elself Keyj=mid1-1
Elself Key=a(mid2) Then
flag=True-21-12345678Elself Key>a(mid2) Then
i=mid2+1
Else
i=mid1+1:j=mid2-1
End If
s=s & ″ ″ & mid1 & ″:″ & mid2
Loop
Text2.Text=s
已知数组a(l To 10)中分别是12、21、34、45、59、63、72、86、94、100,key的值为34,程序运行后Text2中显示的内容是(　　)
A.4:7　1:2 B.4:7　1:2　3:3
C.4:7　1:3　3:3 D.4:7　3:3 答案解析-22-123456786.编写一个VB程序,实现如下功能:在文本框text1中输入英文句子,单击“第1个最长单词”按钮,找到第1个最长单词并显示在文本框text2中。运行效果如图所示:-23-12345678为实现上述功能,请在划线处填入合适代码
Private Sub Command1_Click()
Dim s As String, m As String
Dim n As Integer, c As Integer, max As Integer,t As Integer
s = Text1.Text
n = Len(s)
c = 0
max = 0
For i = 1 To n
m =mid(s,i,1)
If m >= ″a″ And m <= ″z″ Or m >= ″A″ And m <= ″Z″ Then
①　　　　　　　?-24-12345678Else
If c > max Then
max = c
t= i - 1
End If
c = 0
End If
If i = n Then
If c > max Then-25-12345678max = c
t = i
End If
End If
Next i
Text2.Text =②　　　　　　　?
End Sub-26-12345678答案: ①c=c+1　②Mid(s,t-max+1,max)
解析: 程序中变量c表示单词字母的个数,t表示最长单词的结束字母的位置,变量max表示最长单词的字母个数。程序中每次循环取出1个字符,如果是字母,则变量c加1,否则说明一个单词结束,判断若c>max,表明找到更长的单词,记录单词长度max,并更新位置t,c重置为0。若已是最后一个字母,则判断最后一个单词是否为最长单词。所以①处填c=c+1,用于累计单词中字母个数。②处是取出最长单词,显示在文本框text2中,填Mid(s,t-max+1,max)。-27-123456787.(2018·11浙江选考)数组a中存储的是左右交替上升的n个正整数,如下表所示:
依据对分查找思想,设计一个在数组a中查找数据key的程序。实现该功能的VB程序如下,但加框处代码有错,请改正。
Private Sub Command1_Click()
Const n=6
Dim a(1 To n)As Integer,flag As Boolean
Dim i As Integer,j As Integer,m As Integer,key As Integer
'读取一组正整数,按上述规则存入数组a中,代码略。-28-12345678key=Val(Text1.Text)
i=1
j=(n+1)2
flag=False
Do While im=(i+j) 2
If key=a(m)Then
　　flag=True
ElseIf key　　j=m-1
Else
　　i=m+1
End If-29-12345678Loop
If Not flag And j>0 Then
m=n-i　'②
If key=a(m)Then flag=True
End If
If flag Then
Text2.Text=Str(m)
Else
Text2.Text=″找不到″
End If
End Sub-30-12345678答案: ①i<=j　②n-j+1
解析: 通过代码j=(n+1)2,得知对分查找的范围为左边数据(左半部分是升序),显然在左边进行常规的对分查找。根据对分查找条件得知第一空答案为i<=j。左边对分查找结束后如果查找失败(i>j):如果j的值为0,则key肯定小于a(1),数组a中肯定不存在,因为a(1)最小。如果j的值大于0,则意味着key的值介于a(j)和a(j+1)之间,由于左右两边数据排序位次对称(左边第j个数据对应右边第n-j+1个数据),比a(j)稍大的在右边数组中,也就是第a(n-j+1)。如果a(n-j+1)和key相等,则查找成功。所以②的答案为:n-j+1。-31-123456788.有来自K(1<=K<=20)个不同国家的N(1<=N<=100)个小朋友排成一行准备拍照。国籍用数字1,2,3…N表示,每个小朋友的国籍依次存入数组a(1)到a(K)。由于小朋友太多,没有办法全部被拍入。摄像师决定拍摄一段连续区间内的小朋友,这个区间内每种国籍的小朋友至少要有1个,求满足要求的最小区间长度。例如有10个小朋友,5种国籍,从左到右排列,国籍编号依次是2,1,2,4,3,3,5,5,3,5,则最小的一段包含所有5种国籍的区间是从第2个到第7个小朋友,区间长度为6。算法解析区间的长度至少为K(国籍的数量),最大为N(小朋友的数量)。我们可以通过二分K到N之间的求得最小区间长度。
实现上述功能的VB代码如下,但加框处代码有错,请改正。-32-12345678Dim a(1 To 100) As Integer　'依次存储为1到100的小朋友的国籍编号
Dim K As Integer,N As Integer
Private Sub Form_Load()
'产生N的值,表示人数,产生K的值,表示国籍种数
'产生编号为1到N的小朋友的国籍编号,并存储在数组a中
'代码略
End Sub-33-12345678Private Sub Command1_Click()　'使用二分的思想计算最小区间
Dim M As Integer
i=K:j=N
Do While i<=j
M=(i+j)2
If pd(M)=True Then　'调用Pd函数,判断区间长度为M时,是否包含所有国籍
j=M-1
ans=M
Else
i=m-1　'①
End If-34-12345678Loop
Text1.Text=Str(ans)
End Sub
Function pd(M As Integer) As Boolean
Dim f(1 To 20) As Integer　'f(i)表示国籍为i的小朋友是否包含
Dim t As Integer　't用于统计当前区间包含的国籍数量
pd=False
For i=1 To N-M+1
For j=i To i+M-1
f(a(j))=1
Next j-35-12345678t=0
For j=1 To K　'统计已包含的国籍的数量
t=t+j　'②
Next j
If t=K Then pd=True:Exit Function　'若包含K个国籍,返回True
For j=1 To K　'f数组元素重新初始化为0
f(j)=0
Next j
Next i
End Function答案: ①m+1　②t+f(j) -36-12345678解析: 本题题目看起来很难,难点1,不是在具体的一列数中查找某个Key,而是利用对分查找在[K,N]中(最小值K表示国籍的数量,最大值N表示小朋友数量)找符合排队条件的M的最小值;难点2,在自定义函数pd中,巧妙地用数组嵌套f(a(j))表示第j个小朋友的国籍,只要该国国籍的小朋友出现,则相应的数组元素值为1,而不必管相同国籍的小朋友有几个。具体的对M个小朋友排队思路为:在N个小朋友中取连续的M个,一共有N-M+1种情况,这就是pd函数中的外层循环,对每种情况都测试,即取连续的M个小朋友,把他们的国籍记录在数组f中,按照上面的分析,出现相同国籍的小朋友,f的数组元素永远是1,这样,当M个小朋友的国籍数累加起来(保存在变量t中)为K时,就表示排队成功。要改的第①空可以根据对分查找的对称性改为i=M+1。另外在本题中,可能存在多个M能排队成功,这时我们需要找到最小值,所以在主程序中,当pd(M)=true时,循环并不能马上结束。根据以上分析,变量t用来保存当前从i开始的M个数中共包含的国籍数,而数组f才是表示出现相应国籍的数据,所以第②空应改为t+f(j)。