python~ハノイの塔と再帰関数

こんにちは,Keymaleです.今回はハノイの塔です.再帰関数として有名な問題ですね.ハノイの塔を解くにあたり,まずはスタックを実装します.

スタック

スタックとはLIFO(Last In First Out)と呼ばれ,最後に入れたものからしか取り出せない構造です.以下のクラスで実装しました.

ハノイの塔

ハノイの塔を解く関数を作ります.

AからCにn枚のディスクを移動するとき,以下の再帰ステップが生じます

1:上のn-1枚のディスクをAからBにCをテンポラリで利用して移動
2:最後の一枚をAからCに移動
3:n-1枚をBからCにAをテンポラリで利用して移動

これを実装すると以下のようになります.

動かしてみる

最後にスタックとハノイの塔の関数を組み合わせて動かして見ます.

AからCにディスクが移動しました.