第十四章迭代和递归.docx

上传人:p** 文档编号:563947 上传时间:2023-11-02 格式:DOCX 页数:3 大小:30.99KB
下载 相关 举报
第十四章迭代和递归.docx_第1页
第1页 / 共3页
第十四章迭代和递归.docx_第2页
第2页 / 共3页
第十四章迭代和递归.docx_第3页
第3页 / 共3页
亲,该文档总共3页,全部预览完了,如果喜欢就下载吧!
资源描述

《第十四章迭代和递归.docx》由会员分享,可在线阅读,更多相关《第十四章迭代和递归.docx(3页珍藏版)》请在第壹文秘上搜索。

1、第十四章迭代和递归一、迭代1 .迭代的特点迭代是一种根据反馈不断重第的过程,其最终目的是为了使结果更符合目标的需求。在计算机中我们也经常使用到这种方法,让计算机重更执行一段指令或代码,这组指令或代码每执行一次,都会从原值中推导出一个新值,2 .迭代的三要素:(1)迭代变量:即从旧值中推导出的新值(2)迭代关系式:即用旧值推导出新值的公式或方法(3)控制迭代过程:即迭代必须有结束条件。3 .迭代案例及分析3.1 牛顿迭代法求a的平方根基本思路:先估测一个近似值X,然后不断令X等于X和a/x的平均数。经过多次迭代之后,X的值将逐渐逼近a的平方根。这种方法只能无限接近平方根,对完全平方数往往无法得出

2、整数根结果。迭代三要素分析:迭代变量:近似值X;迭代关系式:x=(x+ax)2;控制迭代过程:前后两次产生的X的差的绝对值小于10-5a=3x=a/2whileabs(x+a)2-x)0.00001:=(x+a)2Print(aJ1的平方根为ll,round(x+ax)2,4)3.2 斐波那契数列求和提示:斐波那契数列:1,12358,13,21.迭代三要素分析:1迭代变量:an迭代关系式:an=an+an-23控制迭代过程:n=15al=a2=1sum=0foriinrange(15):#求前15位斐波那契数的和sum=sum+alal,a2=a2,al+a2print(sum)3.3 欧几

3、里得算法求最大公药数7又称辗转相除法)defgcd(m,n):whilen!=0:m,n=njm%nreturnmprint(gcd(24,15)二、递归1 .递归的特点有一类问题的解法具有这样的特征,在大问题的解决中嵌套着与原问题相似的规模较小的问题,这种解决问题的方式在计算机科学中称为递归,通过函数自己调用自己实现。计算机在执行递归程序时,是通过栈的调用来实现的。递归算法的执行过程可以拆分成两个阶段:(1)递推:将原问题推导到问题边界,每层向下递推时都需要将当前层状态入栈;(2)回归:从边界将结果层层返回,每层向上回归时都需要从栈中取出上一层状态,当栈为空时,回归结束。图521递归调用过程

4、2 .递归解决问题需要满足两个条件(1)递归公式:将规模为n的问题缩小为规模为n-1的问题的方法递归边界:当n缩小到一定值时,可以直接给出结果的时候3.递归案例及解析3.1求n阶乘结果提示:n!=l*2*3*4*5*.*(n-l)*n递归条件分析U递归公式:fac(n)=n*fac(n-l)递归边界:当n=l时,即fac(l)=ldeffac(n):ifn=1:return1else:returnn*fac(n-l)print(fac(15)图523 3个圆盘的汉诺塔模型3 .2汉诺塔问题汉诺塔游戏的装置是一块铜板,上面有三根柱,其中最左侧的一根柱上放着从大到小的n个圆盘。游戏目标是把所有圆盘

5、从最左侧柱上移动到最右侧柱上,中间的柱作为过渡。游戏规定每次只能移动一个圆盘,且大圆盘不能压在小圆盘上面。递归条件分析:递归公式:“n层汉诺塔”问题可以分解为:L层”从a到b;2.“1”层从a到c;3.“n-1”层从b到c;递归边界:当n=l时,直接从a到Cdefhanoi(n,a,bjc):#a起始柱,b中间柱,c目标柱ifn=l:print(,-.format(ajc)returnelse:hanoi(n-l,ajcjb)hanoi(lja,bjc)hanoi(n-l,bjajc)returnhanoi(3j,A,j,B,C)三、迭代和递归的关系1 .迭代的迭代公式和递归的递归公式,本质上都是递推公式C2 .当一个问题可以用迭代处理,则这个问题也一定可以用递归处理,反之也成立。3 .对于同一个问题,用迭代处理的效率一定优于用递归处理,但递归的代码可读性往往更好。

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!