用 Python 解決河內塔問題

河內塔問題是一個基本的數學難題，一開始就介紹給新程式設計師，以擴大他們解決問題的測驗。

問題很簡單，涉及三個杆。一根杆包含幾個按遞減順序排列的圓盤，最大的圓盤在底部，最小的圓盤在頂部。我們必須使用第二個杆將其從第一杆轉移到第三杆。

我們必須牢記某些規則。我們只能同時移動一個圓盤，並且必須在杆的頂部取出圓盤。此外，我們不能將較大的磁碟放在較小的磁碟之上。
記住所有這些，我們必須解決這個問題並計算解決它所採取的行動總數。

在本教程中，我們將介紹如何解決這個問題。我們將使用遞迴方法在 Python 中解決河內塔問題。

此方法將建立一個函式，該函式將根據某些條件遞迴呼叫自身以解決河內塔問題。
我們在下面的程式碼中實現了這個邏輯。

def ToH(n, A, B, C):
    if n == 1:
        print("Disk 1 from", A, "to", B)
        return
    ToH(n - 1, A, C, B)
    print("Disk", n, "from", A, "to", B)
    ToH(n - 1, C, B, A)


ToH(3, "A", "B", "C")

輸出：

Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C
Disk 3 from A to B
Disk 1 from C to A
Disk 2 from C to B
Disk 1 from A to B

在上面的例子中，我們使用杆 C 將三個圓盤從杆 A 移動到杆 B。

如你所見，上例中的總移動次數為 7。對於 n 個磁碟，使用此方法進行的總移動次數始終等於 2^n -1。

隨著時間的推移，出現了一些其他解決方案來使用堆疊解決河內塔問題。儘管如此，還是不​​建議使用它們，因為這些方法在時間和速度方面效率很低。