资源简介

查找——对分查找
一、教学分析
算法是计算机程序的灵魂。《算法与程序设计》课程的教学目标，就是让学生体验算法的思想，了解算法在解决问题过程中的地位和作用。对分查找是算法中一个基础的算法，也是选考中要求的重要算法之一。
学生之前已经学习了顺序查找，为本课时的学习奠定了查找算法的基本概念。对分查找共2个课时，本课时是第1课时，通过本课时的学习，使学生掌握对分查找的基本原理，为第2课时对分查找的程序实现打下基础。因此本课时是承上启下的关键课时。
二、教学目标
1. 知识与技能：
理解对分查找的概念和特点，通过分步解析和分析多种不同的查找键值获取对分查找的解题结构。
2. 过程与方法：
通过自主探究实践，逐步归纳对分查找的基本思想和方法，剖析算法，为后续的程序实现奠定基础。
3. 情感态度与价值观：
通过亲身体验，模拟对分查找的过程，感受对分查找的魅力，促进学生计算思维的形成。
三、教学重点和难点
重点：
1. 对分查找的原理。
通过游戏引入对分查找算法，使学生得到对分查找感性体验，能更清晰地理解对分查找的原理。
2. 对分查找范围的下标变化及中间值下标的变化。
借助动画全程模拟对分查找过程，使学生在亲身体验中理解对分查找的范围下标和中间值下标的变化过程。
难点：
1. 对分查找的最多查找次数的计算。
通过引入二叉树帮助学生掌握最多查找次数的计算，借此突破本课难点。
四、教学过程
1. 活动一：新课引入
（1）教师展示“砸金蛋”游戏一：9个金蛋，每个金蛋藏有数字（数字随机无序），砸出幸运数字“25”，需要几次。
（2）教师展示“砸金蛋”游戏二：商家良心发现，把金蛋按数字从小到大排序，此时要砸出幸运数字“25”，又该如何砸，才能以最少砸蛋次数砸出。
（3）学生讨论回答。
（4）教师引导：这个游戏含有一个非常经典的算法，引出对分查找的概念。
2. 活动二：原理感知
（1）学生利用“对分查找模拟”动画观看对分查找的全过程，并根据“学习任务单”上的任务一“看动画感知原理”的要求结合动画填写任务单中每次比较的范围、mid值以及key与d（min）的关系，从中
了解对分查找的原理。
比较次数
比较范围
mid
Key与d(mid)的关系
第一次
d(1)~d(11)
6
Key第二次
第三次
第四次
（2）教师在学生完成任务一后，与学生一起进行分析
A、i和j下标的功能
B、mid的计算公式
C、i和j在不同情况时的变化
3. 活动三：原理剖析
（1）为了更深刻地理解对分原理，学生分组实践“学习任务单”中的任务二“推算数据剖析原理”。将需要4次查找的key值（包括查找不成功）融入任务中。使学生在推算过程中，逐渐归纳出需要不同次数查找到的数据个数，为本课难点“最多查找次数”积累经验。
（2）任务二完成的同学可以尝试完成任务三“归纳总结”。
（3）教师检验任务二的完成情况，借助二叉树，分析分别需要1次、2次、3次、4次的数据。
（4）分析得出n个数据的最多查找次数的计算公式，对比总结两种查找。
序列要求
最少查找次数
最多查找次数
顺序查找
无要求
1
n
对分查找
有序
1
└Log2n┘+1
5. 活动四：巩固提升
（1）学生借助极域系统的测验平台，进行一次小测验，借此巩固知识。
（2）教师根据测验结果进行实时分析，帮助学生完成知识的巩固与提升。

展开更多......

收起↑