浙教版 (2019)选修1 数据与数据结构5.2 迭代与递归教案

这是一份浙教版 (2019)选修1 数据与数据结构5.2 迭代与递归教案，共7页。

课程标准
和
教学目标
递归
教材内容：5.2迭代和递归 之 递归
适应的课程标准：
1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。
教学目标：
●能结合具体程序实例，掌握递归函数的定义。
●能够运用递归的思想和方法，编程实现“汉诺塔”。
指向的核心素养：
●信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。
●计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。
●数字化学习与创新：要使学生熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。
●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。
学习环境：有教学控制软件的多媒体机房，pythn编程环境。
建议课时：1课时
教学活动设计
教学环节
教学过程
设计意图
情境导入
导入1：展示“俄罗斯套娃”，略加简介：相传俄罗斯民族有两家表亲相邻，表兄妹童年相伴长大，后来表兄远走它乡，由于思念家乡的表妹，每年做木娃娃，一年比一年做的娃娃大。数年后，他回到了家乡，将娃娃送给了表妹，后人模仿传称套娃，又叫吉祥娃娃。引入递归的思想。
导入2：分形图案生成（递归算法），选择IDLE中的Help菜单——Turtle Dem——Fractalcurves，简介其基本原理。
通过导入生活中的递归案例，以便顺利过渡到递归算法思想的分析。
学习任务一：阶乘问题
●学习任务一：阶乘问题
问题：利用递归算法求n的阶乘（n!=1×2×…×n）。由数学知识可知，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 s
print(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 s
print(fac(3))
3*fac(2)
2*fac(1)
1*fac(0)
6
设问：
前面，我们已经学习过斐波那契数列的递推公式：
a1 = 1
a2 = 1
an=an-1+an-2(当n>2时)
你能编写对应的递归程序由计算机计算一年后的兔子总数吗？
参考程序：
Fibnacci程序递归算法：
def fib(n):
if n == 1 r n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
print("到12月共有%d只兔子." % (fib(12)))
教师总结：能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。特别地，如当规模N=0或1时，能直接得解。因此，在设计递归算法时，要满足两个条件，即要确定递归公式和递归结束条件。
设计意图：递归是程序设计里面比较高级的技术。递归函数的定义比较特殊，它基于自己定义自己。初学者感觉困惑的地方就在于：这种定义方法有意义吗？这是一种循环定义吗？建议使用简短例子，介绍递归函数的定义方法，递归公式的建立，以及递归结束条件。引用上节已经练习过“兔子有多少只？”程序实例，学生动手写递归程序，初步体会“迭代算法”与“递归算法”的区别。通过对递归程序的执行过程的仔细分析，同时跟踪递归函数中参数的变化，引导加深概念理解，最后总结递归算法的执行过程中的递推和回归两个阶段。
自主学习
学生自主编写程序，教师及时跟踪、辅导、点评、总结
参考程序：
Fibnacci程序迭代算法一：
rabbit = [0,1,1]
fr i in range(1,11):
x = rabbit[-1] + rabbit[-2]
rabbit.append(x)
print(rabbit)
Fibnacci程序迭代算法二：
a = 1
b = 1
print(a)
print(b)
fr 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 Dem——Minimal_Hani，使用现成的数字化学习工具，直观展示“迷你汉诺塔”游戏的动画过程。
考虑一般情形，为了将n个盘子从A柱经过B柱移动到C柱，可建立如下模型：
将n-1个盘子从A柱经过C柱移动到B柱
将A柱中剩下的一个盘子移动到C柱
将n-1个盘子从B柱经过A柱移动到C柱
设计意图：递归是计算思维能力之一。首要是寻找和发现问题的规律与内部结构。能够由具体情况概括出一般规律，通过本问题的细致分析，学生可以体会到抽象与建模的基本过程。
2.设计算法
根据上述抽象与建模可以发现，原来与n有关的问题变成了与n-1有关的问题，重复这个过程，每次n减1，最后当n=1时，直接移动该盘子。因此，该问题可采用递归算法来实现，即：
（1）定义一个实现盘子移动的函数mve。如将n个盘子从A柱经过B柱移动到C柱，可调用函数mve(n, a, b, c)，其中，n表示A柱上的盘子个数，a、b、c分别表示A柱、B柱、C柱。
（2）将n-1个盘子从B柱经过A柱移动到C柱，可以分解成如下递归调用：
mve(n-1, a, c, b)
a→c
mve(n-1, b, a, c)
（3）当n=1时，直接移动盘子，递归结束。
设计意图：难点在于根据模型写出对应的程序实现，而本算法中的函数参数是疑难点。实参与形参的区别、参数在每次递归中变化情况，可以略加展开说明。
3. 编写程序
根据算法，得到的程序及测试效果如下：
程序
测试效果
def mve(n, a, b, c):
if(n == 1):
print(a,"->",c)
return
mve(n-1, a, c, b)
mve(1, a, b, c)
mve(n-1, b, a, c)
mve(3, "A", "B", "C")
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
计算思维能力的培养，首要是问题的抽象与建模。它是决定问题解决的关键之一。其次，算法设计是重点与难点。可以在模型指导下配合讲解递归函数的设计，鼓励学生自己动手编写程序。尝试修改函数中的次数参数，观察参数变化带来不同的效果。
拓展学习
递归程序一般具有如下结构：
（1）首先指出数据规模“最简单”的情况，数据如何进行计算。
（2）数据规模“较复杂”的情况，可以归结为“较简单”的数据计算。
递归程序的程序正确性与数学归纳法紧密联系。数学归纳法的基本证明过程：
（1）验证当n = 1（或其它值）时，递归式成立。
（2）假设当n = k时，递归式成立，证明n = k+1时，递归式亦成立。
具体使用递归时应避免“无限递归”的情形。如果一个递归永远也达不到基准情形，则它会永远继续递归调用，而程序也永不停止。这个现象称为“无限递归”。下面是一个会引起无限递归的最简单的函数：
Def recurse():
Recurse()
无限递归的函数并不会真的永远执行，pythn运行环境会在递归深度达到上限时报告一个出错信息：“RuntimeErrr:Maximum recursin depth exceeded”，即“运行时错误：超出最大递归深度”（默认上限为1000）
递归设计是一个难点，而它的基本思想原理与数学归纳法密切相关，同时还应当注意“无限递归”问题。
课堂小结
知识梳理：
1. 递归代算法的基本思想与应用；
2. 递归算法的实现技术；
3. 递归算法的数学原理与注意事项。
迭代表达式的建立是难点，课后作业提供了相应练习。
作业布置
基础作业（面向所有学生）：
完成课本“思考与练习”第4题
本节安排了三道题目，也可以结合本章习题布置作业。
课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。
教学设计思路
本课内容为递归，建议分配1课时完成。递归在解决一类问题时十分有用，往往描述简洁，易于理解，并能极大地减少程序代码量。它的关键在于识别出内在的递归结构。
它与高中数学教材中的“数学归纳法”原理紧密相连，了解这个原理更有助于知识内容的理解与掌握。
首先，启发学生对“递归”思想有所感悟，可以引用生活的事例（比如俄罗斯套娃），或者从身边的小事讲起，例如“帮拿作业本”。
其次，以阶乘为例，介绍其递归公式，引入递归函数的定义。然后重点强调设计递归算法时，要满足两个条件：确定递归公式和递归结束的条件。
再次，为进一步引导学生使用递归算法来解决问题，可以使用汉诺塔游戏为例，重点放在问题的分解与综合上，重点在于提示其内在的递归结构。
本节主要内容为递归。学生对于递归相对陌生，理解难度较大，建议从抽象与建模、设计算法、程序实现三个方面，深化细化，引导学生理解并掌握递归算法。
针对
核心素养培养的
设计考虑
信息意识、信息社会责任：本节课在导入时选择了两个案例，导入一“俄罗斯套娃”来自生活，导入二“分形图案生成”，递归算法可以创造出美妙图案；这些实例目的是引起学生探究的兴趣，提示学生意识到递归算法思想的奇妙运用，教师引导总结“即大问题的解决中嵌套着原问题相似的规模较小的问题”，目的是能够启发思考、归纳出递归算法的普遍运用，增强学生对此类问题的敏感性，对递归算法的思想有初步的意识。
计算思维：本节中的递归算法即为计算思维的核心之一，主要表现在如下四个方面：一是如何将一个复杂的问题简单化处理，这体现了简洁性；二是对于每次简化的问题，其表达方式与原方式保持一致，反映了结构性；三是问题解决是有终止的，简化到一定程度，一定是可以解决的，反映了构造性；四是可以用有限的步骤处理近于无限功能的方法，体现了简约性。
数字化学习与创新：本节选择IDLE中的Help菜单——Turtle Dem——Minimal_Hani，使用现成的数字化学习工具，直观展示“迷你汉诺塔”游戏的动画过程，为典型的数字工具应用。