资源简介

中小学教育资源及组卷应用平台
第3课《算法应用重效率》教学设计
课题 算法应用重效率 单元 第八单元 学科 信息科技 年级 五年级下
核心素养目标 信息意识：具备理解数据如何被拆分、传递和利用，以便更高效地完成任务的意识，明白数据集的分割可以使处理任务更具效率和可扩展性。计算思维：明白分而治之的原理，形成在面对复杂问题时，将大问题拆解为易于处理的子问题，并且利用算法来高效地解决这些问题的思维。数字化学习与创新：能够将一个复杂的学习内容划分为多个小部分，每个部分可以独立地解决保证学习效率的提高和创新思维的培养。信息社会责任：在进行数据分割处理时应确保不会泄露个人信息或带来不公平的偏见。
教学重点 学会运用分而治之的思维解决繁杂问题。
教学难点 能够运用所学知识内容提高算法应用的效率。
教学过程
教学环节 教师活动 学生活动 设计意图
导入新课 板书课题。1、活动背景妈妈购物结算时，收款员忘了给某个物品消磁，我用更快的方法找到了没有消磁的物品。用算法高效解决问题，离不开我们的思考。2、新知导入观看视频 学习新知引入，观看教学视频。 用提问的方式引入课题，增强课堂互动性。将学生的注意吸引到课堂。
讲授新课 新知讲解：一、分解问题日常生活中，有时可以采用分而治之的思想解决问题。 活动：找出没有消磁的物品小智的妈妈在超市采购了24件物品，可是出门的时候发现收款员忘了给某个物品消磁(图8-3-1)。1.比较下面两种做法，你觉得哪种做法更好，为什么 (1)逐一将物品通过检验机;(2)取一半物品过检验机，将发出警报的这堆物品继续分一半过检验机，以此类推。逐一将物品通过检验机和取一半物品过检验机并将发出警报的物品继续分一半过检验机这两种做法相比较，通常第二种做法更好。原因在于：逐一检验需要检验每一个物品，当物品数量较多时，检验的工作量和时间成本会显著增加。而取一半物品过检验机，将发出警报的这堆物品继续分一半过检验机，以此类推，这种方法类似于折半的思想，能够快速缩小可能存在问题的物品范围，减少检验的工作量和时间。2.与“用折半查找猜数”相比较，上面的做法(2)有哪些不同 操作对象不同：第二种方法的操作对象是实际的物品，目的是找出可能存在问题（发出警报）的物品；而折半查找猜数的操作对象是数字，目的是在一个给定的数字范围内找出目标数字。 判断依据不同：第二种方法是根据检验机发出的警报来判断物品是否有问题；折半查找猜数是根据猜测的数字与目标数字的大小关系（“高了”或“低了”）来缩小猜测范围。与将物品逐一通过检验机相比，每次取一半物品通过检验机解决问题的效率更高。类似地，在现实生活中，我们可以将一个大规模的问题分解为若干个规模较小的相同子问题，各个子问题形式相同，解决的方法也一样。拓展阅读分治思想分治算法的基本思想是：将一个复杂的问题分为若干个子问题来进行求解，然后综合各个子问题得到复杂问题的最终答案;如果这些子问题仍难以解决，可以再把它们分为若干个更小的子问题，直至可以直接求出答案为止。二、分析已知条件对同一个问题分析的深度不同，设计出的算法效率会不同吗 活动：优化猜数算法小智妈妈让小智猜自行车的价格，价格范围在1000元以内。在小智猜价格的过程中，妈妈会根据小智猜的价格进行相应的提示，“高了”或“低了”。小智打算继续用折半查找，但是他猜的第一个数字却是650。你知道这是为什么吗 你觉得小智这样修改猜数算法的优势是什么 答：小智原本打算用折半查找法，正常情况下在价格范围1000元以内，第一次猜测的数字应该是500（1000的一半向下取整）。他猜650可能是因为他没有严格按照折半查找的规则来，也有可能是他凭借自己的直觉或者对自行车价格有一定的预估，认为价格可能在650元左右。如果小智坚持严格按照折半查找法，优势在于可以更高效地缩小价格范围。每次猜测都能将可能的价格区间缩小一半，从而以最快的速度逼近正确答案。估算自行车的价格范围后，合理调整猜数范围，有助于减少猜测次数。活动：探析问题理解对算法效率的影响有若干只鸡、兔同在一个笼子里，从上面数，有35个头;从下面数有 94只脚。请问：鸡和兔各多少 1.尝试理解如图 8-3-2所示的三个程序，分析算法设计的缘由，并填写表8-3-1。表 8-3-1 算法设计分析程序算法缘由为算法提供的已知条件算法所做的处理(a)通过设定变量来计算鸡和兔的数量。总头数为35，总脚数为94设定变量总脚数为94，总头数为35，然后通过变量运算来求解鸡和兔的数量。(b)通过设定变量来计算鸡和兔的数量。总头数为35，总脚数为94设定变量总脚数为94，总头数为35，然后通过变量运算来求解鸡和兔的数量。(c)通过循环和条件判断来计算鸡和兔的数量。总头数为35，总脚数为94设定变量总头数为35，总脚数为94，然后通过循环和条件判断来求解鸡和兔的数量。2.你认为哪个算法效率更高 请分析其效率高的原因。认为程序 (a) 和 (b) 的效率更高。原因如下：程序 (a) 和 (b)：这两个程序通过简单的变量运算来求解鸡和兔的数量，算法简单直接，计算量较小，效率较高。 程序 (c)：该程序通过循环和条件判断来求解，虽然也能得到正确结果，但循环和条件判断的增加会导致计算量增大，效率相对较低。综上所述，程序 (a) 和 (b) 的算法效率更高，因为它们采用了更直接和简单的计算方法。拓展阅读枚举思想将所有可能的候选答案一一列举，然后验证该候选答案是否为正确的解。将所有候选答案验证后，就可以找出正确的解(或无解)。在解决某些问题时，可能没有办法按一定的规律从众多的候选答案中找出正确的解，就可以采用枚举思想。当问题规模很大时，采用人工方式很难处理，可以用计算机验证每一个候选答案，从而求解问题，使用枚举算法时，需要明确问题的答案范围，避免无效搜索，从而提高算法的效率。解决问题时，分析问题的已知条件及内在逻辑，建立前提条件与结果之间的关系，通过数学表达式的计算实现问题求解，有助于提高求解问题的效率。三、课堂练习完成教材19—21页相关课堂练习题。四、拓展延伸1、优化分而治之算法避免重复计算：如果在分解子问题的过程中，出现了重复计算的情况，可以通过记忆化（memoization）来缓存已经计算过的结果，减少不必要的计算。例如，在合并排序（Merge Sort）中，可以通过使用指针而不是重复排序来减少合并过程中的时间复杂度。合并过程优化：有些分而治之问题的合并步骤可能存在重复计算，可以通过优化合并策略来减少计算量。例如，合并两个已排序的数组时，可以通过指针来遍历两个数组，而不是重新计算每一对元素的合并。平衡子问题的大小：分而治之算法的效率通常依赖于子问题的规模平衡。过大的子问题可能会导致合并过程繁重，而过小的子问题可能使得递归的深度增大。合理分割子问题的大小可以减少计算量和递归的深度，进而提高效率。并行化计算：如果可以对子问题的计算和合并过程进行并行化处理，尤其是在多核处理器上，将显著提高整体效率。例如，MapReduce是一种典型的分而治之方法，通过并行处理多个子问题来提高效率。2、分而治之算法在实际中的应用图像处理：在图像处理领域，分而治之算法常用于图像分割、边缘检测等任务。例如，快速傅里叶变换（FFT）就使用了分而治之的方法，它将计算大规模傅里叶变换的问题拆解成多个小规模的傅里叶变换，极大提高了计算效率。计算几何：计算几何中的许多经典问题都可以通过分而治之进行解决。例如，最近点对问题（找出平面中最近的两点）通常使用分而治之的策略，先将点集分成两个子集，递归计算子集中的最近点对，再合并子集的解。排序与搜索：例如，归并排序（Merge Sort）和快速排序（Quick Sort）都属于分而治之算法，特别适用于大规模数据的排序。快速排序通过将数组分为小于和大于基准元素的两部分，然后递归排序这些部分，达到优化排序的效果。3、动态规划与分而治之的区别与联系相同点：都是将大问题拆解成更小的子问题，递归地求解子问题，最终合并子问题的解得到原问题的解；都可以通过分解问题，减少计算复杂度，尤其在处理重叠子问题时，可以减少不必要的计算。不同点：子问题的重叠性：分而治之算法通常是将一个问题分解成不重叠的子问题，而动态规划则通常是将问题分解成有重叠子问题。动态规划通过存储子问题的解（通常使用表格），避免重复计算，而分而治之算法则不一定需要存储中间结果。子问题的合并方式：在分而治之中，子问题的解通常是通过递归调用合并的，而动态规划通过逐步构造最优解的表格来避免递归，直接从小到大计算出最终解。算法结构：分而治之是通过递归来求解子问题，而动态规划则是通过迭代的方式来逐步解决子问题。动态规划常常依赖于自底向上的构建方式，而分而治之则是自顶向下的递归求解。五、小结与评价1、单元拓展解决同一个问题有不同的算法，不同算法的效率可能不同，我们应该从效率出发选择高效算法。你想挑战下面的哪个任务 试试你的本领吧。任务一：我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题:鸡翁一，值钱五;鸡母一，值钱三;鸡雏三，值钱一;百钱买百鸡，则翁、母、雏各几何 尝试使用枚举法得到答案并优化算法。任务二：小慧的妹妹将声母卡的顺序打乱了。以小组为单位，探究将声母卡排序的算法，帮助她重新排序，并比较不同算法效率的高低。任务三：利用“计时器”可以观察算法运行的时间。尝试执行“连加”程序，输入不同的数据，观察运行过程以及结果。想一想，在“连加”程序里，所输入的数值与“和的累加”算法步骤的执行次数、运行时间有什么关系 答：执行次数关系：“和的累加”算法通常是一个简单的循环累加过程。假设输入的数据个数为 n，在基本的累加算法中，循环的次数就等于 n。也就是说，输入数值的个数越多，“和的累加”算法中循环步骤的执行次数就越多。 运行时间关系：一般情况下，随着输入数值的增加，“和的累加”算法的运行时间会相应增加。因为更多的输入意味着更多的计算步骤，计算机需要花费更多的时间来完成这些操作。2、单元阅读并行计算提高算法效率在使用计算机解决复杂计算问题时，通常会采用并行计算。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机也可以是以某种方式互连的若干台独立计算机构成的集群。并行计算是提高计算机系统计算速度和处理能力的一种有效手段。贵州省首个超算中心(贵安超算中心)，采用并行计算，具备每秒1.3亿亿次的超算能力。排序算法的重要性排序算法在计算机科学中有着非常重要的应用，其主要原因在于它可以有效地对大量数据进行整理，使得数据检索、分析和处理更为高效。提高搜索效率:对数据进行排序后，可以使用二分查找等高级搜索算法在数据中快速查找特定元素，大大提高了搜索效率。简化数据处理过程:对数据进行排序，可以简化合并排序、快速排序等算法的处理过程，提高其性能。优化数据传输效率:在网络传输中，数据通常需要按照一定的顺序进行传输。对数据进行排序，可以有效地减少数据传输量，提高数据传输效率增强数据安全性:在加密和解密数据的过程中，排序算法也扮演着重要的角色。例如，加密和解密算法通常需要将数据进行排序，以便更好地处理数据。提高数据处理速度:在处理大量数据时，排序算法可以有效地提高数据处理速度。例如，在进行机器学习和数据分析时，排序算法可以使得数据处理过程更加高效。3、单元评价本单元我们通过对猜数、消磁物品查验、鸡兔同笼等问题的不同算法进行分析与比较，感受了解决问题时需要考虑算法的效率。在学习过程中，你有哪些收获呢 表现得怎么样 请就本单元学习作出评价!4、单元练习1.你认同下面哪些说法 (1)解决同一问题有多种算法，应该具有采用高效算法解决问题的意识。(2)算法中某些步骤的执行次数与问题的规模有关，通过比较不同数据规模下算法步骤的执行次数变化趋势，可以比较算法的效率。(3)应该选择效率高的算法，而不必考虑已知问题中的已知条件。答：认同（1）。解决同一问题确实有多种算法，例如在查找元素时，有顺序查找、折半查找等算法。不同的算法在时间复杂度、空间复杂度等方面存在差异，采用高效算法可以更快速地解决问题，节省资源和时间，所以应该具有采用高效算法解决问题的意识。2.说说你的发现与思考。对本年级所学课程内容进行回顾，选择你感兴趣的案例，思考是否有更高效的算法解决该案例，为什么 5、学习评价请从解决问题有多种算法、“数”出算法中某些步骤的执行次数、探究问题规模对算法效率的影响、算法应用需要重视效率及小组合作等方面，评价本单元的学习表现。答：“数”出算法中某些步骤的执行次数。这有助于我们深入了解算法的运行过程和性能。通过精确地统计某些关键步骤（如循环次数、比较次数、赋值次数等）的执行次数，我们可以量化算法的工作量。例如在一个简单的查找算法中，统计比较操作的次数，就能知道在不同数据规模下该算法需要多少次比较才能找到目标元素。6、单元总结本单元我们通过理解算法逻辑、“数”出算法步骤执行次数、分析问题规模对算法执行步骤的影响，找到了比较高效的猜数算法，解决了小智想在猜数游戏中获胜的需求。在学习过程中，我们懂得了解决同一问题有多种算法，明白了算法中某些步骤的执行次数与问题的规模有关，能够判断解决同一问题的不同算法在效率上的高低。通过解决消磁物品查验、猜自行车价格鸡兔同笼的过程，理解了可以对问题分而治之，以及分析已知条件优化算法从而更高效地解决实际问题。 认识分而治之的思想。完成问答。学习拓展阅读。学习如何优化猜数算法。探究问题理解对算法效率的影响情况。回答提问。学习拓展阅读。完成课堂练习。进行课外知识拓展。进行单元小结与评价。 引导学生认识分而治之的思想内容，逐步分析在算法各个环节中如何实践该思想，加深所学。引导学生在思考中强化对本课知识点的认识，调动课堂参与度和学生思考能力。引导学生学会运用分而治之的思维解决繁杂问题。详细介绍分治思想内容，完善学生知识体系。结合具体的案例引导学生如何进行算法优化，让所学内容生动形象。通过填写表格结合鸡兔同笼问题分析，帮助学生更好的理解问题理解对算法效率的影响情况，加深所学内容。结合案例进行对比分析，在对比中强化对本课知识点的掌握。拓宽学生知识面。在课堂练习中强化所学知识内容。拓宽学生知识面。引导学生完成单元总结与评价，回顾本单元学习内容并巩固知识点。
课堂小结 算法应用重效率1、进行新知引入2、总结算法设计与实现过程3、完成课堂练习4、进行知识拓展5、完成单元总结内容 总结回顾 对本节课内容进行总结概括。
课后作业 1、研究并实现“最大子数组和问题”的分而治之解法，并与暴力法进行效率比较。2、讨论在图像处理（如图像压缩）中如何应用分而治之算法。 布置作业 拓展学生的学习能力
课堂板书 观看板书 强调教学重点内容。
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://www.21cnjy.com/" 21世纪教育网(www.21cnjy.com)

展开更多......

收起↑