介绍

汉诺塔（港台：河内塔）（Tower of Hanoi）是根据一个传说形成的数学问题：

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

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

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

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

实现

JavaScript

// wiki - https://en.wikipedia.org/wiki/Tower_of_Hanoi
// Recursive Javascript function to solve tower of hanoi

export function TowerOfHanoi (n, from, to, aux, output = []) {
  if (n === 1) {
    output.push(`Move disk 1 from rod ${from} to rod ${to}`)
    return output
  }
  TowerOfHanoi(n - 1, from, aux, to, output)
  output.push(`Move disk ${n} from rod ${from} to rod ${to}`)
  TowerOfHanoi(n - 1, aux, to, from, output)
  return output
}

// Driver code (A, C, B are the name of rods)

// const n = 4
// TowerOfHanoi(n, 'A', 'C', 'B')

参考

• 汉诺塔 - 维基百科，自由的百科全书 (opens new window)