用 Python 解決河內塔問題

Manav Narula 2021年10月2日 2021年7月13日
用 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。

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

Author: Manav Narula
Manav Narula avatar Manav Narula avatar

Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.

LinkedIn