5.2 迭代与递归 　课件-2022—2023学年浙教版（2019）高中信息技术选修1

知识回顾 算法效率的高低由算法复杂度来度量，时间复杂度反映算法执行所需的时间，空间复杂度反映算法执行所占用的存储空间。 算法运行需要时间，一般将算法中语句的执行次数作为时间复杂度的度量标准。 时间复杂度大O阶推导： 用常数1取代运行时间中的所有加法常数； 在修改后的运行次数函数中，只保留最高项； 若最高阶项存在且不是1，则去除此项的系数。 如何量化算法的时间复杂度？ 时间复杂度O(n2) 1 知识回顾 n = int(input()) s = (1+n)*n/2 print(s) n = int(input()) s = 0 for i in range(1,n+1): s += i print(n) n = int(input()) s=0 x=0 for i in range(1,n+1): for j in range(1,n+1): x += 1 s += x print(s) 请使用大O阶方法计算下列三种算法的时间复杂度。 O(1) O(n) O(n2) 算法的时间复杂度反映了程序的执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映算法的优劣。 2 CHZX 5.2 迭代与递归 浙江省高中信息技术 选择性必修一 《数据与数据结构》 昌化中学 应彤鑫 3 迭代算法 算法思想 程序实现 01 4 迭代算法 Diedai suanfa 某饲养场引进了1对刚出生的新品种兔子，第2个月进入成熟期，第3个月开始生育兔子，新生的兔子成熟后的下月又会新生1对兔子……若所有的兔子都不会死去，则到第12个月时，该饲养场共有多少对兔子？ 兔子繁殖过程： 1月：兔①新生，共1对 2月：兔①成熟，共1对 3月：兔①生兔②，共2对 4月：兔①生兔③，兔②成熟，共3对 5月：兔①生兔④，兔②生⑤，兔③成熟，共5对 6月：兔①生兔⑥，兔②生兔⑦，兔③生兔⑧，兔④⑤成熟，共8对 ...... 5 迭代算法 Diedai suanfa 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月开始，当月兔子数=上月兔子数+当月新生兔子数 规律：第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}对兔子“) 迭代算法：旧值不断推出新值的过程 时间复杂度O(n) 6 迭代算法 Diedai suanfa 迭代算法：利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，这组指令每执行一次时，都会将变量从原值递推出一个新值，即由旧值不断推出新值的过程。 f1 = 1 f2 = 1 i = 3 while i <= 12: f = f1 + f2 f1 = f2 f2 = f i += 1 print(f"第{i-1}月共有{f}对兔子“) 迭代算法处理问题： 确定迭代变量：由旧值递推出新值的变量； 建立迭代关系式：从变量的前值推出下个值的公式； 控制迭代条件：经过若干次重复执行后能够结束。 7 迭代算法 Diedai suanfa 欧几里得算法又称辗转相除法，用于计算两个整数m、n的最大公约数。基于定理：gcd(m,n)=gcd(n,m%n),即整数m、n的最大公约数等于n和m除以n的余数的最大公约数，当余数为0时取当前算式的除数即为最大公约数。现任意输入两个正整数，请编程实现计算最大公约数的功能。 m = int(input("请输入正整数m：")) n = int(input("请输入正整数n：")) while n != 0: temp = n n = m % n m = temp print("最大公约数是：",m) 迭代算法处理问题： 确定迭代变量： 建立迭代关系式： 控制迭代条件： 确定迭代变量：m、n 建立迭代关系式：n→m，m%n→n 控制迭代条件：余数为0 8 迭代算法 Diedai suanfa 0 e+1/jc 0 e+1/jc 9 递归算法 算法思想 程序实现 02 10 递归算法 Digui suanfa 俄罗斯一票否决了“乌克兰提出的取消俄罗斯一票否决权”的提案 一网民因造谣“自己因为造谣被公安拘留15天”而被拘留15天 美国谴责“中国谴责美国干涉中国内政”是中国干涉美国内政 禁止套娃→禁止禁止套娃→