漢諾塔問題

漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說的益智玩具。梵天創(chuàng)造世界的時(shí)候做了三根柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定睡陪，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤夕凝。（以上介紹來自百度百科）

這是一個(gè)五層的漢諾塔示意gif圖：

hanoi.gif

假如要讓我們用程序模擬這個(gè)過程。應(yīng)該怎樣去做呢?

首先可以把每一個(gè)柱子具象化為數(shù)組码秉，三個(gè)柱子就是三個(gè)數(shù)組逮矛。其實(shí)具象化為棧比較好， 因?yàn)橹又荒軓淖钌隙巳〕鲎仓荒軓淖钌隙朔湃胄攵Γ俏覀冎饕懻摑h諾塔，不再做棧的實(shí)現(xiàn)府蔗，相應(yīng)的晋控，我們對(duì)數(shù)組進(jìn)行規(guī)定，只進(jìn)行pop和push操作姓赤，這樣我們也能得到類似棧的效果赡译。(實(shí)際上在JS中，如果不借助node-gyp用C++實(shí)現(xiàn)棧結(jié)構(gòu)不铆，用JS數(shù)組實(shí)現(xiàn)棧結(jié)構(gòu)也是最簡(jiǎn)單的)

首先我們定義三根柱子:

// JavaScript
let a = []            // 假設(shè)a為源柱
let b = []            // 中間柱
let c = []            // 假設(shè)c為目標(biāo)柱
let count = 0         // count用于計(jì)算總共移動(dòng)的次數(shù)

# Python
a = []                # 假設(shè)a為源柱
b = []                # 中間柱
c = []                # 假設(shè)c為目標(biāo)柱
count = 0             # count用于計(jì)算總共移動(dòng)的次數(shù)

1.僅有一個(gè)圓盤需要被移動(dòng)的情況

現(xiàn)在我們假設(shè) a數(shù)組中存放著一個(gè)數(shù) a = [1], 那么要把 a中的 一個(gè)大小為1的盤子移動(dòng)到 c中蝌焚，我們只需要直接做這個(gè)移動(dòng)操作： a → c ，即一步即可完成漢諾塔誓斥， 進(jìn)行移動(dòng)后三個(gè)數(shù)組分別為:

• a == [ ]
• b == [ ]
• c == [1]

相應(yīng)的, 我們需要定義“移動(dòng)”圓盤的代碼實(shí)現(xiàn)：

// JavaScript
/**
 * @function 在兩根柱子間移動(dòng)一片圓盤
 * @param {需要移動(dòng)的源數(shù)組} source 
 * @param {要移動(dòng)到的目標(biāo)數(shù)組} target 
 */
const move = (source, target) => {
  target.push(source.pop())             // 用目標(biāo)數(shù)組push 源數(shù)組的pop值來抽象移動(dòng)
  count ++                              // 每移動(dòng)一次總移動(dòng)次數(shù)count 自加一次
}

# Python
def move(source: list, target: list) -> None:    
    global count                      # 引用全局的count變量
    target.append(source.pop())       # 進(jìn)行移動(dòng)
    count = count + 1                 # 移動(dòng)次數(shù)+1

則我們第一步的函數(shù)可以簡(jiǎn)單定義:

// JavaScript
const once = (one ,two, three) => {
  move(one, three)
}
once (a, b, c)  //直接調(diào)用

# Python
def once(one: list, two: list, three: list) -> None:
    move(one, three)
once(a, b, c)  # 直接調(diào)用

2.假設(shè)兩層的漢諾塔要怎么做呢只洒？

// JavaScript
const twice = (one, two, three) => {
  once(one, three, two)    // 首先將第一個(gè)最小的圓盤移動(dòng)到第二根柱子
  move(one, three)          // 將剩下的最大的圓盤移動(dòng)到第三根柱子
  once(two, one, three)   // 將第一次移動(dòng)的圓盤移動(dòng)到第三根柱子上
}

# Python
def twice(one: list, two: list, three: list) -> None:
    once(one, three, two)
    move(one, three)
    once(two, one, three)
  

兩層的情況我們必須考慮的是，要保證大圓盤在小圓盤下劳坑，我們要借助一個(gè)中間柱子來暫時(shí)存放小的圓盤毕谴，然后移動(dòng)大圓盤到目標(biāo)的柱子，再將小圓盤移動(dòng)到目標(biāo)柱。

3.三層的情況

// JavaScript
const third = (one, two, three) => {
  twice(one, three, two)
  move(one, three)
  twice(two, one, three)
}

# Python
def third(one: list, two: list, three: list) -> None: 
    twice(one, three, two)
    move(one, three)
    twice(two, one, three)

到第三層涝开，我們可以理解為循帐，先將上面的兩層移動(dòng)到第二根柱子，這樣我們才能把最大的底座移動(dòng)到第三根柱子上忠寻，然后再將第二根柱子上的兩塊圓盤惧浴， 借助第一根柱子（此時(shí)把它看做中轉(zhuǎn)柱）移動(dòng)到第三根柱子。

4.四層的情況

// JavaScript
const fourth = (one, two, three) => {
  third(one, three, two)
  move(one, three) 
  third(two, one, three)
}

# Python
def fourth(one: list, two: list, three: list) -> None:
    third(one, three, two)
    move(one, three)
    third(two, one, three)

同理奕剃，我們的需要是，先把最下面的最大的圓盤移動(dòng)到目標(biāo)柱捐腿，為此纵朋，我們需要把上面的三層圓盤先移動(dòng)到第二根柱子上，怎么移動(dòng)呢茄袖？將第三根柱子暫時(shí)當(dāng)做中間柱操软，將第二根柱子看做目標(biāo)柱，其實(shí)就是調(diào)用第三次的方法宪祥！然后將最大的圓盤移動(dòng)到第三根柱子上聂薪，接著把第二根柱子上的圓盤借助第一根柱子做中轉(zhuǎn)柱 移動(dòng)到第三根柱子上。

5.規(guī)律

發(fā)現(xiàn)規(guī)律了嗎?其實(shí)我們幾步都在做同樣的事情!
那么就天然符合遞歸!

// JavaScript
const hanoi = (n, src, sav, tar) => {
  if (n == 1) {
    move(src, tar)
  } else {
    hanoi(n - 1, src, tar, sav)
    move(src, tar)
    hanoi(n - 1, sav, src, tar)
  }
}

# Python
def hanoi(n: int, src: list, sav: list, tar: list) -> None:
    if n == 1:
        move(src, tar)
    else:
        hanoi(n - 1, src, tar, sav)
        move(src, tar)
        hanoi(n - 1, sav, src, tar)

n用作遞歸的結(jié)束條件蝗羊，其實(shí)n表示的就是問題規(guī)模藏澳，可以看到，每一次我們執(zhí)行完hanoi耀找，問題的規(guī)模都會(huì)縮小一次!
調(diào)用方法:

// 給a柱子添加圓盤翔悠，由大到小排列
for (let i = 4; i >= 0; i--) {
  a.push(i)
}

hanoi(a.length, a, b, c)  // 調(diào)用

# 給a柱子添加圓盤，由大到小排列
for index in reversed(range(0, 4)):
    a.append(index)

hanoi(len(a), a, b, c)