资源简介

二、 迭代算法及其应用
1. 用于计算正数a的算术平方根(近似值)的算法如下:xi＋1=(xi＋),i=1,2,3…,近似值的初始推测值x1可以是任何正数,例如x1=a,运用上述算法公式计算x2,然后由x2计算x3,直到相邻两值的绝对值小于设定的精度e为止,此时xi就是要求的近似解。上述过程采用的算法属于(　A　)
A. 迭代算法 B. 递归算法
C. 枚举算法 D. 解析算法
【解析】 本题考查迭代算法的思想。本题采用迭代关系式,由迭代计算的方法,符合迭代算法的基本思想,A正确。
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
下列选项中,代码顺序正确的是(　B　)
A. ①②③ B. ②①③
C. ③①② D. ②③①
【解析】 变量L需要先定义后使用,因此③在①之后。第一次落地,经过的距离为h,即s的初值,后续落地都是先上升后落下,经过的是2段路程,上升距离是原高度h的一半,这个过程可以用②①表示。B正确。
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
下列选项中,代码顺序正确的是(　B　)
A. ①②③ B. ①③②
C. ③①② D. ③②①
【解析】 本题考查迭代算法的程序实现。根据迭代变量的初始值f=－1,s=0,t=1,第一次循环要累加到s中的值为1,根据模拟,代码顺序为①③②,才能保证第i次循环时,正好是第i项被累加到s中。B正确。
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)＋"项的值为"＋ 　　②　　)
则画线处缺失的代码是(　B　)
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正确。
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　)
A. s=90 B. s=100
C. s=110 D. s=190
【解析】 本题考查迭代算法的程序实现。本程序的功能是求s=2＋4＋6＋…＋18和,因此最后输出的结果为s=90,A正确。
6. 下列程序段使用“累乘相加算法”,将k进制数转换为十进制数:
k=input("请输入k进制(k<10):")
s=input("请输入k进制表示的数值s:")
n=0
for t in s:
　　　　　　　　
print(k,"进制数",s,"转换为十进制为:",n)
则方框中缺失的代码是(　D　)
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正确。
7. 下列程序段的功能是计算表达式s=l－1/3＋1/5－1/7＋…＋1/21的值:
s,f=O,1
for i in range(l,22,2):
　　　①　
　　　②　
print(s)
则画线处缺失的代码是(　D　)
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正确。
8. 有如下Python程序:
while a!=b:
　　if a>b:
　　　　a=a－b
　　else:
　　　　b=b//2
print (b)
若a, b的值分别为22和16,程序运行后输出的结果是(　C　)
A. 0 B. 1
C. 2 D. 16
【解析】 本题考查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
实现上述功能的Python程序如下,请回答下列问题:
x=int(input("请输入一个整数:"))
print(x,"→",end="")
n=0
while　x!=1:
　　if ①　x % 2==1 或x % 2!=0　:
　　　　x=x*3＋1
　　else:
　　　　②　x=x//2　
　　if x==1:
　　　　print(x)
　　else:
　　　　print(x,"→",end="")
　　③　n＋=1或n=n＋1　
print("运算次数为:",n)
(1)请在画线处填入合适的代码。
(2)程序执行时,若输入x的值为120,则运算次数为　20　。
【解析】 本题考查迭代算法的程序实现。(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次。(共16张PPT)
二、 迭代算法及其应用
第五章　数据结构与算法
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 用于计算正数a的算术平方根(近似值)的算法如下:xi＋1=(xi＋),i=1,2,3…,近似值的初始推测值x1可以是任何正数,例如x1=a,运用上述算法公式计算x2,然后由x2计算x3,直到相邻两值的绝对值小于设定的精度e为止,此时xi就是要求的近似解。上述过程采用的
算法属于(　　)
A. 迭代算法 B. 递归算法
C. 枚举算法 D. 解析算法
【解析】 本题考查迭代算法的思想。本题采用迭代关系式,由迭代计算的方法,符合迭代算法的基本思想,A正确。
A
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
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
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)＋"项的值为"＋ ② )
则画线处缺失的代码是(　　)
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
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
关键能力练
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
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
【解析】 本题考查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
实现上述功能的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
【解析】 本题考查迭代算法的程序实现。(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次。

展开更多......

收起↑