Java 数据结构与算法系列精讲之汉诺塔

Java 数据结构与算法系列精讲之汉诺塔

简介

汉诺塔是一种经典的问题，在计算机科学中也非常常见，它可以帮助我们理解递归算法的核心思想。本文将对汉诺塔问题进行详细介绍，讲述解题方法和具体实现。

问题描述

汉诺塔问题的描述是这样的：有三根柱子 A、B、C，其中 A 柱子上面有由小到大排列的 N 个盘子（编号从上到下依次为 1、2、3、...、N）。现在我们想要将 A 柱子上的所有盘子移动到 C 柱子上，但是每次只能移动一个盘子，并且要保证大盘子不能在小盘子上面。

解题思路

从 A 柱子到 C 柱子，最简单的方法是，将 A 柱子上的 N-1 个盘子移动到 B 柱子上，然后将 A 柱子上的最后一个盘子移动到 C 柱子上，再将 B 柱子上的 N-1 个盘子移动到 C 柱子上。这个方法可以通过递归实现。

代码实现

我们可以定义一个递归函数，参数包括要移动盘子的数量 n，以及三个柱子 A、B、C。代码实现如下：

public class HanoiTower {
    public static void move(int n, char a, char b, char c) {
        if (n == 1) {
            // 只有一个盘子，直接移到 C 柱子上
            System.out.println("Move disk " + n + " from " + a + " to " + c);
        } else {
            // 先将 A 柱子上的 n-1 个盘子移到 B 柱子上
            move(n-1, a, c, b);
            // 将 A 柱子上最后一个盘子移到 C 柱子上
            System.out.println("Move disk " + n + " from " + a + " to " + c);
            // 最后将 B 柱子上 n-1 个盘子移到 C 柱子上
            move(n-1, b, a, c);
        }
    }

    public static void main(String[] args) {
        HanoiTower.move(3, 'A', 'B', 'C');
    }
}

示例说明

我们以汉诺塔问题中有 3 个盘子为例，运行上面的代码得到以下输出：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

以上输出展示了将 3 个盘子从 A 移动到 C 的具体步骤。每一步输出都显示了要移动的是哪个盘子，从哪个柱子移动到哪个柱子。

再以汉诺塔问题中有 4 个盘子为例，运行上面的代码得到以下输出：

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
Move disk 4 from A to C
Move disk 1 from B to C
Move disk 2 from B to A
Move disk 1 from C to A
Move disk 3 from B to C
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

以上输出展示了将 4 个盘子从 A 移动到 C 的具体步骤。同样地，每一步输出都显示了要移动的是哪个盘子，从哪个柱子移动到哪个柱子。