资源简介

(共15张PPT)
二、 迭代算法及其应用
第五章　数据结构与算法
知识过关
迭代算法的概念和特点
(1)迭代是重复反馈过程的活动,其目的通常是使结果符合目标需求。
(2)让计算机重复执行一组指令(或步骤),这组指令(或步骤)每执行一次时,都会让变量从原值递推出一个新值。
(3)利用迭代算法处理问题,需要考虑以下三个方面:
①确定迭代变量:一个直接或间接地不断由旧值递推出新值的变量。
②建立迭代关系式:将变量从前一个值推出其下一个值的公式(或关系)。
③控制迭代过程:设定迭代结束的条件。
(4)如下面利用欧几里得算法求最大公约数的Python程序,可以看出m和n是迭代变量,迭代关系是n→m和m%n→n,由旧值推出新值,然后循环执行,直到余数为0,结束迭代。
def gcd(m, n):
　　while n != 0:
　　　　temp = n
　　　　n = m % n
　　　　m = temp
　　return m
典例精选
【例1】 阶乘n!=1×2×3×…×n,利用迭代思想可以实现阶乘功能,实现上述功能的Python代码如下。请在画线处填入适当的代码。
def factorial(k):
　　s=1
　　for i in range(1,k+1):
　　　　s=s*i
　　return ①__________
n = int(input())
print("阶乘的结果是:",②_______________)
【解析】 本题考查迭代算法知识。①自定义函数中,k为形式参数,由代码可知,阶乘的结果记录在变量s中,因此自定义函数的返回值是s。②此处需要将实际参数n的值代入函数factorial(),从而经过迭代运算得到实际的函数值。
s
factorial(n)
输入一个n,用迭代法编程输出第n项f(n)的值。请在画线处填入合适的代码。
　　def f(n):
　　　　i = 2; a = 0; ①__________
　　　　while i <= n:
　　　　　　c = ②__________
　　　　　　a = b
　　　　　　b = c
　　　　　　i += 1
　　　　　　③________________________
　　n = int(input())
　　print(f(n))
b=1
a + b
return b或return c
【解析】 本题考查对迭代算法的理解。根据题目所给的递推关系可知,每个数是前两个数之和,即每次迭代都需要两个值,因此可以确定迭代变量有两个。初值a=0,b=1,那么可以确定迭代关系为a+b→c、c→b和b→a。由此不断循环,直到计算出第n项为止,结束迭代。
【例3】 一个楼梯有n阶,上楼可以一步上一阶,也可以一步上二阶。要求:编写一个程序,输入一个正整数n(表示楼梯阶数),输出共有多少种不同的走法可以到达第n阶。
这是一个典型的递推问题。若只有一级阶梯,方案数为1;若有二级阶梯,方案数为2;根据递推可发现,要达到n级阶梯,只能通过n－1级走一阶或n－2级走二阶达到。可以归纳出下面的递推公式:

请在画线处填入合适的代码。
n = int(input())
a = 1; b = 2
for i in range(3,n+1):
　　__________
　　a = b
　　b = c
if n == 1:
　　print(1)
else:
　　print(b)
c=a+b
【解析】 定义两个迭代变量a和b,可将上面的递推公式转换成如下迭代关系:c=a+b, a=b,b=c。初始值a=1,b=2。不断地重复执行,直到计算出n级阶梯的方案种数。可以看出,该题解法和例2非常类似,其实这也是斐波那契数列。
自我检测
1. 手机上的各种应用软件,上架后并不是一成不变的,而是需要根据用户体验及反馈不断调整、优化、完善软件的各种功能。其中体现的算法思想是(　　)
A. 枚举 B. 解析
C. 迭代 D. 递归
【解析】 本题考查的是迭代算法的算法思想。题干体现了软件版本的更新与迭代过程,C正确。
C
2. 下面Python程序是使用迭代算法求s的值。
n=int(input())
s=0;i=0
while i<=n:
　　i+=2
　　s+=i**2
print(s)
程序执行时,输入n的值为6,则输出的结果为(　　)
A. 35 B. 10
C. 120 D. 83
【解析】 本题考查迭代算法的程序实现。本题程序的功能是求s=4+16+36+64=120,因此最后输出的结果为120,C正确。
C
3. 关于下面的自定义函数,下列说法中错. 误. 的是(　　)
def gcd(a,b):
　　r=a% b
　　while r!=0:
　　　　　a= b
　　　　　b=r
　　　　　r=a% b
　　return b
A. 函数gcd的功能是求最大公约数
B. 函数gcd采用了迭代算法思想
C. 调用函数gcd(6,15)和gcd(9,24)的结果相同
D. 将函数gcd()中的返回值改为return r,结果不变
【解析】 该代码段的功能是求a、b的最大公约数,采用了迭代算法思想,代入后可知gcd(6,15)和gcd(9,24)的结果相同,A、B、C均不符合题意;将返回值改为return r,结果变为0,D符合题意。
D

展开更多......

收起↑