JavaSE递归求解汉诺塔问题的思路与方法

关于JavaSE递归求解汉诺塔问题的思路与方法，应该是这样的：

必要前提

在讲解算法大家之前，我们需要先了解一下汉诺塔问题的规则。汉诺塔问题是一个经典的算法问题，它来源于印度的传说。大概形式就是：有三个柱子，分别记为A、B、C，A柱子上有n个大小不相同的盘子，盘子大小依次从小到大排列。现在要把A柱子上的n个盘子移到C柱子上，但是规定每次只能移动一个盘子，且大盘子不能放在小盘子上面。

递归求解

大家都知道这个问题可以使用递归求解，那么，我们试着分析一下递归的过程吧。

1. 如果只有一个盘子需要从A柱子移动到C柱子上，那么我们只需要直接通过输出语句将其移动过去即可，代码如下所示。

public static void move(char a, char c) {
    System.out.println(a + "-->" + c);
}

1. 如果有2个盘子需要从A柱子移动到C柱子上，那么我们可以将其逐个移动至B柱子，然后将第2个盘子移动至C柱子，最后再把B柱子上的第1个盘子移动至C柱子，代码如下所示。

public static void hanoi(int n, char a, char b, char c) {
    if(n == 1) {
        move(a, c);
    } else {
        hanoi(n-1, a, c, b);
        move(a, c);
        hanoi(n-1, b, a, c);
    }
}

1. 同样的，如果有3个盘子需要移动，那么我们就可以将其逐个移至B柱子，然后将第3个盘子移动至C柱子，然后再从B柱子将前两个盘子移动至C柱子，代码如下所示。

public static void hanoi(int n, char a, char b, char c) {
    if(n == 1) {
        move(a, c);
    } else {
        hanoi(n-1, a, c, b);
        move(a, c);
        hanoi(n-1, b, a, c);
    }
}

通常情况下，如果我们需要将n个盘子从A柱子移动至C柱子，那么我们就可以将其逐步分解为 n-1、1、n-1 三部分问题，然后分别递归求解即可。代码如下所示。

public static void hanoi(int n, char a, char b, char c) {
    if(n == 1) {
        move(a, c);
    } else {
        hanoi(n-1, a, c, b);
        move(a, c);
        hanoi(n-1, b, a, c);
    }
}

在上述代码中，hanoi(n-1, a, c, b)就是将前n-1个盘子从A柱子移动至B柱子上的递归调用。关于基本求解方法，我们可以通过本文的第一条示例来进行理解。

示例一

首先，我们可以试着将2个盘子从A柱子移动至C柱子，运行代码如下所示。

public static void main(String[] args) {
    hanoi(2, 'A', 'B', 'C');
}

程序的输出结果是：

A-->B
A-->C
B-->C

可以看到，我们的程序能够正确的将2个盘子从A柱子移动至B柱子上了。其实，这个过程和之前的描述是一致的。

示例二

再来看一下另一个例子，代码如下所示。

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

程序的输出结果是：

A-->C
A-->B
C-->B
A-->C
B-->A
B-->C
A-->C

可以看到，我们的程序能够正确的将3个盘子从A柱子移动至B柱子上了。同样的，这个过程也是基于上面所讲的思路而实现的。

暂时就讲到这里，希望我的回答能够帮助你理解JavaSE递归求解汉诺塔问题的思路与方法。