5.2 迭代与递归 教学设计（2课时表格式）-2023新浙教版《高中信息技术》选择性必修第一册.rar

迭代教学设计迭代教学设计迭代迭代教材内容：教材内容：5.2 迭代和递归之迭代适应的课程标准：适应的课程标准：1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。教学目标：教学目标：能结合具体程序实例，掌握迭代的思想和方法。能够运用迭代的思想和方法，编程实现方程根的求解。指向的核心素养：指向的核心素养：信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。数字化学习与创新：要使学生为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。学习环境：学习环境：有教学控制软件的多媒体机房，python 编程环境。课程标准课程标准和和教学目标教学目标建议课时：建议课时：1 课时教学环节教学环节教学过程教学过程设计意图设计意图教学活动设计教学活动设计情境导入情境导入导入 1：自主编写程序展示“美妙的图案”，引导学生体会 python turtle 海龟作图的美妙之处，对作图的原理略加简介，引入迭代的思想。提问：如果将中程序中“t.left(90)”语句的参数 90 修改为 91，效果又如何？导入 2：“兔子有多少只？”：假定我们有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始怀孕（真实情况是六个月左右），在第二月结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每只雌兔在开始繁殖后每月都产下一对兔子，假定没有兔子死亡，在一年后总共有多少对兔子？请同学们计算前几个月兔子的数量，填写下表，看看能不能找到规律？时间（月）1234567兔子（对）11235设计意图：通过导入生活中的迭代算法问题，以便顺利过渡到迭代算法思想的分析。学习任务一：斐波那契数列的求解学习任务一：斐波那契数列的求解学习任务一：斐波那契数列的求解通过同学小组讨论，教师总结“兔子有多少只？”问题的分析过程：若用 an表示第 n 个月底兔子的数目，因为每个月底的兔子可以被分成两个部分：一部分是上个月底就有的兔子 an-1,另外一部分就是这个月新生下来的，而这个新生的显然就是上两个月就存在的那些兔子生出来的 an-2。时间1234567总数112358老兔子111235新兔子001123我们可以写出这样的递推公式：a1=1a2=1an=an-1+an-2(当 n2 时)设计意图：引入时提供了两个具体实例，特别是第二个需要学生自己动手实践，建议放手让学生讨论并自主实现算法。需要注意的是，学生在编写程序的过程，可能会有不同的实现，应充分尊重学生的想法，放手让学生多想多试。通过“兔子有多少只？”程序实例，学生可以初步理解“迭代算法”的思想实质。通过对实际程序两种实现的对比分析，引导学生自主阅读教材内容，加深概念理解，并由教师引导，总结概括出迭代算法的三个重要方面即“确定迭代变量”、“建立迭代关系式”、“控制迭代过程”。自主学习自主学习学生自主编写程序，教师及时跟踪、辅导、点评、总结参考程序：Fibonacci 程序迭代算法一：rabbit=0,1,1for i in range(1,11):x=rabbit-1+rabbit-2 rabbit.append(x)print(rabbit)Fibonacci 程序迭代算法二：a=1b=1print(a)print(b)for i in range(3,13):c=a+b print(c)a=b b=c算法一通过数组的形式实现，它与数学中“数列”的关系紧密，便于与数学学科横向联系，算法二设置了三个变量，巧妙地用了 a，b，c 三个变量来中转兔子的数量，初始时，a,b 都为 1，从第三个月开始，c 表示总数，a表示新生下来的兔子或者前两个月的时候就存在的老兔子，也就是 an-2，b 表示前一个月底已经存在的兔子，也就是 an-1，如此滚动向前计算。体会其中 a 和 b 的变化情况。算法二更集中地体现了计算机中迭代算法的特点。对学生编程中不同的实现方式，即时发现、即时点评，可以让学生互评、自评，激发大家探索与思考。学习任务二：牛顿迭代法求解平方根学习任务二：牛顿迭代法求解平方根教材直接提供了牛顿迭代法的算法过程，但里面涉及到几个更细致的问题，可以在时间允许的情况下，采用问题驱动方式，更好地训练学生的计算思维。问题定义。假设实数已经是一个非常清楚的概念，问题在于什么是平方根？数学上认为，如果 x2=y，则非负数x 称为 y 的平方根。这是一个严格的数学定义。但是它并没有给出一种从任一 y 求出 x 的方法。从计算的角度来讲，如果平方根是无理数，就不能写成数字的有效表计算思维能力的培养，首要是问题的清晰定义。它是决定问题解决的关键之一，通过本项目问题定义的细致分析，学生可以体会到一个问题的描述性定义与解决一个问题的操作性定义之间的差异。描述性定义指向操作性定义的过程，是思维的一次本质上的飞跃。注意此处的终止条件与教材中的不同，但只要言之成理，思路正确，示形式，计算必须在有限的步骤内完成，应该是一个有终止条件的过程。因此一般而言，必须把近似误差 e 作为参数事先给定。根据我们的分析：你能把我们的问题重新修改一下吗？可以安排小组讨论，共同探究。数学定义我的定义如果 x2=y，则非负数 x称为 y 的平方根。通过大家共同探究，总结出一个共同认可的操作定义：对于任意非负实数 y，设法找到一个非负实数 x，使得对于任意非负实数 y，设法找到一个非负实数 x，使得，其中 e 为事先设置的允许误差。，其中 e 为事先设置的允许误差。实现方法可以不同。不必局限于教材的具体实现，建议多启迪学生思维，多元思考。知识讲解（2）知识讲解（2）牛顿迭代法的算法思想如下，你觉得它与操作定义是否一致？是否一定能求出平方根？1.设定迭代变量 x 的初始值 x0，如取 x0=y/2；2.确定迭代公式：，并求出 x 的下一个值xn+1;3.如此继续下去，直到，迭代结束。以求 2 的平方根为例，e 取值为 10-5，则迭代变量迭代的过程如表所示。迭代次数迭代次数x xn nx xn+1n+11 111.50.252 21.51.4166670.0069443 31.4166671.4142160.000006当前后两次求出的为 0.000006 时，停止迭代，故 2 的平方根约为 1.414216。首先这个算法描述了一个计算过程，只要能做实数的算术运算、求绝对值、比较大小，就可以机械地重复上述过程。其次这个算法的核心思想是一步步地迭代，从一个初始值逐步地逼近平方根，它是一个逼近、近似的过程。这个算法有点必须证明，即该算法在计算 x 的过程中，序列一定是收敛的，只要迭代的次数足够多，那么就能任意小，因此对任何允许的误差 e，这样的迭代都能保证结束。本例参考代码：程序测试效果y=int(input(请输入一个需要求其平方根的数：)x=y/2while abs(x*x-y)1e-5:x=(x+y/x)/2请输入一个需要求其平方根的数：22 的 平 方 根 约 为 1.414214用迭代算法处理问题，需要考虑以下三个方面：1.确定迭代变量。2.建立迭代关系式。3.控制迭代过程。牛顿迭代法的程序实现难度不大，建议教师引导学生从多个维度来进行探索：不同的初始值、不同的终止条件对迭代次数的影响。为下一步拓展学习提供思维锚点。print(y,的 平 方 根 约 为,round(x+y/x)/2,6)教材参考代码：程序测试效果a=int(input(请输入一个需要求其平方根的数：)x=a/2while(abs(x+a/x)/2-x)0.00001):x=(x+a/x)/2print(a,的平方根约为,round(x+a/x)/2,6)请输入一个需要求其平方根的数：22 的平方根约为 1.414214试比较二者的细微差别，谈谈你的看法。拓展学习拓展学习牛顿法的数学原理，在高中数学课本选修 2-2 第一章“导数及其应用”第 2 节已经作了介绍，阅读课本相关材料，回答课后两个问题。设计意图：牛顿迭代法的数学原理是算法的核心与灵魂，离开思想核心，仅关注算法具体实现的细枝末节是舍本逐末。理解它的思想实质，并把它与后面接触的二分查找算法求解方程的根联系起来。埋下伏笔，为后续章节的学习打下基础。课堂小结课堂小结知识梳理：1.迭代算法的基本思想与应用；2.迭代算法的实现技术；3.迭代算法的数学原理与注意事项。迭代表达式的建立是难点，课后作业提供了相应练习。作业布置作业布置基础作业（面向所有学生）：建议完成课本“欧几里德算法”练习本节安排了五道题目，前三题相对简单，侧重于对变量简单迭代关系的认知，后两题较难，对后续章节的学习也起到了铺垫作用。课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。建议根据学生的基础和能力，设置不同难度的作业，以满足不同层次的学生需求。教学设计思路教学设计思路学生对于三种基本的程序结构已经比较熟悉，顺序结构最简单，实现方便；选择结构需要正确描述条件，只要搞清楚不同情况下如何进行相应处理，用选择语句实现也不太困难；困难的地方，往往是循环结构，由于循环体不仅仅是语句的简单重复，里面还包括变量迭代的技术。迭代一节，主要问题是求解非负实数平方根的牛顿迭代法，它与高中数学教材数列相关内容紧密相连，了解这个公式的背景，更有助于知识内容的理解与掌握。首先，启发学生对“迭代”思想有所感悟，可以引用教材中“软件迭代开发”的事例，或者从身边的小事讲起，例如电子钱包、一卡通余额等每日变化情况。或者举例个人的成长经历等，处处都体现了迭代的过程。其次，可以举一些比较熟悉甚至司空见惯的程序实例，帮助学生理解迭代的思想方法。可以从最简单的话题开始，如变量的重新赋值、更新变量等，逐步过渡到循环语句中的迭代语句。在对“迭代”方法有一定认识的基础上，可以适时与数学中所讲的迭代方法进行类比，以引入牛顿迭代法的思想。再次，计算平方根的牛顿方法就是迭代思想的巧妙运用。这是本节的难点，主要思想是从一个近似值开始，迭代地优化计算结果，达到问题的求解。教师可以结合牛顿迭代公式的讲解，以程序实例演示：更多的迭代次数，会得到更近似的结果。本节主要内容为迭代思想与方法，是对学生平常编程经验的总结与升华。应当避免抽象的概念讲解，充分利用学生既有的编程经验，在学生熟悉的程序实例上进行总结、概括，抽取出迭代的思想与方法，进而提炼出迭代算法的三个关键步骤。通过牛顿法求解平方根的问题与讨论，引导学生逐步理解并掌握迭代的一般编程方法。针对针对核心素养培养的核心素养培养的设计考虑设计考虑信息意识、信息社会责任：本条目通过设置真实问题情境，简单易懂的程序实例入手，唤起学生对常见编程技术共性的初步体悟，对迭代算法的应用普遍性建立基本的信息意识。本节课在导入时选择了两个案例，第一个案例生动有趣，海龟作图里面角度略微改变（90 度修改为 91），可以创造出美妙图案；第二个案例“兔子知多少？”，在前面的学习过程中，学生可能早已经接触到该类问题，教师引导总结提升到理论层次的方式，目的是能够启发思考、归纳出迭代算法的普遍运用，对科技发展、工程应用的重要意义。计算思维：周以真教授认为计算思维是“把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的方法”。导入环节通过简单实例，引入了迭代思想和方法。在教学重点、难点的把握上，特别是牛顿迭代法求根的问题中，教学中专门设计了“问题定义”环节，把一个“平方根”的数学定义转化成了一个可计算的操作定义，为引入牛顿迭代法作好很好的铺垫；牛顿迭代法求根算法，是迭代思想与方法的深化；拓展提高阶段，引入数学材料，引导学生深入到牛顿算法的数学原理，对算法的注意事项能够有更深的理解。数字化学习与创新：本节在导入一中，通过编写的图形界面小程序美妙图案的生成过程，展示了迭代算法的魅力，为典型的数字工具应用。递归教学设计递归教学设计递归递归教材内容：教材内容：5.2 迭代和递归之递归适应的课程标准：适应的课程标准：1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。教学目标：教学目标：能结合具体程序实例，掌握递归函数的定义。能够运用递归的思想和方法，编程实现“汉诺塔”。指向的核心素养：指向的核心素养：信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。数字化学习与创新：要使学生熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。学习环境：学习环境：有教学控制软件的多媒体机房，python 编程环境。课程标准课程标准和和教学目标教学目标建议课时：建议课时：1 课时教学环节教学环节教学过程教学过程设计意图设计意图教学活动设计教学活动设计情境导入情境导入导入 1：展示“俄罗斯套娃”，略加简介：相传俄罗斯民族有两家表亲相邻，表兄妹童年相伴长大，后来表兄远走它乡，由于思念家乡的表妹，每年做木娃娃，一年比一年做的娃娃大。数年后，他回到了家乡，将娃娃送给了表妹，后人模仿传称套娃，又叫吉祥娃娃。引入递归的思想。通过导入生活中的递归案例，以便顺利过渡到递归算法思想的分导入 2：分形图案生成（递归算法），选择 IDLE 中的 Help 菜单Turtle DemoFractalcurves，简介其基本原理。析。学习任务一：学习任务一：阶乘问题学习任务一：阶乘问题问题：利用递归算法求 n 的阶乘（n!=12n）。由数学知识可知，n 阶乘的递归定义为：它等于 n乘以 n-1 的阶乘，即 n！=n*(n-1)!,并且规定 0 的阶乘为 1。设函数 fac(n)=n!，则 fac(n)可表示为：展示一般递归函数定义方法：程序测试效果def fac(n):if n=0:s=1 else:s=n*fac(n-1)return sprint(fac(3)6描述递归过程：设 计 意图：递归是程序设计里面比较高级的技术。递归函数的定义比较特殊，它基于自己定义自己。初学者感觉困惑的地方就在于：这种定义方法有意义吗？这是一种循环定义吗？建议使对应地，可以跟踪递归函数中参数 n 的变化情况：程序测试效果def fac(n):if n=0:s=1 else:print(str(n)+*fac(+str(n-1)+)s=n*fac(n-1)return sprint(fac(3)3*fac(2)2*fac(1)1*fac(0)6设问：前面，我们已经学习过斐波那契数列的递推公式：a1=1a2=1an=an-1+an-2(当 n2 时)你能编写对应的递归程序由计算机计算一年后的兔子总数吗？参考程序：Fibonacci 程序递归算法：def fib(n):if n=1 or n=2:return 1else:return fib(n-1)+fib(n-2)print(到 12 月共有%d 只兔子.%(fib(12)教师总结：能采用递归描述的算法通常有这样的特征：为求解规模为 N 的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。特别地，如当规模 N=0 或 1 时，能直接得解。因此，在设计递归算法时，要满足两个条件，即要确定递归公式和递归结束条件。用简短例子，介绍递归函数的定义方法，递归公式的建立，以及递归结束条件。引用上节已经练习过“兔子有多少只？”程序实例，学生动手写递归程序，初步体会“迭代算法”与“递归算法”的区别。通过对递归程序的执行过程的仔细分析，同时跟踪递归函数中参数的变化，引导加深概念理解，最后总结递归算法的执行过程中的递推和回归两个阶段。自主学习自主学习学生自主编写程序，教师及时跟踪、辅导、点评、总结参考程序：Fibonacci 程序迭代算法一：rabbit=0,1,1for i in range(1,11):x=rabbit-1+rabbit-2 rabbit.append(x)print(rabbit)Fibonacci 程序迭代算法二：a=1b=1print(a)print(b)for i in range(3,13):c=a+b print(c)a=b b=c算法一通过数组的形式实现，它与数学中“数列”的关系紧密，便于与数学学科横向联系，算法二设置了三个变量，巧妙地用了 a，b，c 三个变量来中转兔子的数量，初始时，a,b 都为 1，从第三个月开始，c 表示总数，a 表示新生下来的兔子或者前两个月的时候就存在的老兔子，也就是 an-2，b 表示前一个月底已经存在的兔子，也就是 an-1，如此滚动向前计算。体会其中 a 和 b 的变化情况。算法二更集中地体现了计算机中迭代算法的特点。对 学 生编 程 中不 同 的实 现 方式，即时发现、即时点评，可 以 让学 生 互评、自评，激发大 家 探索 与 思考。学习任务二：学习任务二：汉诺塔游戏学习任务二：汉诺塔游戏汉诺塔游戏更为复杂，为了更好地理解这个问题。教材对此问题进行了详细的分解。一是抽象与建模；二是设计算法；三是编写程序。上一节中课后习题第 5 题，我们专门设置了对应的习题，学生应该对这个问题有所了解。建议本块内容教学按照学生的思维规律，由具体到抽象，由简单到复杂，依序进行。1.抽象与建模为 了 明 确 规 则，推 演 过 程，选 择 IDLE 中 的 Help 菜 单 Turtle DemoMinimal_Hanoi，使用现成的数字化学习工具，直观展示“迷你汉诺塔”游戏的动画过程。计 算 思维 能 力的培养，首 要 是问 题 的抽 象 与建模。它是 决 定问 题 解决 的 关键之一。其次，算法 设 计是 重 点考虑一般情形，为了将 n 个盘子从 A 柱经过 B 柱移动到 C 柱，可建立如下模型：设计意图：递归是计算思维能力之一。首要是寻找和发现问题的规律与内部结构。能够由具体情况概括出一般规律，通过本问题的细致分析，学生可以体会到抽象与建模的基本过程。2.设计算法根据上述抽象与建模可以发现，原来与 n 有关的问题变成了与 n-1 有关的问题，重复这个过程，每次 n 减 1，最后当 n=1 时，直接移动该盘子。因此，该问题可采用递归算法来实现，即：（1）定义一个实现盘子移动的函数 move。如将 n 个盘子从 A 柱经过 B 柱移动到 C 柱，可调用函数 move(n,a,b,c)，其中，n 表示 A 柱上的盘子个数，a、b、c 分别表示 A 柱、B 柱、C 柱。（2）将 n-1 个盘子从 B 柱经过 A 柱移动到 C 柱，可以分解成如下递归调用：move(n-1,a,c,b)acmove(n-1,b,a,c)（3）当 n=1 时，直接移动盘子，递归结束。设计意图：难点在于根据模型写出对应的程序实现，而本算法中的函数参数是疑难点。实参与形参的区别、参数在每次递归中变化情况，可以略加展开说明。3.编写程序根据算法，得到的程序及测试效果如下：程序测试效果def move(n,a,b,c):A-C与难点。可以在模型指导下配合讲解递归函数的设计，鼓励学生自己动手编写程序。尝试修改函数中的次数参数，观察参数变化带来不同的效果。将 n-1 个盘子从 A 柱经过 C柱移动到 B 柱将 A 柱中剩下 的 一 个 盘子 移 动 到 C柱将 n-1 个 盘子从 B 柱经过 A 柱移动到 C 柱 if(n=1):print(a,-,c)return move(n-1,a,c,b)move(1,a,b,c)move(n-1,b,a,c)move(3,A,B,C)A-BC-BA-CB-AB-CA-C拓展学习拓展学习递归程序一般具有如下结构：（1）首先指出数据规模“最简单”的情况，数据如何进行计算。（2）数据规模“较复杂”的情况，可以归结为“较简单”的数据计算。递归程序的程序正确性与数学归纳法紧密联系。数学归纳法的基本证明过程：（1）验证当 n=1（或其它值）时，递归式成立。（2）假设当 n=k 时，递归式成立，证明 n=k+1 时，递归式亦成立。具体使用递归时应避免“无限递归”的情形。如果一个递归永远也达不到基准情形，则它会永远继续递归调用，而程序也永不停止。这个现象称为“无限递归”。下面是一个会引起无限递归的最简单的函数：Def recurse():Recurse()无限递归的函数并不会真的永远执行，python 运行环境会在递归深度达到上限时报告一个出错信息：“RuntimeError:Maximum recursion depth exceeded”，即“运行时错误：超出最大递归深度”（默认上限为 1000）递归设计是一个难点，而它的基本思想原理与数学归纳法密切相关，同时还应当注意“无限递归”问题。课堂小结课堂小结知识梳理：1.递归代算法的基本思想与应用；2.递归算法的实现技术；3.递归算法的数学原理与注意事项。迭 代 表达 式 的建 立 是难点，课后 作 业提 供 了相 应 练习。作业布置作业布置基础作业（面向所有学生）：完成课本“思考与练习”第 4 题本节安排了三道题目，也可以结合本章习题布置作业。课 后 作业 是 课堂 学 习的延伸，是 巩 固和 升 华知 识 点的 有 效途径。教学设计思路教学设计思路本课内容为递归，建议分配 1 课时完成。递归在解决一类问题时十分有用，往往描述简洁，易于理解，并能极大地减少程序代码量。它的关键在于识别出内在的递归结构。它与高中数学教材中的“数学归纳法”原理紧密相连，了解这个原理更有助于知识内容的理解与掌握。首先，启发学生对“递归”思想有所感悟，可以引用生活的事例（比如俄罗斯套娃），或者从身边的小事讲起，例如“帮拿作业本”。其次，以阶乘为例，介绍其递归公式，引入递归函数的定义。然后重点强调设计递归算法时，要满足两个条件：确定递归公式和递归结束的条件。再次，为进一步引导学生使用递归算法来解决问题，可以使用汉诺塔游戏为例，重点放在问题的分解与综合上，重点在于提示其内在的递归结构。本节主要内容为递归。学生对于递归相对陌生，理解难度较大，建议从抽象与建模、设计算法、程序实现三个方面，深化细化，引导学生理解并掌握递归算法。针对针对核心素养培养的核心素养培养的设计考虑设计考虑信息意识、信息社会责任：本节课在导入时选择了两个案例，导入一“俄罗斯套娃”来自生活，导入二“分形图案生成”，递归算法可以创造出美妙图案；这些实例目的是引起学生探究的兴趣，提示学生意识到递归算法思想的奇妙运用，教师引导总结“即大问题的解决中嵌套着原问题相似的规模较小的问题”，目的是能够启发思考、归纳出递归算法的普遍运用，增强学生对此类问题的敏感性，对递归算法的思想有初步的意识。计算思维：本节中的递归算法即为计算思维的核心之一，主要表现在如下四个方面：一是如何将一个复杂的问题简单化处理，这体现了简洁性；二是对于每次简化的问题，其表达方式与原方式保持一致，反映了结构性；三是问题解决是有终止的，简化到一定程度，一定是可以解决的，反映了构造性；四是可以用有限的步骤处理近于无限功能的方法，体现了简约性。数字化学习与创新：本节选择 IDLE 中的 Help 菜单Turtle DemoMinimal_Hanoi，使用现成的数字化学习工具，直观展示“迷你汉诺塔”游戏的动画过程，为典型的数字工具应用。