復雜遞歸問題：漢諾塔

• 漢諾塔問題是法國數(shù)學家Edouard Lucas于1883年， 根據(jù)傳說提出來的。
• 傳說在一個印度教寺廟里， 有3根柱子， 其中一根套著64個由小到大的黃金盤片， 僧侶們的任務就是要把這一疊黃金盤從一根柱子搬到另一根， 但有兩個規(guī)則：一次只能搬1個盤子大盤子不能疊在小盤子上

分解為遞歸形式

我們還是從遞歸三定律來分析河內(nèi)塔問題
基本結(jié)束條件（最小規(guī)模問題），如何減小規(guī)模，調(diào)用自身

• 假設我們有5個盤子， 穿在1#柱， 需要挪到3#柱
  如果能有辦法把最上面的一摞4個盤子統(tǒng)統(tǒng)挪到2#柱，那問題就好解決了：
  把剩下的最大號盤子直接從1#柱挪到3#柱

• 再用同樣的辦法把2#柱上的那一摞4個盤子挪到3#柱，就完成了整個移動

  
  
  
  

  接下來問題就是解決4個盤子如何能從1#挪到2#？
  此時問題規(guī)模已經(jīng)減?。?/p>

• 同樣是想辦法把上面的一摞3個盤子挪到3#柱，把剩下最大號盤子從1#挪到2#柱，再用同樣的辦法把一摞3個盤子從3#挪到2#柱
• 一摞3個盤子的挪動也照此：分為上面一摞2個，和下面最大號盤子
• 那么2個盤子怎么移動？
• 不行， 就再分解為1個盤子的移動

遞歸思路

• 將盤片塔從開始柱， 經(jīng)由中間柱， 移動到目標柱：
  首先將上層N-1個盤片的盤片塔，從開始柱，經(jīng)由目標柱，移動到中間柱；
  然后將第N個（最大的）盤片，從開始柱，移動到目標柱；
  最后將放置在中間柱的N-1個盤片的盤片塔，經(jīng)由開始柱，移動到目標柱。
• 基本結(jié)束條件， 也就是最小規(guī)模問題是：
  1個盤片的移動問題