漢羅塔是一種經典的謎題,它的規則如下:
有三個棒,編號為A、B、C;
有 n 個盤子, 編號為1、2、3......n,他們按照從小到大的順序從A棒開始擺放,最下面的編號為n,最上面的是編號為1。現在我們需要把A棒上的盤子全部移到C棒上,并且保證按照原來的規則擺放,即從下至上編號從大到小。在移動過程中需要遵守以下規則:
每次只能移動一個盤子;
每次移動過程中,盤子都需要從一個棒挪到另外一個棒上;
小盤子不能放在大盤子的下面。
def hanoi(n, A, B, C):
if n == 1:
print(A, "-->", C)
else:
hanoi(n-1, A, C, B) # 把n-1個盤子從A通過C移到B
print(A, "-->", C) # 把第n個盤子從A移到C
hanoi(n-1, B, A, C) # 把n-1個盤子從B通過A移到C
if __name__ == '__main__':
n = 3
hanoi(n, "A", "B", "C")
上述代碼是求解漢羅塔問題的Python代碼,其中,hanoi函數是遞歸實現的。當 n==1 時,只需要將第一個盤子從A棒移到C棒,可以直接輸出即可。當n>1時,可以將問題分成3個子問題:
1. 把n-1個盤子從A通過C移到B;
2. 把第n個盤子從A移到C;
3. 把n-1個盤子從B通過A移到C。
遞歸通常通過代碼調用自身來實現。Python會默認執行最后一行代碼。在上面的代碼中,如果當前文件被作為Python腳本執行,那么__name__變量就會被賦值為"__main__"。
下一篇vue公用組件打包