1

ウィキペディアでハノイの塔を解くこの再帰アルゴリズムを見ました。誰かがこのアルゴリズムの再帰方程式を得る方法を説明してもらえますか?

再帰的な解決策

  • ペグ A、B、C にラベルを付けます — これらのラベルは異なるステップで移動する場合があります
  • n をディスクの総数とする
  • ディスクに 1 (最小、一番上) から n (最大、一番下) までの番号を付けます。

ペグ A からペグ C に n 個のディスクを移動するには:

  • n−1 個のディスクを A から B に移動します。これにより、ディスク n だけがペグ A に残ります。
  • ディスク n を A から C に移動する
  • n−1 個の円盤を B から C に移動して、円盤 n の上に置く

上記は再帰的なアルゴリズムです。ステップ 1 と 3 を実行するには、同じアルゴリズムを n-1 に再度適用します。ある時点でn = 1のアルゴリズムが必要になるため、手順全体は有限数のステップです。このステップ、つまり単一のディスクをペグAからペグBに移動するのは簡単です。

4

1 に答える 1

2

最初の 3 つのステップは線形時間で実行できます。次の 3 つのステップは再帰的な部分です。次に、単純にプレーン テキスト形式で記述されたものを再帰的な形式で記述します。

T(n,A,C) = T(n-1,A,B) + 1 + T(n-1,B,C).

一方、ラベルは重要ではなく、T(n,A,B) = T(n,B,C)=T(n,A,C)=... であるため、ラベルを取り除くことができます。式は ?

于 2013-10-31T11:43:48.693 に答える