数据查找-学习任务单 (2)

学习任务单 课程基本信息 课题 数据查找 学习目标 1.通过具体实例，理解查找的概念和基本方法。 2.掌握顺序查找的算法思想，熟悉顺序查找算法的代码框架。 3.理解并掌握对分查找的算法思想，熟悉对分查找算法的代码框架。 4.掌握顺序查找与对分查找算法的使用条件和优缺点。 课前学习任务 1.复习浙教版信息技术必修1《数据与计算》第3章3.3.2枚举算法及其程序实现的内容，能熟练使用枚举算法基本框架。 2.复习浙教版信息技术选择性必修1《数据与数据结构》第2章2.1.2数组的基本操作，能熟练使用数组元素访问及数组遍历的方法。 3.复习浙教版信息技术选择性必修1《数据与数据结构》第4章4.1.2二叉树“猜数字游戏” 4、复习浙教版信息技术选择性必修1《数据与数据结构》第5章5.1.1算法的效率，时间复杂度。 课上学习任务 【学习任务一】 在打乱的扑克牌中寻找出“红桃5”这张牌，讲一讲你寻找的方法。 【学习任务二】 顺序查找算法程序实现： 数组d[0]-d[n]存储被查找的数据，key中存储要查找的数据。 for i in range（ ）：#遍历数组索引 if ：#数组中某个索引位置上的数与key相等 #输出查找数据在数组中的索引位置 #结束查找 else: #输出“没找到”。 【学习任务三】 对分查找算法程序实现： 数组d[0]-d[n]升序存储被查找的数据，key中存储要查找的数据。 key=int(input())；f=False；i=0 #变量f=False 表示查找失败，f=True 表示查找成功 j= #j表示查找区间的终点索引 while : #查找条件 mid= #计算查找区间中间位置 if d[mid]==key: #查找成功并结束查找 f=True break if d[mid]>key: #查找不成功，调整下一次查找的区间范围 else: if f==True: #输出查找结果 print("查找成功！下标为"+str(mid)) else: print("没有找到！") 【学习任务四】 顺序查找算法和对分查找算法对比： 查找算法顺序查找对分查找优点算法简单，对数据是否有序没有要求。查找效率高，适用于大数据查找。 缺点查找效率较低，当数据量大时不宜使用。要求被查找数据必须有序。查找次数一般情况是，当需要查找的数据规模为 n 时，顺序查找最少查找____次，最多查找____次，其平均查找次数是_____。最少查找次数____，无论是否找到，最多进行_____次查找。算法思想顺序查找本质上是一种_____算法思想。对分查找思想符合_____算法的思想。 推荐的学习资源 顺序查找平均查找次数：第一个数的比较次数为1，第二个数的比较次数为2。。。以此类推第N个数的比较次数为N，所以总的比较次数为1+2+…+N=N(N+1)/2,平均比较次数为(N+1)/2,也即平均查找长度。 对分查找最多的查找次数(n个数据)：n个数据对分x次最后变为1个数据，n/2**x=1，x=log2n 最后一个数据还要参与一次查找因此最多查找次数：int(log2n)+1。 3.猜数字游戏：在猜数字游戏中，甲方事先在纸上写出一个100以内的正整数，让乙方猜，乙方每猜一次，甲方都会告诉乙方“猜大了”或是“猜小了”，直至猜出正确结果。乙方如果采取“折半”的策略进行猜数字，就一定能够在7次以内猜对结果，具体过程可抽象成如下图所示的二叉树（每个节点为乙方所猜的数字，每条边实际数字与所猜数字之间的大小关系，图中仅呈现前4次的猜数字情况）。 4.推导大O阶的方法（时间复杂度）： 用O()来体现算法时间复杂度，称之为大O记法。其推导方法如下: （1）用常数1取代运行时间中的所有加法常数。 （2）在修改后的运行次数函数中，只保留最高阶项。 （3）如果最高阶项存在且不是1，那么去除与这个项相乘的常数。得到的结果就是大O阶。 例如，1/2n(n-1)保留高阶项，1/2n2去除常数即n2。 ... ...