5.2 迭代与递归（教学课件）信息技术浙教版2019选择性必修1

第2节 迭代与递归（2课时） 第5章 数据结构与算法 浙教版（2019） 选修一 迭代 01 递归 02 学习目录 能结合具体程序实例，掌握迭代和递归的思想和方法。 01 引导学生自觉应用迭代、递归算法，解决生活、学习中的问题。 03 能够运用迭代和递归的思想和方法,编程实现方程根的求解。 02 学习目标 PART 01 迭代 新课导入 想 想 一 某饲养场引进了1对刚出生的新品种兔子，第2个月进入成熟期，第3个月开始生育兔子，新生的兔子成熟后的下月又会新生1对兔子……若所有的兔子都不会死去，则到第12个月时，该饲养场共有多少对兔子？ 新课导入 兔子繁殖过程： 1月：兔①新生，共1对 2月：兔①成熟，共1对 3月：兔①生兔②，共2对 4月：兔①生兔③，兔②成熟，共3对 5月：兔①生兔④，兔②生⑤，兔③成熟，共5对 6月：兔①生兔⑥，兔②生兔⑦，兔③生兔⑧，兔④⑤成熟，共8对 ...... 迭代算法 新课导入 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月 …月 1对 1对 2对 3对 5对 8对 13对 21对 34对 55对 89对 144对 …对 (元素的入栈顺序和出栈顺序相反) 规律：第3月开始，当月兔子数=上月兔子数+当月新生兔子数=上月兔子数+上上月兔子数 迭代算法：旧值不断推出新值的过程 f1 = 1 # 1月兔子数 f2 = 1 # 2月兔子数 i = 3 while i <= 12: f = f1 + f2 f1 = f2 f2 = f i += 1 print(f"第{i-1}月共有{f}对兔子“) 时间复杂度〇(n) 新课导入 想 想 一 第一天往钱罐子里面投入1元，存钱罐总金额为1元；第二天往钱罐里面投入2元，存钱罐总金额为3元；第三天往存钱罐里面投入3元，存钱罐里面总金额为6元；那么第n天时存钱罐里面一共有多少钱? 新课导入 n=int(input("存钱天数:")) s=0 for i in range(1,n+1): print("存钱罐的钱数:",s) 我们利用循环不断执行累加求和，从原值s算出新值s最终计算出存钱罐的钱数，这种将变量从原值递推出一个新值的算法，我们称之为迭代算法。 s=s+i 迭代 一 概念 迭代是重复反馈的过程，其目的通常是为了接近并达到所需的目标或结果。每一次对过程的重复被称为一次迭代，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。 特性 迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令(或一定步骤)这组指令(或这些步骤)每执行一次，都会将变量从原值推出一个新值。 迭代 一 03 02 01 利用迭代算法解决问题， 需要做好三个方面 确定迭代变量 在能够用迭代算法处理问题中，至少具有一个直接或间接地不断有旧值推出新值的变量，这个变量就是迭代变量。 建立迭代关系式 所谓迭代关系式，指如何从变量的前一个值推出下一个值的公式(或关系)。 控制迭代过程 迭代过程在经过若干次重复执行以后要能结束，因此，要设定迭代结束的条件。 (元素的入栈顺序和出栈顺序相反) 迭代算法的设计方法 迭代 一 迭代算法：利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，这组指令每执行一次时，都会将变量从原值递推出一个新值，即由旧值不断推出新值的过程。 f1 = 1 # 1月兔子数 f2 = 1 # 2月兔子数 i = 3 while i <= 12: f = f1 + f2 f1 = f2 f2 = f i += 1 print(f"第{i-1}月共有{f}对兔子“) 迭代算法: ①确定迭代变量 ②建立迭代关系式 ③控制迭代过程 迭代 一 采用迭代算法求a的平方根 基本思路 先估测一个近似值x，然后不断令x等于x和 的平均数（迭代公式为：xn+1=(xn+)(n≥0)),经过若干次迭代后，x的值将逐渐逼近a的平方根（当xn+1与xn值无限逼近时，可看作xn+1=xn，则公式xn+1=(xn+)可化简为x2n+1=a,xn+1就是a的平方根）。以求2的平方根为例，可估测一个近似值（如x0=1）作为初值，设定前后两次求出的x的差的绝对值小于10-5。 迭代 一 设定迭代变量x的初始值x0，如取x0=1。 确定迭代公式：xn+1=(xn+),并求出xn+1的值。 重复步骤2，直到前后两次求出的x值（xn和xn+1）满足一定的误差，即| xn+1–xn |＜10-5，迭代结束。xn+1就是所求的平方根。 1 2 3 操作步骤 迭代 一 迭代变量迭代过程 当前后两次求出的x值（xn和xn+1）的差的绝对值为0.000002时，停止迭代，得出2的平方根约为1.414214。 程序： a=int(input("请输入一个需要求其平方根的数：")) x=a/2 while ((abs((x+a/x)/2 – x))>0.00001): x=(x+a/x)/2 print(a,"的平方根约为",round((x+a/x)/2,6)) 测试结果： 请输入一个需要求其平方根的数：2 2 的平方根约为 1.414214 迭代 一 拓展链接 欧几里得算法 欧几里得算法又称辗转相除法，用于计算两个整数m，n的最大公约数。基于定理： gcd(m, n)=gcd(n, m mod n) 即：整数m，n的最大公约数等于n和m除以n的余数的最大公约数。 欧几里得算法在执行时，也是一个反复迭代的过程，直到余数等于0为止。 python代码 def gcd(m,n): while n!=0: temp=n n=m%n m=temp return m m，n是迭代变量，迭代关系是n→m和m% n→n，由旧值推出新值，然后循环执行，直到余数为0，结束迭代。 迭代 一 只需知道数据之间相互链接的顺序 探讨与讨论 一 通常是为了接近并达到所需的目标或结果，对过程进行重复，每一次重复得到的结果会被用来作为下一次的初始值。这种用计算机解决问题的一种基本方法是( ) A.迭代法 B.查找法 C.分析法 D.排序法 A 迭代 一 只需知道数据之间相互链接的顺序 探讨与讨论 二 斐波那契在《计算之书》中，提出了“生小兔问题”如果每对兔子(一雄一雌)每月能生殖一对小兔子，每对兔子第一个月没有生殖能力，但从第二个月以后便能每月生一对小兔子。假定这些兔子都没有死亡现象，那么从第一对刚出生的兔子开始，12个月以后会有多少对兔子呢?这种问题的解决通常是为了接近并达到所需的目标或结果，对过程进行重复，每一次重复得到的结果会被用来作为下一次的初始值。这种用计算机解决问题的一种基本方法是( ) A.排序法 B.查找法 C.二分法 D.迭代法 D 迭代 一 只需知道数据之间相互链接的顺序 探讨与讨论 三 定义如下函数: def fn(x): if x<=2: return x else: return fn(x-1)+fn(x-2) ans=fn(6) print(ans) 执行上述程序后输出的结果是( ) A.13 B.12 C.11 D.10 A 递归 二 美国谴责“中国谴责美国干涉中国内政”是中国干涉美国内政 禁止套娃→禁止禁止套娃→禁止禁止禁止套娃→…… 俄罗斯一票否决了“乌克兰提出的取消俄罗斯一票否决权”的提案 一网民因造谣“自己因为造谣被公安拘留15天”而被拘留15天 套娃 递归 二 大问题的解决中嵌套着与原问题相似的规模较小的问题。 这种解决问题的方式在计算机科学中称为递归，通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 递归 二 概念 在计算机科学中，指一种通过重复将问题分解为同类的子问题而解决问题的方法，它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 把大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，规模较小的又转化为规模更小的问题求解，当问题小到一定程度时，可以直接得出它的解，从而回归求解问题原来的解。即“大事化小，小事化了”的思想。 1、每一步解决问题的方法有一致的规律：递归公式 2、可以达到某个边界条件：递归出口 能使函数的定义和算法的描述简洁且易于理解，极大地减少程序代码量。 思想 条件 作用 递归 二 案例 特征 为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，递归核心整体方法和局部方法是一致的。 整数的阶乘、斐波那契的兔子问题、汉诺塔问题、八皇后问题、猴子吃桃问题等 递归 二 大事化小 小事化了 问题提出 寻求规律 假如有一对刚出生的小兔子，只需要一个月小兔子就能长成大兔子，从第三个月开始，这对大兔子每个月都会生下一对小兔子。新出生的小兔子又会花一个月长大，再花一个月开始生兔子… 如果每对兔子都经历这样的出生、成熟、生育的过程，并且永远不死，那么每个月兔子的对数是多少呢？ n个月兔子的对数？ n→n-1→n-2→……→3→2→1 1个月有1对，2个月有1对 … fibo(n) =fibo(n-1)+fibo(n-2) 递归出口 递归公式 递归 二 问题解决 问题思考 迭代：速度快，效率高；但程序冗杂 递归：程序简洁易懂；但速度慢，效率低 def fibo(n): if n<=2: return 1 else: return fibo(n-1)+fibo(n-2) 和迭代相比时空复杂度？ def fibo(n): i=3 a,b=1,1 while i<=n: a,b=b,a+b i+=1 return b 时间复杂度：O(2^N) 空间复杂度：O(N） 时间复杂度：O(N) 空间复杂度：O(1) 递归 二 求n的阶乘（n!=1×2×…×n） 由数学知识牵引 由数学知识可知，n阶乘的递归定义为：它等于n乘以n–1的阶乘，即n!=n×(n–1)!，并且规定0!=1。设函数fac(n)=n!，则fac(n)可表示为： fac(n)= 1 （n=0） n×fac(n–1) （n＞0） 按照这个公式，可以将求n!的问题转化成求(n-1)!的问题；而求(n-1)!的问题，又可以转化成求(n-2)!的问题；求（n-2）!的问题，又可以转化成求(n-3)的问题，如此继续，直到最后转化成求0！的问题。再反过来，依次求出1！，2！，…，直到最后求出n!。因此，在该问题中，递归公式是fac(n)=n*fac(n-1),当n=0时递归结束。 递归 二 求n的阶乘的相应的程序及测试结果如下： 程序： def fac(n): if n==0: s=1 else: s=n*fac(n–1) return s print(fac(3)) 测试结果： 6 (元素的入栈顺序和出栈顺序相 当主程序执行函数fac(3)时，引起第1次函数调用，进入函数后，参数n=3，应执行计算3*fac(2)。直到计算fac(0)，将引起对函数fac的第4次调用。 递归 二 以上调用的执行和返回情况，如下图所示： 递归调用过程 递归 二 对于阶乘问题，可以在原程序上通过添加一条语句来跟踪参数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 递归 二 拓展链接 递归与栈 计算机在执行递归程序时，是通过栈的调用来实现的。递归程序是将复杂问题分解为一系列简单的问题，从要解的问题起，逐步分解，并将每步分解得到的问题放入“栈”中，运用栈的“后进先出”的性质，这样栈顶是最后分解得到的最简单的问题，解决了这个问题后，次简单的问题可以得到答案，以此类推。所以，分解问题可以看作是进栈的过程，而解决问题则是出栈的过程。 对于求n阶乘的递归函数fac(n)，当调用它时系统自动建立一个栈，该栈中的元素包含每次调用的计算结果和返回地址的情况。 递归 二 求fac(3)，即y=fac(3)，判断可知执行得到f=3*fac(2)，但是，这并不是确切的值，还有fac的函数调用，所以系统就会将当前计算出的结果存放入栈内，相当于执行完fac(3)后在执行fac(2)之前，系统就会在栈顶插入f=3*fac(2)以及一个返回地址。把这些运算得到的内容压入栈顶后，然后去执行fac(2)，产生f=2*fac(1)，n变为了1。此时还没有结束，在执行fac(1)前，系统又把产生的f=2*fac(1)和一个返回地址又压入到先前开辟的栈中……当执行fac(0)时，符合“n=0”这个条件，所以f=1，此时系统就会把f=1和一个返回地址压入到栈中。此时，不再进行向后的fac函数运算，递归调用结束。下个阶段就是数据出栈，系统会自动地把栈顶的数据读出来，即首先把f=1和一个返回地址读出，然后读出第二个数据f=2*fac(1)以及一个返回地址……直到执行完f=6，按照栈底数据的返回值，就把f赋值给了主程序中的y。 计算fac(3)过程中参数的入栈和出栈过程 递归 二 汉诺塔游戏 汉诺塔游戏的装置是一块铜板，上面有三根针，其中最左侧一根针上放着从大到小的n个圆盘。游戏的目标是把所有圆盘从最左侧一根针上移动到最右侧一根针上，中间一个针作为过渡。游戏规定每次只能移动一个圆盘，并且大盘子不能压在小盘子上面。 3个圆盘的汉诺塔模型 递归 二 抽象与建模 1 A B C 1 2 3 A B C A B C A B C A B C A B C A B C A B C A B C A→C，A→B，C→B，A→C，B→A，B→C，A→C 将n-1个圆盘从A柱经过C柱移动到B柱 将A柱中剩下的一个圆盘移动到C柱 将n-1个圆盘从B柱经过A柱移动到C柱 将n个圆盘从A柱经过B柱移动到C柱子，建立模型： 递归 二 设计算法 2 01 03 05 实现圆盘移动函数 利用建立的模型实现递归调用 重复执行步骤2，直到n=1时，直接移动圆盘，递归结束。 实现将n个圆盘从A柱经过B柱移动到C柱子 move(n,a,b,c) move(n-1,a,c,b) a→c move(n-1,b,a,c) 当n=1时，a→c 将n-1个圆盘从A柱经过C柱移动到B柱 将A柱中剩下的一个圆盘移动到C柱 将n-1个圆盘从B柱经过A柱移动到C柱 将n有关的问题变成n-1的问题，重复该过程，每次n减1，最后当n=1时，直接移动该圆盘。 递归 二 编写程序 3 程序： def move(n, a, b, 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–>C A–>B C–>B A–>C B–>A B–>C A–>C 递归 二 只需知道数据之间相互链接的顺序 探讨与讨论 一 楼梯上有8级台阶，从下开始往上走，每次可以走一步或者两步，自定义函数fg可以计算走完n级台阶有多少种走法。实现对应功能的Python程序如下： def fg(n): if n==1: return 1 elif n==2: return 2 else: return fg(n-1)+fg(n-2) Print(‘走完8级台阶的方法共有’，fg(8)，‘种’) 则走完这8级台阶的走法有（ ） A.34种 B.35种 C.36种 D.37种 A 课堂小练 三 只需知道数据之间相互链接的顺序 探讨与讨论 一 利用迭代和递归思想解决问题时有何区别？算法实现时两者有哪些优缺点? 迭代的思想，是一种由旧值不断推出新值的过程。它包括三个方面： 一、确定迭代变量；二、建立迭代关系式；三、控制迭代过程，使 程序能够停止下来。 递归思想，是一种把数据规模较大、较复杂的问题分解成规模较小的问题， 进而构造出整个问题解的思想方法。递归算法的执行过程分 两 个阶段，其中的关键是如何建立递归关系式与控制程序停止。 一般而言，迭代思想实现的难点在于建立正确的 ，通常要借助循环语句。而递归思想比较难以理解，程序编写简洁，但递归程序的效率 。 递推和回归 迭代公式 相对不高 课堂小练 三 2.递归算法的函数调用时，处理参数和返回地址通常使用的数据结构是( ) A.数组 B.队列 C.栈 D.链表 3.下列有关迭代算法和递归算法的描述，不正确的是( ) A.在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口 B.一般来说，迭代算法效率较低，而递归算法效率较高 C.递归中一定有迭代，但迭代中不一定有递归 D.通常情况下，迭代算法和递归算法可以相互转换 C B 小结 四 小 结 迭代：概念、特性 递归：概念、特性 迭代与 递归 递归是重复调用函数自身实现循环； 迭代是函数内某段代码实现循环。 谢谢观看 第2节 迭代与递归 浙教版（2019） 选修一 $$