Java用递归方法解决汉诺塔问题详解

问题描述

汉诺塔问题的经典描述是：在有三根柱子的情况下，有三个大小不同的盘子从下往上按从大到小的顺序放在柱子A上，要将这三个盘子移动到柱子C上，要求每次只能移动一个盘子，且大盘子不能放在小盘子上面。

解题思路

汉诺塔问题是递归问题的典型，使用递归可以比较简单地解决该问题。

我们可以将解决汉诺塔问题的方法抽象为三个步骤：

1. 将 A 上的 n-1 个盘子通过将它们移动到第二根柱子B上而转移为子问题。
2. 直接将 A 上的最大盘子移动到柱子 C 上。
3. 将 B 上的n-1个盘子通过将它们移动到第三根柱子 C 上而转移为子问题。

用递归思想，每次仅考虑 n-1 个盘子的移动，直到抵达最后一个最大的盘子，也就解决了整个问题。

代码实现

Java 代码实现如下：

public class HanoiTower {

    public static void hanoi(int n, char A, char B, char C) {
        if (n == 1) {
            System.out.println(A + " -> " + C);
        } else {
            hanoi(n - 1, A, C, B);
            System.out.println(A + " -> " + C);
            hanoi(n - 1, B, A, C);
        }
    }

}

其中，n 表示盘子的数量，A、B、C分别表示三个柱子。

示例说明

以 n = 3 为例，考虑如何将三个盘子从柱子 A 移动到柱子 C。

```
初始状态：A(3,2,1)，B()，C()

A B C
- - -
3 - -
2 - -
1 - -

1. 将 A 上的 2 个盘子通过将它们移动到第二根柱子B上而转移为子问题。这时，状态变为：

A B C
- - -
3 - -
2 1 -
1 2 -

1. 直接将 A 上的最大盘子 3 移动到柱子 C 上。这时，状态变为：

A B C
- - -
- 3 -
2 1 -
1 2 -

1. 将 B 上的 2 个盘子通过将它们移动到第三根柱子C上而转移为子问题。这时，状态变为：

A B C
- - -
- 3 -
- 2 1
1 - 2

1. 直接将 A 上的盘子 2 移动到柱子 C 上。这时，状态变为：

A B C
- - -
- 3 2
- - 1
1 - -

1. 将 B 上的 1 个盘子通过将它移动到第三根柱子C上而转移为子问题。这时，状态变为：

A B C
- - -
- - 3
- 1 2
- - 1

1. 直接将 A 上的盘子 1 移动到柱子 C 上。这时，状态变为：

A B C
- - -
- - 3
- - 2
- - 1

最终，所有盘子已经从柱子 A 移动到柱子 C 上。

可以发现，这个递归方法实际上是一颗二叉树，每个结点表示一个状态，叶子结点表示最终状态。可以使用递归的回溯实现。