5.2 迭代与递归（分层作业）信息技术浙教版2019选择性必修1

5.2迭代与递归 2课时（分层作业） 【基础达标】 1.迭代是 的活动，其目的通常是 。 2.利用迭代算法处理问题，需要考虑以下三个方面： 、 、 。 3.欧几里得算法又称 ，用于计算两个整数m，n的 。 4.欧几里得算法在执行时，也是一个反复迭代的过程，直到余数等于 为止。 5.递归是通过函数 来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 6.递归算法的执行过程分 和 两个阶段。 7.计算机在执行递归程序时，是通过 的调用来实现的。 8.通常是为了接近并达到所需的目标或结果，对过程进行重复，每一次重复得到的结果会被用来作为下一次的初始值。这种用计算机解决问题的一种基本方法是() A.迭代法 B.查找法 C.分析法 D.排序法 9.直接或间接地调用函数自身的方法为 ,不断用变量的旧值推出新值的过程为 。 A.递归;枚举 B.迭代;枚举 C.迭代;递归 D.递归;迭代 10.运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的（） A.问题性质相同，问题规模相同 B.问题性质不同，问题规模相同 C.问题性质相同，问题规模不同 D.问题性质不同，问题规模不同 11.下列有关迭代算法和递归算法的描述，不正确的是() A.在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口 B.一般来说，迭代算法效率较低，而递归算法效率较高 C.递归中一定有迭代，但迭代中不一定有递归 D.通常情况下，迭代算法和递归算法可以相互转换 【巩固提升】 1.下列关于递归和迭代两种算法的描述错误的是 A.迭代算法和递归算法原理不同，因此迭代程序和递归程序不能相互转换 B.递归是重复调用函数自身 C.迭代通常使用计数器结束循环 D.递归中遇到满足终止条件的时候逐层返回 2.关于迭代与递归算法，下列说法错误的是() A.迭代是重复反馈的活动，其目的通常是逼近所需目标或结果 B.递归是重复调用函数自身 C.迭代程序可以转换成等价的递归程序 D.迭代和递归是同一种算法的两种不同的表述 3.下列程序代码采用的算法是() def mi (x,n): if n==0: return 1 else: return x*mi (x,n-1) A.迭代法 B.枚举法 C.递归法 D.解析法 4.通常是为了接近并达到所需的目标或结果，对过程进行重复，每一次重复得到的结果会被用来作为下一次的初始值。这种用计算机解决问题的一种基本方法是() A.迭代法 B.查找法 C.分析法 D.排序法 5.定义如下函数: def f(s): if len(s)==1: return s[0] elif len(s)==2: return s[0]+s[1] else: return f(s[0:len(s)//3])+f(s[len(s)//3:len(s)]) 执行语句s-f([1,2,3,4,5,6]),函数f被调用的次数是() A.3 B.5 C.7 D.15 6.斐波那契在《计算之书》中，提出了“生小兔问题”如果每对兔子(一雄一雌)每月能生殖一对小兔子，每对兔子第一个月没有生殖能力，但从第二个月以后便能每月生一对小兔子。假定这些兔子都没有死亡现象，那么从第一对刚出生的兔子开始，12个月以后会有多少对兔子呢?这种问题的解决通常是为了接近并达到所需的目标或结果，对过程进行重复，每一次重复得到的结果会被用来作为下一次的初始值。这种用计算机解决问题的一种基本方法是() A.排序法 B.查找法 C.二分法 D.迭代法 7.定义如下函数: def fn(x): if x<=2: return x else: return fn(x-1)+fn(x-2) ans=fn(6) print(ans) 执行上述程序后输出的结果是() A.13 B.12 C.11 D.10 8.定义如下函数: def f(s): if len(s)<2: return True elif s[0]==s[len(s)-1]: return f(s[1:len(s)-1]) else: return False 下列关于该自定义函数的说法正确的是（） A.该函数主要用到的是迭代思想 B.将该函数中的elif修改为if,不会影响运行结果 C.执行语句print(f("6678766")),输出的结果是False D.如果执行语句print(f([1,2,3])),运行时将报错 9.定义如下函数: def f(a,b): ifa<b: #① a,b=b,a ifa%b==0: return b else: return f(b,a%b) 执行语句print(f(27,121)),注释①处的代码执行的次数是（） A.1 B.2 C.3 D.4 10.递归算法可以用三个字来概括，但不包括下列选项中的() A.解 B.分 C.治 D.合 11.以下程序代码采用的算法是()。 def gcd(m, n): while m%'n !=0 : m,n=n,m%n return n a=int(input("请输入 a的值:")) b=int(input("请输入b的值:")) print(gcd(a,b)) A.枚举法 B.二分法 C.递归法 D.迭代法 12.斐波那契在《计算之书》中提出了一个有趣的兔子问题:假设一对大兔子每个月可以生一对小兔子，一对小兔子生下后一个月长成大兔子，第2个月开始也生一对小兔子。则一对小 兔子一年后可以变成多少对兔子?以下是解决该问题的Python程序代码: def fib(n) If n ==1 or n==2: retum ① else: retum fib(n-1)+fb(②) n=int(imput("输入需要计算的项数:") print("第"，str(n)+"项的值为:",fb(③)) input("运行完毕，请按回车键退出...") 要实现上述要求，填入的代码完全正确的一组是() A.①0;②n-1;③n+1 B.①1;②n-2;③n C.①2;②n;③n D.①3;②n-3;③n+1 13.定义如下雨数 def peach(day): if day = 7 num = 1 else: num=(peach(day+1)+1)*2 return num print(peach(1)) 执行该程序段后，输出的结果是 A.14 B.9 C.190 D.382 14.定义如下函数: def peach (day): if day == 7: num =1 else: num=(peach(day+1)+1)*2 return num print (peach(1)) 执行该程序段后，输出的结果是（） A.14 B.94 C.190 D.382 15.下列函数实现的功能是 def mi(x,n): if n==0: return 1 else: return x*mi(x,n-1) A.计算x的n次方 B.计算n的次方 C.计算m!*n D.计算汇*n! 16.有如下Python程序段[1]: def peach(n): if n== 10: return 1 else: return (peach (n+1)+1)*2 print (peach (8)) 执行该程序段后，输出的结果是（） A.2 B.6 C.8 D.10 17.在递归算法中，以下哪个部分是必须的? A 递归终止条件 B 递归参数传递 C 递归返回值 D 递归调用语句 【链接高考】 1.有如下 Python 程序段: #程序段 1 def fac (n): for i in range(1,n+1): s = s*j return s print(fac (5)) #程序段 2 def fac(n): if n == 1: return 1 else returnn*fac(n-1) #① print(fac (5)) 下列关于两个程序段的说法，正确的是（） A.程序1和程序2都使用了递归算法 B.若问题规模为 n，程序1和程序2的时间复杂度不同 D.若程序2中自定义 C.若程序1中问题规模为n，则"的值就是其循环执行的次数函数内的代码只保留①处语句，也能获取到目标值 2.定义如下函数: def mep(n): if n==l: return 1 else : return (mep(n-1)+1)* 2 执行语句t=mep(5),t的值为 A.22 B.23 6..45 D.46 3.定义如下函数: def fn1(n, num1,num2): if n =- 1: return numl return fn1(n - 1, num2,num1 + num2) def fn2(n): if n == 1 or n == 2: return 1 return fn2(n - 1) + fn2(n - 2) 下列说法正确的是() A.两种算法的时间复杂度相同 B.fn1(n,1,1)与fn2(n)的功能相同 C.执行语句fn2 (8)时，fn2(5)被调用了2次 D.fnl函数的调用次数取决于numl和num2的值 4.定义如下函数: def fib(n): if n<3: return 1 return fib(n-1)+fib(n-2) 若T(n)表示函数fib的调用次数,当n>3时，下 列说法正确的是() A.T(n) =T(n-1)+T(n-2) B.T(n) =T(n-1)+T(n-2)-1 C.T(n) =T(n-1)+T(n-2)+1 D.T(n)=2*(T(n-1)+T(n-2)) 5.有如下Python 程序段: def f( s) : if len(s)==1: return True elif len(s)==2; return s[0]==s[1] elif s[0]==s[ -1]: retumn f(s[l: -1]) else: return False print(f("1234321")) 执行该程序段后,下列说法正确的是 A.输出结果为False B.雨数f运用了选代算法 C.函数f的调用次数为4 D.函数f的时间复杂度为〇(n2) 6.将十进制正整数转化为二进制数，对应的Python程序如下: def toStr (n, base): s ="01" if n < base: returns [n] else: return ① n= int(input('请输入正整数:)) result = toStr (n,2) print (result) 则代码中①处的语句可为() A.toStr (n//base,base)+ s [n%base] B.s [n%base]+ toStr(n//base, base) C.toStr (n%base,base)+s [n//base] D.s [n//base]+ toStr (n%base, base) 7.有如下Python程序段: def f(x): if x == 1: return 1 else: return x * f(x -1) S=0 for i inrange (1,6): s+ =f(i) 执行该程序段后，变量s的值b是 A.33 B.34 C.154 D.153 8.迭代算法与递归算法都需要 某些代码，两者既有区别又有密切的联系。迭代是重复 的活动，其目的通常是逼迫 其结束方式，通常使用 结束循环。 递归的重复方式是重复 ，其结束方式是遇到 的情况时逐层返回。 9.编写递归函数计算前n个正整数的和,即计算s=1+2+…+n。请在划线处填人合适的代码。 def s(n) : if n==1: return 1 else : return 10.斐波那契在《计算之书》中提出了一个有趣的兔子问题:假设一对兔子每个月可以生一对小兔子，一对兔子出生后第2个月就开始生小兔子。则一对兔子一年内能繁殖成多少对?程序 代码如下，请补全划线处对应的代码: def fib(n): f2=f1= (1) for i in range (3, (2) ): f1,f2=f2,f1=f2 retum (3) n=int(input("输入月份数:")) print("兔子总对数为:"，fib(n)) n=int(input("输入月份数:")) print("兔子总对数为:",fib(n)) (1) (2) (3) 参考答案 【基础达标】 1.重复反馈过程、为了使结果符合目标需求 2.确定迭代变量、建立迭代关系式、控制迭代过程 3.辗转相除法、最大公约数 4.0 5.自己调用自己 6.递推、回归 7.栈 8.答案：A [解析]迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。所以选项A符合题意。故选:A。 9.答案：D [解析]直接或间接地调用函数自身的方法为递归算法，不断用变量的旧值推出新值的过程为迭代法故选:D。 10.答案：C [解析]运用分治策略将一个难以直接解决的大问题分割成规模较小的子问题分别解决，最终达到解决大问题的目的。这要求原问题和子问题的问题性质相同，问题规模不同，所以选项C符合题意。故选: C。 11.答案：B [解析]迭代算法通常效率较高，而递归算法可能效率较低。这是因为递归算法在递归调用时需要保存上下文，包括局部变量和返回地址，而这可能导致开销较大。此外，递归算法在递归深度较深时可能引起栈溢出，因此需要小心处理递归深度。所以选项B符合题意。故选:B。 【巩固提升】 1.答案：A [解析]所有迭代可以被转换为递归，但递归并不总是可以被转换为迭代;递归是重复调用函数自身;迭代通常使用计数器结束循环;递归循环中，遇到满足终止条件的情况时逐层返回来结束。故选:A。 2.答案：D [解析]迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。迭代法是一类利用递推公式或循环算法通过构造序列来求问题近似解的方法。递归算法一种通过重复将问题分解为同类的子问题而解决问题的方法。一般理解为函数可以直接或者间接的调用自身。迭代可以转换为递归，但递归不一定能转换为迭代。迭代与递归并不是一种具体算法，而是一种看 待问题的思想。迭代和递归是两种不同的看待问题的思想。D选项错误。故选D。 3.答案：C [解析]递归算法是一种直接或者间接调用自身函数或者方法的算法。说简单了就是程序自身的调用。分析本题代码可知采用的算法是递归法。故选:C。 4.答案：A [解析]本题考查计算机解决问题的方法。迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值，迭代法又分为精确迭代和近似迭代。查找法是指对指定数据在数组中进行查找。排序法是对数据排序后进行后续处理。分析法是“综合法”的对称。把复杂的经济现象分解成许多简单组成部分，分别进行研究的方法。其实质是通过调查研究，找出事物的内在矛盾，并对矛盾的各个方面进行深入研究。故本题选A。 5.答案：C [解析]递归过程如下所示,s=f([1,2,3,4,5,6]),调用1次;f([1,2,3,4,5,6])，return f([1,2])+f([3,4,5,6]),调用2次;f([3,4,5,6]),return f([3])+f([4,5,6]),调用2次;f([4,5,6]),return f([4])+f([5,6]),调用2次;累计7次。 6.答案：D [解析](1)排序算法是将一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 (2)查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。 (3)二分法也称折半搜索算法，对数搜索算法是一种在有序数组中查找某一特定元素的搜索 算法，搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束;如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较，如果在某一步骤数组为空，则代表找不到，这种搜索算法每一次比较都使搜索范围缩小一半。 (4)迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令进行重复执行，在每次执行这组指令时，从变量的原值推出它的一个新值。分析题目内容，这种用计算机解决问题的一种基本方法是迭代法。故选:D。 7.答案：A [解析]根据递归式fn(x)-fn(x-1)+fn(x-2)发现该问题类似于斐波那契数列,满足边界条件x<=2时，fn(x)=x;可以推导出fn(1)=1, fn(2)=2, fn(3)=3, fn(4)=5, fn(5)=8, fn(6)=13。 8.答案：B [解析]该函数用到的是递归思想;该函数可以用于判断字符串是否是回文串,显然“6678766”是回文串,返回True;该函数也可以用于判断列表中的元素是否前后对称,[1,2,3]不对称,返回False,不会报错。 9.答案：C [解析]本题函数f的功能是通过辗转相除法求两数的最大公约数,27和121的最大公约数求解过程为:121%27=13;27%13=1;13%1=0,总共需要调用函数f3次,注释①处语句也执行3次。 10.答案：A [解析]本题考查的是递归算法。结合分治策略，递归也可以用“分”“治”“合”三个字概况。分:将原有问题分解成K个子问题;治:对这K个子问题分别求解。如果子问题的规模仍然 不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。合:将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。结合分治策略，递归也可以用“分”“治”“合”三个字概况。故选:A。 11.答案：D [解析]迭代是重复反馈过程的活动，其目的通常是为了使结果符合目标需求。 12.答案：B [解析]斐波那契数列是:1、1、2、3、5、8等，即从第三项开始后一项是前2项之和，故①处n=1和n=2均为1，如果n>2，则fib(n)的值为前两项之和，故②处填n-2，同理③处调用fib()函数，参数是n。故选:B。 13.答案：A [解析]由题意可知: peach(1)=[peach(1+1)+1]x2=[peach(2)+1]x2=[peach(2+1)+1]x2x2=4peach(3)+2=4[peach(3+1)+1]+2=4[peach(4)+1]+2=4[peach(4+1)+1]+2=4[peach(5)+1]+2=4[peach(5+1)+1]+2=4[peach(6)+ 1]+ 2=4peach(6+1)+1]+2=4peach(7)+1+2=41+1+2=10,故答案为:A。 14.答案：C [解析]阅读程序段可知，只有当day==7时，num的值为1，所以从1到6，需要调用6次，numm的值分别为4，10，21，45，95，190。故选:C。 15.答案：A [解析]分析程序，参数是x和n，当n=0时，返回1，否则返回x*mi(,n-1)。而函数mi(,n-1)当n-1不等于0时，返回2*mi(,n-2)，依次类推，即函数实现的功能是计算z的n次方。故选:A。 16.答案：D [解析]阅读程序段可知，当调用peach(8)时，它会调用peach(9)，而peach(9)会调用peach(10)，因为n等于10时返回1。然后，peach(9)将返回(1+1)*2=4，接着peach将返回(4+1)*2=10。故选:D。 17.答案：A [解析]在递归算法中，递归终止条件是必须的。递归终止条件用于指定递归何时结束，即递归的停止条件。如果没有递归终止条件，递归函数将会无限循环调用自身，导致程序陷入死循环。因此，递归终止条件是递归算法中必须的部分。 【链接高考】 1.答案：C [解析]考查算法的时间复杂度和递归。A项,程序1没有使用递归算法;B项,两个程序段算法的时间复杂度都是O(n);C项,根据代码foriin range(1，n+1),"的值就是其循环执行的次数,正确;D项,递归算法在递推阶段必须有终止递推的条件。 2.答案：D [解析]考查对递归函数的理解 “递”的过程 “归”的过程 mep(5)=(mep(4)+1)*2 mep(5)=46 mep(4)=(mep(3)+1)*2 mep(4)=22 mep(3)=(mep(2)+1)*2 mep(3)=10 mep(2)=(mep(1)+1)*2 mep(2)=4 mep(1)=1 mep(1)=1 3.答案：B [解析]A选项错误，fn1是线性时间复杂度，fn2是指数时间复杂度。B选项正确，两者都计算斐波那契数列的第n项。C选项错误，fn2(5)会被调用多于2次。D选项错误，fn1函数的调用次数只取决于参数n的值，与num1和num2无关。故选:B。 4.答案：C [解析]由函数fib(n)的定义可知，当n>3时，函数fib(n)共调用了函数fib(n-1)和函数fib(n-2)各一次，再加上自身的一次调用，共有T(n-1)+T(n-2)+1次调用，即T(n)=T(n-1)+T(n-2)+1。答案选择为C。 5.答案：C [解析]考查函数递归的分析和理解。根据代码，这是利用递归判断一个字符串是否是“回文串”。选项A,"1234321"是“回文串”,应该输出 True,错误。选项 B,函数f运用了递归算法,不是迭代算法,错误。选项C，f("1234321")→f("23432")→f(" 343")→f("4")→True,调用4次,正确。选项D,根据以上分析,该算法的时间复杂度是O(n)。 6.答案：A [解析]分析程序可知，当n>= base时，十进制转换为二进制的方法是“除权取余、逆序排列”，该程序采用递归算法，故第一空第一部分继续调用toStr方法，第二部分将余数保存到列表s中，故填toStr(n//base,base)+s[n%base]，故本题选A选项。故选:A。 7.答案：D [解析]for i inrange(1,6):可知I的取值范围为[1,5]，所以当z =1时，f(1)= 1,f(2)=2*1=2，同理可得f(3)=6(4)=24，f(5)=120，所以s=1+2+6+24+120=153。故选:D。 8.答案：重复执行、反馈过程、所需目标或结果、计数器、调用函数自身、满足终止条件 [解析]本题考查的是迭代与递归算法。迭代算法与递归算法都需要重复执行某些代码，两者既有区别又有密切的联系。迭代是重复反馈过程的活动，其目的通常是逼迫所需目标或结果，其结束方式，通常使用计数器结束循环。递归的重复方式是重复调用函数自身，其结束方式是遇到满足终止条件的情况时逐层返回。 9.答案：n+s(n-1) [解析]本题考查递归算法。递归函数功能是求n个正整数的和:s=1+2+…+n,所以n项和为n+s(n-1)。 10.答案：(1)1、(2)n +1、(3)f2 [解析](1)分析题干可知，这是一个斐波那契数列，即满足数量1、1、2、3、5、8..，即从第三项开始，后一项等于前两项之和，故f1和f2的初值是1。 (2)循环变量i表示月份，其范围是从3 ~ n。range(start,stop,[step]),start:计数从start开始。默认是从0开始。例如range(5)等价于range(0,5);stop:计数到stop结束，但不包括stop。故此空填n +1。 (3)循环结束后，f2的值即出生第n个月能繁殖的总对数，故填f2。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$