资源简介 (共12张PPT)迭代算法与递归算法选修一:数据结构探究一:写一段程序实现求 n!迭代是重复反馈过程的活动,其目的通常是为了使结果符合目标要求n=5result=n #第一次迭代result=n*4 #第二次迭代result=n*3 #第三次迭代result=n*2 #第四次迭代result=n*1 #第五次迭代迭代关系式探究一:迭代的概念迭代算法:①重复反馈的过程②迭代过程:对迭代过程的重复③每一次迭代结果会被用来作为下一次迭代的初始值探究一:迭代的概念迭代算法解决问题过程:①确定迭代变量。迭代算法处理的问题时,由旧值递推出新值的变量称为迭代变量。②建立迭代关系式(数值关系)。从变量的前一个值推出其下一个值的公式(或关系)。③控制迭代过程(结束条件)。迭代过程在经过若干次重复执行以后要能结束,因此,要设定迭代结束的条件。探究二:迭代算法求a的平方根迭代算法:①确定迭代变量②建立迭代关系式③控制迭代过程迭代法求a的平方根:①估计近似值x,令x等于x和a/x的平均数②x的值逼近于a的平方根,当误差小于时,将x的值作为a的平方根探究二:迭代算法求a的平方根迭代算法:①确定迭代变量②建立迭代关系式③控制迭代过程每次迭代结果将作为下一次迭代的初始值1(n=1)n*fac(n-1)(n≠1)fac(n)探究三:递归算法求 n!递归:大问题中嵌套小问题,通过调用自身,不断降低问题的规模,进而求解n = 55!=5*4!4!=4*3!3!=3*2!2!=2*1!1 ! = 1递推:分解问题回归:代值求解fac(4)4*fac(3)第1次调用第2次调用3*fac(2)第3次调用2*fac(1)第4次调用1返回值1返回值1返回值2返回值6探究三:递归过程探究三:递归算法求 n!递归:大问题中嵌套小问题,通过调用自身,不断降低问题的规模,进而求解1(n=1)n*fac(n-1)(n≠1)fac(n)设计递归算法:确定递归公式和递归结束条件探究四:如何用栈实现递归1*fac(0)2*fac(1)3*fac(2)4*fac(3)5*fac(4)fac(1)fac(2)fac(3)fac(4)fac(5)通过不断的调用自己缩小问题规模,进而求解。空间复杂度大探究五:辨析迭代与递归迭代:由旧值不断推出新值的过程。它包括三个方面:①确定迭代变量;②建立迭代关系式;③控制迭代过程,使程序能够停止下来。递归:是一种缩小问题规模,进而构造出整个问题解的思想方法。①递推 ②回归迭代难点:建立正确的迭代公式,通常要借助循环语句。递归难点:思想比较难以理解,递归程序的效率相对不高。探究五:辨析迭代与递归斐波那契数列是这样一个数列:1,1,2,3,5,8,13,21,34,…,其定义如下:f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)(n>=2)。编程求f(40)的值迭代程序f0=0f1=1n=2while n<=40:f=f1+f0f0=f1f1=fn=n+1print(f1)递归程序def fib(n):if n<1:return 0elif n==1:return 1else:return fib(n-1)+fib(n-2)print(fib(40)) 展开更多...... 收起↑ 资源预览