汉诺塔问题

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至B杆：
每次只能移动一个圆盘；
大盘不能叠在小盘上面。

解法的基本思想是递归。

假设有A、B、C三个塔，A塔有N块盘，目标是把这些盘全部移到B塔。
那么先把A塔顶部的N-1块盘移动到C塔，再把A塔剩下的大盘移到B，最后把C塔的N-1块盘移到B。
每次移动多于一块盘时，则再次使用上述算法来移动。

设f(n)为圆盘数为n的时候所需要整个过程所需要移动的次数，则
f(n) = 2f(n - 1) + 1，又f(1) = 1，易得f(n) = 2 ^ n - 1。
【已知第n-1次时移动f(n-1)次，则计算第n次时“分两部分再相加”，即除最后1个盘之外的其他盘总数的移动次数加上最后1个盘之后盘总数对应的移动次数（其中重复了前一个的步骤，且比其加多1步）。
f(n-1) + (f(n-1)+1) = 2f(n-1)+1】

Lisp版

(define (hannoi n)
  (define (MOVE n from to spare)
    (cond ((= n 0) "Done")
          (else (MOVE (- n 1) from spare to)
                (display from) (display "->") (displayln to)
                (MOVE (- n 1) spare to from))))

  (MOVE n 'A 'B 'C))

// 移动三个盘子时
(hannoi 3)
// 输出
A->B
A->C
B->C
A->B
C->A
C->B
A->B
"Done"

JavaScript版

// 移动n个盘子
// from为起始柱
// to为终点柱
let count = 0
function move(n, from, to, spare) {
  if (n !== 0) {
    // 从起始柱移到中转柱
    move(n - 1, from, spare, to)
    console.log(from + '->' + to)
    count += 1
    // 从中转柱移到终点柱
    move(n - 1, spare, to ,from)
  }
}

// 设定起始柱为A, 终点柱为B, 中转柱为C 
function hannoi(n) {
  move(n, 'A', 'B', 'C')
  console.log('移动次数: ' + count)
  count = 0
}

// 移动两个盘子时
hannoi(2)
// 输出
A->C
A->B
C->B
移动次数: 3

// 移动三个盘子时
hannoi(3)
// 输出
A->B
A->C
B->C
A->B
C->A
C->B
A->B
移动次数: 7

可继续测试验证。从测试结果可见：移动次数呈现一定规律，为2 ^ n - 1。

使用二进制与汉诺塔问题类比
讲解见用二进制来解汉诺塔问题

汉诺塔问题

推荐阅读更多精彩内容