漢諾塔問題深度剖析（python實現）

當我們學習一門編程語言的時候，都會遇到遞歸函數這個問題。而學習遞歸的一個經典案例就是漢諾塔問題。通過這篇文章，觀察移動三個盤子和四個盤子的詳細過程，您不僅可以深刻的了解遞歸，也更加熟悉了漢諾塔的游戲的玩法。

更好的閱讀體驗可訪問 這里。

規則

有a、b、c三個柱子，a從上到下，從小到大有n個盤子。要求把a上所有盤子移動到c，一次只能移動一個盤子，且大盤子不能放小盤子上。

方法

1. 當a上有一個盤子時，直接把該盤子移動到c。

2. 當a上有n個盤子時(n > 1)：

   先把a上n-1個盤子移動到b，
   再把a上最后一個盤子移動到c，
   再把b上所有盤子移動到c。

代碼實現

def mov(n,a,b,c):if n == 1:# 如果a上只有一個盤子，直接把a移動到cprint(a,'-->',c)else:# 先把a上的n-1個盤子移動到bmov(n-1,a,c,b)# 再把a上最后一個盤子移動到cmov(1,a,b,c)# 最后把b上所有盤子(n-1個)移動到cmov(n-1,b,a,c)num = abs(int(input('一共有幾個盤子：')))
print('\n移動步驟為：')
mov(num,'A','B','C')

3個盤子的實例

1. 先把a上的2個移動到b

   先把a上的1個移動到c
   再把a上最后1個移動到b
   再把c上僅有的一個移動到b

2. 再把a上最后一個移動到c

3. 再把b上的兩個移動到c

   先把b上的一個移動到a
   再把b上最后一個移動到c
   再把a上僅有的一個移動到c

也就是：

A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C

4個盤子的實例

1. 先把a上的三個移動到b（套用上面三個盤子的情況，只不過之前是移動到c，現在是b）

   先把a上的2個移動到c

   先把a上的1個移動到b
   再把a上最后1個移動到c
   再把b上僅有的一個移動到c

   再把a上最后一個移動到b

   再把c上的兩個移動到b

   先把c上的一個移動到a
   再把c上最后一個移動到b
   再把a上僅有的一個移動到b

2. 再把a上最后一個移動到c

3. 再把b上的3個移動到c（還是第一步的思路，只是換了個柱子）

   先把b上的2個移動到a

   先把b上的1個移動到c
   再把b上最后1個移動到a
   再把c上僅有的一個移動到a

   再把b上最后一個移動到c

   再把a上的兩個移動到c

   先把a上的一個移動到b
   再把a上最后一個移動到c
   再把b上僅有的一個移動到c

   也就是：

   A --> B
   A --> C
   B --> C
   A --> B
   C --> A
   C --> B
   A --> B
   A --> C
   B --> C
   B --> A
   C --> A
   B --> C
   A --> B
   A --> C
   B --> C

這樣就清晰的看出移動的各個步驟。

總結

再反過來分析一下，當移動一個盤子的時候只需一步就能完成，對應于代碼中的

    if n == 1:# 如果a上只有一個盤子，直接把a移動到cprint(a,'-->',c)

當移動兩個盤子的時候，得需要三步才能完成。例如：把a上的兩個盤子移動到c

1. 先把a上的1個移動到b
2. 再把a上最后1個移動到c
3. 再把b上僅有的一個移動到c

當移動三個盤子的時候，就可以分解成先移動兩個盤子，再移動一個盤子。
當移動四個盤子的時候，就可以分解為先移動三個盤子，再移動一個盤子。依次類推。。

可見當移動兩個或兩個以上個數盤子的時候，都只需要三步就可以完成。其中每一步又可以分解為三步，直到只剩下一個盤子的情況。對應于代碼中的

    else:# 先把a上的n-1個盤子移動到bmov(n-1,a,c,b)# 再把a上最后一個盤子移動到cmov(1,a,b,c)# 最后把b上所有盤子(n-1個)移動到cmov(n-1,b,a,c)

所以，漢諾塔問題，你了解了嗎？

參考：python下實現漢諾塔