汉诺塔问题的递归算法

问题简介

汉诺塔问题是一个根据传说形成的数学问题，传说中越南河内的某间寺院里有三根柱子，其中一根上面串有64个盘子，盘子的尺寸由下到上依次变小。要求按照两条规则将所有盘子移动到另一根柱子上：

1. 每次只能移动一个圆盘
2. 大盘不能叠在小盘上面

以上述规则移动这些盘子，预言说当这些盘子移动完毕，世界就会灭亡，这也就是传说中的梵天寺之塔问题。这个传说的真伪暂且不考虑，我们接下来通过递归的思想通过编程去解决这个问题，给出移动盘子的步骤。

关于递归

递归（Recursion）是一种自己重复自己的过程，一般来说如果一个问题可以拆分为一个与自己一样的小问题的时候，可以通过递归算法进行求解。这样的问题使用递归算法来解决较为便利且代码一般不太复杂，但是递归算法也有自身的缺陷，当我们的问题规模增大的时候，递归算法占用的空间就会成倍增加。

问题分析

我们首先以三阶汉诺塔为例进行举例。将三根柱子依此编号为1，2，3柱，A为起始位置，C为目标位置。在问题的开始，A柱上串有三个盘子，我们将其从小到大称为小，中，大盘。

观察图解过程，我们可以发现问题可以分为三步：

第一步，将小盘和中盘从1挪到2上，对应图解的第1～3步。

第二步，将大盘从1挪到3上，对应图解的第4步。

第三步，再将小盘和中盘从2挪到3上，对应图解的第5～7步。

我们可以看出，第一步和第三步本质上相当于一个二阶汉诺塔问题，第一步以1为起点，2为终点，解决了一个二阶汉诺塔，第三步则变为以2为起点，3为终点。

以此类推，二阶汉诺塔问题则可以分解为两个一阶汉诺塔问题，例如若我们将第一步中小盘与中盘从1挪到2视为一个二阶汉诺塔问题，首先将小盘从1挪到3，然后将中盘从1挪到2，最后将小盘从3挪到2。我们可以将每次小盘的挪动看作一阶汉诺塔问题。至此，汉诺塔的问题就可以通过递归思路实现。

要解决一个N阶汉诺塔，首先解决N-1阶汉诺塔问题，然后将最大的盘子挪到目标柱，最后再解决一次N-1阶汉诺塔问题，而N-1阶汉诺塔问题又可以拆分为两个N-2阶汉诺塔······

代码实现

当明白了汉诺塔问题的本质后，代码实现便异常简单，所以直接给出。

// level：汉诺塔的层数，temp：空柱子的位置，target：目标柱子的位置
void solveHanoiProblem(int level, int temp, int target){
    // beginning：汉诺塔的起始位置
    int beginning = 6 - temp - target;
    // 如果只剩下一层汉诺塔，将一层汉诺塔从起始位置挪到目标位置
    if (level == 1)
        System.out.println("Move disk" + level + " from "+ beginning +" to "+ target);
    else {
        // 解决两次低一阶的汉诺塔问题，并把最底部最大的盘子挪到目标桩上
        solveHanoiProblem(level - 1, target , temp);
        System.out.println("Move disk" + level + " from "+ beginning +" to "+ target);
        solveHanoiProblem(level - 1, beginning, target);
    }
}