第十四章迭代和递归.docx

第十四章迭代和递归一、迭代1 .迭代的特点迭代是一种根据反馈不断重第的过程，其最终目的是为了使结果更符合目标的需求。在计算机中我们也经常使用到这种方法，让计算机重更执行一段指令或代码，这组指令或代码每执行一次，都会从原值中推导出一个新值，2 .迭代的三要素：(1)迭代变量：即从旧值中推导出的新值(2)迭代关系式：即用旧值推导出新值的公式或方法(3)控制迭代过程：即迭代必须有结束条件。3 .迭代案例及分析3.1 牛顿迭代法求a的平方根基本思路：先估测一个近似值X,然后不断令X等于X和a/x的平均数。经过多次迭代之后，X的值将逐渐逼近a的平方根。这种方法只能无限接近平方根，对完全平方数往往无法得出整数根结果。迭代三要素分析：迭代变量:近似值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 欧几里得算法求最大公药数7又称辗转相除法)defgcd(m,n):whilen!=0:m,n=njm%nreturnmprint(gcd(24,15)二、递归1 .递归的特点有一类问题的解法具有这样的特征,在大问题的解决中嵌套着与原问题相似的规模较小的问题，这种解决问题的方式在计算机科学中称为递归，通过函数自己调用自己实现。计算机在执行递归程序时，是通过栈的调用来实现的。递归算法的执行过程可以拆分成两个阶段：(1)递推:将原问题推导到问题边界，每层向下递推时都需要将当前层状态入栈；(2)回归:从边界将结果层层返回，每层向上回归时都需要从栈中取出上一层状态，当栈为空时，回归结束。图521递归调用过程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个圆盘。游戏目标是把所有圆盘从最左侧柱上移动到最右侧柱上，中间的柱作为过渡。游戏规定每次只能移动一个圆盘，且大圆盘不能压在小圆盘上面。递归条件分析：递归公式：“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 .对于同一个问题，用迭代处理的效率一定优于用递归处理，但递归的代码可读性往往更好。