浙教版高一《算法与程序设计》——“对分查找”教学设计（2课时）教案.doc

浙教版高一算法与程序设计“对分查找”教学设计（2课时）作者：宁波市镇海中学吴倩（第一作者）付刚邮编: 315200 电话:一、设计思想本课以浙江省普通高中新课程实验信息技术学科教学指导意见为指导，在高中一年级下学期算法与程序设计选修课阶段开展教学。本课以培养学生能力为目标，突出学生观察、实践、应用能力，领悟生活中的相关应用。二、教材分析1高中信息技术课程标准提出信息技术课的基本理念之一是强调问题的解决，倡导运用信息技术进行创新实践。在课程设置上，算法与程序设计可在高一下学期选修，其中“对分查找”算法是学生技能提升的重要一课；在信息技术学科教学指导意见中“对分查找”算法要求学生了解对分查找的概念、初步掌握该算法，重点是对算法分析，以讲授法为主，适当让学生讨论与体验。2对分查找算法由理解该算法概念、流程图分析、算法描述、程序实现组成，在“查找”模块中是重点要求部分；3初中阶段未学习过相关知识，故这部分作为全新内容学习。三、学情分析1通过信息技术基础必修课信息的加工算法与编程、算法与程序设计选修课的初步学习，学生已经对算法有一定了解，能够应用流程图和伪码对一些简单算法进行分析，能够初步应用VB编写简单应用程序、实现算法。2根据信息技术学科教学指导意见，算法与程序设计可按以下顺序教学：先上“算法和算法表示”，再上“面向对象程序设计的基本知识”，接下来进行“算法实例的程序实现”、“算法实例”、“VB程序设计初步”穿插学习。学生在此可能会遇到来自于对分查找法的分析、查找效率以及程序实现的困难；3学生学习此部分，会自然而然地把“对分查找”和“顺序查找”联系起来，因为顺序查找易于实现，相比之下，对分法稍稍有些困难；也有学生可能会采取先掌握流程再用自然语言实现、进而用程序实现的方法。对此，在教学上可通过流程图的演示帮助学生理解对分查找比顺序查找高效。四、教学目标知识性目标：1. 了解并熟悉对分查找算法的概念、能列举现实生活中的应用实例；2. 能解释对分查找中数字之间的逻辑联系，明确对分查找算法相对于顺序查找法的优势；3. 具备知识迁移能力，发现对分查找算法的现实应用，总结对分查找的规律，能把学习所得应用于现实生活中。技能性目标：1. 能通过流程图，剖析对分查找算法的原理；2. 能使用自然语言表达对分查找算法，并能应用信息技术与他人交流自己对此部分知识的理解；3. 能熟练“对分查找算法”的程序实现，有效利用此算法解决实际问题。情感、态度、价值观目标：要求学生从“了解理解实现应用”对分查找算法的过程，获得对该算法的感性认识，表达对分查找算法的学习体验，养成追求算法高效率、增加程序效率意识、并领悟对分查找算法对于现实应用的价值。五、重点难点重点：分析对分查找算法难点：程序实现、知识迁移六、教学策略与手段以流程图的完善为线索，以生动的、较有价值的实例穿插在各个教学环节，辅助学生理解以提高效率为目标，让学生在应用中体会顺序查找与对分查找的效率采用比较、分组讨论、探究教学法综合运用的教学手段七、课前准备1学生的学习准备：掌握查找的概念，预习对分查找法。2教师的教学准备：CCTV“幸运52”中猜价格游戏的片段；对分查找算法的演示材料和数据。3教学环境的设计与布置：给学生分组（4-6人一组）；八、教学过程播放CCTV“幸运52”中猜价格游戏的片段。猜一件物品的价格。竞猜者说一个价格，再根据主持人提示价格的高低修改下次猜测的范围小组合作模仿视频片断，亲身体验猜价格技巧。由同学研究并指出如何根据高低的提示做出相应策略？分组讨论如果按照“顺序查找”策略来猜价格，情况会怎么样？切入正题今天我们要学习的就是类似于视频中猜价格策略的一种查找算法对分查找算法，它还有两种叫法：折半查找法、二分查找法。它是在有序的数字系列中查找一个数字，可以先确定待查数字所在的范围，然后逐步缩小范围直到找到或找不到记录。例如有序数字系列：7、18、19、29、30、57、65、70、83、90。我们可以把它看作一个一维数组学生根据已学知识完成声明数组和赋值，因为此数组不仅在一个过程中有效，故要以通用里声明Dim d(1 to 10) As IntegerPrivate Sub Form_Load()Dim i As Integeri=1Do While i=10d(i) = Val(InputBox(请按顺序输入数组中各元素的值，第 & i & 个：)List1.AddItem (Str(d(i) i=i+1 LoopEnd Sub我们需要用到的变量：被查找的数Key（由用户输入）、最大数的下标High、最小数的下标Low、位于数字系列中央的数字为第Mid，其中Mid=Fix（Low+High）/2，应满足LowHigh。学生完成对变量的声明和赋值Dim Key As IntegerDim High As IntegerDim Low As IntegerDim Mid As IntegerHigh=10:Low=1 Mid=Fix(High+Low)/2 回顾Fix()函数用法Key=Val(Text1.Text) 回顾Val()函数用法结合猜价格策略 先把Key与第Mid元素进行比较，最好的情况：Key=d(Mid)，这样可以直接输出Key的位置，程序结束；如果Keyd(Mid)，则可以判断被找的数在d(Mid)的前方，而d(Mid)及其后面部分不可能有Key，可以排除，数组的规模缩小近一半，此时可把d(Mid)前的元素作为新数字系列的最高位，使其下标置High。即High=Mid-1提问 既然需要根据d(Mid)和Key的大小关系做出不同的决策，则程序实现需要用什么控制结构？开始High=10:Low=1Key=d(Mid)?结束Keyd(Mid)?YNHigh=Mid-1Mid=Fix(High+l)/2)输出结果：Mid让学生结合上述分析做此部分流程图片断培养学生由此及彼的能力Key=d(Mid)?结束Keyd(Mid)?YNLow=Mid+1YN开始High=10:Low=1Mid=Fix(High+l)/2)High=Mid-1输出结果：Mid既然Keyd(Mid)又当如何呢？请大家思考并小组讨论，之后在上面流程图的基础上划出另一分支。学生按流程图写出代码If Key = d(Mid) Then MsgBox (在第 & Mid & 个位置！) ElseIf Key d(Mid) Then High = Mid - 1Else: Low = Mid + 1End If引出循环结构在其中的运用教师 每当有了新的High和Low，总在算出新Mid，再比较d(Mid)与Key，相等则输出，否则确定新Low或新High，这样重复的操作可以用什么控制结构？学生 循环结构让小组讨论本循环的条件、循环体的组成，并在流程图中体现Key=d(Mid)?结束Keyd(Mid)?YNHigh=Mid-1Low=Mid+1YN开始High=10:Low=1Mid=Fix(High+l)/2)Low=High?输出未找到输出结果：Mid对照流程图写出代码Do While Low = High Mid = Fix(Low + High) / 2) If Key = d(Mid) Then MsgBox (在第 & Mid & 个位置！) Exit Do ElseIf Key d(Mid) Then High = Mid - 1Else: Low = Mid + 1 End IfLoop知识提升对规模为n的数组，通过1次查找折半，新的查找范围不会超过，2次查找，新的查找范围不会超过，则经过K次查找，所剩的查找范围不会超过。因此效率比顺序查找逐个排查要高得多。此程序初步成型，但不够完善，如不能对找不到的情况进行友好反馈，请同学们结合顺序查找的类似方法完善之。Dim Find As BooleanFind = FalseDo While Low = High Mid = Fix(Low + High) / 2) If Key = d(Mid) Then MsgBox (在第 & Mid & 个位置！) Find = True Exit Do ElseIf Key d(Mid) Then High = Mid - 1Else: Low = Mid + 1 End IfLoopIf Find = False Then MsgBox (未找到！)学生作品上交评价学生对此部分学习的评价，对教师教学的评价，对学生过程心得、疑难的回馈重提CCTV猜价格视频，让学生在带着对分查找算法的思想看竞猜技巧九、总结对分查找算法的实施前提：有序数字序列对分查找算法的原理、流程及代码设计对分查找算法的效率【问题研讨】l 如何避免输入非数字l 本程