vv13
博客订阅

汉诺塔问题

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

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

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

提示:可将圆盘临时置于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个圆盘时的解题思路:

  1. 前两个圆盘移动到B柱
  2. 最后一个圆盘移动到C柱
  3. 将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。