迭代与递归-浙教版（2019）高中信息技术选修1.pptx

《迭代与递归-浙教版（2019）高中信息技术选修1.pptx》由会员分享，可在线阅读，更多相关《迭代与递归-浙教版（2019）高中信息技术选修1.pptx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、知知识回回顾算法效率的高低由算算法法复复杂杂度度来度量，时时间间复复杂杂度度反映算法执行所需的时间，空空间间复复杂杂度度反映算法执行所占用的存储空间。算法运行需要时间，一般将算法中语句的执行次数语句的执行次数作为时间复杂度的度量标准。时间复杂度大O阶推导：1.用常数1取代运行时间中的所有加法常数；2.在修改后的运行次数函数中，只保留最高项；3.若最高阶项存在且不是1，则去除此项的系数。如何量化算法的如何量化算法的时间复杂度？时间复杂度？时间复杂度时间复杂度O(nO(n2 2)知知识回回顾n=int(input()s=(1+n)*n/2print(s)n=int(input()s=0for i

2、in range(1,n+1):s+=iprint(n)n=int(input()s=0 x=0for i in range(1,n+1):for j in range(1,n+1):x+=1 s+=xprint(s)请使用大O阶方法计算下列三种算法的时间复杂度。O(1)O(1)O(n)O(n)O(nO(n2 2)算法的时间复杂度反映了程序的执行时间随问题规模增长而增长的量级算法的时间复杂度反映了程序的执行时间随问题规模增长而增长的量级，在很大程度上能很好地反映算法的优劣。，在很大程度上能很好地反映算法的优劣。5.2 迭代与递归浙江省高中信息技术 选择性必修一 数据与数据结构昌化中学 应彤 鑫

3、迭迭 代代 算算 法法算法思想程序实现迭 代 算 法D i e d a i s u a n f aD i e d a i s u a n f a某饲养场引进了1对刚出生的新品种兔子，第2个月进入成熟期，第3个月开始生育兔子，新生的兔子成熟后的下月又会新生1对兔子若所有的兔子都不会死去，则到第12个月时，该饲养场共有多少对兔子？兔子繁殖过程：1月：兔新生，共1对2月：兔成熟，共1对3月：兔生兔，共2对4月：兔生兔，兔成熟，共3对5月：兔生兔，兔生，兔成熟，共5对6月：兔生兔，兔生兔，兔生兔，兔成熟，共8对.迭 代 算 法D i e d a i s u a n f aD i e d a i s u

4、 a n f a1 1月月2 2月月3 3月月4 4月月5 5月月6 6月月7 7月月8 8月月9 9月月1010月月1111月月1212月月月月1对1对2对3对5对8对13对21对34对55对89对144对对规律：第3月开始，当月兔子数当月兔子数=上月兔子数+当月新生兔子数规律：第3月开始，当月兔子数当月兔子数=上月兔子数+当月新生兔子数=上月兔子数上月兔子数+上上月兔子数上上月兔子数f1=1#1月兔子数f2=1#2月兔子数i=3while i=12:f=f1+f2 f1=f2 f2=f i+=1print(f第第i-1月共有月共有f对兔子对兔子“)迭代算法：旧值不断推出新值的过程迭代算法：

5、旧值不断推出新值的过程时间复杂度时间复杂度O O(n)(n)迭 代 算 法D i e d a i s u a n f aD i e d a i s u a n f a迭代算法：利用计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，这组指令每执行一次时，都会将变量从原值递推出一个新值，即由旧值不断推出新值的过程由旧值不断推出新值的过程。f1=1f2=1i=3while i=12:f=f1+f2 f1=f2 f2=f i+=1print(f第第i-1月共有月共有f对兔子对兔子“)迭代算法处理问题：1.确定迭代变量：由旧值递推出新值的变量；2.建立迭代关系式迭代关系式：从变量的前值

6、推出下个值的公式；3.控制迭代条件：经过若干次重复执行后能够结束。迭 代 算 法D i e d a i s u a n f aD i e d a i s u a n f a欧几里得算法又称辗转相除法，用于计算两个整数m、n的最大公约数。基于定理：gcd(m,n)=gcd(n,m%n),即整数m、n的最大公约数等于n和m除以n的余数的最大公约数，当余数为0时取当前算式的除数即为最大公约数。现任意输入两个正整数，请编程实现计算最大公约数的功能。m=int(input(请输入正整数请输入正整数m：)n=int(input(请输入正整数请输入正整数n：)while n!=0:temp=n n=m%n

7、m=tempprint(最大公约数是：最大公约数是：,m)迭代算法处理问题：1.确定迭代变量：2.建立迭代关系式：3.控制迭代条件：1.确定迭代变量：m、n2.建立迭代关系式：nm，m%nn3.控制迭代条件：余数为0迭 代 算 法D i e d a i s u a n f aD i e d a i s u a n f a0e+1/jc0e+1/jc递 归算算 法法算法思想程序实现递 归 算 法D i g u i s u a n f aD i g u i s u a n f a俄罗斯一票否决了“乌克兰提出的取消俄罗斯一票否决权”的提案一网民因造谣“自己因为造谣被公安拘留15天”而被拘留15天美国

8、谴责“中国谴责美国干涉中国内政”是中国干涉美国内政禁止套娃禁止禁止套娃禁止禁止禁止套娃套娃套娃递 归 算 法D i g u i s u a n f aD i g u i s u a n f a在计算机科学中，指一种通过重复将问题分解为同类的子问题而解决问题的方法，它通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。概念思想把大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，规模较小的又转化为规模更小的问题求解，当问题小到一定程度时，可以直接得出它的解，从而回归求解问题原来的解。即“大事化小，小事化了”的思想。1、每一步解决问题的方法有一致的规律：递归公

9、式2、可以达到某个边界条件：递归出口条件案例整数的阶乘、斐波那契的兔子问题、汉诺塔问题、八皇后问题、猴子吃桃问题等斐波那契的兔子问题“大事化小，小事化了”递 归 算 法D i g u i s u a n f aD i g u i s u a n f a问题提出“大事化小”n个月兔子的对数？nn-1n-2321“小事化了”1个月有1对，2个月有1对递归出口寻求规律fibo(n)递归公式假如有一对刚出生的小兔子，只需要一个月小兔子就能长成大兔子，从第三个月开始，这对大兔子每个月都会生下一对小兔子。新出生的小兔子又会花一个月长大，再花一个月开始生兔子 如果每对兔子都经历这样的出生、成熟、生育的过程，

10、并且永远不死，那么每个月兔子的对数是多少呢？=fibo(n-1)+fibo(n-2)递 归 算 法D i g u i s u a n f aD i g u i s u a n f a迭代：速度快，效率高；但程序冗杂递归：程序简洁易懂；但速度慢，效率低问题解决def fibo(n):if n=2:return 1 else:return fibo(n-1)+fibo(n-2)问题思考和迭代相比时空复杂度？def fibo(n):i=3 a,b=1,1 while i=n:a,b=b,a+b i+=1 return b时间复杂度：O(N)空间复杂度：O(1)时间复杂度：O(2N)空间复杂度：O(N

11、)O(2N)O(N)递 归 算 法D i g u i s u a n f aD i g u i s u a n f a汉诺塔游戏汉诺塔游戏的装置是一块铜板，上面有三根针，其中最左侧一根针上放着从大到小的n个圆盘。游戏的目标是把所有圆盘从最左侧一根针上移动到最右侧一根针上，中间一根针作为过渡。游戏规定每次只能移动一个圆盘，并且大盘子不能压在小盘子上面。抽象与建模ABC123ABCABCABCABCABCABCABCABCAC，AB，CB，AC，BA，BC，AC将n-1个圆盘从A柱经过C柱移动到B柱将A柱中剩下的一个圆盘移动到C柱将n-1个圆盘从B柱经过A柱移动到C柱将n个圆盘从A柱经过B柱移动到

12、C柱子，建立模型：递 归 算 法D i g u i s u a n f aD i g u i s u a n f a汉诺塔游戏汉诺塔游戏的装置是一块铜板，上面有三根针，其中最左侧一根针上放着从大到小的n个圆盘。游戏的目标是把所有圆盘从最左侧一根针上移动到最右侧一根针上，中间一根针作为过渡。游戏规定每次只能移动一个圆盘，并且大盘子不能压在小盘子上面。设计算法将n有关的问题变成n-1的问题，重复该过程，每次n减1，最后当n=1时，直接移动该圆盘。123实现圆盘移动函数利用建立的模型实现递归调用实现将n个圆盘从A柱经过B柱移动到C柱子重复执行步骤2，直到n=1时，直接移动圆盘，递归结束。move(n

13、,a,b,c)move(n-1,a,c,b)acmove(n-1,b,a,c)将n-1个圆盘从A柱经过C柱移动到B柱将A柱中剩下的一个圆盘移动到C柱将n-1个圆盘从B柱经过A柱移动到C柱当n=1时，ac递 归 算 法D i g u i s u a n f aD i g u i s u a n f a汉诺塔游戏汉诺塔游戏的装置是一块铜板，上面有三根针，其中最左侧一根针上放着从大到小的n个圆盘。游戏的目标是把所有圆盘从最左侧一根针上移动到最右侧一根针上，中间一根针作为过渡。游戏规定每次只能移动一个圆盘，并且大盘子不能压在小盘子上面。编写程序123实现圆盘移动函数move利用建立的模型实现递归调用实

14、现将n个圆盘从A柱经过B柱移动到C柱子重复执行步骤2，直到n=1时，直接移动圆盘，递归结束。move(n,a,b,c)move(n-1,a,c,b)acmove(n-1,b,a,c)当n=1时，acdef move(n,a,b,c):if n=1:print(a,c)else:move(n-1,a,c,b)move(1,a,b,c)move(n-1,b,a,c)move(3,A,B,C)递 归 算 法D i g u i s u a n f aD i g u i s u a n f a已知列表li=23,87,3,98,45,35,70,求其最大值？1利用max()函数直接求解2利用递归实现？d

15、ef listmax(a,n):if n=1:return a0 else:m=listmax(a,n-1)if man-1:m=an-1 return m抽象与建模求n个长度的列表n中的最大值先求n-1个元素中的最大值接着将其与第n个元素作比较，并返回较大值长度为1时，该元素即为最大值设计算法1、实现求列表元素最大值的函数listmax(a,n)a表示列表，n表示列表长度2、先求n-1个元素的最大值listmax(a,n-1)3、将其与第n个元素作比较4、确定递归出口，长度为1时，返回该元素编写程序递 归 算 法D i g u i s u a n f aD i g u i s u a n f

16、 a已知列表li=23,87,3,98,45,35,70,求其最大值？def listmax(a,n):if n=1:return a0 else:m=listmax(a,n-1)if man-1:m=an-1 return m思考：如何利用栈实现“递”和“归”？递 归 算 法D i g u i s u a n f aD i g u i s u a n f a通过重复将问题分解为同类子问题而解决问题的方法，通过函数自己调用自己来实现。概念概念大事化小，小事化了思想思想递归和迭代？和迭代？递归公式和递归出口条件条件递归和和栈？递归是重复调用函数自身实现循环；迭代是函数内某段代码实现循环。练一练猴子吃桃问题：一只猴子摘了一堆桃子，具体多少它没数。猴子第一天吃了总数的一半多一个，第二天吃了剩余桃子的一半多一个，直到第十天，猴子发现只剩1个桃子了。设计一个递归算法，编程计算猴子总共摘了几个桃子，请在划线处填入合适的代码。def fun(n)：if _：return 1else：return _n=10n=10f(n)=(f(n+1)+1)*2f(n)=(f(n+1)+1)*2