漢諾塔問題

在三個柱子 A，B，C 中的 A 柱子上放著若干圓盤，其中下面的圓盤總比上面的圓盤大，這個規(guī)則三個柱子都必須遵循，目的是：借助三個柱子把若干圓盤都從 A 柱子上移到 C 柱子上，求解其中的步驟。

漢諾塔與遞歸

漢諾塔問題是一個經(jīng)典的遞歸問題。
簡單的遞歸理解就是在一個方法中調(diào)用它本身。
更進一步的理解，就是把一個問題持續(xù)分解為更簡單的問題，直至問題小到可以解決，當然核心還是調(diào)用了它本身來解決。

漢諾塔思想

把 A 柱子上的圓盤移到 C 柱子上的步驟最終只有三個而已

1. 把 A 柱子上的除最后一個外的所有園盤都移到 B 柱子上。
2. 把 A 柱子上剩下的那個圓盤移到 C 柱子上。
3. 把剩下的 B 柱子上的所有圓盤豆移到 C 柱子上。

python 實現(xiàn)

count = 0  # 計算總共有多少步
def hanoi(a, b, c, num):
    """
    漢諾塔
    :param a: A 柱子
    :param b: B 柱子
    :param c: C 柱子
    :param num:  圓盤個數(shù)
    :return: 
    """
    global count 
    if num == 1:  # 當剩下一個盤時，從 "A" 柱子上移到 "C" 柱子上（注意引號）
        count += 1
        print a + "->" + c
        return
    num -= 1
    hanoi(a, c, b, num)  # 第一步： 把 A 柱子上的除最后一個外的所有原盤都移到 B 柱子上。
    count += 1
    print a + "->" + c  # 第二步： 把 A 柱子上剩下的那個圓盤移到 C 柱子上。
    hanoi(b, a, c, num)  # 第三步：把剩下的 B 柱子上的所有圓盤豆移到 C 柱子上。


if __name__ == '__main__':
    hanoi("A", "B", "C", 3)
    print count

返回結(jié)果：

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

感謝閱讀！
如果文章中有錯誤或存在誤解的地方，麻煩多加指教，無比感謝！
The End.