5.4.1 数据查找-教学设计（表格式）
文档属性
| 名称 | 5.4.1 数据查找-教学设计（表格式） |  | |
| 格式 | docx | ||
| 文件大小 | 712.4KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 浙教版（2019） | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2024-04-29 20:55:53 | ||
图片预览
文档简介
教学设计
课程基本信息
课题 数据查找
教学目标
1.通过具体实例理解查找的概念和基本方法。 2.掌握顺序查找的算法思想，熟悉顺序查找算法的代码框架。 3.理解并掌握对分查找的算法思想，熟悉对分查找算法的代码框架。 4.理解并掌握顺序查找与对分查找算法的使用条件和优缺点。
教学内容
教学重点： 1.顺序查找算法思想及程序实现。
2.对分查找算法思想及程序实现。 3.顺序查找、对分查找算法优缺点。
教学难点： 1.对分查找算法查找过程。
2.对分查找算法基本框架及程序实现。
教学过程
【创设情境】 在乱序扑克牌中寻找“红桃5”，讲一讲你的寻找方法？ 学生回答：在乱序扑克牌中，一张一张依次寻找，直到找到为止。 二、【探究学习】 查找的定义 查找（Search）又称检索，是计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 常用查找算法：顺序查找、对分查找。 顺序查找算法基本思想 顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。 ”乱序扑克牌查找“——顺序查找自然语言描述： 问题描述：在不考虑扑克牌花色的情况下，仅在A到K,13张扑克牌中寻找指定的牌。扑克牌2～ 10 为数字本身,A 为 1 ,J 为 11 ,Q 为 12 ,K 为 13，变量Key存储要查找的牌。 第一步：将代表13张扑克牌对应的数字存储于数组d中， 要查找的扑克牌对应数字储于变量key中。 第二步：依次将d数组中元素与key进行比较。 第三：若数组中某个数与key相等则查找成功,若所有元素比较完毕仍找不到，则查找失败。 提问：上述算法过程是必修1中学习过的什么算法？ 回答：枚举算法。 ”乱序扑克牌查找“——顺序查找过程演示： 问题： 若将上述问题规模扩大，在n张牌中寻找，则最理想情况是查找_____1__次？最差的情况需要查找____n____次？平均查找次数：___(n+1)/2_____。 平均查找次数：假设将数组中n个数据查找一次所使用的查找次数之和（1+2+3+4+......+n-1+n）再除以数据总个数n。平均查找次数为：(n+1)/2。 6、顺序查找算法程序实现： 算法框架：枚举算法框架（循环结构，循环体内使用分支结构） #key中存储要查找的数，待查找数据存储在d数组中。 for i in range（0,n,1）： #遍历数组索引 if d[i]==key： #如果查找成功，输出索引位置，并结束查找。 print(i) break else: #全部查找完毕没找到，输出“没找到！” print(“没找到！”) 顺序查找算法小结 三、【创设情境】：在新的扑克牌（ 新扑克牌按照A到K有序排列）中寻找”红桃5“，除了顺序查找有没有更高效的查找算法？（参考选择性必修1《数据与数据结构》第4章中的“猜数字游戏”的方法。） 回答：可以使用对分查找方法。 【探究学习对分查找】 1、对分查找算法思想： 首先将查找的数与有序数组内，处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据数组的有序性，确定应该在数组的前半部分，还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。 2、新扑克牌查找“——对分查找自然语言描述： 问题描述：在不考虑扑克牌花色的情况下，仅在A到K,13张升序排列的扑克牌中寻找指定的牌。扑克牌2～ 10 为数字本身,A 为 1 ,J 为 11 ,Q 为 12 ,K 为 13，变量Key存储要查找的牌。 第一步：将13张扑克牌对应的数字（升序）存储于数组d中， 要查找的扑克牌对应数字储于变量key中。 第二步： 依次将d数组查找区间中间位置的数mid与key进行比较。 第三步： 若mid与key相等则查找成功结束查找,若key大于mid下一次查找区间为右半部分，反之为左半部分。重复第二三两个步骤直到区间元素个数为零，即查找失败。 3、”13张升序排列扑克牌“——对分查找过程演示： 4、“13张升序排列扑克牌”——对分查找流程图描述 5、对分查找程序实现 key=int(input())；f=False；i=0 #所有数据（升序）存储在数组d中 j= len(d)-1 while i<=j : mid= (i+j)//2 if d[mid]==key: f=True break if d[mid]>key: j=mid-1 else: i=mid+1 if f==True: print("查找成功！下标为"+str(mid)) else: print("没有找到！") 6、二叉排序树的定义、对分查找最多查找次数 （1）13张扑克牌对分查找我们可以用一棵二叉树来表示。 （2）二叉排序树： ①若左子树不为空，则左子树的值均小于它的根节点的值. ②若右子树不为空，则右子树的值均大于它的根节点的值 ③它的左右子树也分别为二叉排序树。 （3）假设对分查找数据规模为n最多查找次数？ 二叉树的高度为:int(log2n), 最多查找次数为二叉数高度加1：int(log2n)+1. 顺序查找、对分查找对比总结 课堂总结（本节课的主要内容） 查找的定义。 顺序查找算法思想及程序实现。 对分查找算法思想及程序实现。 两种算法的优缺点。
备注：教学设计应至少含教学目标、教学内容、教学过程等三个部分，如有其它内容，可自行补充增加。
课程基本信息
课题 数据查找
教学目标
1.通过具体实例理解查找的概念和基本方法。 2.掌握顺序查找的算法思想，熟悉顺序查找算法的代码框架。 3.理解并掌握对分查找的算法思想，熟悉对分查找算法的代码框架。 4.理解并掌握顺序查找与对分查找算法的使用条件和优缺点。
教学内容
教学重点： 1.顺序查找算法思想及程序实现。
2.对分查找算法思想及程序实现。 3.顺序查找、对分查找算法优缺点。
教学难点： 1.对分查找算法查找过程。
2.对分查找算法基本框架及程序实现。
教学过程
【创设情境】 在乱序扑克牌中寻找“红桃5”，讲一讲你的寻找方法？ 学生回答：在乱序扑克牌中，一张一张依次寻找，直到找到为止。 二、【探究学习】 查找的定义 查找（Search）又称检索，是计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 常用查找算法：顺序查找、对分查找。 顺序查找算法基本思想 顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。 ”乱序扑克牌查找“——顺序查找自然语言描述： 问题描述：在不考虑扑克牌花色的情况下，仅在A到K,13张扑克牌中寻找指定的牌。扑克牌2～ 10 为数字本身,A 为 1 ,J 为 11 ,Q 为 12 ,K 为 13，变量Key存储要查找的牌。 第一步：将代表13张扑克牌对应的数字存储于数组d中， 要查找的扑克牌对应数字储于变量key中。 第二步：依次将d数组中元素与key进行比较。 第三：若数组中某个数与key相等则查找成功,若所有元素比较完毕仍找不到，则查找失败。 提问：上述算法过程是必修1中学习过的什么算法？ 回答：枚举算法。 ”乱序扑克牌查找“——顺序查找过程演示： 问题： 若将上述问题规模扩大，在n张牌中寻找，则最理想情况是查找_____1__次？最差的情况需要查找____n____次？平均查找次数：___(n+1)/2_____。 平均查找次数：假设将数组中n个数据查找一次所使用的查找次数之和（1+2+3+4+......+n-1+n）再除以数据总个数n。平均查找次数为：(n+1)/2。 6、顺序查找算法程序实现： 算法框架：枚举算法框架（循环结构，循环体内使用分支结构） #key中存储要查找的数，待查找数据存储在d数组中。 for i in range（0,n,1）： #遍历数组索引 if d[i]==key： #如果查找成功，输出索引位置，并结束查找。 print(i) break else: #全部查找完毕没找到，输出“没找到！” print(“没找到！”) 顺序查找算法小结 三、【创设情境】：在新的扑克牌（ 新扑克牌按照A到K有序排列）中寻找”红桃5“，除了顺序查找有没有更高效的查找算法？（参考选择性必修1《数据与数据结构》第4章中的“猜数字游戏”的方法。） 回答：可以使用对分查找方法。 【探究学习对分查找】 1、对分查找算法思想： 首先将查找的数与有序数组内，处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据数组的有序性，确定应该在数组的前半部分，还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。 2、新扑克牌查找“——对分查找自然语言描述： 问题描述：在不考虑扑克牌花色的情况下，仅在A到K,13张升序排列的扑克牌中寻找指定的牌。扑克牌2～ 10 为数字本身,A 为 1 ,J 为 11 ,Q 为 12 ,K 为 13，变量Key存储要查找的牌。 第一步：将13张扑克牌对应的数字（升序）存储于数组d中， 要查找的扑克牌对应数字储于变量key中。 第二步： 依次将d数组查找区间中间位置的数mid与key进行比较。 第三步： 若mid与key相等则查找成功结束查找,若key大于mid下一次查找区间为右半部分，反之为左半部分。重复第二三两个步骤直到区间元素个数为零，即查找失败。 3、”13张升序排列扑克牌“——对分查找过程演示： 4、“13张升序排列扑克牌”——对分查找流程图描述 5、对分查找程序实现 key=int(input())；f=False；i=0 #所有数据（升序）存储在数组d中 j= len(d)-1 while i<=j : mid= (i+j)//2 if d[mid]==key: f=True break if d[mid]>key: j=mid-1 else: i=mid+1 if f==True: print("查找成功！下标为"+str(mid)) else: print("没有找到！") 6、二叉排序树的定义、对分查找最多查找次数 （1）13张扑克牌对分查找我们可以用一棵二叉树来表示。 （2）二叉排序树： ①若左子树不为空，则左子树的值均小于它的根节点的值. ②若右子树不为空，则右子树的值均大于它的根节点的值 ③它的左右子树也分别为二叉排序树。 （3）假设对分查找数据规模为n最多查找次数？ 二叉树的高度为:int(log2n), 最多查找次数为二叉数高度加1：int(log2n)+1. 顺序查找、对分查找对比总结 课堂总结（本节课的主要内容） 查找的定义。 顺序查找算法思想及程序实现。 对分查找算法思想及程序实现。 两种算法的优缺点。
备注：教学设计应至少含教学目标、教学内容、教学过程等三个部分，如有其它内容，可自行补充增加。