4.3非数值计算——二分查找 教案 2022—2023学年高中信息技术教科版（2019）必修1

4.3 非数值计算——二分查找
[学科核心素养]
在学习二分查找的算法思想后，能够敏锐地对信息的价值做出判断，并能用恰当的方式获取与处理信息，从而有助于问题的解决。（信息意识）
在学习活动中，能够选择合适的方法来解决问题，提升算法思想，可以用计算机的思维来解决生活中的实际问题。（计算思维）
在完成学习任务中，能够创造性地解决问题，能够运用数字化学习工具开展自主学习和合作学习，能够养成创新的习惯。（数字化学习与创新）
具有一定的信息安全意识与能力，能够遵守信息法律法规，信守信息社会的道德与伦理准则，既能有效维护信息活动中个人的合法权益，又能积极维护 他人合法权益和公共信息安全。（信息社会责任）
[课程标准要求]
①运用合适的算法形成解决问题的方案。
②了解算法中的分治思想，并运用二分查找解决实际问题。
③体验递归算法，并结合具体问题开展编程实践。
[学情分析]
这节课主要介绍非数值计算中的分治方法的概念以及二分查找的算法思想，主要用到python语言来学习，教学对象为高一学生，本节是必修一第四章的第三节内容，那么在之前的学习中，学生已经初始python语言，并能编写简单程序，对一些基本循环语句有初步了解，也学习了各种算法，对经典问题的解决也有一定的基础。但是部分学生对代码只停留在记忆层面，对一些问题的解决没有形成固定的算法思想。所以本节课来介绍一种二分查找的思想。
[教学目标]
知识与技能
了解分治方法的概念，以及特点步骤等。
了解二分法的算法思想。
过程与方法
能够使用二分法的思想解决生活中的实际问题。
能够在python中用代码实现经典的二分法实例。
情感态度价值观
增强对信息技术的求知欲，养成积极地学习和使用信息、参与信息的态度。
通过完成活动,学生理解并掌握计算机语言处理问题的思维方式，感受编程的价值从而运用到实际生活中。
通过分组学习，提升团结协作学习的能力。
[教学内容分析]
本节为教科版必修一第四章的第三节的第一课时，主要来介绍分治法以及二分查找的思想，本节我们将学习分治法中的二分查找，以及迭代法，掌握在面对这类问题时的解决方式，完成算法设计;学会在生活中根据实际问题选择合适的方法，进而运用所学的知识解决问题。
[教学重难点]
重点：掌握二分查找的方法，来解决实际问题。
难点：能在python中熟练的编写二分查找的程序 ，快速的解决问题。
[教学方法]
问题解决法、启发法、创设情境、讲授法
策略：情境-陶冶教学策略、指导性探究
[教学准备]
网络机房、多媒体课件、网上学习平台，多媒体投影设备，录播教室，教科书。
[教学过程设计]
课堂导入。
上课前，教师展示课件，本节课学习的章节。并告知学生本节课的学习目标，提前预习几分钟。
教师提问：“同学们思考一下，计算一定得是数吗？’
答：计算的对象可以是自然界和人类社会的一切事物。某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。非数值计算更多探讨“算法”问题。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。
【环节设计】课前预习可以让学生带着问题进入课堂，在上新课时更容易接受和理解。
二．讲授新知。
1.分治策略的概念：分治策略是对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
2.所能解决的问题的特征：该问题的规模缩小到一定的程度就可以容易地解决。该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（前提）利用该问题分解出的子问题的解可以合并为该问题的解。（关键）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
3. 分治法的基本步骤，①将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。②若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。③将各个子问题的解合并为原问题的解。
【环节设计】介绍分治策略的概念及相关的知识。
三．互动游戏。
教师：老师将在心里说一个1~1000之间的数，同学们猜一猜这个数字是多少？（如果回答的数不对，老师将告知这个数比正确的数大还是小）。
学生回答几个数。教师提问：思考怎样才能最快地找到答案
板书：
最多需要10次即可找到答案，思考：如果是1~100，最多需要几次找到答案？如果是1~10000呢？
教师请学生回答。发现规律，2的n次方最接近总目标数，则最多需要n次即可找到答案。得出结论，用这种方法目标越大，优势越明显。
【环节设计】通过小游戏带学生体验二分法的优势，吸引学生的兴趣，为下面的介绍做铺垫。
四．详细介绍二分查找。
1.概念：二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。 每一次比较后可以将查找区域缩小一半。
分组活动——翻页数比赛。
假设我们的信息技术书本为200页，目标为68页，记录下每次翻开的页数，看看谁找的最快。
教师展示一组的表格。
【环节介绍】详细介绍二分查找的概念思想。
五．在python中编写二分查找的代码。
1.讲解例题。如何判断一个数在已知数组中的位置？
A=[1,5,3,7,36,12,68,79,2]
A.sort()
num=int(input(“请输入要查找的数”))
left=0
right=len(list)-1
while(left<=right):
mid=(left+right)//2
if num>A[mid]:
left=mid+1
elif numright=mid-1
else:
print(“该数为数组中的第{}个数”.format(mid+1))
2.教师提问：如果输入的数据不在范围内，会出现什么结果呢？程序还需要在哪些地方进行完善？
i=0
for e in A:
if num==e:
……
else:
i++
if i==len(A):
print(“该数字不存在于当前数组”)
知识拓展。小游戏：如何找出1-1000之间的某个数？
import random
x = random.randint(1,1000)
while 0y = int(input("请输入这个数："))
if xprint("大了")
elif x>y:
print("小了")
else:
print("就是",x)
break
【设计意图】像学生讲解python中二分查找代码的实现。
六．课堂练习——补全翻字典程序。‘
课后预习作业——汉诺塔。
移动3个木盘的方法是：根据木盘叠放规则，要使A杆上最大的木盘（记为x)移动到C杆上（子问题1, 如图第4步），必须先把 x上方的所有木盘移动到B杆上（子问题2, 如图4中的前3步），然后再将B杆上所有的木盘移动到C杆上（子问题3, 如图中的后3步）。
【环节设计】本节课的课堂练习用于巩固所学知识，课后预习作业
七．课堂总结。
【设计环节】学生总结巩固本节课的知识。
[教学反思]
这节课通过一个猜数字小游戏引入，可以很好的激发学生的兴趣，经过举例，分组讨论，让学生对知识的理解掌握牢固。不足之处是对于算法的解释不太形象，可能会让一些同学难以理解。