第三节 排序和查找 教案
文档属性
| 名称 | 第三节 排序和查找 教案 |  | |
| 格式 | zip | ||
| 文件大小 | 119.0KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 沪教版 | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2017-12-29 14:35:37 | ||
图片预览
文档简介
第三节 排序和查找
一、教材分析
排序和查找算法是一种在数据处理时经常要用到的算法思想。在日常生活和学习中，经常需要对各种数据进行查找，而且总是希望要查找的数据井然有序，这就是排序问题。
二、教学重点、难点
重点：理解和掌握两种排序和查找方法的基本思想
难点：熟练运用排序和查找算法的基本思想分析实际问题和实现程序设计过程。
三、教学过程
1、新课导入
（1）热身：游戏（2分钟）
教师展示一件特色物品，让一个学生来猜这个物品的价格，其他学生只需要根据这个学生猜出的价格提示“高了”或是“低了”，如果学生能在五次内猜对这个物品的价格，就把这件物品“赠送”给他……。21·cn·jy·com
（2）讨论：你觉得怎么样猜可以猜的快一点呢？有什么技巧吗？你从这个游戏当中得到什么启示？(3分钟)
（3）教师引导：这个世界不是缺少问题，而是缺少发现，其实在这个游戏的背后，含有一个非常经典的算法。引出对分查找的的概念。21cnjy.com
2、新课：
教学步骤一：分析对分查找的原理和思想。（3分钟）
（1）对分查找是效率很高的查找方法，但被查找的数据必须是有序的。
（2）首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。
（3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
教学步骤二：分解对分查找算法（5分钟）
假设：用一个数组d（1 to 10）来存放升序的元素序列，用i表示查找范围的起始位置的下标，j表示终止位置的下标,mid表示中间位置元素的下标。2·1·c·n·j·y
（1）? ? ? ? 第一种情况：要找的值在后半部分；
以查找键KEY=48为例分析
第一次比较：
范围d(1)～d(10),mid= (1+10)2, d(mid)所以可以确定接下来要找的范围是后半部分。
比较后i=mid+1
第二次比较：
范围d(6)～d(10),mid= (6+10)2,d(mid)所以可以确定接下来要找的范围是后半部分。
比较后：i=mid+1
第三次比较：
范围d(9)～d(10)，
mid= (9+10)2,d(mid)=Key ，找到了。
思考：如果要找的是52???i,j,mid分别是多少？
这也说明当i=j的时候是查找的最后可能次数，这也是终止查找的一个关键条件。
教学步骤三：继续分解对分查找算法中包含的其他情况。
画一画：请仿照上面的画法,分别画出key=17和key=20的查找示意图。
（2）? ? ? ? 第二种情况：要找的值在前半部分；
以查找键KEY=17为例分析：
结果分析：
第一次比较后：j=mid-1第二次比较后：i=mid+1第三次比较后：找到了
（3）第三种情况：要找的值找不到；以查找键KEY=20为例分析：
结果分析：
第一次比较后：j=mid-1第二次比较后：i=mid+1
第三次比较后：i=mid+1第四次比较：i=j 但是d(mid)≠key,所以找不到。
教学步骤四：对各种情况进行归纳总结。
（1）Key与d(mid)的大小比较影响i,j的取值的规律：
i的取值规律：if d(mid)j的取值规律：if d(mid)>key then j=mid-1
用分支结构实现。
(2)继续进行重复查找的条件： i≤j，用循环结构实现。
教学步骤五：构建对分查找的流程图
教学步骤六：对分查找算法的初步程序实现。
教师事先设计好Vb窗体，学生只需要在相应的程序体输入代表算法思想的关键语句。
附主要程序体：
Private Sub Command2_Click()
? ?Dim key As Integer, mid As Integer, i As Integer, j As Integer
? ?key = Val(Text1.Text)
? ?i = 1: j = 10
??Do While i <= j
? ? mid = (i + j) 2
? ? If d(mid) = key Then
? ?? ?Text2.Text = "找到了，是第" & mid & "个"
? ?? ?Exit Sub
? ? End If
? ? If d(mid) < key Then
? ?? ?i = mid + 1
? ?? ?Else
? ?? ?j = mid - 1
? ? End If
??Loop
? ? Text2.Text = "找不到"
End Sub
程序说明：1、获得要查找的数据key的值? ?key = Val(Text1.Text)
2、i,j赋初值。 i = 1: j = 10
3、求mid的值。mid = (i + j) 2
4、分三种情况，（1）如果key=d(mid),则如果 d(mid) = key 那么
Text2.Text = "找到了，在第" + Str(mid) + "个"。
（2）如果key>d(mid),那么i=mid+1 否则 j=mid+1
5、重复上述的3,4步，直到i超出j(或者理解为i<=j不成立，所以不能用for next,而要用do while语句）21教育网
6、如果有找到key,那执行第4步（1）步后应该输出找到的位置后退出程序，如果不退出，说明key没有找到，所以在相应位置要输出“找不到”。21世纪教育网版权所有
教学步骤七：评价。
评价学生的程序实现情况，并讨论或实践问题：如果是降序序列，该怎么样改动程序？如果序列元素不是10个，而是100个或更多呢？www.21-cn-jy.com
教学步骤八：总结提升。
（1）由于对分查找过程中的每次比较都能使得搜索空间减半，对分查找将不会使用超过log2n次比较来找到目标值。【来源：21·世纪·教育·网】
（2）提升对分查找算法的实际意义：同学们可能还没有意识到二分查找是多么高效，那不妨设想一下在一个包含一百万个人名的电话簿中找一个名字，二分查找可以让你不超过21次就能找到指定的名字。如果你能够将世界上所有的人按照姓名排序，那么你可以在35步以内找到任何人。21·世纪*教育网
一、教材分析
排序和查找算法是一种在数据处理时经常要用到的算法思想。在日常生活和学习中，经常需要对各种数据进行查找，而且总是希望要查找的数据井然有序，这就是排序问题。
二、教学重点、难点
重点：理解和掌握两种排序和查找方法的基本思想
难点：熟练运用排序和查找算法的基本思想分析实际问题和实现程序设计过程。
三、教学过程
1、新课导入
（1）热身：游戏（2分钟）
教师展示一件特色物品，让一个学生来猜这个物品的价格，其他学生只需要根据这个学生猜出的价格提示“高了”或是“低了”，如果学生能在五次内猜对这个物品的价格，就把这件物品“赠送”给他……。21·cn·jy·com
（2）讨论：你觉得怎么样猜可以猜的快一点呢？有什么技巧吗？你从这个游戏当中得到什么启示？(3分钟)
（3）教师引导：这个世界不是缺少问题，而是缺少发现，其实在这个游戏的背后，含有一个非常经典的算法。引出对分查找的的概念。21cnjy.com
2、新课：
教学步骤一：分析对分查找的原理和思想。（3分钟）
（1）对分查找是效率很高的查找方法，但被查找的数据必须是有序的。
（2）首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。
（3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
教学步骤二：分解对分查找算法（5分钟）
假设：用一个数组d（1 to 10）来存放升序的元素序列，用i表示查找范围的起始位置的下标，j表示终止位置的下标,mid表示中间位置元素的下标。2·1·c·n·j·y
（1）? ? ? ? 第一种情况：要找的值在后半部分；
以查找键KEY=48为例分析
第一次比较：
范围d(1)～d(10),mid= (1+10)2, d(mid)
比较后i=mid+1
第二次比较：
范围d(6)～d(10),mid= (6+10)2,d(mid)
比较后：i=mid+1
第三次比较：
范围d(9)～d(10)，
mid= (9+10)2,d(mid)=Key ，找到了。
思考：如果要找的是52???i,j,mid分别是多少？
这也说明当i=j的时候是查找的最后可能次数，这也是终止查找的一个关键条件。
教学步骤三：继续分解对分查找算法中包含的其他情况。
画一画：请仿照上面的画法,分别画出key=17和key=20的查找示意图。
（2）? ? ? ? 第二种情况：要找的值在前半部分；
以查找键KEY=17为例分析：
结果分析：
第一次比较后：j=mid-1第二次比较后：i=mid+1第三次比较后：找到了
（3）第三种情况：要找的值找不到；以查找键KEY=20为例分析：
结果分析：
第一次比较后：j=mid-1第二次比较后：i=mid+1
第三次比较后：i=mid+1第四次比较：i=j 但是d(mid)≠key,所以找不到。
教学步骤四：对各种情况进行归纳总结。
（1）Key与d(mid)的大小比较影响i,j的取值的规律：
i的取值规律：if d(mid)
用分支结构实现。
(2)继续进行重复查找的条件： i≤j，用循环结构实现。
教学步骤五：构建对分查找的流程图
教学步骤六：对分查找算法的初步程序实现。
教师事先设计好Vb窗体，学生只需要在相应的程序体输入代表算法思想的关键语句。
附主要程序体：
Private Sub Command2_Click()
? ?Dim key As Integer, mid As Integer, i As Integer, j As Integer
? ?key = Val(Text1.Text)
? ?i = 1: j = 10
??Do While i <= j
? ? mid = (i + j) 2
? ? If d(mid) = key Then
? ?? ?Text2.Text = "找到了，是第" & mid & "个"
? ?? ?Exit Sub
? ? End If
? ? If d(mid) < key Then
? ?? ?i = mid + 1
? ?? ?Else
? ?? ?j = mid - 1
? ? End If
??Loop
? ? Text2.Text = "找不到"
End Sub
程序说明：1、获得要查找的数据key的值? ?key = Val(Text1.Text)
2、i,j赋初值。 i = 1: j = 10
3、求mid的值。mid = (i + j) 2
4、分三种情况，（1）如果key=d(mid),则如果 d(mid) = key 那么
Text2.Text = "找到了，在第" + Str(mid) + "个"。
（2）如果key>d(mid),那么i=mid+1 否则 j=mid+1
5、重复上述的3,4步，直到i超出j(或者理解为i<=j不成立，所以不能用for next,而要用do while语句）21教育网
6、如果有找到key,那执行第4步（1）步后应该输出找到的位置后退出程序，如果不退出，说明key没有找到，所以在相应位置要输出“找不到”。21世纪教育网版权所有
教学步骤七：评价。
评价学生的程序实现情况，并讨论或实践问题：如果是降序序列，该怎么样改动程序？如果序列元素不是10个，而是100个或更多呢？www.21-cn-jy.com
教学步骤八：总结提升。
（1）由于对分查找过程中的每次比较都能使得搜索空间减半，对分查找将不会使用超过log2n次比较来找到目标值。【来源：21·世纪·教育·网】
（2）提升对分查找算法的实际意义：同学们可能还没有意识到二分查找是多么高效，那不妨设想一下在一个包含一百万个人名的电话簿中找一个名字，二分查找可以让你不超过21次就能找到指定的名字。如果你能够将世界上所有的人按照姓名排序，那么你可以在35步以内找到任何人。21·世纪*教育网