浙教版信息科技六年级上册第二单元算法的效率大单元整体教学设计.docx

第二单元算法的效率【单元整体构想】一、单元内容简介求解同一个问题，可能会有多种算法，但是解决同一个问题的多种算法，效率可能是不一样的。不同的算法在考虑问题求解正确的基础上，还需要分析问题求解的效率。本单元安排了“算法的效率”内容，在算法的描述、算法的执行等内容的基础上，采用多种算法来解决同一个问题，体现算法执行的不同效率。本单元通过多种算法的执行及评估，让学生意识到评价算法的标准除了正确性和有效性以外，执行效率也是一个需要关注的因素，帮助学生初步养成运用算法的思维习惯，形成设计与分析简单算法的能力。二、单元设计的望远镜思维经过五年级的学习，学生已经能根据简单问题的描述，进行抽象建模，采用恰当的方式描述算法，初步具备了信息处理的能力。经过六年级上第一单元的学习，学生已经知道在计算机中实现算法的一般步骤,通过问题健找、抽象与建模、设计算法、验证与优化算法等过程，己经对算法与程序的关系有了具体的体验。在此基础上，本单元将“算法的描述”“算法的执行”和“算法的效率”三个部分有机贯穿于各个算法问题的讨论，通过观察并体验采用不同算法解决同一个问题在时间效率上的差别。此外，本单元与此后要学习的第三单元“算法的影响”相关联。通过分析信息社会中各种与算法有关的应用，让学生感受到人们对这些应用有一个共同要求，即在用户可以接受的时间内给出正确的结果。好的算法能在给定的资源条件下（例如存储空间、网络带宽等），助力达成目标，或者在达成目标的前提下少用其他资源，因而具有价值。三、单元设计的放大镜思维本单元的知识内容在设计上继续围绕“算法”这条核心逻辑主线，融合“数据”“信息处理”等多条逻辑主线螺旋上升。本单元围绕“同一个问题可以采用多种算法来解决，而不同的算法可能具有不同的效率”和“解决问题的一般步骤包括抽象、分解、建模和制订解决方案”等大概念，共设计5节课，安排了猜数字和“韩信点兵”等游戏，对同一个问题设计多种不同算法，如猜数字可分别采用顺序查找和二分法查找算法解决，“韩信点兵”可分别采用枚举、筛选、同余算法解决，并针对不同算法，讨论算法评价的方法。通过本单元的学习，能帮助学生学会比较不同算法的效率，体验算法效率的差别，树立算法效率的意识。本单元各课内容如下表所示:课序课题简介第8课算法的多样性分析猜数字游戏问题、设计解决问题的多种算法、验证解决问题的多种算法。第9课算法的评价方法学习算法评价的方法、体验算法评价。第10课“韩信点兵”枚举法的实现抽象与建模、枚举算法设计、筛选算法的程序实现。第11课“韩信点兵”筛选法的实现抽象与建模、筛选算法设计、筛选算法的程序实现。第12课“韩信点兵”同余法的实现抽象与建模、同余法设计、同余法的程序实现。【单元目标设计】素养目标在典型的信息科技应用场景中，尝试采用不同方法解决同一个问题，熟悉一些常用经典算法的程序实现和执行过程；能针对不同的输入数据的规模，分析解决问题的不同算法在时间效率上的高低。逻辑主线单元主要涉及的大概念1 .同一个问题可以采用 多种算法来解决，而不 同的算法可能具有不同 算法 的效率。2 .解决问题的一般步骤 包括抽象、分解、建模和 制订解决方案。单元目标描述1 .通过分析生活中的具体问题解决实 例，认识到解决同一个问题可能存在多 种算法。2 .通过同一个问题的多种算法验证，认 识到不同的算法存在运行效率上的差 异。3 .通过估算算法的时间复杂度，理解影 响算法运行时间的因素，能根据简单问 题求解的需要设计合适的算法。【单元评价设计】本单元的评价可以基于真实的生活问题创设情境，围绕“能采用多种算法解决问题，并对多种算法进行效率分析”展开。一、最终评价任务设计在进行大扫除时，要把甲、乙两个班的学生分成若干个人数相同的小组，并且使每个小组都是同一个班的学生。每个小组最多有几名学生？实践：请用多种算法来解决问题。二、评价量规设计可根据学生的回答情况进行评价，如算法描述、算法实现、算法多样性等方面。评价内容评分指标（5分）得分利用算法解决问题具备按照抽象建模、设计算法、验证算法的步骤解决问题的意识。算法的多样性解决该问题可采用多种算法，如枚举、辗转相除法、更相减损术等。算法的实现能利用流程图或程序实现算法。算法的效率具备算法效率意识，能根据问题解决需要选择合适的算法解决问题【单元过程设计】一、单元问题设计问题一：猜数字游戏，你能用多种算法来解决吗？设计意图：猜数字游戏是前面几节课探究过的问题，学生已经熟知该情境。通过类似的驱动性问题，一方面引发学生回顾前面学习过的内容，归纳问题解决的思维与方法；另一方面激发学生思考解决该问题的其他算法，引导学生感知解决同一个问题可能有多种算法。学生回答的引导方向：学生可回顾前几节课中解决猜数字问题的思想与方法,就是模拟了整个猜数字游戏的过程，所猜数字可随机输入。因此，就所猜数字输入的先后次序可引入一定的规则，如依次输入、取中间数输入等。问题二：你觉得怎样的算法才是“好”的算法？设计意图：对算法“好”和“差”的思考，一方面激发学生探究算法的本质，理解利用算法解决问题需要满足正确、有效、高效等相关要求；另一方面引发学生关注算法评价要素，意识到算法效率也是一个需要关注的要素，以及算法效率可以从“时间”和“空间”两个方面衡量。学生回答的引导方向：利用算法求解问题，首先要确保所采用的算法能正确解决问题；其次要能在一定时间内完成，且执行速度越快越好，存储空间越少越好，即占用的资源越少越好，等等。二、单元学习策略本单元的学习要融入具体问题的解决过程。教材中通过猜数字游戏、“韩信点兵”等问题让学生经历抽象建模、设计算法、验证算法、优化算法等环节，体验算法的多样性，并意识到算法的效率。在实际教学中，教师可以根据学生与学校的实际情况对问题进行适当简化，鼓励学生发现、分析问题，以解决问题为导向设计算法、学习新知、探索实践等。课题第8课算法的多样性1 .通过设计猜数字的算法，理解顺序查找和二分查找的思想，地川口厂树立使用多种方法解决同一个问题的意识。教学目标2 .通过验证猜数字游戏的算法，初步掌握顺序查找和二分查找的程序设计方法，提高算法实现的能力。教学重点设计猜数字游戏的多种算法。教学难点实现及验证猜数字游戏的多种算法。1 .网络教室、PythOn编程环境。环境与素材2.童童家到学校的图片。3 .猜数字游戏的二分查找程序。教学过程一、讨论下图中，童童从学校到家有哪几条路线可走？二、建构现实中，解决一个问题的算法往往具有多样性，即可用不同的算法来解决同一个问题。例如，解决问题猜数字游戏问题，除了前面学过的算法外，还可以采用顺序查找和二分查找算法。1.问题分析猜数字游戏中，同学A输入数字的过程其实是一个“查找”问题，即在1-100范围内查找目标数da,可采用多种不同的策略来解决。例如：策略一：按顺序依次查找。依次将L2,3,99,100(或IO0,99,98,2,1)与da比较，直到找到为止。策略二：取中间数查找。1-100范围内的数是依次增加的，依据该有序性可依次取中间数来查找。先取ITOO的中间数50与da比较，若da等于50,则查找成功；若da小于50,则取1-49的中间数25与da比较；若da大于50,则取51T00的中间数75与da比较如此反复，直到找到为止。在1-100范围内查找目标数37的过程如下所示：目标数为37,初始范围为I-Ioo1249519899100I中间数第一次比较：37<50,范围调整为1-4912-2426474849I中间数第二次比较：37>25,范围调整为26-4926273638474849I中间数第三次比较：37-37,查找成功【小知识】计算机中的“查找”指根据根据所给条件找出满足条件的的对象，即在存储存储的一批数据内找出出一个特定的数据，或者确定在这批数据内是否存在这样的数据。【试一试】采用“按顺序依次查找”的策略，在1-100范围内查找数37,一共需比较多少次？2 .解决问题的多种算法设计根据解决问题采用的策略，将其设计成算法。例如，上述猜数字游戏就可将“按顺序依次查找”设计成顺序查找算法，“取中间数查找”设计成二分查找算法。算法一：顺序查找。假设目标数为37,并用变量da表示，取到的数用变算法二：二分查找。假设目标数为37,并用变量da表示，计算得到的中间值用变量cai表示，用变量cz和zz表示可取数的范围，初始查找范围为1-100,则CZ的初值为LZZ的的终值为100。对应的算法流程图如下:CHD3 .解决问题的多种算法验证上述问题两种算法可以通过编写程序或流程图的的执行进行验证。算法一的程序验证：da=37cai=lwhilecai<101:ifcai=da:Print（"找到的数为："，cai）breakelse:cai=cai+lbreak语句的作用是终止所在的的循环。【想一想】上述程序中，若变量da的值为137,则程序运行结果是什么？若要显示对应提示，则应如何修改程序？算法二的流程图验证：根据上述算法二的流程图，可通过表格的形式列出变量cz、ZZ和Cai的值来验证算法。循环轮次caiZZI通过3次循环，找到数37。【试一试】若变量da的值为137,请用表格的形式列出变量cz、ZZ和Cai的值。三、练习在上述算法一中，若变量Cai的取值依次为100,99,2,1,则相应的算法和程序如何修改？参考答窠：流程图修改：99程序修改：da=37cai=100whilecai>0:ifcai=da:Print（"找找到到的数为："，cai）breakelse:cai=cai'l课后反思/评价标准课题第9课算法的评价方法教学目标教学重点 教学难点环境与素材1 .通过“数”算法中循环的执行次数，认识到解决同一个问题的不同算法可能存在时间效率上的差别，初步掌握算法效率评价的方法。2 .通过给算法加计数变量等操作，比较语句的执行次数，深入理解算法的时间复杂度，形成算法效率的意识。初步掌握算法效率评价的方法。多种算法的效率比较。1 .网络教室、PythOn编程环境。2 .多种算法的效率比较。教学过程一、讨论解决某个问题可能会有多种不同的算法，如何评价算法的“好”与“差”呢？算法具有多样性，但如何知道我所设计的算法好不好呢？对算法的评价是有一定标准的。二、建构针对某个问题，可以设计多个算法来解决，但不同算法的效率是有差异的。算法有“好”与“差”之分，在一定条件下，当然要选择“好”的算法。1 .算法评价的方法“好”的算法，除了符合“正确性、有效性”等标准外，还需要有较高的算法运行效率，即算法运行所消耗的时间较短。一般情况下，算法运行需要的时间与待求问题的规模有关，如通过循环的方式求100个人的总分与求1000个人的总分，循环体执行的次数是不一样的,执行时间显然有差别。估算该算法的运行时间，可以在问题规模相同的情况下,将算法中循环语句的执行次数作为度量标准。例如，用顺序查找算法在1-100内查找数37的程序如下：da=37cai=lwhiIecai<101:ifcai=da:Print（"找到的数为："，cai）breakelse:cai=cai+l上述程序在执行时，变量cai的数值决定了循环语句while会执行的次数，当变量Cai的值变为37时，WhiIe语句总的执行次数为37。【试一试】修改上述程序，增加一个变量Ci来统计While语句的执行次数，并显示数值。2 .算法评价体验解决同一个问题的不同算法，在执行时的运行时间是有一定差异的。同样是在ITOO范围内查找目标数37,利用二分查找算法时，中间值依次取50、25、37,也就是说，循环只需执行3次，与顺序查找算法相比，循环少执行34次，显然运行时间更短。【想一想】在ITOOO范围内查找目标数37,利用二分查找算法，循环执行的次数是多少？三、练习在IToO范围内，分别采用顺序查找和二分查找算法查找目标数1、50和100,估算循环的执行次数。目标数查找算法循环执行次数1顺序二分50顺序二分顺序100二分参考答案:目标数查找算法循环执行次数1顺序1二分650顺序50二分1顺序100100二分7课后反思/评价标准课题第10课“韩信点兵”枚举法的实现教学目标1 .理解枚举算法的思想，掌握枚举算法解决问题的一般过程。2 .通过使用枚举算法解决“韩信点兵”问题，掌握枚举算法的程序实现。教学重点掌握枚举算法解决问题的一般过程。教学难点掌握枚举算法的程序实现。环境与素材1 .网络教室、PythOn编程环境。2 .“韩信点兵”相关图片、视频等素材。教学过程一、探索你知道“韩信点兵”的故事吗？韩信是怎么快速算出士兵的总人数的？韩信带领一队士兵，3个3个数，余2个；5个5个数，余3个；7个7个数，余2个。一共有多少人呢？人数可能是23,128,233,338,443,548,653,758二、建构“韩信点兵”故事是一个有超的猜数游戏。其求解的算法有多种，如枚举法。1 .问题描述相传有一次，韩信带领1500名士兵去打仗。战后，死伤四五百人。剩下的士兵中，他命令士兵3人一排，结果多出2人；接着命令土兵5人一排，结果多出3人；又命令士兵7人一排，结果又多出2人。韩信马上算出人数：我军还有1073名勇士!假如由你来“点兵”，你将采用何种算法？2 .抽象与建模韩信点兵的过程可表示为数的除法运算。 ÷3=2 ÷5=O3f=?÷7=O2“口”指剩下的士兵总数，用变量X来表示。根据“死伤四五百人”可知，变量X的范围为1000-1100,且同时满足“x除以3余数为2、X除以5余数为3、X除以7余数为2”这三个条件。可建立如下模型：枚举X在100OTlOO范围内的每一个值，判断条件“x除以3余数为2、X除以5余数为3、X除以7余数为2”是否同时满足，满足条件的X就是要求的解。即：当x=1000时，条件"x除以3余数为2、X除以5余数为3、X除以7余数为2”是否同时满足？当X=100l时，条件"x除以3余数为2、X除以5余数为3、X除以7余数为2”是否同时满足？当X=IlOO时，条件"x除以3余数为2、X除以5余数为3、X除以7余数为2”是否同时满足？3 .算法设计根据上述抽象与建模,解决“韩信点兵”问题可采用枚举法。X依次取100O-IlOO范围内的值，采用循环结构；判断条件“x除以3余数为2、X除以5余数为3、X除以7余数为2”是否同时满足，可以采用分支结构。检母靠法农林Bl4 .算法的程序实现在Python中，求余数的运行符为“”，即表达式x%y的功能是“用x除以y,取余数”，如“5%2”的结果就是1。因此，条件“x除以3余2”就可以表示为：x%3=2o要判断多个条件是否同时满足，需要用“and”逻辑运行符，条件“x除以3余数为2、X除以5余数为3、X除以7余数为2”就可表示为：x%3=2andx%5=3andx%7=2。上述算法用Python语言编写的程序如下：x=1000whilex<1101:ifx%3=2andx%5=3andx%7=2:Print（"剩余的士兵数为：”，x）x=x+l三、练习假如“韩信点兵”的问题描述修改为：韩信带领1500名士兵去打仗。战后，死伤一二百人。剩下的士兵中，他命令士兵3人一排，结果多出1人；接着命令士兵5人一排，结果多出4人；又命令士兵7人一排，结果多出3人。问：剩下的士兵一共多少人？请你利用枚举算法解决上述问题。参考答案：X=1300whilex<1401:ifx%3=landx%5=4andx%7=3:Print（"剩余的士兵数为：”，x）breakx=x+l课后反思/评价标准课题第11课“韩信点兵”筛选法的实现教学目标1 .理解筛选法的思想，掌握用筛选法解决问题的一般过程。2 .通过使用筛选法解决“韩信点兵”问题，掌握筛选法的程序实现，进一步体会算法的多样性。教学重点掌握用筛选法解决问题的一般过程。教学难点掌握筛选法的程序实现。环境与素材1 .网络教室、PythOn编程环境。2 .“韩信点兵”相关图片、视频等素材。教学过程一、探索完成下表，你能得出符合条件的最小被除数是多少吗？除数余数被除数的可能值325、8、11、14、17、20、23、265372二、建构“韩信点兵”问题还可以用筛选法来求解。1 .抽象与建模“韩信点兵”问题中，剩下的士兵总数用变量X来表示。变量X的范围为1000-1100,且需同时满足“X除以3余数为2、X除以5余数为3、X除以7余数为2”三个条件。由此，可建立如下模型：在100OTlOO这些数中，分别利用上述三个条件逐一进行筛选，最终剩下来的值就是所求解。即先根据“x除以3余数为2”条件，删除1000-1100中不满足该条件的数，筛选出满足该条件的数；再根据“x除以5余数为3”条件，在上述筛选出的数中，删除不满足该条件的数，筛选出满足该条件的数；最后根据“x除以7余数为2”条件，将筛选出来的数中不满足该条件的数删除，满足该条件的数筛选出来。筛选过程示意图如下所示：第一次筛选：根据“x除以3余数为2”条件IoOol100110Q2j；104WK)ajl410冲07110冲073卜09小间1明1100×××××××X第二次筛选：根据“X除以5余数为3”条件100010011002"104210431044'"1070107110721073109710961099110C××××X×××XXXX第三次筛选：根据“X除以7余数为2”条件100011IOra1O421O431O44p07C107110721073110971099109911OO×××XXX×××XXXX2 .算法设计根据上述的抽象与建模，用筛选法解决“韩信点兵”问题的算法如下：(1)用a存储IoOoTU)O范围内的数;(2)在a中删除不满足“x除以3余数为2”条件的数；(3)在a中删除不满足“x除以5余数为3”条件的数；(4)在a中删除不满足“x除以7余数为2”条件的数；(5)找出a中剩下的数。3 .算法的验证利用Python语言编写程序，对上述算法进行局部验证。例如，显示IooO-IIoo范围内满足“x除以3余数为2”条件的数，对应的程序及运行结果如下所示：程序运行结果x=1000100110041007101010131016whilex<1101:101910221025102810311034ifx%3=2:103710401043104610491052105510581061106410671070print(x,end="n)107310761079108210851088x=x+l109110941097HOO代码print(x,end="“)”中的end"”表示Print()输出后不换行而输出空格。【想一想】在上述算法中，若对调步骤(2)和步骤(4),对算法效率有何影响？三、练习编程实现：在1000-1100范围内将满足“x除以7余数为2”条件的数显示出来。参考答案：X=100Owhilex<l100:ifx%7=2:Print(X,end=”")x=x+l课后反思/评价标准课题第12课“韩信点兵”同余法的实现教学目标1 .了解同余法的思想，掌握用同余法解决问题的一般过程。2 .通过使用同余法解决“韩信点兵”问题，掌握同余法的程序实现，进一步体会算法的多样性。教学重点掌握用同余法解决问题的一般过程。教学难点掌握同余法的程序实现。环境与素材1 .网络教室、PythOn编程环境。2 .“韩信点兵”相关图片、视频等素材。教学过程一、探索完成下表，你发现了什么现象？能得出什么结论？被除数除数余数233235237128312851287233323352337二、建构“韩信点兵”问题除了通过枚举、筛选的算法思想来解决外，还可以依据同余的算法思想来解决。孙子算经中曾记载着利用同余思想求解的方法，这种方法被称为“中国剩余定理工【小知识】数学上，两个整数除以同一个整数，若余数相同，则对于除数，这两个整数相同。1 .抽象与建模在韩信点兵过程，剩下的士兵总数用变量X表示。变量X的范围为1000-1100,且需同时满足“x除以3余数为2、X除以5余数为3、X除以7余数为2”三个条件。由此，可建立如下模型：根据同余思想，可先找出同时满足“x除以3余数为2、X除以5余数为3、X除以7余数为2”三个条件的任意一个数，如233,然后将该数加减3、5、7的最小公倍数105的整数倍，在IoOoTlOO范围内的数即是所求解。【试一试】388(=233+105)被3、5、7除的余数分别是多少？2 .算法设计根据上述抽象与建模，用同余算法解决“韩信点兵”问题时，用变量S表示所取到的同时满足三个条件的任意一个数，如233,变量k表示三个数的最小公倍数。通过加或减k的整数倍，使s的值大于等于1000且小于等于1100,可以采用循环结构，根据条件“s小于1000”来选择k或减k的值，可以采用分支结构。算法的流程图如下：UXkJ*5>7轮出、的值/'(JrJ3 .算法的程序实现上述算法用Python语言编写的程序如下：s=233#取到的同时满足三个条件的任意一个数k=3*5*7#计算3、5、7的小最公倍数whiles<1000ors>1100:#在1000,1100内找到满足条件的数ifs<1000:s=s+k#若小于1000,则加上公倍数else:s=s-k#若大于IlO0,则减去公倍数Print("剩余的士兵数为：”，s)三、拓展孙子算经中记载了如下算题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？对于这个问题，首先找出能被5与7整除而被3除余1的数70,被3与7整除而被5除余1的数21,被3与5整除而被7除余1的数15。如果所求的数被3除余2,那么取数70X2=140,140是被5与7整除而被3除余2的数。如果所求数被5除余3,那么取数21X3=63,63是被3与7整除而被5除余3的数。如果所求数被7除余2,那么取数15X2=30,30是被3与5整除而被7除余2的数。140+63+30=233,由于63与30都能被3整除，所以233与140这两个数被3除的余数相同，都是余2。同理，233与63这两个数被5除的余数相同，都是3；233与30被7除的余数相同，都是2。所以，233是满足要求的一个数。三、练习若将上述“韩信点兵”问题的查找范围调整为2500-2600,修改上述算法及程序，并输出结果。参考答案：s=233k=3*5*7whiles<2500ors>2600:ifs<2500:s=s+kelse:s=s-kPrint（"剩余的士兵数为I"，s）课后反思/评价标准