20190710-漢諾塔演算法

漢諾塔：漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界
的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵
天命令婆羅門把圓盤從下麵開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤
上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

關鍵點：

一次只能移動一個盤子
大盤不能重疊在小盤子上

當n=1的時候
1. 直接將1從X移動到Z

當n=2的時候
1. 將1從X移動到Y軸
2. 將2從X移動到Z軸
3. 將1從Y移動到Z軸

當n=3的時候
1. 將1從X移動到Z
2. 將2從X移動到Y
3. 將1從Z移動到Y
4. 將3從X移動到Z
5. 將1從Y移動到X
6. 將2從Y移動到Z
7. 將1從X移動到Z

當n=4的時候

當前挪動的盤子為1,挪動軌跡為x==>y
當前挪動的盤子為2,挪動軌跡為x==>z
當前挪動的盤子為1,挪動軌跡為y==>z
當前挪動的盤子為3,挪動軌跡為x==>y
當前挪動的盤子為1,挪動軌跡為z==>x
當前挪動的盤子為2,挪動軌跡為z==>y
當前挪動的盤子為1,挪動軌跡為x==>y
當前挪動的盤子為4,挪動軌跡為x==>z
當前挪動的盤子為1,挪動軌跡為y==>z
當前挪動的盤子為2,挪動軌跡為y==>x
當前挪動的盤子為1,挪動軌跡為z==>x
當前挪動的盤子為3,挪動軌跡為y==>z
當前挪動的盤子為1,挪動軌跡為x==>y
當前挪動的盤子為2,挪動軌跡為x==>z
當前挪動的盤子為1,挪動軌跡為y==>z

總結規律為：

要想移動n個盤子從X軸到Z軸需要經過如下三步：
1. 將n-1個盤子從X軸移動到Y軸
2. 將第n個盤子從X軸移動到Z軸
3. 將n-1個盤子從Y軸移動到Z軸

轉換為演算法
• 遞歸的結束條件：
• 當n=1的時候，直接將n移動到Z軸
• 遞歸條件：
1. 將n-1個盤子從X軸移動到Y軸
2. 將第n個盤子從X軸移動到Z軸
3. 將n-1個盤子從Y軸移動到Z軸

代碼

def hannota(n,x,y,z):
    if n ==1:
        print('%s->%s'%(x,z))#當n=1的時候，直接將n移動到z軸
    else:
        hannota(n-1,x,z,y)#將n-1個盤子從X軸移動到Y軸
        print('%s->%s'%(x,z))#將第n個盤子從X軸移動到Z軸
        hannota(n-1,y,x,z)#將n-1個盤子從Y軸移動到Z軸
hannota(3,'x','y','z')