微项目5 用递归算法优化程序

微项目5 用递归算法优化程序 1 学习目标 1、了解递归的定义 2、掌握递归算法的思路与过程 3、探究递归算法的优势 4、学会用递归的算法解决实际问题 先行组织 递归算法 现在，我们把问题反过来思考 f(5)=f(4)*5 f(4)=f(3)*4 f(3)=f(2)*3 f(2)=f(1)*2 f(1)=f(0)*1 递推 问题逐渐缩小 回归 大问题的解决中嵌套着与原问题相似的规模较小的问题。 这种解决问题的方式在计算机科学中称为递归，通过函数自己调用自己来实现，即一个函数在其定义中直接或间接调用自身的一种方法。 递归算法 1.大问题能分解成结构相似且规模较少的问题，这些小问题的阶可以方便地构造出大问题的解； 2.当递归到达某个边界时，当递归到达某个边界，如问题规模缩减为0或1时，能直接得解。这个边界被称为递归出口。 ·能采用递归算法解决的问题特征 因此，在设计递归算法时，要满足两个条件： 确定递归公式和递归结束条件。 递归算法 1（n=0） n*f(n-1)（n>0） f(n) 5！= 5 * 4！ 4！= 4 * 3！ 3！= 3 * 2！ 2！= 2 * 1！ 1！= 1 * 0！ 0！= 1 递推：分解问题 回归：代值求解 任务一：利用递归思想设计一个函数f，用来计算5的阶乘 def f(n): if n==0: ___________ else: ___________ return f f=1 f=n*f(n-1) 递归算法 递归程序的执行过程 1.在递推阶段，把较复杂的问题的求解递推到一些简单问题的求解。必须要有终止递推的情况。 2.在回归阶段，当获得最简单情况的解后，逐级返回依次得到稍复杂问题的解。 递归算法 迭代：由旧值不断推出新值的过程。它包括三个方面： ①确定迭代变量； ②建立迭代关系式； ③控制迭代过程，使程序能够停止下来。 递归：是一种缩小问题规模，进而构造出整个问题解的思想方法。 ①递推 ②回归 迭代难点：建立正确的迭代公式，通常要借助循环语句。 递归难点：思想比较难以理解，递归程序的效率相对不高。 辨析迭代与递归： 递归算法——斐波那契数列 任务一：兔子问题（斐波那契数列） 假定我们有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始怀孕（真实情况是六个月左右），在第二月结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每只雌兔在开始繁殖后每月都产下一对兔子，假定没有兔子死亡，在n个月后总共有多少对兔子？ f1 = 1 f2 = 1 fn=fn-1+fn-2(当n>2时) 时间 0 1月 2月 3月 4月 5月 6月 …… 幼兔 1 成兔 0 总数 1 请列出求解兔子总对数fn的数学表达式： 时间 0 1月 2月 3月 4月 5月 6月 …… 幼兔 1 0 1 1 2 3 5 成兔 0 1 1 2 3 5 8 总数(fn) 1 1 2 3 5 8 13 递归算法——斐波那契数列 递归定义的表达式为：f(n)= 1 n<=2 f(n-1)+f(n-2) n>2 def fib(n): if n == 1 or n == 2: return 1 else: return fib(n-1) + fib(n-2) n=int(input('请输入月份：')) for i in range(1,n+1): print(fib(i)) 递归算法——汉诺塔游戏 汉诺塔游戏 汉诺塔游戏的装置是一块铜板，上面有三根针，其中最左侧一根针上放着从大到小的n个圆盘。 游戏的目标是把所有的圆盘从最左侧一根针上移动到最右侧一根针上，中间一根针作为过渡。 游戏规定每次只能移动一个圆盘，并且大盘子不能压在小盘子上面。 递归算法——汉诺塔游戏 汉诺塔游戏 启始针A 过渡针B 目标针C 一个盘子: 二个盘子: 三个盘子呢？ n个盘子呢？ 将n-1个盘子从A柱经过C柱移动到B柱 将A柱中剩下的一个盘子移动到C柱 将n-1个盘子从B柱经过A柱移动到C柱 n-1个看成一个整体 A->C 2号：A->B 1号：A->C 2号：B->C 递归算法——汉诺塔游戏 将n-1个盘子从A柱经过C柱移动到B柱 将A柱中剩下的一个盘子移动到C柱 将n-1个盘子从B柱经过A柱移动到C柱 【设计算法】 1.定义一个实现盘子移动的函数move。 如将n个盘子从A柱经过B柱移动到C柱，可调用函数move(n, a, b, c)， 其中，n表示A柱上的盘子个数，a、b、c分别表示A柱、B柱、C柱。 2.当n=1时，直接移动盘子，递归结束。 move(n-1, a,