资源简介

(共28张PPT)
专题五　迭代、递归算法及应用
思维导图
归纳提炼
一、数据结构与算法的关系
1.算法的设计和选择总是依赖于数据结构,算法设计的同时也伴随着数据结构的设计。
2.算法是编程思想,数据结构则是这些思想的基础。
3.算法效率
算法效率的高低可由算法复杂度来度量。算法复杂度又分为算法的时间复杂度和空间复杂度。
4.时间复杂度
(1)时间复杂度反映了算法执行所需要的时间,常用O()来表示,称之为大O记法。
(2)算法中语句的执行次数作为时间复杂度的度量标准。
(3)语句总的执行次数T(n)是关于问题规模n的函数。所谓问题规模(也称为输入的大小)是指处理问题的大小,即用来衡量输入数据量的整数。
(4)算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级,在很大程度上能很好地反映出算法的优劣。
(5)常见的时间复杂度耗费时间的大小关系为:
O(1)5.空间复杂度
(1)空间复杂度反映了算法执行所需要占用的存储空间。
(2)空间复杂度比较常用的有:O(1)、O(n)、O(log2n)。
6.数据结构对算法效率的影响
选择不同的数据结构,算法的运行效率可能也会不同。
二、迭代算法
1.迭代算法的概念
不断用变量的原值递推出新值的过程称为迭代算法。
2.利用迭代算法解决问题,需要考虑的三个方面
①确定迭代变量。
②建立迭代关系式。
③控制迭代过程。
【归纳与提升】
迭代算法的难点在于寻找和建立正确的迭代公式,一般使用循环结构语句实现。
三、递归算法
1.递归算法的概念
一个函数在其定义中直接或间接调用自身来解决问题的方法称为递归算法。
递归算法的实质是:将规模大的问题分解成规模小的问题,然后从这些小问题的解中方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法。当递归到达某个边界,如问题规模缩减为0或1时,能直接得解。
2.设计递归算法时,需要满足的两个条件:
①确定递归公式。
②确定递归结束条件。
3.递归过程的两个阶段
①递推:把较复杂的问题的求解递推到一些简单问题的求解。
②回归:当获得最简单情况的解后,逐级返回依次得到稍复杂问题的解。
【归纳与提升】
正确区分迭代算法和递归算法
(1)迭代是利用变量的原值递推出变量的一个新值;而递归算法是指一个函数在其定义中直接或间接调用自身来解决问题的一种方法,它通常把一个复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大地减少代码量,降低编程的难度。因此,迭代算法效率较高,而递归算法比较占用空间,程序运行效率较低。
(2)递归是自己调用自己,而迭代就是不断地调用赋值语句;递归中一定有迭代,但是迭代中不一定有递归,大部分情况下递归和迭代可以相互转换。
典型例题
[例1]下列四个常见的时间复杂度之间的大小关系正确的是(　 　)
A.O(log2n)B.O(log2n)C.O(1)D.O(1)C
解析:常见的时间复杂度从低到高为:
O(1)[例2]有如下Python 程序:
def trans(n):
　 ch="0123456789ABCDEF"
　 if n<16:
　　　return ch[n%16]
　else:
　　　digit=trans(n∥16)+ch[n%16]
　　　return digit
n=int(input("请输入一个正整数:"))
print(trans(n))
执行该程序时,输入“268”(不含引号),则输出的结果为(　 　)
A.C01 B.C010 C.10C D.010
C
解析:本题考查递归算法、自定义函数、进制转换等相关知识。本题是以递归的方式实现十进制数转换十六进制数。268D=10CH,故答案为C。
[例3]Python从最初发布到现在的版本不断更新的过程可以看出,一款软件从上市到最终框架的成型,是不断试错、不断根据用户体验反馈快速调整和完善得到的结果。这个例子体现的算法思想是(　 　)
A.枚举 B.解析 C.迭代 D.递归
C
解析:软件在原有的基础上不断更新、完善得到的结果,属于迭代思想,因此答案为C。
[例4](2023·浙江1月选考)定义如下函数:
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
解析:本题主要考查的是递归算法。递归过程可用下图表示:
函数rf共被调用7次,故答案为C。
[例5]对于任意非空字符串s,甲、乙程序段输出结果相同,则乙程序段加框处的正确代码为(　 　)
D
def f(s,t):　　　　　　　　　　　　　　 r=""
if t>=len(s)-2:　　　　　　　　　　n=len(s)
　　　return s[t]　　　　　　　　　　 for i in range(0,n,2):
　　return f(s,t+2)+s[t]　　　　　　　　　 　　　　　　　
print(f(s,0))　　　　　　　　　　　　 print(r)
　　　　甲程序段　　　　　　　　　　　　　　乙程序段
A.r = s[n-i]+r B.r = r+s[n-i-1]
C.r = r+s[i] D.r = s[i]+r
解析:本题主要考查递归函数和字符串处理知识。根据甲程序段代码可知,该程序段是典型的利用自定义函数实现的递归算法,假设非空s="ABCDEF",其调用过程如下:
f(s,0)→f(s,2)+s[0]→f(s,4)+s[2]+s[0]→s[4]+s[2]+s[0]→"ECA",其本质是将 s 中的偶数位置的字符取出,然后逆序连接输出。观察乙程序段和选项,能实现上述同样功能的只有选项D,因此答案为D。
[例6]角谷猜想。对于任意一个正整数n,若n为偶数,则将其除以2,若n为奇数,则将其乘以3,然后加1。经过有限次运算后,就能将n变为1。编写程序,实现如下功能:输入一个正整数n,输出n变成1的全过程,并统计输出运算的次数。程序运行界面如下图所示。
请输入一个整数n:10
运算过程为:
10- - >　5- - >　16- - >　8- - >　4- - >2　- - >1
运算次数为:6
实现上述功能的程序如下,请回答下列问题:
(1)根据角谷猜想,输入n为12,则实现12变成1的过程共需进行的运算次数为　　　　。
解析:(1)12变成1的全过程为:12- - >6- - >3- - >10- - >5- - >16- - >
8- - >4- - >2- - >1,共9次,因此答案为9。
9
(2)请在程序划线处填入合适的代码。
def jgguess(x):
global cnt　#声明变量cnt为全局变量
if x==1:
return　　　#return表示返回函数调用处,无返回值
　elif 　　　　①　　　　:
print('→',x∥2,end='')
cnt+=1
jgguess(x∥2)
else:
print('-->',3*x+1,end='')
cnt+=1
　　　　②　　　　
n=int(input('请输入一个整数n:'))
print('\n运算过程为:')
cnt=0
print(n,end="")
jgguess(n)
print('\n运算次数为:'+　　　　③　　　　)
程序划线①处应填入的代码为:　　　　　　　　　　　　　　　;
程序划线②处应填入的代码为:　　　　　　　　　　　　　　　;
程序划线③处应填入的代码为:　　　　　　　　　　　　　　　。
x%2==0　
jgguess(3*x+1)　
str(cnt)
解析:(2)本题主要考查的是递归算法。根据代码jgguess(x∥2),可知①处表示整数x为偶数时的情况,因此代码为x%2==0;程序②处表示整数x为奇数时,将其乘以3加1处理,然后再递归调用,因此②处代码为jgguess(3*x+1);使用全局变量cnt统计运算次数,最后输出时,因为使用“+”,所以需将cnt转换为字符串,故③处代码为str(cnt)。
[例7]分解质因数:把一个大于1的正整数分解成若干个质数相乘的形式,比如100=2*2*5*5。一个数的质因数不容易直接看出来,且手工分解质因数效率低。下面分别用迭代和递归两种方法实现质因数分解。代码如下,请在程序划线处填入合适的代码。
(1)迭代法 (2)递归法
def f(x) : lst=[] k=2 while x>=k: if　　　①　　: 　　　　　　lst.append(k) 　　　　　　x∥=k else: 　　　②　　 　　return lst n=int(input("请输入n的值:")) print(n,"的质因数为:",f(n)) def f(n,lst=[]):
　　if　　　③　　　:
　　　　return lst
　　for i in range(2,n+1) :
　　　　if n%i==0:
　　　 　 lst.append(i)
　　　 　 return　　　④　　
n=int(input("请输入n的值:"))
print(n,"的质因数为:",f(n))
程序划线①处应填入的代码为:　　　　　　　　;
程序划线②处应填入的代码为:　　　　　　　　;
程序划线③处应填入的代码为:　　　　　　　　;
程序划线④处应填入的代码为:　　　　　　　　。
x%k==0　　
解析:本题主要考查迭代与递归的应用。(1)采用迭代算法实现,划线①处表示k是x的质因数的情况,因此①处代码为x%k==0,划线②处表示k不是x的质因数的情况,则k加1后再尝试,因此②处代码为k+=1。(2)采用递归算法实现,划线③处为递归出口,当n<=1时返回lst,因此③处代码为n<=1,划线④处为下一层递归,因此代码为f(n//i,lst) 。
k+=1　　
n<=1　
f(n//i,lst)
感谢观看

展开更多......

收起↑