第二章 递归与分治 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第二章 递归与分治
递归的概念 ■简单地说,递归就是用自己来定义自己。 ■一般地说,一个递归过程P可以表示为基语句 S(不含P和P自身的组合β: P≡β(S,P) ■这样的表示包含了过程不终止的可能,因此递 归算法应更准确地表述为 P≡ if b then Q elseβ(S,P) 其中Q也不包含P,B为递归终止条件。 2021/22 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 递归的概念 ◼ 简单地说，递归就是用自己来定义自己。 ◼ 一般地说，一个递归过程P可以表示为基语句 S(不含P)和P自身的组合β： P β(S, P) ◼ 这样的表示包含了过程不终止的可能，因此递 归算法应更准确地表述为 P if B then Q else β(S, P) 其中Q也不包含P，B为递归终止条件
递归元 ■递归算法的思想是将对较大规模的对象的操作 归结为对较小规模的对象实施同样的操作。 ■这种规模的变化就体现在递归算法的变元中的 类(一个或几个)变元上,这类变元被称之为 递归元。 递归元的变化是在递归定义中确定的,它的变 化应能导致递归算法的终止。 在递归算法的设计中递归元是非常重要的 2021/22 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 递归元 ◼ 递归算法的思想是将对较大规模的对象的操作 归结为对较小规模的对象实施同样的操作。 ◼ 这种规模的变化就体现在递归算法的变元中的 一类(一个或几个)变元上，这类变元被称之为 递归元。 ◼ 递归元的变化是在递归定义中确定的，它的变 化应能导致递归算法的终止。 ◼ 在递归算法的设计中递归元是非常重要的
Hanoi塔问题 ■ Hanoi塔的解可以很自然地看成这样一个过程: (1)先将A上面于是可得到如下的程序 n-1个盘移至C。 void hanoi(int n, int Fr; int To, int as) (2)再将A上剩下 的1个盘移至B Hanoi(n-1, Fro, AsS, To Move(fro, To); (3)最后将C上的 Hanoi(n-1, ASS, To, Fro) n-1个盘移至B 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 Hanoi塔问题 ◼ 例1：Hanoi塔问题：有A、B、C三根柱子。A 上有n个圆盘，自下而上由大到小地叠在一起。 A B C ◼ 现要将A上的全部圆 盘移到B上，并要求： (1)每次只能移动一个 圆盘；(2)任何时刻都 不允许将较大的圆盘 压在较小的圆盘上； (3)圆盘只能在A、B、 C三个柱子间移动。 ◼ Hanoi塔的解可以很自然地看成这样一个过程： (1)先将A上面 n–1个盘移至C。 (2)再将A上剩下 的1个盘移至B。 (3)最后将C上的 n–1个盘移至B。 于是可得到如下的程序： void Hanoi(int n, int Fr, int To, int As) { if (n > 0) { Hanoi(n–1, Fro, Ass, To); Move(Fro, To); Hanoi(n–1, Ass, To, Fro)} }
Hanoi塔问题的时间复杂性 Hanoi塔问题的时间复杂性为O(2n) ■证明:对n归纳证明移动次数move(n)=2n-1。 ■归纳基础:当n=1,move(1)=1=21-1 ■归纳假设:当n≤k,move(n)=2n-1 ■归纳步骤:当n=k+1,移动次数为 move(k+1)=2move(k)+1=2(2k-1)+1 2 k+1 由归纳法可知对任意的n有move(n)=2n-1 2021/221 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 Hanoi塔问题的时间复杂性 ◼ Hanoi塔问题的时间复杂性为O(2n )。 ◼ 证明：对n归纳证明移动次数move(n) = 2n – 1。 ◼ 归纳基础：当n = 1， move(1) = 1 = 2 1 – 1。 ◼ 归纳假设：当n k， move(n) = 2 n – 1。 ◼ 归纳步骤：当n= k + 1，移动次数为 ◼ move(k+1) = 2(move(k)) + 1 = 2(2k – 1) + 1 = 2k+1 – 1 ◼ 由归纳法可知对任意的n有move(n) = 2n – 1