一个古老而又经典的算法-汉诺塔问题

哈诺塔问题相信只要学习计算机的人都知道。这是一个古老而又伟大的问题。在这篇文章中，主要是给出递归解决汉诺塔问题的代码方法。毕竟面试的时候，HR比我们要变态很多，怎么蹂躏我们怎么玩。

一、什么是汉诺塔问题

这个问题来源于印度。有三个金刚石塔，第一个从小到大摞着64片黄金圆盘。现在把圆盘按大小顺序重新摆放在最后一个塔上。并且规定，在小圆盘上不能放大圆盘，在三个塔之间一次只能移动一个圆盘。

image

也就是说将 from 上的圆盘全部移动到 to 上，并且要保证小圆盘始终在大圆盘上。

如何来求解呢？很明显这道题大家都知道使用递归的方式来做。不过如何去考虑递归呢？

在这里我想说一下我个人目前关于递归的理解。递归其实就是一个方程式：f(n) = f(n-1) + a;也就是说在设计递归的时候应该考虑下面三个方面：

（1）求解f(n)的时候，假设f(n-1)已经求解出来了。我们不要去考虑f(n-1)是如何求解出来的。

（2）关键点在于递归的结束条件。

（3）递归往往和分治法是分不开的。对于复杂的递归，往往将递归拆分。然后再合并

整体的递归方法流程是这样的。首先我们要写一个递归方法。

（1）首先判断递归结束时候的操作

（2）递归分解

而本题的汉诺塔就是使用典型的递归思想。首先我们求解f(n)

① 将 n-1 个圆盘从 from -> buffer

image

② 将 1 个圆盘从 from -> to

image

③ 将 n-1 个圆盘从 buffer -> to

image

④以上三步都是为了求解f(n)，最后我们给出递归结束的条件。只有一个圆盘的时候，只需一次移动操作即可。

二、代码实现

public class Hanoi {
    public static void move(int n, String from, String buffer, String to) {
        //第一步：递归结束的条件
        if (n == 1) {
            System.out.println("from " + from + " to " + to);
            return;
        }
        // n-1 个圆盘从 from -> buffer
        move(n - 1, from, to, buffer);
        //将 1 个圆盘从 from -> to
        move(1, from, buffer, to);
        //将 n-1 个圆盘从 buffer -> to
        move(n - 1, buffer, from, to);
    }
​
    public static void main(String[] args) {
        Hanoi.move(3, "石柱1", "石柱2", "石柱3");
    }
}

image