汉诺塔问题

汉诺塔是根据一个传说形成的数学问题：

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

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

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

问：如何移？最少要移动多少次？

递归思路

假设有1个盘子时，直接将圆盘从A -> C即可，需要1次。
假设有2个盘子时，挪动圆盘A -> B，A -> C，B -> C，需要3次，其中A视为起始柱子，B可视为转移柱子，C为目标柱子。
假设有3个盘子时，挪动圆盘A -> C，A -> B， C -> B，A -> C，B -> A，B -> C，A -> C，需要7次。
...

若按照这个思路下去，从3个盘子开始，问题就会变得有点绕了，但我们不妨思考一下3个圆盘时的解题思路：

前两个圆盘移动到B柱
最后一个圆盘移动到C柱
将B柱上的两个圆盘移动到C柱

移动3个圆盘的核心思想和2个盘子是一样的，只需要解决移动1个圆盘的问题和2个圆盘的问题，这两个问题我们都可以很简单的算出方法来，那如果是A柱子上有4个圆盘呢？那就将3个圆盘移动到B柱，将最后1个圆盘移动到C柱，再将B柱上的3个圆盘移动到C柱即可，由以上方法可以得出：要将N(N >= 2)个圆盘从A柱子移动到目标柱子，只需要将N - 1个圆盘移动到转移柱子，然后将第N个圆盘从A柱子移动到目标柱子，再将N - 1个圆盘从转移柱子移动到目标柱子即可。

因此我们可以得出一个方法，将N个数量级的问题经过不断的递归，最终只需要解决1个圆盘移动的问题和2个圆盘移动的问题：

let count = 0
function move(N, from, buffer, target) {
    if (N === 1) {
    	count += 1
        console.log(`move ${N} from ${from} to ${target}`)
    } else {
    	move(N - 1, from, target, buffer)
        move(1, from, buffer, target)
        move(N - 1, buffer, from, target)
    }
}
move(5, 'A', 'B', 'C') // count = 31

由算法打印的结果可知，移动次数 = 2次移动N-1个盘子 + 1次移动第N个盘子 = 2 * 2(2^(n - 1) - 1) + 1 = 2^N - 1。

递归思路​

递归思路