【核心素养目标】第8单元 第2课《问题规模影响算法执行时间》教案【黔教版2024】《信息科技》五年级下册

中小学教育资源及组卷应用平台
第2课《问题规模影响算法执行时间》教学设计
课题 问题规模影响算法执行时间 单元 第八单元 学科 信息科技 年级 五年级下
核心素养目标 信息意识：能够具备良好的信息意识，这样才能更好地理解如何通过优化算法，降低计算资源消耗，从而提高效率。计算思维：通过学习本课内容，能够帮助学生从问题规模的增长中预测计算复杂度，并尝试优化解决方案。数字化学习与创新：在实际操作中理解算法的执行时间如何受问题规模变化的影响，进而在设计新的算法时更注重创新和效率提升。信息社会责任：明白根据问题规模优化算法，不仅可以提高技术效率，也有助于节约资源等，体现了在信息化社会中对可持续发展和社会责任的承担。
教学重点 1、明白问题规模会影响算法执行时间。
教学难点 1、能对比多个算法节约问题算法执行时间。
教学过程
教学环节 教师活动 学生活动 设计意图
导入新课 板书课题。1、活动背景依据一个猜数范围就判断猜数算法的效率，未必是可靠的。猜数范围会影响猜测次数，也就是算法步骤的执行次数与问题的规模有关。我们可以利用不同的猜数范围多做一些判断。2、新知导入观看视频 学习新知引入，观看教学视频。 用提问的方式引入课题，增强课堂互动性。将学生的注意吸引到课堂。
讲授新课 新知讲解：一、步骤执行次数与问题规模有关猜数游戏中，猜测步骤的执行次数会受到要猜数字自身数值的影响，最少1次就猜中，最多甚至需要将所有数字猜一遍。最多猜测次数对衡量算法的好坏具有实际意义，所以我们可以利用最多猜测次数进行算法效率的比较。猜测步骤的执行次数还会受到猜数范围的影响，随着猜数范围的变化，猜测步骤的最多执行次数会发生怎样的变化呢 活动：比较不同猜数范围的猜测次数选择本单元第1课中的“猜数算法1”猜数，为了使猜数次数最多，每次猜测的数字都是猜数范围的最大值。1.当所猜数字范围分别是0~20、0~50、0~100、0~150时，请你分析各需要猜测多少次才能猜中，并填写表8-2-1。表 8-2-1 不同猜测范围的猜中次数记录游戏序次第1次第2次第3次第4次目标数字2050100150猜测的范围0~200~500~1000~150猜中时的猜测次数56782.利用“折半查找”程序，通过调整猜数范围参数，验证你的结果是否正确，并填写表8-2-2。表 8-2-2 猜数结果对比游戏序次第1次第2次第3次第4次目标数字2050100150猜测的范围0~200~500~1000~150猜中时的猜测次数5678是否与我的结果一致是是是是3.猜数范围增加后，猜测次数是否也增加了 是否增加了同样的倍数 果猜测的范围增加，猜测次数的增加取决于算法的时间复杂度。例如，如果算法的时间复杂度是O(log n)，那么范围增加后，猜测次数的增加不是线性的，而是对数级的；如果时间复杂度是O(n)，那么增加的次数会是线性增长。因此，范围的增加不一定会导致猜测次数按同样的倍数增加，具体增加的倍数取决于算法的时间复杂度。拓展阅读“猜数算法 1”采用的是折半查找，折半查找要求线性表中的元素是有序排列的。当线性表中的元素按照从小到大的顺序排列时，折半查找的具体过程如下:将被查元素与线性表中间的元素进行比较，有3种可能:(1)如果表中间的元素等于被查元素，表示查找成功；(2)如果表中间的元素>被查元素，表示被查元素只能在查找表的前半部分，则在前半部分继续进行折半查找；(3)如果表中间的元素<被查元素，表示被查元素只能在查找表的后半部分，则在后半部分继续进行折半查找。随着数据输入规模的增加，猜测步骤的最多执行次数也随之增加，但是和数据输入规模增加的倍数并不一致。二、算法的时间效率可估算活动：对比不同算法的时间效率将“猜数算法 1”与“猜数算法 4”进行比较，分析哪个算法的效率高。将每次猜测的数字都设为猜数范围的最大值。1.当所猜数字范围分别是0~10、0~100、0~1 000、0~10 000 时，两种算法分别需要多少次才能猜中 填写表8-2-3。表 8-2-3 两种算法的猜中次数记录游戏序次第1次第2次第3次第4次目标数字10100100010000猜测的范围0~100~1000~10000~10000“猜数算法 1”猜中时的猜测次数471014 “猜数算法 4”猜中时的猜测次数101001000100002.分别运行“折半查找”和“顺序查找”程序，通过调整猜数范围参数，验证你的猜测结果是否正确。3.根据你的发现，分别为两种算法的猜中次数绘制折线图，你认为哪种算法的效率高 从理论上来说，折半查找（猜数算法1）的效率更高。因为折半查找每次都将查找范围缩小一半，而顺序查找是逐个数字进行尝试。随着猜测范围的增大，折半查找的增长速度远远慢于顺序查找。拓展阅读“猜数算法 4”采用的是顺序查找。顺序查找的基本思想是:从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较，如果某个元素等于被查元素，则查找成功，停止查找;如果将线性表中所有元素都比较完，仍未找到与被查元素相等的元素，则查找失败。无论基于哪种算法猜数字，随着猜数范围的扩大，猜数步骤的执行次数均会增加。但是随着输入规模的增大，我们发现顺序查找的猜测次数相对较多，效率较低;折半查找的猜测次数相对较少，效率较高。当猜数范围不断扩大时，不同算法的效率差异会越来越明显。也就是，随着问题规模的增加，可以通过算法中某些步骤的执行次数变化趋势比较算法效率的高低。三、课堂练习完成教材19—21页相关课堂练习题。四、拓展延伸1、时间复杂度与空间复杂度除了时间复杂度，空间复杂度也是影响算法效率的重要因素。贪心算法：贪心算法通常具有较低的时间复杂度，但可能需要较高的空间复杂度。例如，快速排序通常可以使用O(log n)的空间，但最坏情况下可能需要O(n)的空间。选择合适的贪心策略可以提高时间效率，尽管其空间复杂度可能较高。选择合适的数据结构：选择合适的数据结构可以在提高效率的同时减少空间消耗。例如，在需要频繁插入、删除元素的场景中，使用链表比数组更适合；而对于需要快速查找的场景，哈希表可能比数组更高效。2、分治法与动态规划分治法与动态规划是两种常用的算法设计思想，它们都涉及到将大问题拆解成小问题的策略，但使用的场景和方法略有不同。分治法：分治法通过递归将问题分解为多个子问题，直到问题变得足够简单，可以直接求解。然后，通过合并子问题的解来得到最终结果。典型的应用有归并排序、快速排序、二分查找等。分治法的一个关键特点是子问题通常是独立的，不会有重叠动态规划：动态规划是通过解决重叠子问题的方式来优化分治法。其关键在于通过保存子问题的解来避免重复计算，从而提高效率。动态规划的应用通常涉及到最优子结构和重叠子问题。经典问题如最长公共子序列、背包问题、斐波那契数列等。与分治法不同，动态规划更注重将子问题的解存储在表格中，避免重复计算，从而节省时间，但可能增加空间消耗。3、大数据与并行计算分布式计算框架（如 Hadoop, Spark）：Hadoop：Hadoop是一个开源的大数据处理框架，采用MapReduce编程模型。它将大规模计算分割成多个任务并在多个节点上并行处理，适合处理海量数据。Spark：Spark比Hadoop的MapReduce模型更高效，它支持内存中的数据处理，可以比Hadoop更快地处理迭代算法，适合实时数据分析和机器学习等应用。并行算法（如MapReduce）：MapReduce：MapReduce是一种编程模型，常用于大规模数据集的处理。它将任务分为两个阶段：Map阶段（数据的分配和局部处理）和Reduce阶段（结果的合并）。这种模型可以在分布式系统中并行处理大量数据。在进行并行计算时，数据的划分与负载均衡非常关键。MapReduce将任务分解成多个小任务，通过多个计算节点并行处理，从而大大缩短处理时间。在解决大规模问题时，算法的选择不仅需要考虑时间和空间的复杂度，还要考虑实际的计算资源。例如，分治法和动态规划可以有效地将大问题分解为小问题，提高效率；而在分布式计算框架和并行算法的帮助下，能够进一步解决问题规模带来的时间瓶颈。 认识在猜数游戏中步骤执行次数与问题规模有关。比较不同算法猜数范围的猜测次数。学习拓展阅读。完成各个算法之间的时间效率比较。完成问题分析。学习拓展阅读。完成课堂练习。进行课外知识拓展。 引导学生学习知识点，引入本课所学知识内容。引导学生通过算法比较实践 ，选择出猜测次数更低的算法，并完成表格填空和问答题提高学生的对比分析能力。完善知识点内容，强化所学知识。在对比中强化所学知识，并选择效率最高的算法。引导学生根据提问和对比选择效率更高的算法，提高课题互动性。补充教材知识点内容，完善知识点的广度和深度。考察学生的学习能力和知识点转化能力。拓宽学生知识面。
课堂小结 问题规模影响算法执行时间1、进行新知引入2、步骤执行次数与问题规模有关3、算法的时间效率可估算4、完成课堂练习5、进行知识拓展 总结回顾 对本节课内容进行总结概括。
课后作业 1、设计一个程序，测试不同规模的输入数据对查找算法（如线性查找、二分查找）执行时间的影响，并绘制执行时间与输入规模的关系图。 布置作业 拓展学生的学习能力
课堂板书 观看板书 强调教学重点内容。
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://www.21cnjy.com/" 21世纪教育网(www.21cnjy.com)