浙教版 (2019)选修1 数据与数据结构第五章 数据结构与算法5.2 迭代与递归优质课件ppt

课程标准

和

教学目标

迭代

教材内容：5.2迭代和递归之迭代

适应的课程标准：

1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。

教学目标：

●能结合具体程序实例，掌握迭代的思想和方法。

●能够运用迭代的思想和方法，编程实现方程根的求解。

指向的核心素养：

●信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。

●计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。

●数字化学习与创新：要使学生为熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。

●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。

学习环境：有教学控制软件的多媒体机房，python编程环境。

建议课时：1课时

教学活动设计

教学环节

教学过程

设计意图

情境导入

导入1：自主编写程序展示“美妙的图案”，引导学生体会python turtle海龟作图的美妙之处，对作图的原理略加简介，引入迭代的思想。

提问：如果将中程序中“t.left(90)”语句的参数90修改为91，效果又如何？

导入2：“兔子有多少只？”：假定我们有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始怀孕（真实情况是六个月左右），在第二月结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每只雌兔在开始繁殖后每月都产下一对兔子，假定没有兔子死亡，在一年后总共有多少对兔子？

请同学们计算前几个月兔子的数量，填写下表，看看能不能找到规律？

设计意图：通过导入生活中的迭代算法问题，以便顺利过渡到迭代算法思想的分析。

学习任务一：斐波那契数列的求解

●学习任务一：斐波那契数列的求解

通过同学小组讨论，教师总结“兔子有多少只？”问题的分析过程：若用an表示第n个月底兔子的数目，因为每个月底的兔子可以被分成两个部分：一部分是上个月底就有的兔子an-1,另外一部分就是这个月新生下来的，而这个新生的显然就是上两个月就存在的那些兔子生出来的an-2。

我们可以写出这样的递推公式：

 a1 = 1

 a2 = 1

an=an-1+an-2(当n>2时)

设计意图：引入时提供了两个具体实例，特别是第二个需要学生自己动手实践，建议放手让学生讨论并自主实现算法。需要注意的是，学生在编写程序的过程，可能会有不同的实现，应充分尊重学生的想法，放手让学生多想多试。通过“兔子有多少只？”程序实例，学生可以初步理解“迭代算法”的思想实质。通过对实际程序两种实现的对比分析，引导学生自主阅读教材内容，加深概念理解，并由教师引导，总结概括出迭代算法的三个重要方面即“确定迭代变量”、“建立迭代关系式”、“控制迭代过程”。

自主学习

学生自主编写程序，教师及时跟踪、辅导、点评、总结

参考程序：

Fibonacci程序迭代算法一：

Fibonacci程序迭代算法二：

算法一通过数组的形式实现，它与数学中“数列”的关系紧密，便于与数学学科横向联系，算法二设置了三个变量，巧妙地用了a，b，c三个变量来中转兔子的数量，初始时，a,b都为1，从第三个月开始，c表示总数，a表示新生下来的兔子或者前两个月的时候就存在的老兔子，也就是an-2，b表示前一个月底已经存在的兔子，也就是an-1，如此滚动向前计算。体会其中a和b的变化情况。算法二更集中地体现了计算机中迭代算法的特点。

对学生编程中不同的实现方式，即时发现、即时点评，可以让学生互评、自评，激发大家探索与思考。

学习任务二：牛顿迭代法求解平方根

教材直接提供了牛顿迭代法的算法过程，但里面涉及到几个更细致的问题，可以在时间允许的情况下，采用问题驱动方式，更好地训练学生的计算思维。

问题定义。假设实数已经是一个非常清楚的概念，问题在于什么是平方根？数学上认为，如果x2= y，则非负数x称为y的平方根。这是一个严格的数学定义。但是它并没有给出一种从任一y求出x的方法。从计算的角度来讲，如果平方根是无理数，就不能写成数字的有效表示形式，计算必须在有限的步骤内完成，应该是一个有终止条件的过程。因此一般而言，必须把近似误差e作为参数事先给定。根据我们的分析：你能把我们的问题重新修改一下吗？可以安排小组讨论，共同探究。

通过大家共同探究，总结出一个共同认可的操作定义：

对于任意非负实数y，设法找到一个非负实数x，使得，其中e为事先设置的允许误差。

计算思维能力的培养，首要是问题的清晰定义。它是决定问题解决的关键之一，通过本项目问题定义的细致分析，学生可以体会到一个问题的描述性定义与解决一个问题的操作性定义之间的差异。描述性定义指向操作性定义的过程，是思维的一次本质上的飞跃。注意此处的终止条件与教材中的不同，但只要言之成理，思路正确，实现方法可以不同。不必局限于教材的具体实现，建议多启迪学生思维，多元思考。

知识讲解（2）

牛顿迭代法的算法思想如下，你觉得它与操作定义是否一致？是否一定能求出平方根？

1.设定迭代变量x的初始值x0，如取x0=y/2；

2.确定迭代公式：，并求出x的下一个值xn+1;

3.如此继续下去，直到，迭代结束。

以求2的平方根为例，e取值为10-5，则迭代变量迭代的过程如表所示。

当前后两次求出的为0.000006时，停止迭代，故2的平方根约为1.414216。

