高中信息技术浙教版：5-4-1 数据查找-教学设计

教学设计 课程基本信息 学科 信息技术 年级 高二 学期 春季 课题 数据查找 教科书 教学目标 1.通过具体实例理解查找的概念和基本方法。 2.掌握顺序查找的算法思想，熟悉顺序查找算法的代码框架。 3.理解并掌握对分查找的算法思想，熟悉对分查找算法的代码框架。 4.理解并掌握顺序查找与对分查找算法的使用条件和优缺点。 教学内容 教学重点： 1.顺序查找算法思想及程序实现。 2.对分查找算法思想及程序实现。 3.顺序查找、对分查找算法优缺点。 教学难点： 1.对分查找算法查找过程。 2.对分查找算法基本框架及程序实现。 教学过程 1、 【创设情境】 在乱序扑克牌中寻找“红桃5”，讲一讲你的寻找方法？ 学生回答：在乱序扑克牌中，一张一张依次寻找，直到找到为止。 二、【探究学习】 1、 查找的定义 查找（Search）又称检索，是计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 2、 常用查找算法：顺序查找、对分查找。 3、 顺序查找算法基本思想 顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。 4、 ”乱序扑克牌查找“——顺序查找自然语言描述： 问题描述：在不考虑扑克牌花色的情况下，仅在A到K,13张扑克牌中寻找指定的牌。扑克牌2～ 10 为数字本身,A 为 1 ,J 为 11 ,Q 为 12 ,K 为 13，变量Key存储要查找的牌。 第一步：将代表13张扑克牌对应的数字存储于数组d中， 要查找的扑克牌对应数字储于变量key中。 第二步：依次将d数组中元素与key进行比较。 第三：若数组中某个数与key相等则查找成功,若所有元素比较完毕仍找不到，则查找失败。 提问：上述算法过程是必修1中学习过的什么算法？ 回答：枚举算法。 5、 ”乱序扑克牌查找“——顺序查找过程演示： 问题： 若将上述问题规模扩大，在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(“没找到！”) 6、 顺序查找算法小结 三、【创设情境】：在新的扑克牌（ 新扑克牌按照A到K有序排列）中寻找”红桃5“，除了顺序查找有没有更高效的查找算法？（参考选择性必修1《数据与数据结构》第4章中的“猜数字游戏”的方法。） 回答：可以使用对分查找方法。 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 w