文章也同时在简书更新

汉诺塔问题(Hanoi Tower）

汉诺塔问题的描述就是有三根柱子，其中一根从上至下按照从小到大的顺序叠放着若干圆盘，我们的目标就是借助另外两根空柱子，把这一碟圆盘移到另外任意一根柱子上。在移动端过程中，编号较大的圆盘只能在较小的下面，而不能在上面。例如3可以在1，2的下面，但不能在1，2的上面。

解决汉诺塔问题的一个很好的思路就是利用递归，把n个圆盘移到另外一根柱子上需要先把底盘上方的n-1个圆盘进行移动，而移动这n-1个又需要先移动更上面的n-2个，如此循环至最开始的只有一个圆盘的情况。

上述思路的核心就是把一个复杂问题分解成若干较小的问题，而较小的问题的模型和大问题的相同，直到最后到达一个临界点，该临界点处问题的解决非常简单。这种把大问题不断分解成较小的子问题的思路与递归契合，而最终的临界点条件满足后，我们就能向上回溯，从最简单的情况到最复杂的情况，一层层地解决。

算法简述

首先，递归移动上方的n-1个圆盘到一根“合适”的柱子上
接着，移动底盘到另一根“合适”的柱子，简单的一步操作
最后，把这n-1个圆盘叠加在底盘上，与第一点的递归操作相同

算法伪代码如下：

hanoi(n) {
    if (n==0) {
        return;
    }
    
    if (n==1) {
        move(n);
        return;
    }
    
    hanoi(n-1);
    move(n);
    hanoi(n-1);
}

在实际编写过程中，我们更多地是需要考虑如何把每一步过程详细地表达出来，我们可以在move(n)函数中打印相关信息，即n号圆盘从from柱子移动到to柱子。

如果由人工操作，只要告诉我们应该移动哪个圆盘，按照大编号在下的规则，我们就很容易看出应该把这个圆盘移到哪个柱子上。因为n号圆盘在移动时，你不能放在含有比它小的圆盘的柱子上，只能放在另外一根上面，这一点很直观。

但是如果要把该过程打印出来，让机器来进行柱子的判断还是比较复杂的，因此我们最好把移动的起点，终点，中间暂存的柱子也加入递归函数中，即加入三根柱子的实时状态。于是伪代码就变成了如下：

void hanoi(n, from, to, tmp) {
    if (n == 0) {
        return;
    }
    
    if (n == 1) {
        moveBottom(n, from, to);
        return;
    }
    
    hanoi(n-1, from, tmp, to);
    moveBottom(n, from, to);
    hanoi(n-1, tmp, to, from);
}