浙教版信息技术选修1 5.4 查找算法的程序实现——对分查找算法 教案

对分查找算法教学设计
教学目标
知识与技能:理解对分查找的概念和特点,通过分步解析获取对分查找的解题结构,初步掌握对分查找算法的程序实现。
过程与方法:通过分析多种不同的情况,逐步归纳对分查找的基本思想和方法, 在不断推进中明确对分查找算法，提升计算思维。
情感态度与价值观:1.通过实践体验科学解题的重要性,增强效率意识，提升信息意识素养,感受对分查找算法魅力。
2.掌握相关的数字化学习系统和学习工具，并运用其从事自主学习
学情分析
学生应该已经掌握程序设计的基本思想,掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作,这节课学生可能会遇到的最大问题是:如何归纳总结对分查找解决不同情况问题的一般规律,鉴于此,在教学中要积极引导学生采取分解问题、归纳问题等学习策略。
重点难点
归纳总结对分查找解决不同情况问题的一般规律,分类讨论对分查找key与d(m)三种数量关系,对应修改范围
教学策略：
1、教学线索：回顾对分查找意义---巩固对分查找原理--- 分解对分查找过程---归纳对分查找考点---实践解决问题。
2、学习线索：分解问题---归纳问题---实践提升，在三个阶段的不断推进中明确对分查找算法，提升计算思维。
教学过程
教学步骤一：前情回顾
1．对分查找算法的实际意义：对分查找的高效性。
（1）一个包含一百万个人名的电话簿中找一个名字，对分查找可以让你不超过20次就能找到指定的名字。
（2）将全国13亿人按身份证号排列后，你可在31次比较后找到这个人的信息。
设计意图：增强效率意识，提升信息意识素养
2．对分查找的基本思想：
（1）前提：前提是被查找的数据必须是有序的（递增/递减）
（2）基本思想：
在有序的数据序列中（一般放在数组中），首先把查找的数据与数组中间位置的元素进行比较，
若相等，则查找成功并退出查找；
否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；
在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。
3. 对分查找一般过程分解（以有n个元素的递增数组为例）：
1、i的初值=1，j的初值=n
2、中间数的下标m与i，j的关系是：m=Int((i+j)/2)
3、确定退出循环的条件
①区间的二个端点 i,j必须满足的条件是i<=j
②标志变量取反值flag=true
4、若key>d(m)，说明应在下半区继续查找，修改i 还是j? i=m+1
5、若key设计意图：通过分析和归纳，让学生巩固理解并掌握对分查找的方法及前提条件，为后一阶段对分查找算法的实现作好铺垫。
教学步骤二：互动热身训练（注：依据互动数据决定是否对练习进行讲解）
1.（必做）数组变量d（1）到d（8）的值依次为87、76、69、66、56、45、37、23，用“对分查找”找到“69”的过程中，依次被访问到的数据是（）
A．69
B．66、69
C．66、76、69
D．56、66、76、69
2.（选做）在有序单词序列"bike,cake,data,easy,feel, great,hive,mark, sweet"中,用对分查找算法找到" easy"过程中,依次被访问到的数据为
A.feel, data. easy
B.great, data, easy
C.bike, cake, data, easy
D.feel. cake. data, easy
互动设计意图说明：课堂数据可视化的应用使课堂交互真正得以“实时实地”。 通过学生行为数据反馈可即时了解学生对某一知识点的掌握情况，从而减少师生间反馈所需的时间，促使课堂交互真正实现“实时实地”。
教学步骤三：对分查找考点分析
（一）常规考点
互动练习：1. （必做）某对分査找算法的VB程序段如下:
i = 1: j = 9: n = 0
key = Val(Textl.Text)
Do While i <= j
n = n + 1
m = Fix((i + j) / 2)
If key = d(m) Then Exit Do
If key < d(m) Then j = m - 1 Else i = m + 1
查找次数
剩余搜索区间
1
N/2
2
N/2^2
3
N/2^3
…
…
m
N/2^m
Loop
数组元素d(1)到d（9）的值依次为“7，12，18，25，39，58，61，72，86”。若该程序段运行结束后，n的值为2，则key的值是
A.18或72 B. 12或61 C.39 D. 7或58
（二）搜索区间长度和查找次数
对分查找算法的最多查找次数：int(Log2N )+1
查找次数分析：（右图）
互动练习：
1. （必做）某公司的员工管理系统中有1200条员工记录（每条员工记录已按员工编号升序排序），现用对分查找法搜索一员工信息，开始搜索的记录范围为１200条，若第5次对分查找后还需继续搜索，则第６次搜索的记录范围内的记录数为（　　）
Ａ．18 Ｂ．19Ｃ．37 Ｄ．75
2. （选做）有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用对分查找查找一个元素，则最多需要（ ）次比较就能确定是否存在所查找的元素
A.11 B.12 C.13 D.14
（三）数组元素下标值的变化规律（变量跟踪法）
变量跟踪法:（(师生共同讨论)
讨论并回答以下两个问题。?
问题1:当d(m)>key时,新查找的范围在哪里?i和j如何变化?
问题2:在什么情况下查找会结束?继续进行重复查找的条件是什么?
设计意图：为了让学生在教师的引导下能自我解析变量跟踪法，本题分解了问题动作，找出数组元素下标值的变化规律，从而使学生建立起对分查找算法形成的科学逻辑结构。
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)
1
3
4
7
11
16
19
20
27
30
写出每一次循环结束后m,i,j,p的值
对分查找核心程序
当Key=1时
开 始：m=0,i=1,j=10,p=0
第一次：m=（ ）,i=（ ）,j=（ ）,p=（ ）
第二次：m=（ ）,i=（ ）,j=（ ）,p=（ ）
第三次：m=（ ）,i=（ ）,j=（ ）,p=（ ）
Key = Val(Text1.Text)
p=0:i = 1:j = n
Do While i <= j
m=(i+j)\2
If a(m) = Key Then
p=m:Exit Do
Else If a(m) < Key Then
i=m+1
Else
j=m-1
End If
Loop
思考：循环结束时p=0意味着什么？
当Key=20时
开 始：m=0,i=1,j=10,p=0
第一次：m=（ ）,i=（ ）,j=（ ）,p=（ ）
第二次：m=（ ）,i=（ ）,j=（ ）,p=（ ）
当Key=21时
开 始：m=0,i=1,j=10,p=0
第一次：m=（ ）,i=（ ）,j=（ ）,p=（ ）
第二次：m=（ ）,i=（ ）,j=（ ）,p=（ ）
第三次：m=（ ）,i=（ ）,j=（ ）,p=（ ）
互动练习：
1. （必做）某对分查找算法的VB程序段如下：
i=1: j=6: n=0: f=False
key=val(Text1.Text)
Do while i<=j and f=False
n=n+1
m=(i+j)\2
If key=d(m) then f=True
If keyLoop
数组元素d(1)到d(6)的值依次为“13，18，25，30，35，59”。文本框Text1中输入33后运行该程序，运行结束后下列说法不正确的是（ ）
A．变量f的值为False
B. 变量i的值为5
C. 变量m的值为4
D. 变量n的值为2
29051253683000
2. （选做）已知一无序数组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))
（四）表达式的改变和查找成功后的处理方法对结果的影响
互动练习：
1. （必做）程序如下：
Randomize
key = Int (Rnd*100)
i = 1: j = 7
s = ""
Do While i <= j
m = (i + j) \ 2
If key = a(m) Then
s=s+"M" : Exit Do
End If
If key < a(m) Then j = m – 1: s=s+“L" Else i = m + 1: s=s+“R"
Loop
Text1.Text =s
数组元素a(1)到a(7)的值依次为“25,36,39,42,47,66,78”，执行该程序段,文本框Text1中显示的内容是“RLR"，则可以确定随机产生的Key值范围是（ ）
A．（25，36）
B．（47，66）
C．（66,78)
D．(78,100)
2. （选做）已知数组元素a(1)到a(9)的值依次为19,28,37,46,55,64,73,82,91,若在 Text1中输入29,然后执行以下程序段
Key= Val(Text1.Text)\10
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
ElseIf a(m) Mod 10 > Key Then
i=m+1
Else
j=m-1
End If
Text2. Text= Str(m)+Text2. Text
Loop
则在执行该程序段后,Text2中示的内容是
A.5 7 8
B.55 37 28
C.82 73 55
D.8 7 5
教学步骤四：课堂小结
对分算法几个注意问题：
（1）对分查找的前提：被查找数据必须是有序的。
（2）新的查找范围的确定：i=m+1 或 j=m-1
（3）数组元素下标值的变化规律
（4）表达式的改变和查找成功后的处理方法对结果的影响
（5）对分查找算法的最多查找次数
教学步骤五：课后进阶练习
数组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
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）
Else
（3）
End If
Loop
If i > j Then s = "没有找到！" Else s = "位置：" + Str(m)
Text2.Text = s
上述程序中方框处可选语句为：
①i = m + 1
②j = m - 1
③If Key < a(m) Then j = m - 1 Else i = m + 1
则（1）、（2）、（3）处语句依次是
A．①、②、③ B．①、③、② C．②、①、③ D．③、②、①
设计意图：扩充课堂内容，丰富学生知识面，通过学生自己的分析、探索，找出问题答案。
自我评价
本人课堂教学的特点是利用信息技术手段，创设数字化学习环境，将教学内容与各种技术方法连接起来，让学生在体验中分解问题、归纳问题，在实践中完成教学任务要求。课堂教学模式以学生互动探究为主教师小结为辅。教学过程中注重培养学生的“计算思维”能力，增强效率意识，提升信息意识素养。
教学反思
　　整节课学生参与度高。老师的主导作用和学生的主体地位得到了充分的体现。学生在师生互动、生生互助中比较好地掌握了对分查找的思想和算法实现，教学效果好。