江苏省海安高级中学高中信息技术选修 算法与程序设计 二分法查找 教学设计
二 分 法 查 找 教学设计
一、教材与学情分析
本课选自教育科学出版社出版的高中《算法与程序设计》(选修)第三章《算法的实现》。教材是以学生已有知识经验为基础,从提高学生分析与解决问题的能力出发,让学生体验并掌握二分法查找算法的思想,并将这一算法体现到具体的应用中。但对于本地区选修《网络技术应用》的学生来说,这部分内容都是零基础。
二、教学目标
知识与技能:理解二分法查找的算法思想,学会使用二分法查找解决问题。
过程与方法:通过学习并应用二分法查找数据的过程,提高分析与解决问题的能力。
情感、态度与价值观:培养学生的自主学习、互相协作、分析问题的能力。
三、教学难点
二分法查找算法的理解,如何使用二分法解决实际的问题。
四、教学过程
(一)创设情境、激发兴趣、导入课题
[游戏1]:[来源:Zxxk.Com]
现在有20个小圆球,其大小、颜色等完全相同,其中有一个小球比其它19个小球重5克,现给你一天平(无具体刻度),要求将该小球找出来,我们该怎么办?
[设计意图]:通过小组讨论与交流,部分小组认为两两比较,这种方法可以解决问题。教师追问:不管较重的小球在什么位置,我们能不能用更少的次数找出小球?有小组能够想到:先
将20个球分为两分(每10个一分),分别放到天平左右两个托盘中,如果,左则重,将左则球分为两等分(每分5个球),再将这两部分别放到天平的左右两则,如果左右两则平衡,则另一小球就是我们要找的小球,如果不等,再将重
的一侧分为两分,以此类推,就能很快找到小球。(不管小球在何处,都能在5步以内找到该小球)
[游戏2]:
请两个同学到讲台前配合玩一个关于数字竞猜的小游戏,由第一个同学随意在
纸片上写下一个数字(整数),同时告诉第二个同学所写数字的区间(100-300之间),由第二个同学来猜,第一个同学根据第二个同学所猜的数字给出提示:“高了”、“低了”、“正确”。
师:我们仔细分析这个同学的猜数过程,可以发现每次猜的数都是相应范围中间的数,这实际上采用了“二分法查找”算法思想。这是一种非常重要的编程算法思想。
设计思想:通过游戏的吸引力,激发学生学习兴趣,形成良好的课堂氛围,调动学生的求知欲望。通过这样的方式导入课题:一方面可以激发学生学习的兴趣和热情;另一方面也是让学生初步感受编程算法思想——二分法。为下面教学活动的开展做好铺垫。
(二)学生自主探究,教师讲解分析
师:二分法查找中对被查找的数据有没有要求呢?从被猜数字的范围100~300可以看出,这是一个有序的数列,也就是说,被查的数据必须是有序的,否则二分法查找无法进行。第二位学生猜数的具体过程到底是怎么进行的呢?
生:第一步:将100设为下界,300设为上界,取上下界的中间元素200与实际值225进行比较,200比225小。第二步:将200右边相邻的数201设为下界,上界还是300,取上下界的中间元素250与225进行比较,250比225大。第三步:将249作为上界,下界还是201,取上下界的中间元素225与225比较,正确,即猜中。
如果学生回答得不完整,教师可以补充。
师(强调):这是二分法查找的具体情况,那么推广到一般情况是什么样的呢?
学生交流之后,师生共同总结。
(1)用自然语言描述
设置4个变量,low(下界)、high(上界)、mid(中间元素)、real(实际值),设置下界low=100,上界high=300,取中间元素 mid=(low+high)/2,mid=200,比real(225)小,左侧舍弃,取mid右侧数据作为low,即low=mid+1,再取mid=(low+high)/2,比225大,右侧舍弃,取mid左侧数据作为high,即high=mid-1,以此类推,如找到,则结束。
(2)动画演示
播放“二分法查找 微视频”,帮助学生进一步理解二分法查找算法思想。
(3)用流程图描述
用投影展示事先准备好的流程图。 并请学生根据二分法查找思想及过程,将四个