迭代算法及其应用一轮复习课件-2025-2026学年浙江省高三信息技术选择性必修一

迭代算法及其应用 1 知识过关 2 迭代算法的概念和特点 (1)迭代是重复反馈过程的活动,其目的通常是使结果符合目标需求。 (2)让计算机重复执行一组指令(或步骤),这组指令(或步骤)每执行一次时,都会让变量从原值递推出一个新值。 (3)利用迭代算法处理问题,需要考虑以下三个方面: ①确定迭代变量:一个直接或间接地不断由旧值递推出新值的变量。 ②建立迭代关系式:将变量从前一个值推出其下一个值的公式(或关系)。 ③控制迭代过程:设定迭代结束的条件。 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 4 典例精选 5 【例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) 【例2】 斐波那契数列是这样一个数列:1,1,2,3,5,8,…,其定义如下: f(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级走二阶达到。可以归纳出下面的递推公式: f(n)= 请在画线处填入合适的代码。 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非常类似,其实这也是斐波那契数列。 自我检测 12 1. 手机上的各种应用软件,上架后并不是一成不变的,而是需要根据用户体验及反馈不断调整、优化、完善软件的各种功能。其中体现的算法思想是(　　) A. 枚举 B. 解析 C. 迭代 D. 递归 【解析】 本题考查的是迭代算法的算法思想。题干体现了软件版本的更新与迭代过程,C正确。 C 13 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 14 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 15 必备知识练 16 1. 用于计算正数a的算术平方根(近似值)的算法如下:xi＋1=(xi＋),i=1,2,3…,近似值的初始推测值x1可以是任何正数,例如x1=a,运用上述算法公式计算x2,然后由x2计算x3,直到相邻两值的绝对值小于设定的精度e为止,此时xi就是要求的近似解。上述过程采用的 算法属于(　　) A. 迭代算法 B. 递归算法 C. 枚举算法 D. 解析算法 【解析】 本题考查迭代算法的思想。本题采用迭代关系式,由迭代计算的方法,符合迭代算法的基本思想,A正确。 A 17 2. 一个球从某一高度h(单位:米)落下,每次落地后反弹回原来高度的一半,再落下。编程计算球在第10次落地时,经过的距离s,程序代码段如下: h=20.0; s=h for i in range(9): 　　　　　 print(s) 方框中的代码由以下三部分组成: ①L=h*2　②h=h/2　③s=s＋L 下列选项中,代码顺序正确的是(　　) A. ①②③ B. ②①③ C. ③①② D. ②③① 【解析】 变量L需要先定义后使用,因此③在①之后。第一次落地,经过的距离为h,即s的初值,后续落地都是先上升后落下,经过的是2段路程,上升距离是原高度h的一半,这个过程可以用②①表示。B正确。 B 18 3. 利用迭代法计算圆周率π值的方法是:计算公式=1－＋…,直到最后一项的绝对值小于10－7为止,程序如下: s=0 f=－1 t=1 while abs(1/t)>=10**(－7): 　　　　　　　　 s=s*4 print(round(s,6)) 方框中的代码由以下三部分组成: ①f=－f　②t＋=2　③s＋=f*1/t 下列选项中,代码顺序正确的是(　　) A. ①②③ B. ①③② C. ③①② D. ③②① 【解析】 本题考查迭代算法的程序实现。根据迭代变量的初始值f=－1,s=0,t=1,第一次循环要累加到s中的值为1,根据模拟,代码顺序为①③②,才能保证第i次循环时,正好是第i项被累加到s中。B正确。 B 19 4. 斐波那契数列是指除了数列的第1项和第2项,接下来每一项都等于其前两项之和,如1,1,2,3,5,8,13,…,下列程序能够根据输入的n(n≥2),计算并输出斐波那契数列的第n项。 n=int(input("请输入斐波那契数列的第n项(n≥2):")) a,b=1,1 i=3 while i<=n: 　　 ①   　　a=b 　　b=c 　　i＋=1 print("第"＋str(n)＋"项的值为"＋ ② )  20 则画线处缺失的代码是(　　) A. ①b=a＋c　②str(a) B. ①c=a＋b　②str(b) C. ①c=a＋b　②str(a) D. ①b=a＋c　②str(b) 【解析】 迭代过程中,新的值c为前两项a,b的和,①填c=a＋b,模拟发现,循环处理一次,第i项的新值保存在b中,最后输出第n项的值,需要将b转换为字符串类型再进行字符串连接。B正确。 B 5. 下列Python程序的功能是使用迭代算法求s的值: n=int(input()) s=0 for i in range(1,n): 　　if i % 2==0: 　　　　s=s＋i print(s) 程序执行时,输入n的值为20,则输出的结果是(　　) A. s=90 B. s=100 C. s=110 D. s=190 【解析】 本题考查迭代算法的程序实现。本程序的功能是求s=2＋4＋6＋…＋18的值,因此最后输出的结果为s=90,A正确。 A 22 6. 下列程序段使用“累乘相加算法”,将k进制数转换为十进制数: k=input("请输入k进制(k<10):") s=input("请输入k进制表示的数值s:") n=0 for t in s: 　　　　　　　　 print(k,"进制数",s,"转换为十进制为:",n) 则方框中缺失的代码是(　　) A. n=n*k＋t B. n=n*k＋int(t) C. n=(n＋int(t))*int(k) D. n=n*int(k)＋int(t) 【解析】 根据累乘相加算法,从左往右遍历k进制数的每一位数字时,n需要扩大k倍再加上当前遍历的数值,由于输入的k和t都是字符串类型,D正确。 D 23 关键能力练 24 7. 下列程序段的功能是计算表达式s=l－1/3＋1/5－1/7＋…＋1/21的值: s,f=O,1 for i in range(l,22,2): 　　 ①   　　 ②   print(s) 则画线处缺失的代码是(　　) A. ①s=f/i　②f=－1 B. ①s=s－f/i　②f=－f C. ①s=s＋f/i　②f=－1 D. ①s=s＋f/i　②f=－f 【解析】 本题考查迭代算法。由于f的值在1和－1之间交替出现,因此②肯定是f=－f,然后结合第一项是正值,D正确。 D 25 8. 有如下Python程序: while a!=b: 　　if a>b: 　　　　a=a－b 　　else: 　　　　b=b//2 print (b) 若a, b的值分别为22和16,程序运行后输出的结果是(　　) A. 0 B. 1 C. 2 D. 16 C 26 【解析】 本题考查Python循环相关知识。列出表格如下所示: 循环次数 0 1 2 3 4 5 a 22 6 6 6 2 2 b 16 16 8 4 4 2 综上所述,b=2。C正确。 9. 对于任意一个自然数,若该自然数为偶数,则将其除以2;若是奇数,则将其乘以3,然后再加 1。如此经过有限次运算后,总能够得到自然数1 。 编写一个由键盘输入一个整数x,把x经过有限次运算后,输出最终变成1的全过程的程序,并计算运算的次数n。 程序运行界面如图所示: 请输入一个整数:21 21→64→32→16→8→4→2→1 运算次数为:7 28 实现上述功能的Python程序如下,请回答下列问题: x=int(input("请输入一个整数:")) print(x,"→",end="") n=0 while　x!=1: 　　if ①________________________:  　　　　x=x*3＋1 　　else: 　　　　②__________  　　if x==1: 　　　　print(x) 　　else: 　　　　print(x,"→",end="") 　　③____________________  print("运算次数为:",n) (1)请在画线处填入合适的代码。 (2)程序执行时,若输入x的值为120,则运算次数为__________。  x % 2==1 或x % 2!=0 x=x//2 n＋=1或n=n＋1 20 29 【解析】 本题考查迭代算法的程序实现。(1)①本题使用的是迭代算法,当自然数变为1时,循环结束,否则,若x为奇数时,x=n*3＋1,因此此处代码为x % 2==1或x % 2!=0。②若x为偶数时,x=x∥2,因此此处代码为x=x∥2。③每循环一次表示一次运算,根据语句print("运算次数为:",n)可知,变量n的功能是统计运算次数,因此此处代码为n＋=1或n=n＋1。(2)程序执行时,输入x的值为120时,变量x的值的变化过程为:120→60→30→15→46→23→70→ 35→106→53→160→80→40→20→10→5→16→8→4→2→1,因此共运算20次。 30 $