第三节 排序和查找 教案

第三节 排序和查找 一、教材分析 排序和查找算法是一种在数据处理时经常要用到的算法思想。在日常生活和学习中，经常需要对各种数据进行查找，而且总是希望要查找的数据井然有序，这就是排序问题。 二、教学重点、难点 重点：理解和掌握两种排序和查找方法的基本思想 难点：熟练运用排序和查找算法的基本思想分析实际问题和实现程序设计过程。 三、教学过程 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)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 = " ... ...