5.2迭代与递归课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第五章浙教版（2019）

5.2 迭代与递归 《数据与数据结构》 一、温故知新 斐波那契数列螺旋线也称为“黄金螺旋”，是根据斐波那契数列画出来的螺旋曲线，自然界中存在许多斐波那契数列螺旋线的图案。 一、温故知新 斐波那契数列第1项和第2项都是1，从第三项开始，每一项等于前两项之和，即： 1、1、2、3、5、8、13、21、34、55、89、144、233..... 以下是计算斐波那契数列第n项的值的递推函数。 def fib(n): f=[1]*n for i in range(2,n): f[i]=f[i-1]+f[i-2] return f[n-1] n=8 print(fib(n)) (1)方框内算法的时间复杂度是：_____。 O(n) f=[1,1,1,1,1,1,1,1] f[2]=f[1]+f[0]=1+1=2 f[3]=f[2]+f[1]=2+1=3 f[4]=f[3]+f[2]=3+2=5 f[5]=f[4]+f[3]=5+3=8 f[6]=f[5]+f[4]=8+5=13 f[7]=f[6]+f[5]=13+8=21 n=8 f=[1,1,2,3,5,8,13,21] (2)该算法的缺点是什么？如何优化？ 【答案】f=[1]*n浪费了大量的存储空间。 1次 6次 6次 1次 1次 1次 T(n)=16=2*n 一、温故知新 def fib(n): f=[1]*n for i in range(2,n): f[i]=f[i-1]+f[i-2] return f[n-1] n=8 print(fib(n)) (1)右边方框算法的时间复杂度是：_____。 (2)与左边的算法相比，上面的算法优势在于____________更低。 【结论】右边的算法用到了__________。 O(n) def fib(n): a=b=c=1 for i in range(3,n+1): c=a+b a,b=b,c return c n=8 print(fib(n)) 只使用3个变量，生成斐波那契数列第n项的值： 空间复杂度 迭代思想 一、迭代的基本思想 是一种不断用变量的旧值推出新值的过程。它是解决问题的一种基本方法，通过让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，这次迭代的结果都会用来作为下一次的初始值。 常见的算法： 辗转相除法&辗转相减法求最大公约数 数列求和 斐波那契数列 欧几里得算法 进制转换 求1+2+3+4+······+10的和 s = 0 for i in range(1,11): s = s + i print(s) s = 0 + 1 s = 1 + 2 s = 3 + 3 s = 6 + 4 s = 10 + 5 s = 15 + 6 s = 21 + 7 s = 28 + 8 s = 36 + 9 s = 45 + 10 ①迭代变量：s 累加器 旧值推出新值 每一次迭代得到的结果是下一次迭代的初始值 ②迭代关系式：s = s + i ③迭代过程：for i in range(1,11) 执行若干次重复操作后，要设定迭代结束条件 一、迭代--数列求和 6 【例1】计算表达式s=1-1/3+1/5-1/7+...+1/21的值。 s,f=0,1 for i in range(1,22,2): _______ f = -f print(s) s=s+f/i 一、迭代应用--数列求和 7 【例2】将二进制数转化成十进制数（累乘法） b=input(“请输入一个二进制数：”) d=0 for c in b: ________ print(f“二进制数{b}对应的十进制数为{d}”) d=d*2+c 这么写有bug 一、迭代应用--进制转换 b=input(“请输入一个二进制数：”)（累加法） d=0 for i in range(len(b)):#此处有修改 _________________________ print(f“二进制数{b}对应的十进制数为{d}”) d=d+b[i]*2**(len(b)-i-1) 这么写有bug d=d*2+int(c) d=d+int(b[i])*2**(len(b)-i-1) 8 二、递归的基本思想 基本思想：大事化小，小事化了的原则。通过重复将问题分解为同类的子问题而解决问题的方法，它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 二、递归的基本思想 【例】计算n!的值，思考当主函数 执行fun(5)时，递归的调用过程。 def fun(n): if n==1: return 1 else: return n*fun(n-1) print(fun(5))#主程序 递归出口(边界) 递归体 fun(5)=5*fun(4) fun(4)=4*fun(3) fun(3)=3*fun(2) fun(2)=2*fun(1) fun(1)=1 递推 =2*1=2 =3*2=6 =4*6=24 =5*24=120 回归 递归 第1次调用 第2次调用 第3次调用 第4次调用 第5次调用 fun(n)= 1 （n=0） n*fun(n-1) （n>0） 阶乘是所有小于等于该数的正整数的积 斐波那契数列 以新代旧 #迭代实现： def fib(n): a=b=c=1 for i in range(3,n+1): c=a+b a,b=b,c return c n=7#主程序 print(fib(n)) a=1 b=1 c = 1+ 1 c = 1 + 2 c = 2 + 3 c = 3 + 5 c = 5 + 8 斐波那契数列 #递归实现： def fib(n): if n == 0 or n == 1: return 1 else: fib(n-1)+fib(n-2) n=7#主程序 print(fib(n)) 自己调用自己 fun(7)=fun(6)+fun(5) fun(6)=fun(5)+fun(4) fun(5)=fun(4)+fun(3) fun(4)=fun(3)+fun(2) fun(3)=fun(2)+fun(1) 递推 =3+2=5 =5+3=8 =8+5=13 =13+8=21 回归 第1次调用 第2次调用 第3次调用 第4次调用 第5次调用 fun(2)=fun(1)+fun(0) = 1 + 1 = 2 第6次调用 =2+1=3 #迭代实现： n = int(input(“输入十进制数：”)) result = “” while n != 0: _________________ n = n // 2 print(result) #递归实现： def DtoB(n): if n//2 == 0: _________ else: ____________________ n = int(input("输入十进制数：")) print(DtoB(n)) result = str(n%2) + result return str(DtoB(n//2)) + str(n%2) return n 思考：两段代码的功能是什么？ 假设n=10 DtoB(10)=str(DtoB(5)) + str(0) DtoB(5)=str(DtoB(2)) + str(1) DtoB(2)=str(DtoB(1)) + str(0) DtoB(1)= 1 =”1”+”0”=”10” =”10”+”1”=”101” =”101”+”0”=”1010” 课堂小结 递归的必要条件 递归的适用情况 递归的定义 函数的递归调用是指一个函数在它的函数体内，直接或间接地调用它自身，称为递归调用。 确定递归体 寻找递归结束条件 问题在规模小时能够直接得出答案 可以通过同一套规则转化为比该问题更为简单的子问题。 Academic report presentation $$