河内四塔

Question

到目前为止，我知道如何用3个塔来制作河内塔，但我不知道如何实现4个塔的Frame-Steward算法。在

这就是我现在的三塔功能。在

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

这是我尝试的算法，但它不起作用，请帮忙。在

^{pr2}$

Answer 1

Wikipedia对rpeg和n个磁盘的算法进行了很好的描述：

The algorithm can be described recursively:

• For some k, 1 <= k < n, transfer the top k disks to a single peg other than the start or destination pegs, taking T(k,r) moves.

• Without disturbing the peg that now contains the top k disks, transfer the remaining n-k disks to the destination peg, using only the remaining r-1 pegs, taking T(n-k,r-1) moves.

• Finally, transfer the top k disks to the destination peg, taking T(k,r) moves.