资源简介

课题 算法的评价方法 课时 1课时
学习目标 1.通过“数”算法中循环的执行次数，认识到解决同一问题的不同算法可能存在 时间效率上的差别，初步掌握算法效率评价的方法。 2.通过实验探究，观察相应程序的执行，比较多种算法的效率，形成算法效率的 意 识 。 3.通过实践，知道算法效率与问题规模有关，初步理解算法的时间复杂度。
学习重点 初步掌握算法效率评价的方法 学习难点 多种算法的效率比较
学习准备 PPT、任务记录单、顺序查找和二分查找的参考程序
学习过程
学习版块 学生活动 教师活动 设计意图 改进设计
回顾：游戏体验，复习旧知 打开上节课的“猜数字”游戏程序代码，与同桌交流，回顾知 识。同桌之间确定目标数后，采用不同的方法玩“猜数字”游戏， 比一比谁猜的次数更少。思考：如何评价哪种算法更“好”呢 教师出示“猜数字”游戏程序代码，引导学生简单回顾：同一 个问题可以采用多种算法来解决。组织学生采用不同的方法猜数 字，比一比谁猜的次数更少。教师运用引导问题“在前一课中，我 们学习了在1～100内查找目标数的2种算法。如何评价哪种算法 更‘好’呢”,启发学生根据猜数字次数的不同结果提出疑问并展 开讨论。 通过游戏体验，回顾猜数字游戏的不同算法，提出疑问： 如何评价算法的“好” 引导学生思考算法评价的标准，激发学习兴趣。
讨论：小组交流，提出猜想 1.根据教师提供的问题支架，同桌之间展开讨论。 2.汇报算法的评价方法，交流算法效率的影响因素。 1.教师引导学生依据问题支架讨论分析：“算法具有多样性， 但如何知道我所设计的算法好不好呢 有什么标准吗 如何评价猜数字游戏中顺序查找算法和二分查找算法的好与差呢 影响算法效率的因素有哪些 ”学生讨论交流时，教师巡视课堂，适时参与学生的探讨交流。 2.分别选择巡课时交流讨论热烈的小组和探讨交流成果明显的 两组进行汇报，教师点评学生的回答，师生共同总结讨论结果。教师提出算法评价的标准；教师进一步引导学生提出实验猜想。 教师提出评价算法的维度，引导学生制订评价算法的规 则。通过讨论分析，学生厘清实验探究内容并进行实验猜想，为接下去的实验探究做好铺垫。
建构：剖析过程，实验验 证 活动一 算法的评价方法 1.以顺序查找算法在1～100内查找目标数37为例，思考：如 何计算算法运行时间 2.集体观看课件演示顺序查找数据比较过程，数出需要比较的次数。 3.自主阅读顺序查找程序代码，推理判断程序中的while 语句执 行的次数，模拟执行过程并估算循环执行次数。 4. 根据变量cai 的数值决定循环语句while 执行次数的特点，修 改程序，增加统计次数变量ci 。对照流程图，填写程序代码。 5.汇报讲解算法步骤，运行程序并验证预测。总结算法的评价方法：用循环语句执行的次数来评估算法的时间复杂度。 活动二 相同数据规模下不同算法评价体验 1.以二分查找算法在1～100内查找目标数37为例，思考：如 何计算算法运行时间 2.集体观看课件演示二分查找数据比较过程，数出需要比较的 次数。 3.自主阅读二分查找程序代码，判断推理程序中的while语句执 行的次数，估算循环执行次数，并分析比较取中间数的次数和循环 执行次数之间的关系。 4.思考相同范围内查找同一个数哪种算法的运行时间更短，通 过实验比较相同范围内查找同一个目标数时顺序查找算法和二分查 找算法的运行时间。 实验一：相同数据规模下不同算法的效率对比 在1～100范围内，分别采用顺序查找算法和二分查找算法查 找目标数1、50和100。运行程序代码，记录循环执行次数并填写实 验结论。 活动三 不同数据规模下算法评价体验 1.探索利用二分查找算法在1～1000范围内查找目标数37,记 录循环执行的次数，并尝试写出二分查找算法的比较过程。 2.根据表2修改程序中的查找数据的范围，运行程序，观察二 分查找算法在不同数据范围内查找目标数37时的while语句执行次 数并记录，填写实验结论。 实验二：不同数据规模下算法的效率对比 根据教师提供的程序修改代码，验证算法运行的时间与待求问题数据规模之间的关系。 ① 教师提出算法的评价标准：好的算法，除了符合正确性、有效性的标准外，还需要有较高的算法运行效率，即算法运行所消耗 的时间较短。估算算法的运行时间，可以在问题规模相同情况下， 将算法中的循环语句的执行次数作为度量标准。引导学生以顺序查找算法在1～100内查找目标数37为例，思考：算法运行时间如何 计算 ② 教师出示课件，演示顺序查找数据比较过程，引导学生数出 需要比较的次数。 ③ 教师出示顺序查找程序代码，引导学生观察程序中的while 语句执行了多少次，模拟算法执行过程，估算循环执行次数。 ④ 教师引导学生探索发现，顺序查找程序执行时，变量cai 的 数值决定了循环语句while会执行的次数。启发学生优化算法，增 加统计次数变量ci, 修 改 程 序 。 ⑤ 教师先选择运行验证不成功的学生汇报演示，再请验证成功 的学生补充讲解算法步骤，运行程序，验证预测并总结得出算法的 评价方法：用循环语句执行的次数来评估算法的时间复杂度。 1.教师提示：“解决同一问题的不同算法，在执行时的运行时 间是有一定差异的。”引导学生以二分查找算法在1～100内查找目 标数37为例，就“如何计算算法运行时间”展开思考。 2.教师出示课件，演示二分查找数据比较过程，引导学生分析二分查找取中间数、和目标数比较、改变查找范围，如此反复，直到找到目标数的比较过程，数出需要比较的次数。 3.教师出示二分查找程序代码，引导学生观察程序中的while 语句执行了多少次以及是怎么执行的，估算循环执行次数，分析得 出取中间数的次数和循环执行次数之间的关系。 4.教师引导学生根据猜想，运用实验探究相同范围内查找同 一个数哪种算法的运行时间更短。在实验完成后，引导学生总结实 验结论：不同算法解决同一问题在时间效率上有差别。通过对多组 数据的实验测试，发现在相同问题规模下，不同的算法查找同一个数，二分查找算法比顺序查找算法循环执行的平均次数要少。教师 进而提问“二分查找算法一定优于顺序查找算法吗”,引导学生思 考：不同数据规模下查找同一个目标数算法的效率一样吗 教师通过“不同数据规模下查找同一个目标数算法的效率一 样吗”的问题，引导学生利用二分查找算法，探索在1～1000范围 内查找目标数37时循环执行的次数，并分析二分查找算法的比较 过 程 。 引导学生完成实验二并总结实验结论。 教师提出算法的评价标准，引导学生思考算法运行时间的度量方法。通过回顾前一节课内容，将旧知与新知建立联系，让学生探究发现顺序查找中cai的数值决定了while循环语句执行的次数，体现了以生为本的课堂理念。 通过分析，找出手动计算的缺点， 启发学生用变量计数，进而总结出用循环语句执行的次数评估算法运行时间的方法。通过阅读、理解、修改运行程序，进而验证猜想，促进计算思维的形成。 实验一让学生观察讨论辨析，继而发现二分查找取中间 数的次数决定了while语句执行的次数。通过阅读、理解和修改运行 程序，让学生验证猜想并填写任务记录单，培养他们的科学探究精 神。在实践中，学生对比问题规模相同时算法的不同效率，知道不 同算法解决同一问题在时间效率上有差别。 “问题规模”是一个比较抽象的概念，通过实验二的实践，学生对“问题规模”的概念有更加直观的感受。二分查找法适 合应用在数据量较大时，对于有序的数据，它可以大大减少计算量。 通过实验的探究，学生能深刻体会算法步骤的执行次数与问题的数 据规模有关。
应用：链接生活，迁移应用 1.举例说说生活中应用二分查找算法的案例，如猜价格、修电 路、除次品等。 2.选择自己熟悉的特定场景，剖析具体应用过程。例如：某小区突然停电，电工需要排查一段10km 长的电线。如果沿着线路一 小段一小段地排查，耗时耗力。每查一个点要爬一次电线杆，假设 10km 长的电线共有200根电线杆。 1.教师启发学生找一找身边应用二分查找算法的案例。 2.基于生活案例，借助用二分查找算法找故障电线的过程，引 导学生分析过程： (1)设电线两端分别为A 、B, 电工首先从中点C (第100根电 线杆)查，用随身带的仪器向两端测试时，发现AC 段正常，则断 定故障在BC 段 。 (2)然后再到BC 中点D,发 现BD 正常，可见故障在CD 段， 再 到CD 中 点E 进行排查。这样每查一次，就可以把待查线路长度 缩减一半。 (3)只要经过7次查找，就可以将故障发生的范围缩小到50～100m 左右，即在一两根电线杆附近。这样每次一半一半地测 试，很容易就能找到故障点。 通过分析生活中的实例，让学生根据需求设计合适的算法并评估算法运行效率，知道算法运行效率的重要性，进一步激发学生的学习兴趣。
小结：自我评价，总结提升 1.完成在线问卷。 2.总结课堂知识点。 教师提供问卷网址，引导学生完成在线问卷。学生完成后， 教师及时反馈问卷答案。 引导学生进行课堂总结，回顾算法的评价方法、算法的时间复杂度等，初步形成算法效率的意识。 通过问卷对学习成果进行检测。回顾总结算法的评价标准有正确性、有效性、较高的运行效率。通过实验体验算法的评价，引导学生理解不同算法解决同一问题时在运行时间上有差别，算法中循环语句的执行次数与问题规模有关。
作业指导
板书 算法的评价方法 顺序查找 二分查找第9课 算法的评价方法
任务记录单
实验一：相同数据规模下不同算法的效率对比
在1～100范围内，分别采用顺序查找算法和二分查找算法查 找目标数1、50和100。运行程序代码，记录循环执行次数并填写实 验结论。
实验二：不同数据规模下算法的效率对比
表1相同规模下不同算法的效率对比记录表
目标数
查找算法
循环执行次数
顺序
1
二分
顺序
50
二分
顺序
100
二分
实验结论：数据规模
(相同/不同)情况下，查找
(相同/不同)的目标数，
(顺序查找/二
分查找)算法平均查找次数更
(多/少)，算法运行效
率更
(高/低)。
表2不同数据规模下算法的效率对比记录表
查找范围
目标数
顺序查找循环执行次数二分查找循环执行次数
11000
37
1-10000
37
1-100000
37
1~-1000000
37
1-10000000
37
实验结论1：随着查找的范围变大，顺序查找循环执行次数
(增多/减少/不变)，二分查找循环执行次数
(增多/减少/不变)。
实验结论2：数据规模
(相同/不同)的情况下，
查找目标数37时，
(顺序查找二分查找)算法平均查
找次数更
(多/少)。

展开更多......

收起↑