资源简介

专题16　算法思想
学业要求 知　识　点 学业水平等级
1.理解迭代算法的思想，应用迭代算法处理实际的问题 4
2.理解递归算法的思想，应用递归算法处理实际的问题 4
知识点　递归算法
【知识梳理】
1.迭代算法思想：让计算机重复执行一组________(或一些步骤)，这组指令(或这些步骤)每执行一次，都会让变量从________递推出一个新值。
2.利用迭代算法处理问题需要考虑三个方面：(1)确定____________；(2)建立____________；(3)控制____________。
3.为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。当________到达某个边界，能直接得到解。
4.递归是指在函数的定义中调用________自身的方法，这里的调用分两种：直接调用与间接调用。递归就是有去有回：“有去”指递归问题必须可以分解为若干个规模较小且与原问题相同的子问题，这些子问题可以用相同的________思路来解决；“有回”指这些问题的演化过程是一个从大到小、由近及远的过程，并且存在一个明确的终点(临界点)，一旦到达这个临界点，就不用再往更小、更远的方向走下去。最后，从这个临界点开始，原路返回到原点，解决原问题。
5.利用递归算法解决问题的关键步骤：(1)抽象建立________，确定________；
(2)确定________(即递归结束条件)。
算法复杂度又分为算法的时间复杂度和空间复杂度，其中时间复杂度反映了算法执行所需要的时间，而空间复杂度反映了算法执行所需要占用的存储空间。
【经典案例】
时间复杂度常用符号O表述，不包括低阶项和首项系数。时间复杂度从低到高可以分为常量阶O(1)、对数阶O(log2n)，线性阶O(n)、平方阶O(n2)等。迭代算法是用计算机处理问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值，是要解决上次计算与下次计算之间数据传递的问题。递归算法设计三步曲：①函数的参数和返回值。这个递归函数的功能是什么，怎样调用这个函数，即设计好递归函数的返回值和参数列表。②找到递归出口。什么时候应该结束这个递归，它的边界条件(出口)是什么(边界条件)。③设计递推公式。一层递归的逻辑。在非边界情况时，怎样从第n层转变成第n＋1层。
【例1】 定义如下函数：
def rf(n)：
if n<3：
return n
return rf(n－1)＋rf(n－3)
执行语句v＝rf(5)，函数rf被调用的次数是(　　)
A.11 B.5
C.7 D.15
思维点拨
明考向 本题考查递归算法思想
精点拨 当参数n大于等于3时，两次递归调用，否则直接返回值。①rf(5)＝rf(4)＋rf(2)，调用rf函数2次；②rf(4)＝rf(3)＋rf(1)，调用rf函数2次；③rf(3)＝rf(2)＋rf(0)，调用rf函数2次；再加上v＝rf(5)本身调用的一次，共7次
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式1】 定义如下函数：
def f(a，s)：
if a>＝s：
return a
else：
return f(a＋1，s－a)
执行语句k＝f(6，21)后，k的值为(　　)
A.6 B.7
C.8 D.9
【例2】 有一堆桃子，猴子第一天吃掉其中的一半，并再多吃一个。之后每天猴子都吃掉剩余桃子的一半，再多吃一个。假设到第十天时，猴子发现只剩下了一个桃子，问原来这堆桃子最初有多少个。实现上述问题的两段Python程序如下：
#程序1 def eat_peach(day)： s＝1 for i in range(9，day－1，－1)： s＝(s＋1)*2 return s print(eat_peach(1))
#程序2 def eat_peach(day)： if day＝＝10： return 1 else： return (eat_peach(day＋1)＋1)*2 print(eat_peach(1))
下列说法不正确的是(　　)
A.程序1和程序2的输出结果相同，均为第1天的桃子数量
B.程序2使用递归算法，函数eat_peach的调用次数为10次
C.将程序1的划线语句修改为range(day，10)，输出结果发生改变
D.将程序2的划线语句修改为print(eat_peach(8))，输出的结果为10
思维点拨
明考向 本题考查迭代与递归算法思想
精点拨 程序1迭代算法循环9－day＋1次，计算得到第day天桃子的数量，day＝1时即第1天桃子数量。程序2递归算法实现计算第1天桃子的数量。程序2为了计算eat_peach(1)，第一次调用函数，应执行计算调用(eat_peach(2)＋1)*2，引起对函数的第二次调用(递归调用)，重新进入函数，这一过程重复直到参数累加到10为止，函数调用了10次；程序1的划线语句修改为range(day，10)，循环执行次数为9－day＋1，执行次数不变，输出结果不发生改变；将程序2的划线语句修改为print(eat_peach(8))，计算的是第8天剩余的桃子数量，输出的结果为10
听课笔记：____________________________________________________________
______________________________________________________________________
【变式2】 定义如下两个函数，fac_1和fac_2：
def fac_1(n)： res＝1 for i in range(1，n＋1)： res *＝i return res
def fac_2(n)： if n＝＝1： return 1 else： return n*fac_2(n－1)
下列说法正确的是(　　)
A.fac_1和fac_2都采用递归算法
B.执行fac_1(4)和fac_2(4)时，两个函数被调用次数不同
C.fac_1(4)和fac_2(4)的返回值不同
D.fac_2函数的算法时间效率远大于fac_1
1.下列关于算法效率的描述，正确的是(　　)
A.算法效率指的是算法的时间复杂度
B.通常，随着问题规模n的增大，函数值增长较慢的算法较优
C.时间复杂度a常用符号T来表示，如2*n*(n－1)，其时间复杂度可以表示为T(n2)
D.常见时间复杂度耗费时间的大小关系为：常数阶<对数阶<指数阶<平方阶
2.下列关于数据结构与算法效率的描述，不正确的是(　　)
A.队列和栈都是一种线性表，但两者有不相同的特性
B.采用相同公式求解n！，使用迭代算法比递归算法的算法效率高
C.使用数组结构在进行数据插入和删除操作时，一定会引起数据移动
D.某单向链表(节点数>2)设有头尾指针，在删除该链表尾节点时需要遍历多个
节点
3.有关递归算法及其应用，下列说法正确的是(　　)
A.递归算法的执行过程分递推和回归两个阶段
B.计算机在执行递归程序时，通过队列的调用来实现
C.使用上述递归算法求斐波那契数列，时间复杂度为O(n)
D.求斐波那契数列的第6项fibo(5)时，fibo(3)被调用了3次
4.定义如下函数：
def f(n)：
if n<＝1：
return 1
elif n＝＝2：
return 2
return f(n－1)＋f(n－2)＋f(n－3)
执行语句v＝f(5)，变量v的值是(　　)
A.13 B.17
C.24 D.31
5.定义如下函数
def mep(n)：
if n＝＝1：
return 1
else：
return (mep(n－1)＋1)*2
执行语句t＝mep(5)，t的值为(　　)
A.22 B.23
C.45 D.46
6.定义如下函数：
def pell(n)：
if n＝＝1：
return 0
elif n＝＝2：
return 1
elif n>2：
return pell(n－1)*2＋pell(n－2)
下列说法不正确的是(　　)
A.执行语句print(pell(3))，输出2
B.函数pell体现了递归的算法思想
C.当n>＝3时，函数pell的被调用次数为n*(n－1)//2次
D.执行语句pell(3)，判断条件“n＝＝2”共执行了2次
7.有如下Python程序段：
def fac(n)：
ans＝1
for i in range(2，n＋1)：
ans *＝i
return ans
def Com(n，m)：
return fac(n)//fac(n－m)//fac(m)
print(Com(5，3))
执行该程序段后，下列说法不正确的是(　　)
A.Com()函数运用了递归思想
B.fac()函数一共被调用了3次
C.输出结果是10
D.将Com(5，3)改为Com(5，2)，运行结果不变
8.对于如下两个Python程序段：
程序a a＝2 res＝1 n＝int(input()) for i in range(n)： res＝res*a print(res) 程序b def powr(a，n)： if n＝＝1： return a elif n＝＝0： return 1 else： tmp＝powr(a，n//2) return tmp*tmp a＝2 n＝int(input()) print(powr(a，n))
下列说法错误的是(　　)
A.若输入n＝8，程序a，b都将输出256
B.若输入n＝10，程序a，b都将输出1024
C.程序a的算法时间复杂度是O(n)
D.程序b的算法时间复杂度是O(log2n)
9.定义如下函数：
def move(n，a，b，c)：
if n＝＝1：
print(a，″→″，c)
return
move(n－1，a，c，b)
move(1，a，b，c)
move(n－1，b，a，c)
执行语句move(2，″A″，″B″，″C″)，输出的第一行内容是(　　)
A.a→c B.A→C
C.a→b D.A→B
10.已知：任取两个自然数，其互质(没有大于1的共同因数)的概率是6/(π*π)，小蓝据此编写了程序：
from math import sqrt
from random import randint
def fun(a，b)：
if b＝＝0：
return a
else：
return fun(b，a % b)
cnt＝0
n＝1000；m＝100000
for i in range(n)：
a＝randint(1，m)
b＝randint(1，m)
if fun(a，b)＝＝1：
　　　　cnt＋＝1
print(sqrt(6*n/cnt))
程序模拟1000次产生2个[1，m]之间的随机数，计算这两个数互质的次数cnt和频率cnt/n，用频率估计概率6/(π*π)，以验证该结论的准确性，则以下说法正确的是(　　)
A.程序输出结果就是6/(π*π)的近似值
B.该程序所描述算法的时间复杂度为O(n)
C.函数fun()用递归算法求两个正整数的最小公倍数
D.要想提高程序结果的精确度，可以扩大n和m的范围
专题16　算法思想
知识点
知识梳理
1.指令　原值
2.(1)迭代变量　(2)迭代关系式　(3)迭代过程
3.递归
4.函数　解题
5.(1)递归模型　递归公式　(2)临界条件
经典案例
例1　C
变式1　C　[本题考查递归函数的应用。递归算法包含递推和回归两部分，函数f(6，21)的值为 f(7，15)，而f(7，15)的值为 f(8，8)，函数f(8，8)的值为8，依次回归，最终函数的值为8。]
例2　C
变式2　B　[本题考查迭代与递归的算法思想。两处程序的功能均为求n的阶乘。A选项程序fac_1体现迭代算法思想。B选项fac_1(4)只调用1次，而fac_2(4)要调用4次。C选项返回值均为24。D选项均循环了n次，因此算法效率一样。]
当堂过关检测
1.B　[本题考查算法效率的计算。A选项算法效率包括时间复杂度和空间复杂度。B选项时间复杂度与n的最高次幂有关，且和系数无关。C选项时间复杂度的常用符号是大写的O。D选项正确的关系是：常数阶<对数阶<平方阶<指数阶。]
2.C　[本题考查不同数据结构的特性和算法描述。A选项队列先进先出，栈先进后出。B选项递归求n！要递推和回归两个阶段，迭代算法的效率高于递归算法。D选项修改尾节点前驱指针区域值为－1，需遍历多个节点。]
3.A　[本题考查递归算法。A选项递归函数中包含一个递推公式，先依次调用自己，再进行回归。B选项通过栈调用来实现。C选项以第6项fibo(5)为例，可以画出二叉树来表示，若根节点为n，则树的高度为n，深度为n的满二叉树的节点数量(函数的调用次数)为n2－1，因此时间复杂度为O(n2)。D选项fibo(3)被调用了2次。fibo(5)＝fibo(4)＋fibo(3)；fibo(4)＝fibo(3)＋fibo(2)。]
4.A　[本题考查递归算法思想。f(5)＝f(4)＋f(3)＋f(2)，f(4)＝f(3)＋f(2)＋f(1)，f(3)＝f(2)＋f(1)＋f(0)＝4，f(4)＝7，f(5)＝7＋4＋2。]
5.D　[本题考查对递归函数的理解。mep(5)＝(mep(4)＋1)*2；mep(4)＝(mep(3)＋1)*2；mep(3)＝(mep(2)＋1)*2；mep(2)＝(mep(1)＋1)*2；mep(1)＝1。]
6.C　[本题考查递归算法思想。B选项pell函数内部调用了自身，因此属于递归算法思想。递归算法包含递推和回归两个过程，pell(3)＝pell(2)*2＋pell(1)＝1*2＋0＝2，pell(2)被调用了2次，因此判断条件“n＝＝2”共执行了2次，AD选项正确。C选项当n分为3和4时，调用次数为3，5，并不符合n*(n－1)//2次。]
7.A　[本题考查自定义函数知识。A选项递归函数是函数调用本身，但函数Com并未调用本身。]
8.B　[本题考查递归程序的阅读与算法复杂度的计算。对于A、B选项根据输入的值模拟运行得到相应的值。C选项程序a的循环次数是n次，算法时间复杂度是O(n)。D选项调用过程是：powr(a，n)→powr(a，n/2)→powr(a，n/4)→powr(a，n/8)→…→powr(a，1)，调用的次数约为log2n次，因此复杂度是O(log2n)。]
9.D　[本题考查递归函数的应用。执行语句move(2，″A″，″B″，″C″)，分别调用move(1，″A″，″C″″B″，)，move(1，″A″，″B″，″C″)，move(1，″B″，″A″，″C″)，因此分别输出A→B、A→C、B→C。]
10.D　[本题考查递归函数和算法复杂度的估算。A选项根据题目要求频率等于概率，cnt/n＝6/(π*π)，(π*π)＝6*n/cnt，该公式计算圆周率的近似值。B选项本段代码的算法复杂度，除了for循环，还要考虑函数fun的复杂度。函数fun是用欧几里得算法求二个数的最大公约数。复杂度是O(log(mix(a，b))。最终的算法复杂度是O(log(mix(a，b)*n)。C选项是求二个数的最大公约数。D选项样本规模越大概率的方法求近似值越接近。]

展开更多......

收起↑