第15课 迭代与递归-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固PPT课件（浙教版2019）

第五章│数据结构与算法 ——5.1　数据结构与算法效率　5.2　迭代与递归，教材P126～138 第15课　迭代与递归 新课程目标 1.理解数据结构与算法的关系，理解不同数据结构对算法效率的影响。　2.理解迭代算法的思想，应用迭代算法处理实际的问题。　3.理解递归算法的思想，应用递归算法处理实际的问题。 目录 CONTENTS 教材整体感悟 知本与探源 01 02 命题整体感知 尝试与研析 01 教材整体感悟 知本与探源 教材整体感悟 知本与探源 1． 数据结构与算法效率 算法的设计和选择总是依赖于数据结构，算法设计的同时也伴随数据结构的设计。算法是编程思想，数据结构则是算法思维的基础。 (1)算法效率的高低可由算法复杂度来度量。算法复杂度分为算法的 ______________和_______________。 (2)将算法中语句的执行次数作为时间复杂度的度量标准。T(n)表示语句总的执行次数，是关于问题规模n的函数。时间复杂度反映了算法执行所需要的时间，常用符号“O”来表示。 　时间复杂度　 　空间复杂度　 教材整体感悟 知本与探源 (3)算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映出算法的优劣。 (4)常见的时间复杂度耗费时间的大小关系为：O(1)<____________< _________<_________<O(n3)<O(2n)<O(n！)。 常见函数的增长率如图所示： 　O(log2n)　 　O(n)　 　O(n2)　 教材整体感悟 知本与探源 (5)选择不同的数据结构，算法的运行效率可能也会不同。 教材整体感悟 知本与探源 2．迭代 (1)迭代算法思想：让计算机重复执行一组指令(或一些步骤)，这组指令(或这些步骤)每执行一次时，都会将变量从原值递推出一个新值。简单地讲，迭代是一种不断用变量的_________递推出________的过程。 (2)利用迭代算法处理问题，需要考虑以下三个方面： ①确定迭代_________；②建立迭代__________；③控制迭代_________。 (3)迭代法也称辗转法，难点在于寻找和建立正确的迭代公式，一般使用循环结构语句实现，其基本格式描述： 　旧值　 　新值　 　变量　 　关系式　 　过程　 教材整体感悟 知本与探源 迭代变量赋初值 while 迭代终止条件： 根据迭代表达式，由旧值计算出新值 新值取代旧值，为下一次迭代做准备 教材整体感悟 知本与探源 3．递归 (1)递归算法思想：递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法，在函数的定义中调用函数自身的方法，这里的调用分两种：直接调用与间接调用。 (2)为求解规模为N 的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。当递归到达某个边界，能直接得解。 (3)递归算法的执行过程分为_________ (“有去”)和_______ (“有回”)两个 　递推　 　回归　 教材整体感悟 知本与探源 阶段。 “有去”指递归问题必须可以分解为若干个规模较小且与原问题相同的子问题，这些子问题可以用相同的解题思路来解决；“有回”指这些问题的演化过程是一个从大到小、由近及远的过程，并且存在一个明确的终点(临界点)，一旦到达这个临界点，就不用再往更小、更远的方向走下去。最后，从这个临界点开始，原路返回到原点，解决原问题。 (4)利用递归算法解决问题的关键步骤： ①抽象建立递归模型，确定递归公式；②确定临界条件(即递归结束条件)。 教材整体感悟 知本与探源 本课核心点 ● 重难点 1．迭代算法举例：计算斐波那契数列是指从第3项开始，每一项的值为前两项之和，该数列为：1，1，2，3，5，8，13，21，… (1)Python代码如下： n＝int(input(”请输入整数：　”)) f1＝f2＝1 for i in range(2，n)： 教材整体感悟 知本与探源 f＝f1＋f2 f1＝f2 f2＝f print(”第”＋str(n)＋”项的值为：　”＋str(f)) (2)运行结果： 教材整体感悟 知本与探源 2． 递归执行过程的理解： 计算机在执行递归程序时，是通过栈的调用来实现的。递归程序是将复杂问题分解为一系列简单的问题，从要解的问题起，逐步分解，并将每步分解得到的问题放入“栈”中，运用栈的“后进先出”的性质，这样栈顶是最后分解得到的最简单的问题，解决了这个问题后，次简单的问题可以得到答案，以此类推。分解问题可以看作是入栈的过程，而解决问题则是出栈的过程。 (1)计算n！的递归方式，Python代码如下： 教材整体感悟 知本与探源 def F(n)： if n＝＝1： return n else： return n*F(n－1) n＝int(input(”请输入整数：　”)) ans＝F(n) 教材整体感悟 知本与探源 print(ans) (2)运行结果：   (3)执行过程分析：   教材整体感悟 知本与探源 3．汉诺塔的递归实现： 从左到右有A、B、C三根柱子，其中A柱子上面放着从大到小的n个圆盘，现在按照一定规则(每次只能移动一个圆盘，并且大盘子不能压在小盘子上面)，将A柱子上的圆盘移动到C柱子上。 (1)Python代码如下： 教材整体感悟 知本与探源 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”) (2)运行结果： 02 命题整体感知 尝试与研析 命题整体感知 尝试与研析 例1下列关于算法效率的说法中，正确的是(　　) A．算法效率指的是算法的时间复杂度 B．通常，随着问题规模n 的增大，函数值增长较慢的算法较优 C．时间复杂度常用符号T 来表示，如2*n*(n－1)，其时间复杂度可以表示为T(n2) D．常见时间复杂度耗费时间的大小关系为：常数阶<对数阶<指数阶<平方阶 B 命题整体感知 尝试与研析 【解析】 选项A，算法效率和算法复杂的相关，包括时间复杂度和空间复杂度，选项错误；选项C，时间复杂度的常用符合是大写的O，选项错误；选项D，正确的关系是：常数阶<对数阶<平方阶<指数阶，选项错误。 命题整体感知 尝试与研析 变式1有如下Python程序段： #生成6个随机整数，存入列表元素a[0]到a[5]中，代码略 b＝[0]*6 for i in range(1，6)： for j in range(i)： if a[i]>a[j]： b[i]＋＝1 命题整体感知 尝试与研析 print(sum(b)) 则该算法的时间复杂度为(　　) A．O(1)　　　　　 B．O(log2n)　　　　　 C．O(n)　　　　　 D．O(n2) 【解析】 双重循环，时间复杂度为O(n2)，选项D正确。 D 命题整体感知 尝试与研析 变式2国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天(第二天和第三天)里，每天收到两枚金币；之后三天(第四、五、六天)里，每天收到三枚金币……这种工资发放模式会一直这样延续下去：当连续N 天每天收到N 枚金币后，骑士会在之后的连续N＋1 天里，每天收到N＋1枚金币(N 为任意正整数)。现在骑士想知道，工作一定的天数后，他能获得的金币数量。小明写了3个Python 自定义函数，完成了骑士的愿望。从时间复杂度的角度来分析，这三个函数的程序效率从高到低依次是(　　) C 命题整体感知 尝试与研析 def f1(day)： golds，i，s＝1，0，0 for j in range(day)： s＋＝golds i＝(i＋1)%golds if i＝＝0： golds＋＝1 命题整体感知 尝试与研析 return s def f2(day)： golds，s＝1，0 while day>＝golds： s＋＝golds*golds day－＝golds golds＋＝1 命题整体感知 尝试与研析 s＋＝golds*day return s def f3(day)： k＝int((2*day)**0.5＋1e－6) if k*(k＋1)>2*day： k－＝1 s＝k*(k＋1)*(2*k＋1) // 6＋(day－k*(k＋1)//2)*(k＋1) 命题整体感知 尝试与研析 return s A．f1>f2>f3　　　　 B．f2>f3>f1　　　　 C．f3>f2>f1　　　　 D．三者相同 【解析】 本题可以快速排除，f3 没有用到循环，故其时间复杂度为O(1)，f1 和f2 都采用了循环，故f3 算法效率最高，选项C正确。 对于f1，采用的是标准的for 循环，循环次数与day 大小相同。 对于f2，采用的是while 循环，观察代码可知，循环条件为day>＝golds， 命题整体感知 尝试与研析 gold 的初值为0，但是每次循环golds 会加1，通过不断地循环，也就是说，循环次数肯定小于day 次，故f2 算法效率大于f1，选项C正确。 命题整体感知 尝试与研析 例2有如下Python 程序段： a＝[13，7，10，21，16，9，7，25] k，p＝a[0]，0 for i in range(1，len(a))： if a[i]<＝k： p＝i k＝a[p] 命题整体感知 尝试与研析 print(p，k) 执行该程序段后，输出的结果是(　　) A． 7 6 B．6 7 C．1 7 D．7 1 【解析】 本题程序是标准的查找列表中最小值的代码。其中p 是最小值的下标，k 是最小值。再根据条件：a[i]<＝k。最小值的下标是6，值是7。选项B正确。 B 命题整体感知 尝试与研析 变式1[2023·衢州一中检测]计算表达式“1/2＋2/3＋3/5＋5/8＋…”的前30 项的和。实现此功能的Python 程序段如下： a，b＝1，2 s＝0 for i in range(30)： print(s) 命题整体感知 尝试与研析 上述程序段中加框处的代码由以下三部分组成： ①b＝b＋a　②s＝s＋a/b　③a＝b－a 下列选项中，代码顺序正确的是(　　) A．①③② B．③①② C．②①③ D．②③① 【解析】 迭代法是一种不断用变量的旧值递推新值的过程。变量a、b 的初值分别为1 和2，观察该表达式，第1 项应为a/b，第2 项应为 C 命题整体感知 尝试与研析 b/(a＋b)，所以第1 步应执行s＝s＋a/b；接下来考虑更新a、b 值，即实现a＝b，b＝a＋b，先执行b＝b＋a，再执行a＝b－a 相当于a＝a＋b－a＝b，故语句执行次序为②①③。 命题整体感知 尝试与研析 变式2现有近似求ex 的公式如下： 实现上述功能的Python 程序段如下： x＝int(input(”请输入x＝”)) n＝int(input(”请输入n＝”)) e＝1；p＝1；i＝0 while i<n： 命题整体感知 尝试与研析 print(e) 上述程序段中加框处的代码由以下三部分组成： ①i＝i＋1　②p＝p*i　③e＋＝x**i/p 下列选项中，代码顺序正确的是(　　) A．①③② B．①②③ C．③①② D．③②① B 命题整体感知 尝试与研析 print(e) 上述程序段中加框处的代码由以下三部分组成： ①i＝i＋1　②p＝p*i　③e＋＝x**i/p 下列选项中，代码顺序正确的是(　　) A．①③② B．①②③ C．③①② D．③②① 【解析】 读程序可知，e 的初值为1，则第一次累加的项为x/1！，即 B 命题整体感知 尝试与研析 x1/1！，可知i＝1，p＝1。则在e 累加之前，i 需加1，即①在③之前。第二次累加的项为x2/2！，可知i＝2，p＝2。则在e 累加之前，p 需乘以i，即②在③之前。代码的正确顺序为①②③。 命题整体感知 尝试与研析 例3[2023·浙江1月选考]有如下Python程序段： def rf(n)： if n<3： return n return rf(n－1)＋rf(n－3) 执行语句v＝rf(5)，函数rf()被调用的次数是(　　) A．11 B．5 C．7 D．15 C 命题整体感知 尝试与研析 【解析】 观察自定义函数可知，当参数n 大于等于3 时，继续两次递归调用(参数为n－1 和n－3)，反之结束递归直接返回n的值。题干执行的语句中参数值为5，数值较小，故可以直接模拟并分析计算过程：①rf(5)＝rf(4)＋rf(2)，调用函数rf 两次；②rf(4)＝rf(3)＋rf(1)，调用函数rf 两次；③rf(3)＝rf(2)＋rf(0)，调用函数rf 两次；再加上v＝rf(5)本身调用的一次，得到答案7。 命题整体感知 尝试与研析 变式1有如下Python 程序段： def putx(n)： if n<1： return if n%2＝＝1： print(”*”*n) else： 命题整体感知 尝试与研析 print(”#”*n) putx(n－1) n＝int(input()) putx(n) 若输入的内容为“5”(不包括引号)，执行该程序段后，输出的结果是(　　) A．　　　　B．　　　 　C．　　 　　D． A 命题整体感知 尝试与研析 【解析】 该程序为函数递归调用，第一次调用函数putx，n＝5，执行print(”*”*n)，所以先输出5 个*，再执行putx(4)；当n＝4 时，执行print(”#”*n)，输出4 个#，再执行putx(3)；以此类推，直到n＝0 时退出自定义函数，递归结束。 命题整体感知 尝试与研析 变式2斐波那契数列： 1，1，2，3，5，8，13，…，现用递归算法求解第n 项，对应的Python 程序段如下： def fib(n)： if (n>2)： 　return fib(n－1)＋fib(n－2) return 1 n＝int(input('输入一个整数')) 命题整体感知 尝试与研析 print(fib(n)) 执行该程序段时，输入一个整数5，则函数fib()被第3 次调用时的返回值为(　　) A．2 B．3 C．5 D．8 【解析】 输入一个整数5，fib(5)为第一次调用函数，函数fib()执行语句“return fib(4)＋fib(3)”，fib(3)为第3 次调用函数fib()，fib(3)＝fib(2)＋fib(1)＝1＋1＝2，第3 次调用时返回值为2。 A 命题整体感知 尝试与研析 变式3将十进制正整数转化为二进制数，对应的Python 程序段如下： def toStr(n，base)： s＝”01” if n<base： return s[n] else： return 　　　　　　 命题整体感知 尝试与研析 n＝int(input('请输入正整数：　')) result＝toStr(n，2) print(result) 则横线处的代码应为(　　) A．toStr(n//base，base)＋s[n%base] B．s[n%base]＋toStr(n//base，base) C．toStr(n%base，base)＋s[n//base] D．s[n//base]＋toStr(n%base，base) A 命题整体感知 尝试与研析 【解析】 利用递归的思想来处理十进制与其他数制的转换问题，函数功能是将每一次得到的余数作为结果逆序保存，整数部分再次利用函数进行转化，直到最后得到的整数部分小于要转换的进制数，转化过程结束。由程序可知，当n<base 时，即n 对应的二进制数为一位二进制数时，递归结束。将十进制正整数n 转化为二进制数的问题可以转化为n 抹掉二进制末位后的结果转化为二进制数字符串加上n 二进制末位对应的字符，选项A正确。 命题整体感知 尝试与研析 例4[2023·学军中学检测]小明学习了算法后，写了以下两段Python代码来求斐波那契数列的第6项。 算法一 算法二 a＝1 b＝1 for i in range(2，6)： c＝a＋b a＝b b＝c print(c) def f(n)： if n＝＝1 or n＝＝2： return 1 else： return f(n－1)＋f(n－2) print(f(6)) 命题整体感知 尝试与研析 下列说法正确的是(　　) A．两种算法的时间复杂度均为O(1) B．算法一是迭代算法，算法二是递归算法，相比之下，算法二的时间效率更高 C．执行算法二代码，f(4)共被调用了2 次 D．执行算法一代码，当i＝4 这一遍循环刚结束时，a的值等于5 C 命题整体感知 尝试与研析 【解析】 选项A， 算法一的时间复杂度为O(1)， 算法二的时间复杂度为O(n)，选项错误；选顶B， 算法一是迭代算法， 算法二是递归算法，相比而言，递归算法有递推和回归两个阶段， 因此算法一的时间效率更高，选项错误；选项C，根据递归函数可知，在计算f(6)的过程中，f(4)会被调用两次，分别作为f(n－1)和f(n－2)，选项正确；选项D，当i＝4这一遍循环结束时，a的值等于3，选项错误。 命题整体感知 尝试与研析 变式1有如下Python程序段： def fibo(n)： f1＝1；f2＝1 for i in range(3，n＋1)： f3＝f1＋f2　　　　　#① f1＝f2　　　　　　　#② f2＝f3　　　　　　　#③ 命题整体感知 尝试与研析 return f3 n＝int(input(”求第n项：　”)) print(fibo(n)) 下列说法正确的是(　　) A．该程序主要应用了递归算法 B．程序执行时若输入“5”，则输出“8” C．假如用大O记法体现该算法的时间复杂度，则记作O(n) D．将语句①交换到语句②后，不会影响程序运行结果 C 命题整体感知 尝试与研析 【解析】 选项A，自定义函数fibo(n)的作用是求斐波那契数列的第n项，是通过迭代算法实现的， 选项错误；选项B，fibo(5)执行过程中，依次计算出的前5项分别为： 1，1，2，3，5，fibo(5)返回结果为“5”，选项错误；选项C，自定义函数中，只有一层for循环，循环执行的次数为O(3*(n－2))，忽略常数项的影响，其时间复杂度为O(n)，选项正确；选项D，若将①交换到②后面，f3每次计算的结果为2*f1， 不符合斐波那契数列的规律， 选项错误。 命题整体感知 尝试与研析 例5用Python编写程序求 。其中e是自然常数，可以在math模块中调用，n！为阶乘，n！＝1×2×3×4×…×(n－1)×n。程序运行时，输入n的值，输出结果s。 (1)实现上述功能的部分程序代码如下，请在横线处填入合适的代码。 import math #导入math模块 def f(n)： sum＝0 命题整体感知 尝试与研析 t＝①_______　 for i in range(②________________)： t＝t*③________________　 return sum n＝int(input(”输入n的值：　”)) s＝④____________ 　1 　1，n＋1　 　math.e/i 　f(n)　 命题整体感知 尝试与研析 (2)以下代码与程序中加框处的代码功能相同的有______ (多选，填字母)。 A．sum＝sum＋t B．sum＋＝t C．sum＝t D．sum＝int(sum＋t) 【解析】 (1)利用函数调用和迭代算法求解表达式的值，sum初始值为0，需要加上第一项(e/1！)，t的初始值为1；range是左闭右开，答案为1，n＋1；第3空为迭代思想，其中e使用math.e；第4空为函数调用。 (2)sum累加结果。 　AB　 命题整体感知 尝试与研析 |随|堂|检|测| 1． 有如下Python 程序段： x＝25；y＝20 if x>y： y＋＝20 if y>50： y＝y**2 命题整体感知 尝试与研析 else： y＝y**2 y＝x＋y print(y) 执行该程序段后，输出的结果和时间复杂度分别为(　　) A．1600　O(1) B．425　O(n) C．400　O(n) D．40　O(1) D 命题整体感知 尝试与研析 【解析】 没有循环，时间复杂度为O(1)，选项B和选项C排除；x>y成立，则y＝40，y>50不成立，y的值不再变化，选项D正确。 命题整体感知 尝试与研析 2．有如下Python 程序段： n＝int(input()) s＝0；i＝1 while i*i<＝n： if i＝＝n//i： s＋＝1 elif n%i＝＝0： 命题整体感知 尝试与研析 s＋＝2 i＋＝1 print(s) 若输入“16”，执行该程序段后，则输出的结果是(　　) A．3 B．4 C．5 D．6 C 命题整体感知 尝试与研析 【解析】 执行过程为： 选项C正确。 i 1 2 3 4 5 s 2 4 4 5 结束 命题整体感知 尝试与研析 3．有如下Python程序： def fx(x)： if x >2： return fx(x－1)*fx(x－2) elif x＝＝1： return 1 elif x＝＝2： 命题整体感知 尝试与研析 return 2 y＝int(input(”请输入y的值： ”)) print(fx(y)) 执行该程序时，若输入y的值为6，则输出的结果是(　　) A．8 B．16 C．32 D．64 C 命题整体感知 尝试与研析 【解析】 执行过程为： 　　　　　　　　　　　f(6) 　　　　　f(5)　　　　　＋　　　　　　f(4) 　　　f(4)　　　＋　　f(3)　　　　　f(3)　　＋　　f(2) 　f(3)　＋　f(2) 　　f(2)＋f(1)　　f(2)＋f(1)　　　　2 f(2)＋f(1) 　　2　 　　2　　 1　　　　2　　 1 2　　 1 选项C正确。 命题整体感知 尝试与研析 4．斐波那契数列是指这样一个数列：1，1，2，3，5，8，13，21，34，…，这个数列从第3项开始，每一项的值等于前两项之和。下列Python程序段的功能是求斐波那契数列的第n项的值。 n＝int(input()) t1＝t2＝1 for i in range(3，n＋1)： # 命题整体感知 尝试与研析 print(”斐波那契数列第”＋str(n)＋”项的值为：　”＋str(t)) 上述程序段中加框处的代码由以下三部分组成： ①t1＝t2　②t2＝t　③t＝t1＋t2 下列选项中，代码顺序正确的是(　　) A．①②③ B．①③② C．③②① D．③①② 【解析】 先求第3项：t＝t1＋t2；再将t1的值更新为t2；将t2的值更新为t，选项D正确。 D 命题整体感知 尝试与研析 5． [2023·绍兴一中检测]有两个自定义Python函数如下： 下列说法不正确的是(　　) A．p2(2，3)的返回值为8 B．函数p2()的时间复杂度是O(n) C．函数p1()和函数p2()均采用了递归算法 D．计算p1(2，3)，函数p1()的调用次数为4 D 命题整体感知 尝试与研析 【解析】 二段程序实现的都是计算ab。选项A，代码正确，可以正确返回2的3次方8；选项B，根据递推的代码：return a*p2(a，b－1)，a的n次方，函数调用n次就能得到结果，函数内部都是顺序结构，所以时间复杂度O(n)，选项正确；选项C，二段代码都有函数的自我调用，是递归算法，选项正确；选项D，分析函数的调用次数： p1(2，3)－>2*p1(2，2) p1(2，2)－>p1(2，1)*p1(2，1) p1(2，1)－>p1(2，0) 命题整体感知 尝试与研析 根据上面分析，p1(2，3) 1次、p1(2，2) 1次、p1(2，1) 2次，p1(2，0)2次，共6次，选项D描述的4次不正确。 感谢聆听，再见！ ex＝1＋＋＋＋…＋，－∞<x<∞ s＝e＋＋＋…＋ $$