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)} }