首先这个算法描述了一个计算过程，只要能做实数的算术运算、求绝对值、比较大小，就可以机械地重复上述过程。其次这个算法的核心思想是一步步地迭代，从一个初始值逐步地逼近平方根，它是一个逼近、近似的过程。这个算法有点必须证明，即该算法在计算x的过程中，序列一定是收敛的，只要迭代的次数足够多，那么就能任意小，因此对任何允许的误差e，这样的迭代都能保证结束。

本例参考代码：

教材参考代码：

试比较二者的细微差别，谈谈你的看法。

用迭代算法处理问题，需要考虑以下三个方面：1.确定迭代变量。2.建立迭代关系式。3.控制迭代过程。牛顿迭代法的程序实现难度不大，建议教师引导学生从多个维度来进行探索：不同的初始值、不同的终止条件对迭代次数的影响。为下一步拓展学习提供思维锚点。

拓展学习

牛顿法的数学原理，在高中数学课本选修2-2第一章“导数及其应用”第2节已经作了介绍，阅读课本相关材料，回答课后两个问题。

设计意图：牛顿迭代法的数学原理是算法的核心与灵魂，离开思想核心，仅关注算法具体实现的细枝末节是舍本逐末。理解它的思想实质，并把它与后面接触的二分查找算法求解方程的根联系起来。埋下伏笔，为后续章节的学习打下基础。

课堂小结

知识梳理：

1. 迭代算法的基本思想与应用；

2. 迭代算法的实现技术；

3. 迭代算法的数学原理与注意事项。

迭代表达式的建立是难点，课后作业提供了相应练习。

作业布置

基础作业（面向所有学生）：

建议完成课本“欧几里德算法”练习

本节安排了五道题目，前三题相对简单，侧重于对变量简单迭代关系的认知，后两题较难，对后续章节的学习也起到了铺垫作用。

课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。建议根据学生的基础和能力，设置不同难度的作业，以满足不同层次的学生需求。

教学设计思路

学生对于三种基本的程序结构已经比较熟悉，顺序结构最简单，实现方便；选择结构需要正确描述条件，只要搞清楚不同情况下如何进行相应处理，用选择语句实现也不太困难；困难的地方，往往是循环结构，由于循环体不仅仅是语句的简单重复，里面还包括变量迭代的技术。

迭代一节，主要问题是求解非负实数平方根的牛顿迭代法，它与高中数学教材数列相关内容紧密相连，了解这个公式的背景，更有助于知识内容的理解与掌握。

首先，启发学生对“迭代”思想有所感悟，可以引用教材中“软件迭代开发”的事例，或者从身边的小事讲起，例如电子钱包、一卡通余额等每日变化情况。或者举例个人的成长经历等，处处都体现了迭代的过程。

其次，可以举一些比较熟悉甚至司空见惯的程序实例，帮助学生理解迭代的思想方法。可以从最简单的话题开始，如变量的重新赋值、更新变量等，逐步过渡到循环语句中的迭代语句。在对“迭代”方法有一定认识的基础上，可以适时与数学中所讲的迭代方法进行类比，以引入牛顿迭代法的思想。

再次，计算平方根的牛顿方法就是迭代思想的巧妙运用。这是本节的难点，主要思想是从一个近似值开始，迭代地优化计算结果，达到问题的求解。教师可以结合牛顿迭代公式的讲解，以程序实例演示：更多的迭代次数，会得到更近似的结果。

本节主要内容为迭代思想与方法，是对学生平常编程经验的总结与升华。应当避免抽象的概念讲解，充分利用学生既有的编程经验，在学生熟悉的程序实例上进行总结、概括，抽取出迭代的思想与方法，进而提炼出迭代算法的三个关键步骤。通过牛顿法求解平方根的问题与讨论，引导学生逐步理解并掌握迭代的一般编程方法。

针对

核心素养培养的

设计考虑

信息意识、信息社会责任：本条目通过设置真实问题情境，简单易懂的程序实例入手，唤起学生对常见编程技术共性的初步体悟，对迭代算法的应用普遍性建立基本的信息意识。本节课在导入时选择了两个案例，第一个案例生动有趣，海龟作图里面角度略微改变（90度修改为91），可以创造出美妙图案；第二个案例“兔子知多少？”，在前面的学习过程中，学生可能早已经接触到该类问题，教师引导总结提升到理论层次的方式，目的是能够启发思考、归纳出迭代算法的普遍运用，对科技发展、工程应用的重要意义。

计算思维：周以真教授认为计算思维是“把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的方法”。导入环节通过简单实例，引入了迭代思想和方法。在教学重点、难点的把握上，特别是牛顿迭代法求根的问题中，教学中专门设计了“问题定义”环节，把一个“平方根”的数学定义转化成了一个可计算的操作定义，为引入牛顿迭代法作好很好的铺垫；牛顿迭代法求根算法，是迭代思想与方法的深化；拓展提高阶段，引入数学材料，引导学生深入到牛顿算法的数学原理，对算法的注意事项能够有更深的理解。

数字化学习与创新：本节在导入一中，通过编写的图形界面小程序——美妙图案的生成过程，展示了迭代算法的魅力，为典型的数字工具应用。