0

これまでのところ、3 つのタワーでハノイのタワーを作成する方法はわかっていますが、4 つのタワーにフレーム スチュワード アルゴリズムを実装する方法についてはわかりません。

これは、現在の 3 つのタワー関数がどのように見えるかです。

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

rウィキペディアには、ペグと n 個のディスクのアルゴリズムがうまく説明されています。

アルゴリズムは再帰的に記述できます。

  • いくつかkの場合1 <= k < nは、一番上のkディスクを開始ペグまたは目的ペグ以外の単一のペグにT(k,r)移動し、移動します。

  • 上位k個のディスクを含むペグを乱すことなく、残りのペグn-kのみを使用して、残りのディスクを移動先のペグに移します。r-1T(n-k,r-1)

  • 最後に、一番上のkディスクをT(k,r)移動先のペグに移します。

于 2014-02-21T23:27:53.800 に答える