4座塔河內塔

Question

到目前爲止，我知道如何做3塔河內塔，但我不知道如何實現4塔的幀管家算法。

這就是我目前的三塔函數的樣子。

def move_three_towers(n, from_tower, to_tower, spare_tower): 
    if (n > 0): 

     move_three_towers(n-1, from_tower, spare_tower, to_tower) 
     print(from_tower, ' --> ', to_tower) 
     move_three_towers(n-1, spare_tower, to_tower, from_tower) 

我需要幫助實施n - k磁盤到另一個塔使用4塔。對於某些1≤k < n

這裏是我的算法嘗試，但它不起作用，請幫助。

def move_four_towers(n, k = 0, from_tower, to_tower, spare_tower1, spare_tower2): 
    if n == 1: 
     print(from_tower, ' --> ', to_tower) 
    if n > 1: 
     move_four_towers(n - k, from_tower, spare_tower2, spare_tower1, to_tower) 
     print(from_tower, ' --> ', to_tower) 
     move_three_towers(k, from_tower, to_tower, spare_tower1) 
     move_four_towers(n - k, spare_tower2, to_tower, spare_tower1, from_tower) 

Answer 1

維基百科給出了該算法的一個很好的描述爲r栓和n個磁盤：

該算法可以遞歸描述：

• 對於一些k，1 <= k < n，調頂部k磁盤到除開始或目標掛鉤以外的單個掛鉤，採取T(k,r)移動。

• ，但不影響現在包含前k磁盤的PEG，剩餘n-k磁盤傳輸到目標掛鉤，使用僅剩下r-1釘，以T(n-k,r-1)移動。

• 最後，將頂部k磁盤轉移到目標掛鉤，採取T(k,r)移動。