还剩4页未读，
继续阅读
浙教版 (2019)选修1 数据与数据结构5.4 数据查找教学设计
展开
这是一份浙教版 (2019)选修1 数据与数据结构5.4 数据查找教学设计，共7页。
课程标准
和
教学目标
二分查找算法的程序实现
教材内容：5.4查找 之 二分查找算法的程序实现
适应的课程标准：
1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。
法。
教学目标：
●掌握常用的二分查找的基本程序结构。
●能够编程实现二分查找。
信息意识：学生能够结合生活中的实例描述数据的内涵与外延，有意识地选择恰当的数据结构表达数据的逻辑关系。
计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。
数字化学习与创新：要使学生能够较为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。
信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
学习环境：有教学控制软件的多媒体机房，pythn编程环境。
建议课时：1课时
教学活动设计
教学环节
教学过程
设计意图
情境导入
回顾一个对具体数据进行查找的基本过程。
巩固旧知，联系新知。
学习任务一：二分查找的基本过程与规则
●学习任务一：二分查找的基本过程与规则
问题：二分查找是对查找键key在n个有序数据里面进行查找，查找过程是否有规则，规则在哪里？引导学生思考并回答问题。
引导学生总结：查找键key每次和区间内的中间位置元素进行比较，中点位置的计算：
m=，每次查找的基本过程。
第一次，在查找范围（i，j）内的递增元素中找到中间位置，将查找键key值和中间位置为5的元素d[5]进行比较，根据比较结果可以确定：在（m，j）内不可能存在值为key的数据，必须在新的范围（i，m-1）中继续查找；
第二次，在查找范围（i，m-1）内的递增元素中找到中间位置，将查找键key值和中间位置为2的元素d[2]进行比较，根据比较结果可以确定：在（m，j）内不可能存在值为key的数据，必须在新的范围（i，m-1）中继续查找；
第三次，在查找范围（i，m-1）内的递增元素中找到中间位置，将查找键key值和中间位置为0的元素d[0]进行比较，根据比较结果可以确定：在（i，m）内不可能存在值为key的数据，必须在新的范围（m+1，j）中继续查找；
第四次，在查找范围（m+1，j）内的递增元素中找到中间位置，将查找键key值和中间位置为d[1]的元素12进行比较，找到key值。
查找完成。
以中间位置m、查找范围i、j变化为例，提炼出一般规则：
设问：再仔细观察某一次里面的查找过程，这种方法是否通用？
教师引导学生总结：查找过程中，查找键key值与d[m]比较，结果必然是如下三种情况之一：
keykey=d[m] 找到了需要的数据。
key>d[m] 由于与①相同的理由，必须在新的范围（m+1，j）中继续查找。
这样，除了出现情况②，在通过一次比较后，新的查找范围将不超过上一次查找范围的一半。
教师引导学生用流程图来描述这个过程：
设计意图：按照由粗到细、逐步求精的策略，推动学生加深对二分查找的深认识。
学习任务二：二分查找的程序实现
●学习任务二：二分查找的程序实现
1. 研究二分查找的第一次查找的程序实现
仍以这些数据为例，回顾二分查找第一次的查找过程：
二分查找算法对数组d的第一次查找过程
设问：经过第一次查找，key和d[m]的比较会出现几种情况？如何使用程序实现？
if d[m] == key:
b=m
if key < d[m]: # 到左边去找
j = m-1
else: # 到右边去找
i = m + 1
i、j代表数组元素的下标，i从0开始增大，j从length-1开始减小，i能否大于j？为什么？
2. 设计算法实现二分查找
设问：上一步中，我们编写了第一次查找的程序代码，如何修改一下，完成整个查找过程？
对于n个递增元素，第一次查找将key值和中间元素d[m]进行比较，若找到则退出程序，若比d[m]小则到左区间找，若比d[m]大则到右区间找
在新区间确定新的中间元素d[m]，将key值和d[m]进行比较，重复刚才的规律，直到找到key值或找遍整个数组
二分查找完成
i = 0
j = len(d)-1
while i <= j:
m = (i+j) //2
if d[m] == key:
f=True
b=m
break
if key < d[m]: # 到左边去找
j = m-1
else: # 到右边去找
i = m + 1
3. 学生动手编写二分查找的程序实现
d=[6,12,15,18,22,25,28,35,46,58,60]
f=False
# i和j定义子数组的边界，一开始搜索的是整个数组
i = 0
j = len(d)-1
while i <= j:
m = (i+j) //2
if d[m] == key:
f=True
b=m
break
if key < d[m]: # 到左边去找
j = m-1
else: # 到右边去找
i = m + 1
if f==True:
print("查找成功！第"+str(b)+"个")
else:
print("没有找到！")
4.二分查找延伸
二分查找过程可用一棵二叉树来描述，树中的每个根结点对应当前查找区间的中点元素，它的左子树和右子树分别对应该区间的左子表和右子表，如下图所示。通常把此树称为二分查找的判定树。
二分查找的判定树实例
在有序表上二分查找一个关键字等于key的元素时，对应着判定树中从根结点到待查结点的一条路径，同关键字进行比较的次数就等于该路径上的结点数，或者说等于待查结点的层数。如上例中，查找key为12的元素时，从根结点到待查结点的一条路径为25→15→6→12，比较次数为4次。通过观察可知，在n个元素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1，即。
由于二分查找在有序表上进行，所以其对应的判定树就是一棵二叉排序树。
设计意图：从第一次查找的实现中可以发现规律，进而引导学生概括出全部算法过程。
设计意图：重点在于第一次查找过程，这个过程清楚了，那么对于后面的查找，遵循同样的规则，以此类推，即可实现对数据的查找。此处在于引导学生意识到什么时候查找结束：找到key值或者是当i大于j的时候，其实已经把整个数组全都找遍了。
设计意图：由第一次查找的代码，概括出查找的规律，是一种抽象思维的过程，最后将整个过程，进一步概括出一个循环和判断的程序结构，这是一个难点。可以多花些时间，鼓励学生多思考、多动手、多验证。
拓展学习
二分查找算法中，有序数组是递增排序和递减排序在程序实现时有何区别？
若查找对象采用链表结构，能否适用二分查找？
二分查找算法的递归实现？
设计意图：根据学生的不同层次水平设置相应的教学任务。
课堂小结
知识梳理：
1. 二分查找算法的基本过程和结构；
2. 二分查找算法的程序实现。
二分查找算法的程序实现是难点，课后作业提供了相应练习。
作业布置
基础作业（面向所有学生）：
思考教材“问题与讨论”：若查找对象采用链表结构，能否适用二分查找？
课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。
教学设计思路
首先，引导学生回顾旧知，与前面所学的二分查找基本思想与方法建立联系，学生可以较熟悉地对若干个数据进行二分查找。
其次，引导学生能够从抽象的角度概括出二分查找的基本规则，并能以合适的数字化学习工具呈现出其每次查找的基本过程。
再次，在学生有了一定认知基础上，可以引入自然语言、流程图，帮助学生理解二分查找的基本程序结构，从而实现对程序实现这个难点的突破。
本节主要内容为查找算法的核心模块。
针对
核心素养培养的
设计考虑
本节侧重于计算思维的训练。程序语言是表达算法思想的工具，为了实现二分查找，在数据组织形式上选择较为简单的整数，并从中概括出二分查找的基本过程和算法步骤。这是一个逐步求精的过程。为了照顾普通学生的需要，可以从分析二分查找的第一次查找入手，然后再就其程序实现进行展开，这是一个由抽象到具体的过程；然后再从第一次查找的实现，推广到查找结束，这是一个思维泛化的过程；再由此出发，抽象出二分查找的整体程序结构，并通过简洁的代码实现，提炼出了二分查找的基本算法。这个基本过程，是一种思维螺旋式上升的提升过程，较好地实现了教学意图。
课程标准
和
教学目标
二分查找算法的程序实现
教材内容：5.4查找 之 二分查找算法的程序实现
适应的课程标准：
1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。
法。
教学目标：
●掌握常用的二分查找的基本程序结构。
●能够编程实现二分查找。
信息意识：学生能够结合生活中的实例描述数据的内涵与外延，有意识地选择恰当的数据结构表达数据的逻辑关系。
计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。
数字化学习与创新：要使学生能够较为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。
信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
学习环境：有教学控制软件的多媒体机房，pythn编程环境。
建议课时：1课时
教学活动设计
教学环节
教学过程
设计意图
情境导入
回顾一个对具体数据进行查找的基本过程。
巩固旧知，联系新知。
学习任务一：二分查找的基本过程与规则
●学习任务一：二分查找的基本过程与规则
问题：二分查找是对查找键key在n个有序数据里面进行查找，查找过程是否有规则，规则在哪里？引导学生思考并回答问题。
引导学生总结：查找键key每次和区间内的中间位置元素进行比较，中点位置的计算：
m=，每次查找的基本过程。
第一次，在查找范围（i，j）内的递增元素中找到中间位置，将查找键key值和中间位置为5的元素d[5]进行比较，根据比较结果可以确定：在（m，j）内不可能存在值为key的数据，必须在新的范围（i，m-1）中继续查找；
第二次，在查找范围（i，m-1）内的递增元素中找到中间位置，将查找键key值和中间位置为2的元素d[2]进行比较，根据比较结果可以确定：在（m，j）内不可能存在值为key的数据，必须在新的范围（i，m-1）中继续查找；
第三次，在查找范围（i，m-1）内的递增元素中找到中间位置，将查找键key值和中间位置为0的元素d[0]进行比较，根据比较结果可以确定：在（i，m）内不可能存在值为key的数据，必须在新的范围（m+1，j）中继续查找；
第四次，在查找范围（m+1，j）内的递增元素中找到中间位置，将查找键key值和中间位置为d[1]的元素12进行比较，找到key值。
查找完成。
以中间位置m、查找范围i、j变化为例，提炼出一般规则：
设问：再仔细观察某一次里面的查找过程，这种方法是否通用？
教师引导学生总结：查找过程中，查找键key值与d[m]比较，结果必然是如下三种情况之一：
key
key>d[m] 由于与①相同的理由，必须在新的范围（m+1，j）中继续查找。
这样，除了出现情况②，在通过一次比较后，新的查找范围将不超过上一次查找范围的一半。
教师引导学生用流程图来描述这个过程：
设计意图：按照由粗到细、逐步求精的策略，推动学生加深对二分查找的深认识。
学习任务二：二分查找的程序实现
●学习任务二：二分查找的程序实现
1. 研究二分查找的第一次查找的程序实现
仍以这些数据为例，回顾二分查找第一次的查找过程：
二分查找算法对数组d的第一次查找过程
设问：经过第一次查找，key和d[m]的比较会出现几种情况？如何使用程序实现？
if d[m] == key:
b=m
if key < d[m]: # 到左边去找
j = m-1
else: # 到右边去找
i = m + 1
i、j代表数组元素的下标，i从0开始增大，j从length-1开始减小，i能否大于j？为什么？
2. 设计算法实现二分查找
设问：上一步中，我们编写了第一次查找的程序代码，如何修改一下，完成整个查找过程？
对于n个递增元素，第一次查找将key值和中间元素d[m]进行比较，若找到则退出程序，若比d[m]小则到左区间找，若比d[m]大则到右区间找
在新区间确定新的中间元素d[m]，将key值和d[m]进行比较，重复刚才的规律，直到找到key值或找遍整个数组
二分查找完成
i = 0
j = len(d)-1
while i <= j:
m = (i+j) //2
if d[m] == key:
f=True
b=m
break
if key < d[m]: # 到左边去找
j = m-1
else: # 到右边去找
i = m + 1
3. 学生动手编写二分查找的程序实现
d=[6,12,15,18,22,25,28,35,46,58,60]
f=False
# i和j定义子数组的边界，一开始搜索的是整个数组
i = 0
j = len(d)-1
while i <= j:
m = (i+j) //2
if d[m] == key:
f=True
b=m
break
if key < d[m]: # 到左边去找
j = m-1
else: # 到右边去找
i = m + 1
if f==True:
print("查找成功！第"+str(b)+"个")
else:
print("没有找到！")
4.二分查找延伸
二分查找过程可用一棵二叉树来描述，树中的每个根结点对应当前查找区间的中点元素，它的左子树和右子树分别对应该区间的左子表和右子表，如下图所示。通常把此树称为二分查找的判定树。
二分查找的判定树实例
在有序表上二分查找一个关键字等于key的元素时，对应着判定树中从根结点到待查结点的一条路径，同关键字进行比较的次数就等于该路径上的结点数，或者说等于待查结点的层数。如上例中，查找key为12的元素时，从根结点到待查结点的一条路径为25→15→6→12，比较次数为4次。通过观察可知，在n个元素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1，即。
由于二分查找在有序表上进行，所以其对应的判定树就是一棵二叉排序树。
设计意图：从第一次查找的实现中可以发现规律，进而引导学生概括出全部算法过程。
设计意图：重点在于第一次查找过程，这个过程清楚了，那么对于后面的查找，遵循同样的规则，以此类推，即可实现对数据的查找。此处在于引导学生意识到什么时候查找结束：找到key值或者是当i大于j的时候，其实已经把整个数组全都找遍了。
设计意图：由第一次查找的代码，概括出查找的规律，是一种抽象思维的过程，最后将整个过程，进一步概括出一个循环和判断的程序结构，这是一个难点。可以多花些时间，鼓励学生多思考、多动手、多验证。
拓展学习
二分查找算法中，有序数组是递增排序和递减排序在程序实现时有何区别？
若查找对象采用链表结构，能否适用二分查找？
二分查找算法的递归实现？
设计意图：根据学生的不同层次水平设置相应的教学任务。
课堂小结
知识梳理：
1. 二分查找算法的基本过程和结构；
2. 二分查找算法的程序实现。
二分查找算法的程序实现是难点，课后作业提供了相应练习。
作业布置
基础作业（面向所有学生）：
思考教材“问题与讨论”：若查找对象采用链表结构，能否适用二分查找？
课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。
教学设计思路
首先，引导学生回顾旧知，与前面所学的二分查找基本思想与方法建立联系，学生可以较熟悉地对若干个数据进行二分查找。
其次，引导学生能够从抽象的角度概括出二分查找的基本规则，并能以合适的数字化学习工具呈现出其每次查找的基本过程。
再次，在学生有了一定认知基础上，可以引入自然语言、流程图，帮助学生理解二分查找的基本程序结构，从而实现对程序实现这个难点的突破。
本节主要内容为查找算法的核心模块。
针对
核心素养培养的
设计考虑
本节侧重于计算思维的训练。程序语言是表达算法思想的工具，为了实现二分查找，在数据组织形式上选择较为简单的整数，并从中概括出二分查找的基本过程和算法步骤。这是一个逐步求精的过程。为了照顾普通学生的需要，可以从分析二分查找的第一次查找入手，然后再就其程序实现进行展开，这是一个由抽象到具体的过程；然后再从第一次查找的实现，推广到查找结束，这是一个思维泛化的过程；再由此出发，抽象出二分查找的整体程序结构，并通过简洁的代码实现，提炼出了二分查找的基本算法。这个基本过程，是一种思维螺旋式上升的提升过程，较好地实现了教学意图。
