0

到目前为止，我知道如何用 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)

我需要帮助使用 4 个塔将 n - k 个磁盘实施到另一个塔。对于一些 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)
4

1 回答 1

1

Wikipedia 很好地描述了rpegs 和 n 个磁盘的算法：

该算法可以递归地描述：

  • 对于一些k, 1 <= k < n, 将顶部k磁盘转移到一个单独的钉子上，而不是开始或目标钉子，采取T(k,r)行动。

  • 在不干扰现在包含前 k 个磁盘的 peg 的情况下，将剩余的n-k磁盘转移到目标 peg，仅使用剩余的r-1peg，T(n-k,r-1)移动。

  • 最后，将顶部的k圆盘转移到目标钉上，采取T(k,r)行动。

于 2014-02-21T23:27:53.800 回答