高中信息技术浙教版（2019）选修1 第五章　课时2　迭代与递归（学案 课件，2份打包）

(课件网) 课时2　迭代与递归 第五章　数据结构与算法 1.通过实例分析，理解迭代和递归算法的基本思想，掌握利用迭代和递归算法解决问题的基本方法。2.能正确分析递归公式和递归结束条件，灵活使用迭代和递归算法解决实际问题，提升学生的计算思维。 目 录 CONTENTS 知识梳理 01 例题精析 02 随堂检测 03 巩固与提升 04 知识梳理 1 1.迭代算法的概念 不断用变量的_____递推出_____的过程称为迭代算法。 2.利用迭代算法解决问题，需要考虑的三个方面 (1)确定_____。 (2)建立_____。 (3)控制_____。 迭代算法的难点在于寻找和建立正确的迭代公式，一般使用循环结构语句实现。 旧值 新值 迭代变量 迭代关系式 迭代过程 3.递归算法的概念 一个函数在其定义中_____来解决问题的方法称为递归算法。 递归算法的实质是：将规模大的问题分解成规模小的问题，然后从这些小问题的解中构造出大问题的解，并且这些规模较小的问题也能采用_____的分解和综合方法。当递归到达某个_____，如问题规模缩减为0或1时，能直接得解。 直接或间接调用自身 同样 边界 4.设计递归算法时，需要满足的两个条件 (1)确定_____。 (2)确定递归的_____(或称为边界条件)。 5.递归过程的两个阶段 (1)_____：把较复杂的问题的求解递推到一些简单问题的求解。 (2)_____：当获得最简单问题的解后，逐级返回依次得到稍复杂问题的解。 递归公式 结束条件 递推 回归 正确区分迭代算法和递归算法 (1)迭代是利用变量的旧值推算出变量的一个新值；而递归算法是指一个函数在其定义中直接或间接调用自身的一种方法，它通常把一个复杂的问题转化为一个与原问题相似的规模较小的问题来解决，可以极大地减少代码量，降低编程的难度。因此，迭代算法效率较高，而递归算法比较占用空间，程序运行效率较低。 (2)递归是自己调用自己，而迭代就是不断地调用赋值语句；递归中一定有迭代，但是迭代中不一定有递归，大部分情况下递归和迭代可以相互转换。 例题精析 2 例1 让计算机重复执行一组指令(或一些步骤)，这组指令(或这些步骤)每执行一次时，都会将变量从原值递推出一个新值的算法是(　　) A.递推算法 B.递归算法 C.迭代算法 D.查找算法 C 解析　本题主要考查的是迭代算法的定义。本题中描述的算法是迭代算法，因此，答案为C。 变式训练　利用迭代算法处理问题时，其中从变量的前一个值推出其下一个值的公式的过程称为(　　) 解析　本题主要考查的是迭代算法的基本步骤。使用迭代算法的三个步骤为：确定迭代变量、建立迭代关系式、控制迭代过程，其中从变量的前一个值推出其下一个值的公式的过程称为建立迭代关系式。因此，答案为D。 D A.确定迭代变量 B.设定迭代结束条件 C.控制迭代过程 D.建立迭代关系式 例2 丑数是指不能被2、3、5以外的质数整除的数。判断丑数的自定义函数程序如下： B 若调用执行自定义函数ugly(30)，下列说法正确的是(　　) A.函数返回值为False B.方框处程序应用了迭代算法 C.该程序的时间复杂度为O(n2) D.条件语句n%i＝＝0执行了3次 解析　本题考查算法思想应用。题目中对丑数的描述等价于：丑数是指只能被2、3、5整除的数。A选项30＝2*3*5，30是丑数。B选项方框中程序为当n能被i整除时，不断求n除以i的商，是一个重复反馈的过程。C选项整个除的次数不会大于n，因此时间复杂度为O(n)。D选项除2、3、5过程中，一次能除通，一次条件不成立，条件语句n%i＝＝0执行了6次。 变式训练　小明设计了一个算法求2n的值，算法思想是：先把2n转换为2*2n－1，而2n－1又可以转换为2*2n－1－1，如此继续，直到2*20，已知20＝1，再反过来，又依次求出21，22，…，直到求出了2n的值。小明求2n的值所采用的算法是( ... ...