漢諾塔問題

背景

3根柱子（x,y,z軸），64個盤子（在x軸上）從下至上盤子是從大到小的。

將盤子從x軸搬到z軸有2個條件：
第一：1次只能挪動1個盤子
第二：大的盤子不能放到小的盤子上面

思路

1.對于問題N，如果問題N-1已經解決了，那么N就很容易解決
2.問題點轉換為了如何求解 N-1

過程

漢諾塔的解決過程：

假如要挪動6個盤子，那么要做以下三步：

1. 第一步：將第 2 - 6個盤子，挪動到Y軸---》求解N-1
2. 第二步：將第1個盤子挪動到Z軸
3. 第三步：將第2-6個盤子從Y軸挪到Z軸

求解N-1的過程類似于求解N的過程（每一步只需要考慮從N-1到N的過程，無需考慮從1-N）
.....
求解第一層：將圓盤從x軸 搬到 z軸

算法

# 漢諾塔問題

def hannuota(n,x,y,z):
    '''
    :param n: 代表要移動n個盤子
    :param x: 代表x軸
    :param y: 代表y軸
    :param z: 代表z軸
    :return:
    '''
    if n == 1:
        print("把第 %d 個盤子 從 %s --》%s"%(n,x,z))
    else:
        # 簡化為三步：
        # 第一步：將前 n-1 個盤子從x軸借助z軸，移動到y軸
        hannuota(n-1,x,z,y)
        # 第二步：將第n個盤子從x軸移動到z軸
        print("把第 %d 個盤子 從 %s --》%s" % (n, x, z))
        # 第三步：將第n-1個盤子從y軸借助x軸移動到z軸
        hannuota(n-1,y,x,z)

print(hannuota(3,"X","Y","Z"))

運行結果

當前搬動的是第1個盤子，搬動路徑為X==Z
當前搬動的是第2個盤子，搬動路徑為X==Y
當前搬動的是第1個盤子，搬動路徑為Z==Y
當前搬動的是第3個盤子，搬動路徑為X==Z
當前搬動的是第1個盤子，搬動路徑為Y==X
當前搬動的是第2個盤子，搬動路徑為Y==Z
當前搬動的是第1個盤子，搬動路徑為X==Z
None