4.2迭代法教学设计人教-中图版高中信息技术选择性必修1数据与数据结构

第4章算法与数据结构4.2迭代法教学设计教学背景信息科技是现代科学技术领域的重要部分，主要研究以数字形式表达的信息及其应用中的科学原理、思维方法、处理过程和工程实现。当代高速发展的信息科技对全球经济、社会和文化发展起着越来越重要的作用。义务教育信息科技课程具有基础性、实践性和综合性，为高中阶段信息技术课程的学习奠定基础。信息科技课程旨在培养科学精神和科技伦理，提升自主可控意识，培育社会主义核心价值观，树立总体国家安全观，提升数字素养与技能。教材分析本节课的教学内容选自人教/地图出版社选择性必修1数据与数据结构第4章算法与数据结构4.2迭代法。学情分析此节课针对的对象是高二年级的学生。学生学习过信息技术基础知识，对计算机、网络、物联网等技术有基本了解:已经学习了Python语言的基本概念，并掌握了基本的结构和算法;对现代生活中的信息系统有所观察和积累。本章通过“编写对弈程序”项目，引领同学们开展自主选题，建议从确定主题、选择数据结构、设计算法和编写程序等几个方面入手，完成小组项目，发布应用程序，详细记录研究过程并形成研究报告。教学目标1.体验迭代法解决问题的过程，能解决实际问题，发展计算思维。2.通过体验排序与查找过程，能对具体问题进行抽象，合理选择数据结构，设计算法解决问题。教学重点与难点教学重点:体验迭代法解决问题的过程，能解决实际问题，发展计算思维。教学难点:通过体验排序与查找过程，能对具体问题进行抽象，合理选择数据结构，设计算法解决问题。教学方法与教学手段案例分析法、讲授法、任务驱动法。教学过程问题导入体验探索背单词小明制订了一个英语学习计划，其中一项内容是背单词：第1天背1个单词，第2天背2个单词，第3天背3个单词......即每天都比前一天多背1个单词，如图4.2.1所示。经过100天的努力，小明觉得收获颇丰。思考：1.经过100天后，小明总共背了多少单词？你是如何算出来的？2.这个事例对你有什么启发？迭代法的概念与特征《荀子·劝学》中有云“不积跬步，无以至千里；不积小流，无以成江海。”要解决复杂问题，可以从简单的小问题开始，一步一步推进，最终解决复杂问题。背单词计数问题正是这样一个通过不断解决小问题，进而求解整个问题的典型示例。思考活动设计背单词计数问题的算法使用计算机解决背单词计数问题，需要为这一问题设计算法。思考：如何设计算法实现背单词计数问题的求解？例1：背单词计数。首先，将背单词的过程描述如下：第1天背了1个单词，累计背了1个单词；第2天背了2个单词，比第1天多背1个单词，累计背了1+2=3个单词；第3天背了3个单词，比第2天多背1个单词，累计背了（1+2）+3=6个单词；第4天背了4个单词，比第3天多背1个单词，累计背了（1+2+3）+4=10个单词；......第100天背了100个单词，比第99天多背1个单词，累计背了（1+2+3+...+99）+100=5050个单词。这一过程可用表4.2.1记录。表4.2.1背单词过程记录表时间当天背的单词数比前一天多背的单词数累计背的单词数第1天111第2天211+2第3天311+2+3第4天411+2+3+4............第100天10011+2+3+4+...+100通过分析，可以得到如下结论（设n为1～100的自然数）：第n天背的单词数为n；每天都比前一天多背1个单词，即每天背单词的增量为1；从第1天至第n天，总共背单词数就为1+2+3+...+n。当n=100时，就可以统计出100天背的单词总数。通过分析发现，背单词的计数问题可抽象并转化为连续自然数求和问题。要使用计算机解决该问题，就要先选择合适的数据结构，再设计算法。方案一：设计数组a，用循环将1至n依次存入数组，然后设计变量sum保存总和（初值为0），再把数组的每一个元素和sum相加，最后，sum值就是所求的结果。方案二：使用变量sum保存总和（初值为0），再使用另一个循环变量i，让循环变量从1增加至100（步长为1），循环过程中执行sum与i相加。当循环结束时，sum值就是最终的结果。算法流程如图4.2.2所示。在求解背单词计数问题过程中，sum的值不断增加（也称为累加），而且每一次都用变量的旧值递推出变量的新值，直至得到最终的结果。这种不断用变量的旧值递推新值的过程称为迭代法，也称辗转法。使用迭代法解决问题需要具备三个要件：确定迭代变量、建立迭代关系式和确定迭代的终止条件。确定迭代变量用迭代法解决问题时，迭代过程中至少存在一个直接或间接地不断由旧值推出新值的变量，这个变量就是迭代变量。在背单词计数问题中，sum的新值由旧值不断推出，因而sum就是迭代变量，它的初值为0，终值就是计算的最终结果。建立迭代关系式迭代关系式指迭代变量由前一个值推出其下一个值的公式（或关系）。建立迭代关系式是解决迭代问题的关键。在背单词计数问题中，迭代关系式就是sum值的累加关系式：sum=sum+i确定迭代的终止条件通常，迭代的实现要使用循环，为防止循环无休止地重复执行下去，必须设置终止条件。在背单词计数问题中，使用了for循环，循环条件是循环变量i≤n。因此，终止条件就是循环变量i＞n。例2：求解扩展后的正三角形个数。（参见教材P119）所示，由多个这样的正三角形可拼成边长为2、3、4个单位的正三角形，如图4.2.5（参见教材P119）所示。如果要拼合成边长为n的正三角形，需要多少个边长为1个单位的正三角形？这里，用f(n)表示拼成边长为n的正三角形所需边长为1个单位的正三角形的数量。显然，f(1)=1。通过观察，不难发现：由边长为1个单位的正三角形，拼成边长为2个单位的正三角形，可视为增加2个蓝色正三角形和1个橘色正三角形，如图4.2.5(a)所示。因而，f(2)=f(1)+2+1=4；由边长为2个单位的正三角形，拼成边长为3个单位的正三角形，可视为增加3个蓝色正三角形和2个橘色正三角形，如图4.2.5(b)所示。因而，f(3)=f(2)+3+2=9；由边长为3个单位的正三角形，拼成边长为4个单位的正三角形，可视为增加4个蓝色正三角形和3个橘色正三角形，如图4.2.5(c)所示。因而，f(4)=f(3)+4+3=16；......同样地，由边长为n1个单位的正三角形，拼成边长为n个单位的正三角形，可视为增加n个蓝色正三角形和n1个橘色正三角形。因而，f(n)=f(n1)+n+n1=f(n1)+2n1。这一过程可以用表4.2.2表示。由此可见，扩展后的正三角形个数能够用迭代法求解，其迭代关系式为f(n)=f(n1)+2n1，且f(1)=1。迭代法的应用迭代法除了可以解决前面提到的背单词计数、求最大公因数、求算术平方根近似值等问题外，其思想还可以用来解决计算机科学中的排序和查找等问题。思考活动设计排序算法某校高一年级组织了7名学生参加演讲比赛，这7名学生的选手编号分别为1～7号。在观众投票环节，选手们获得的票数如表4.2.3所示。表4.2.3参赛选手得票数统计表选手编号1号2号3号4号5号6号7号观众投票数523746331240思考：如果需要用计算机按照得票数对参赛选手们进行排序，如何设计算法?互联网的信息量非常大，比如在如图4.2.7所示的购物应用中，输入“算法”查找到6005条与“算法”有关的图书资料信息。要从中找到一本最贴近需求的书，往往需要对这些列出的数据按照一定的规则进行重新排列。例如，按照销量、价格、好评或者出版时间等排列。这个过程就是排序，而排序所依据的数据项称为关键字。排序是计算机中经常进行的一种操作，其作用是将一组“无序”的数据元素序列按关键字的顺序（升序或降序），调整为“有序”的数据元素序列。为方便学习，我们约定数据元素存储在数组中，排序关键字为整型数据，对数据序列进行升序排列。冒泡排序在众多排序算法中，冒泡排序是最为常见的排序算法之一。它的基本思想是：两两比较相邻元素，如果反序则交换这两个元素，直到整个序列没有反序的元素为止。如何根据冒泡排序的基本思想，对表4.2.3中的数据进行排序？显然，这个排序问题中的关键字是票数值。为简单起见，数组中只存储选手们获得的票数。设数组名为a，则排序前的数组a如图4.2.8（参见教材P123）所示。根据冒泡排序的基本思想，整个排序过程分析如下：第1趟冒泡排序从第1个关键字开始，依次比较相邻的两个关键字，如果第一个关键字大于第二个关键字，则交换这两个关键字。第1趟冒泡排序过程如图4.2.9（参见教材P123）所示。7个关键字经过6次两两比较后，第1趟冒泡排序结束。排序结果是最大关键字“46”被交换到a[6]。第2趟冒泡排序只需要对前6个关键字进行比较。完整的冒泡排序过程，如图4.2.10所示。观察上述排序过程可以发现，7个数据元素需要进行6趟冒泡排序。第1趟需要对7个数据元素进行6次比较，而后的每一趟中需要比较的元素个数比上一趟少1。因此，每一趟中的元素比较次数也比上一趟少1次。所以，如果待排序列中有n个数据元素，则需要进行n1趟冒泡排序，第i趟排序中的元素比较次数为ni（1≤i≤n1）。冒泡排序的基本过程如下：1.比较第1个和第2个元素，如果第1个比第2个大，就交换这两个元素。再比较第2个和第3个元素，如果第2个比第3个大，就交换这两个元素。依此类推，最后比较倒数第二个元素和最后一个元素，如果倒数第二个元素比最后一个元素大，就交换这两个元素。此为第1趟排序，第1趟排序结束后，最后一个元素就是所有元素中最大的。2.按照第1趟排序的方法，对除最后一个元素外的其他所有元素进行第2趟排序。依此类推，持续对个数越来越少的元素进行比较，直到第n1趟结束为止。在这种排序方法中，数值较大的数据元素会像“冒泡”一样经由交换“浮”到数组的末端，冒泡排序法因此而得名。实践活动冒泡排序算法的编程实现与优化1.编写程序，用冒泡排序算法实现演讲比赛选手排序。2.仔细研究图4.2.10（参见教材P123）中冒泡排序每一趟的过程，可以发现第4趟没有发生数组元素的交换，说明此时数组已经是有序的，无须再进行第5趟和第6趟排序。请根据这一发现，编写程序，优化冒泡排序算法。顺序查找顺序查找指在一个无序（或有序）数组中，从头到尾逐一进行比较，找出关键字与给定值相同的数组元素。如果找到，则查找成功，返回该数组元素的下标；否则，查找失败，返回“1”。小明最近迷上了诗词。他制作了大量诗词卡片以便随时吟诵，并对每张卡片都进行了编号。部分卡片的编号存于如图4.2.11所示的数组中。现在，他要查找编号为“77”的卡片。如果采用顺序查找法，应该如何查找呢？按照顺序查找法的思路，从下标为“0”的元素开始，逐一访问这个数组的所有数据元素，并与关键字“77”进行比较。如果相等，查找成功，并返回该元素的下标；如果不相等，就继续向前查找，当数组中没有元素可以访问时，说明数组中没有元素“77”，查找失败，返回“1”。实践活动顺序查找算法的实现1.按照顺序查找法的思路，填写表4.2.4。表4.2.4顺序查找过程步数数组下标关键字与给定值“77”是否相等1023否2175否2.编程实现顺序查找算法，并输入数据，验证其正确性。3.小明和小清各自用Python语言编写了两个不同的顺序查找函数，小清觉得自己的算法比小明的更加实用一些。请设计一个方案，编写程序体验这两段程序的运行效果，分析哪一个算法更加合适，并阐明理由。项目实施设计算法一、项目活动（参见教材P113），列举其中需要使用算法解决的问题，并设计算法。例如，对表4.1.3（参见教材P113）中问题3“对弈双方落子的实现”的分析如下：对弈的每一方落子相当于改变该点位对应的二维数组中元素的值。落子后要检查该方是否满足五子相连的条件，满足就是该方获胜，对弈结束；若不满足，对方继续落子......重复此过程。对弈的过程就转化为对弈结束条件是否满足的判定，即设计五子棋判胜算法。设计五子棋判胜算法，首先要了解五子棋判胜和判负的规则，以最简单的判胜规则——五子相连为例，即相连的同一颜色棋子数等于5时即为获胜。假如一方在棋盘上落子后获胜，那么，必然会出现以下四种相连情况之一：在同一行上，五子相连；在同一列上，五子相连；从左上至右下方向，五子相连；从右上至左下方向，五子相连。五子相连的判胜算法即逐一判断上述四种情况是否存在，如存在，则提示落子方获胜，对弈结束。如果四种情况都不存在，即落子方没有取胜，则对弈继续。用数组a[14][14]表示棋盘，落子点位对应数组元素a[m][n]，使用循环巧妙改变m和n的值，即可判断棋子相连的情况。二、项目检查设计已确定主题的主要算法，并编程实现。课后作业1.若用链表存储表4.2.3（参见教材P118）所示的演讲比赛选手们的得票