太原提高网站排名php网站开发试卷

大体上，要解决一个汉诺塔问题，就需要解决两个更简单的汉诺塔问题

以盘子数量 3 的汉诺塔问题为例

要将 3 个盘子从 A 移动到 C，就要：

1. 将两个盘子从 A 移动到 B（子问题 1）
   1. 为了解决子问题 1，就要解决更简单的子问题 3、4，直到基本情况（即仅移动 1 个盘子）
2. 将 A 最后的盘子移动到 C
3. 将两个盘子从 B 移动到 C（子问题 2）
   1. 为了解决子问题 2，就要解决更简单的子问题 5、6，直到基本情况（即仅移动 1 个盘子）

图示

代码

/*** 汉诺塔问题*/
public class TM0806 {public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {movePlant(A.size(), A, B, C);}/*** @param size      需要移动的盘子的数量* @param start     起始柱子* @param auxiliary 辅助柱子* @param target    目标柱子*/public void movePlant(int size, List<Integer> start, List<Integer> auxiliary, List<Integer> target) {// 当只剩一个盘子时，直接将它从第一个柱子移动到第三个柱子if (size == 1) {target.add(start.remove(start.size() - 1));return;}// 首先将 n-1 个盘子，从第一个柱子移动到第二个柱子movePlant(size - 1, start, target, auxiliary);// 然后将最后一个盘子移动到第三个柱子上target.add(start.remove(start.size() - 1));// 最后将第二个柱子上的 n-1 个盘子，移动到第三个柱子上movePlant(size - 1, auxiliary, start, target);}@Testvoid test() {List<Integer> A = new ArrayList<>();List<Integer> B = new ArrayList<>();List<Integer> C = new ArrayList<>();A.add(3);A.add(2);A.add(1);hanota(A, B, C);Assert.assertEquals(C.get(0).intValue(), 3);Assert.assertEquals(C.get(1).intValue(), 2);Assert.assertEquals(C.get(2).intValue(), 1);}
}