Pythonで再帰を使ってハノイの塔を実装する方法

スポンサーリンク

ハノイの塔は、3本のポールと直径の異なる「n」枚の円盤からなる数学的な問題(パズル)です。

ハノイの塔問題の目的

この問題の目的は,すべての「n」枚の円盤を,元の極から先の極に,前と同じ配置になるように移動させることである.しかし,この目的は,以下の規則に従うことによって達成されなければならない.


ルールと制約事項

問題を解く際に満たさなければならない制約条件は、以下の通りです。

    1. 一度に動かせるディスクは 1 枚だけです。
    1. 一番上のディスクのみを取り外すことができる
  1. 大きいディスクを小さいディスクの上に置くことはできません。

ハノイの塔のビジュアル表現問題

次の図は,3 つの極 (供給元,中間,供給先) と 3 枚の円板を持つハノイの塔の段階的な解法を示している.目標は,3枚の円盤をすべて極Aから極Cに移動させることである.

def TowerOfHanoi(n , s_pole, d_pole, i_pole):          
    if n == 1:
        print("Move disc 1 from pole",s_pole,"to pole",d_pole)
        return
    TowerOfHanoi(n-1, s_pole, i_pole, d_pole)
    print("Move disc",n,"from pole",s_pole,"to pole",d_pole)
    TowerOfHanoi(n-1, i_pole, d_pole, s_pole)
 
n = 3
TowerOfHanoi(n, 'A', 'C', 'B')
# A, C, B are the name of poles
STEP 1
STEP 3 4
STEP 5 6

上の解答からわかるように、3枚の円盤に必要な移動回数=8回なので、必要な総移動回数を一般化した式が

総手数=n2 – 1

ここで、nはディスクの総枚数です。


スポンサーリンク

Pythonでハノイの塔問題を解決する

STEP 7 8

上のコードでは、関数TowerOfHanoiを3枚のディスクに対して再帰的に呼び出しています。

ここで

  • s_pole: 入力極
  • i_pole: 中間極
  • dttpd: 出力極

上記のコードの出力は以下の通りです。

Output 1

まとめ

以上がハノイの塔の問題の解き方です。

このコードは、任意の枚数のディスクに対して一般化することができる。

もし、円盤が4枚の場合の解答が欲しければ、n = 4として、nの値を3から4に変更すれば、円盤が4枚の場合の出力が表示され、以下同様です。

タイトルとURLをコピーしました