起源：
漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
抽象為數學問題：
如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數
?
解：（1）n == 1
?????? 第1次? 1號盤? A---->C?????? sum = 1 次
?????? (2)? n == 2
?????? 第1次? 1號盤? A---->B
?????? ?第2次? 2號盤? A---->C
?????? 第3次? 1號盤? B---->C??????? sum = 3 次
（3）n == 3
第1次? 1號盤? A---->C
第2次? 2號盤? A---->B
第3次? 1號盤? C---->B
第4次? 3號盤? A---->C
第5次? 1號盤? B---->A
第6次? 2號盤? B---->C
第7次? 1號盤? A---->C??????? sum = 7 次
不難發現規律：1個圓盤的次數 2的1次方減1
2個圓盤的次數 2的2次方減1
? ? ? ? ? ? ? ? ? ? ? ? ?3個圓盤的次數 2的3次方減1
? ? ? ? ? ? ? ? ? ? ? ? ?。? 。?? 。??? 。?? 。?
? ? ? ? ? ? ? ? ? ? ? ? ?n個圓盤的次數 2的n次方減1
?故：移動次數為：2^n - 1
有兩種解法，一種是遞歸，一種是棧。先來看遞歸的實現
- 將 n - 1 個圓盤從 A 移動到 C（借助 B）
- 將第 n 個圓盤從 A 移動到 B
- 將 n - 1 個圓盤從 C 移動到 B（借助 A）
移動次數為 2 的 n 次方 - 1
let count = 0
function move(number, from, to, depend) {console.log(`將第 ${number} 號圓盤從 ${from} 移動到 ${to}`)count++
}
// 將 n 個圓盤從 a 移動到 b 借助 c
function hanoi(n, a, b, c) {if (n === 0) {return}hanoi(n - 1, a, c, b) // 將 n -1 個圓盤從 a 移動到 c，借助 bmove(n, a, b) // 將第 n 個圓盤從 a 移動到 bhanoi(n - 1, c, b, a) // 將 n -1 個圓盤從 c 移動到 b，借助 a
}
hanoi(3, 'A', 'B', 'C')
console.log('移動次數', count)
// 將第 1 號圓盤從 A 移動到 B
// 將第 2 號圓盤從 A 移動到 C
// 將第 1 號圓盤從 B 移動到 C
// 將第 3 號圓盤從 A 移動到 B
// 將第 1 號圓盤從 C 移動到 A
// 將第 2 號圓盤從 C 移動到 B
// 將第 1 號圓盤從 A 移動到 B
// 移動次數 7重構上面，使用一個函數
function hanoiRecursion(n, a, b, c, moves = []) {if (n === 0) {return moves}hanoiRecursion(n - 1, a, c, b, moves) // 將 n -1 個圓盤從 a 移動到 c，借助 bmoves.push([a, b]) // move(n, a, b) // 將第 n 個圓盤從 a 移動到 bhanoiRecursion(n - 1, c, b, a, moves) // 將 n -1 個圓盤從 c 移動到 b，借助 areturn moves
}
let moves = hanoiRecursion(3, 'A', 'B', 'C')
console.log('移動路徑', moves)
console.log('移動次數', moves.length)
// // 移動路徑
// // [
// // ["A", "B"], ["A", "C"], ["B", "C"], ["A", "B"],
// // ["C", "A"], ["C", "B"], ["A", "B"]
// // ]
// // 移動次數 7使用棧其實也需要使用遞歸，只是我們通過 3 個棧，表示三個圓柱，可以實時看對應的效果
// 棧類
class Stack {constructor() {this.count = 0;this.items = {};}// 向棧中插入元素push(element) {this.items[this.count] = element;this.count++;}isEmpty() {return this.count === 0;}size() {return this.count;}get length() {return this.count;}// 從棧中彈出元素pop() {if (this.isEmpty()) {return undefined;}this.count--;const result = this.items[this.count];delete this.items[this.count];return result;}peek() {if (this.isEmpty()) {return undefined;}return this.items[this.count - 1];}clear() {this.items = {};this.count = 0;// 或者// while(!this.isEmpty()) {// this.pop()// }}toString() {if (this.isEmpty()) {return "";} else {let i = 0,len = this.count,result = "";while (i < len) {result += this.items[i];if (i !== len - 1) {result += ",";}i++;}return result;}}
}function hanoi(n, source, dest, depend, a, b, c, moves = []) {if (n === 0) {return}// 將 n - 1 個圓盤從 source 移動到 dependhanoi(n - 1, source, depend, dest, a, c, b, moves) moves.push([a, b])// 將第 n 個圓盤從 source 移動到 destdest.push(source.pop()) // 將 n - 1 個圓盤從 depend 移動到 desthanoi(n - 1, depend, dest, source, c, b, a, moves)
}
function hanoiStack(n) {let source = new Stack()let dest = new Stack()let depend = new Stack()let count = nwhile (count) {source.push(count--)}let moves = []console.log('source: ', source)hanoi(n, source, dest, depend, 'A', 'B', 'C', moves)console.log('source: ', source)console.log('dest: ', dest)console.log('depend: ', depend)return moves
}
console.log(hanoiStack(3))
// source: Stack { count: 3, items: { '0': 3, '1': 2, '2': 1 } }
// source: Stack { count: 0, items: {} }
// dest: Stack { count: 3, items: { '0': 3, '1': 2, '2': 1 } }
// depend: Stack { count: 0, items: {} }
// [
// [ 'A', 'B' ],
// [ 'A', 'C' ],
// [ 'B', 'C' ],
// [ 'A', 'B' ],
// [ 'C', 'A' ],
// [ 'C', 'B' ],
// [ 'A', 'B' ]
// ]
.)
