例6-3设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的 描述是:设有3根标号为A,B,C的柱子,在A柱上放着n个盘 子,每一个都比下面的略小一点,要求把A柱上的盘子全部移 到C柱上,移动的规则是:(1)一次只能移动一个盘子;(2) 移动过程中大盘子不能放在小盘子上面;(3)在移动过程中 盘子可以放在A,B,C的任意一个柱子上 问题分析:可以用递归方法求解n个盘子的汉诺塔问题。 基本思想:1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺 塔问题可递归表示为,首先把上边的n-1个盘子从A柱移到B柱 然后把最下边的一个盘子从A柱移到c柱,最后把移到B柱的n 1个盘子再移到c柱。4个盘子汉诺塔问题的递归求解示意图如 图6-4所示
12 例6-3 设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的 描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘 子，每一个都比下面的略小一点，要求把A柱上的盘子全部移 到C柱上，移动的规则是：（1）一次只能移动一个盘子；（2） 移动过程中大盘子不能放在小盘子上面；（3）在移动过程中 盘子可以放在A，B，C的任意一个柱子上。 问题分析：可以用递归方法求解n个盘子的汉诺塔问题。 基本思想：1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺 塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱， 然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n- 1个盘子再移到C柱。4个盘子汉诺塔问题的递归求解示意图如 图6-4所示
图6-4汉诺塔问题的递归求解示意图
13 图6-4 汉诺塔问题的递归求解示意图