《对分查找算法及程序实现》教学设计.doc

《对分查找算法及程序实现》教学设计一、设计思想根据《高中信息技术课程标准》的要求，本模块的学习目的是使学生在原有的基础上进一步体验算法思想，了解算法和程序设计在解决问题过程中的地位和作用因此，本节课从一个猜彩票末尾数字的游戏中展开，辅以如何利用对分查找法在升序数组中快速查找相应数组元素的讲解，讨论对分查找数据次数等讲解对分查找的作用，最后利用一些生活实例，说明了对分查找算法在生活中的作用二、教材分析本课内容来自浙教版高中信息技术的限定性选修模块《算法与程序设计》《学科教学指导意见》对于本课基本要求：1.初步掌握对分查找算法2.初步掌握对分查找算法的程序实现本课将教材内容第二章算法实例 2.4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是对分查找算法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时三、学情分析本次授课对象为高二选考班学生，他们通过了技术学考，已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同情况问题的一般规律，鉴于此，在教学中要积极引导学生采取分析、比较、归纳、迁移等学习策略。

四、教学目标知识与技能：理解对分查找的概念和特点，通过分步解析获取对分查找的解题结构，初步掌握对分查找算法的程序实现过程与方法：通过分析多种不同的可能情况，逐步归纳对分查找的基本思想和方法，确定解题步骤情感态度与价值观：通过实践体验科学解题的重要性，增强效率意识和全局观念，感受对分查找算法的实际作用五、重点难点教学重点和难点：分解并理解对分查找的过程六、教学策略与手段游戏导入，教师讲解算法思想，师生共同分步解析算法，师生评价学生当堂作业，教师引导学生认识生活中的对分查找算法思想问题实例，学生利用算法思想解决生活问题七、教学过程1、新课导入热身游戏（3分钟）教师展示一个装有一张福利彩票的“百宝箱”，让一个学生来猜这个彩票投注的末位数字，老师根据学生猜测的数字说明是“高了”或是“低了”，如果学生能在两次内猜对这个彩票的末位数字，就把这个彩票送给他……教师引导讨论怎样猜可以猜的快一点的技巧，它的背后，含有一个非常经典的算法，由此引出对分查找的的概念2、新课：教学步骤一：分析对分查找的原理和思想3分钟）（1）对分查找是效率很高的查找方法，但被查找的数据必须是有序的2）首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。

3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果教学步骤二：分步解析对分查找算法及练习（10分钟）（一）、讲解刚才的猜彩票末位投注数字比如，如何利用对分查找法查找数组0,1,2,3,4,5,6,7,8,9中的数字“1”第一次查找范围是整组，然后取整组数的中间数字来比较大小（如何取偶数项的中间数字呢，对分查找法一般找最中间偏小的那个数，往往可以用中间项位置=（首项位置+尾项位置）\2，这里的话就是（1+9）\2=5，即取第5项的数字“4”），发现，1<中间项“4”第二次查找范围是前半组，即0,1,2,3，然后取该组的中间数字来比较大小(因为中间项位置=（首项位置+尾项位置）\2，这里的话就是（1+4）\2=，2，，即取第2项的数字“1”），发现，1=中间项“1”因为已经找到数字“1”，查找结束了二）讲解以下例子假设：用一个数组a（1 to 7）来存放升序的元素序列，用i表示查找范围的起始位置的下标，j表示终止位置的下标,mid表示中间位置元素的下标11 22 33 44 55 66 77如果，要查找的值在数组的前半部分例如：查找22.则查找过程如下：然后，请学生完成学习任务单上的第二个任务，让学生仿照以上方法查找出以上数组中的数“11”。

然后教师利用“之江汇”的“移动讲台”功能的“随堂拍”抽查公布个别学生的作业情况最后小结:如果要查找的值在数组的前半部分，j=mid-1.再讲解：11 22 33 44 55 66 77如果，要查找的值在数组的后半部分例如：查找“77”然后，请学生完成学习任务单上的第三个任务，让学生仿照以上方法查找出以上数组中的数“77”然后教师利用“之江汇”的“移动讲台”功能的“随堂拍”抽查公布个别学生的作业情况最后小结:如果要查找的值在数组的后半部分，i=mid+1.最后讲解：11 22 33 44 55 66 77如果，要查找的值不在该数组中中的情况例如：查找50然后再让学生仿照以上方法在以上数组中查找出数字“43”然后教师利用“之江汇”的“移动讲台”功能的“随堂拍”抽查公布个别学生的作业情况最后小结:如果要查找的值在与各段数组的中间项不相等，则查找会结束.教学步骤三：对各种情况进行再次归纳总结当数组内元素值为升序排列时(1)如果keya(mid),新查找的范围为后半部分,j值不变,i=mid+1(3) ①如果找到了,查找会结束；②查找范围大于等于一个元素时,即在i<=j时重复查找,如果查找完最后一个元素，即i>j还是找不到,查找也会结束教学步骤四：构建对分查找的流程图教学步骤五：对分查找算法的程序代码填空体验。

红字代码部分填空）假设有7个数据已经按升序存放数组a中，查找值为key.i=1:j=7 ’查找区间初始化Xb=0 ’记录查找成功时的下标Do while i<=j m=(i+j)\2 ’计算出中间位置 if a(m)=key then xb=m exit do end if if keya(m)）教学步骤六：师生讨论总结对分查找数据的次数师生讨论刚才的彩票末位猜数字以及在数组“11,22,33,44,55,66,77”中查找数字，如果利用对分法去猜测的话，需要最多猜多少次最终讨论出log2n次教学步骤七：举现实生活中利用对分法的实例1).小王用天平称量物品的过程如下：先放置100克砝码，再将砝码改为50克，又将砝码改为75克…….通过这种策略，小王很快完成物品称重工作，此过程借鉴的算法是？(2).某大学的学生数据库中，包含3000条学生记录。

如果取出一条记录并与制定学号进行比较要花10毫秒时间，如果采用对分查找，最多只要检查多少个表项就能找到目标记录？(3). 10万大军三天内完成验血找出传染源的问题（可先将每1000人的血液样本组成1组，一共100份样本，让军医去验，再将含有病毒的血液样本再分组抽测……）最后布置作业:完成任务单里的其他任务详见学习任务单)。