高中信息技术教科版 (2019)选修1 数据与数据结构第3单元 数据的排序与查找3.1 迭代与递归教案及反思

课 题

3.1迭代与递归

课时安排

1

课型

素养目标

课程标准要求：1.通过实现数据的排序和查找，体验迭代和递归的方法。

2.通过列举实例理解算法与数据结构的关系。

信息意识：1.理解迭代和递归的概念。

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

计算思维：1.体验迭代和递归的方法。

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

数字化学习与创新：1.初步掌握迭代和递归方法的基本要求。

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

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

教学重点

理解迭代和递归的概念。

教学难点

掌握迭代和递归的方法和要求。

教学方法

多媒体机房，python编程环境中讲授、演示、动手操作

学习方法

自主探究法

教学过程

个别化教案

一、考勤

二、课前测评：字符串的概念和匹配

三、导入：

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

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

导入2：用迭代法和递归法解决斐波那契问题。通过手工计算和利用迭代、递归法解决斐波那契问题。

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

四、新课内容：

一：斐波那契数列的求解

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

学习任务一：用迭代法解决斐波那契问题

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

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

 a1 = 1

 a2 = 1

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

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

迭代：是从初始值出发，通过一系列步骤来逐步逼近问题最终解的过程。

例如，在上面求斐波那契数的活动中，初始值为1、1两项，从这两项出发，依次求出第3项、第4项……，每轮通过最后两项相加得到新的一项，每一轮都更接近第8项并最终达到第8项。

通过上面的算法分析可知，计算斐波那契数列的过程就是不断做一下操作的过程。

用代表后两项的变量a和b计算出新的项c:   a+b→c

然后让a和b指向新的最后两项，以便下一轮还可以使用a和b计算出新的c。使用一下操作更新变量a和b的值。 b→a   c→b

01. #求第n项斐波那契数

02. def fib(n):

03.     #n小于3时

04.     if n<3:

05.        return 1

06.     #n大于等于3时

07.     a=b=1

08.     for i in range(3,n+1):

09.         c=a+b

10.         a=b

11.         b=c

12.     return c

13. print(fib(8))

利用迭代法解决问题的要点：

(1)确定迭代的起点。

(2)确定逼近最终解的操作。

(3)控制迭代过程。

活动3:用迭代法解决问题

学习任务二：用递归法解决斐波那契问题

活动1：再探斐波那契问题

一个大的斐波那契数由两个更小的数构成，那么计算斐波那契数的任务也可以通过任务的分解来完成。比如求fib（6）可以分解为求fib（5）和fib（4），它们又可以继续分解，最终都可以分解为求fib（1）或fib（2）。

递归：函数直接或间接调用自身称为递归。

递归把一个大问题分解为规模更小的同类问题来求解。因为是同一类问题，所以还是调用原来的函数，只是函数的调用参数有一些变化。

活动2：用递归法解决斐波那契问题

01. def fib(n):

02.     if n==1 or n==2

03.        return 1

04.     else:

05.        return fib(n-1)+fib(n-2)

06. print(fib(6))

使用递归法解决问题的要点：

(1)确定问题最小规模的简单解。

(2)把问题表示为更小规模的相同问题的组合。

(3)通过调用自身来解决问题。

活动3：用递归法解决问题

五、小结

1．斐波那契数列。

2. 迭代与递归概念。

3. 解决实际问题。

作 业

板

书

设

计

斐波那契数列

迭代与递归

教

学

反

思

教案查阅签字