汉诺塔问题

汉诺塔问题

汉诺塔(Towers of Hanoi) 问题:

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

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

问需要多次移动才能将所有圆盘移至 C 杆。

这个问题需要通过递归的思想来解决,将 A 中的 N 个盘移至 C 的问题转变为将 A 中的 N-1 个盘移至 B 中,再将剩下的盘移至 C,最后把 B 中的 N-1 个盘移至 C。

当 N = 3 时,先把前两个盘移从 A 移至 B,然后把 A 中最后一个盘移至 C,最后将 B 中的两个盘移至 C。

当 N = 4 时,参考 N = 3 的场景,先将前三个盘从 A 移至 B,然后把 A 中最后一个盘移至 C,最后将 B 中的三个盘移至 C。

![](https://blog-1255677601.cossh.myqcloud.com/blog/2019-07-16-Jul-16-2019%2016-13-17.gif)

可以通过这个网站体验下

具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let times = 0;
const hanoiTowers = (n, originTower, destTower, bufferTower) => {
if (n > 0) {
// 将 n-1 个盘从 A(originTower)移至 B(bufferTower)
const timesA = hanoiTowers(n-1, originTower, bufferTower, destTower);

console.info(`第 ${++times} 次移动:将第 ${n} 个盘从 ${originTower} 移至 ${destTower}`);

// 将 n-1 个盘从 B(bufferTower)移至 C(destTower)
const timesB = hanoiTowers(n-1, bufferTower, destTower, originTower);

// +1 指将 A(originTower)中最后一个盘移至 C(destTower)中
return timesA + timesB + 1;
} else {
return n;
}
}