ハノイの塔 in Python

世界で闘うプログラミング力を鍛える150問』から、ハノイの塔に関する問題を問いていこう。

古典的なハノイの塔の問題では、3つの塔とN枚のサイズの異なる円盤を用いて塔の間を移動させます。最初は円盤が下から上に向かって小さくなるように (どの円盤も自身より大きな円盤の上に乗っているように) なっています。そして以下のような制約を持ちます。

  1. 一度に1枚の円盤しか動かせない。
  2. 塔の一番上にある円盤を他の塔に移動させる。
  3. 円盤を置くときは、それ自身より大きなものの上にしか置けない。

スタックを用いて、最初の塔に積みあがっている円盤を最後の塔に移動させるプログラムを書いてください。

再帰的なアプローチ

3つの塔を、それぞれ「塔1」「塔2」「塔3」と名前をつけよう。「塔1」が最初に円盤が積みあがっている塔で、「塔3」が最後に円盤を積み上げる塔だ。

円盤の数が少ないとき、どういう風に円盤を移動すればハノイの塔を解けるのか、考えていこう。

円盤がひとつのとき

  1. 円盤を「塔1」から「塔3」に移動する。

これだけの操作で完了だ。

円盤がふたつのとき

小さい方から、円盤を「円盤1」「円盤2」と呼ぶことにしよう。

  1. 「円盤1」を「塔1」から「塔2」に移動する。
  2. 「円盤2」を「塔1」から「塔3」に移動する。
  3. 「円盤1」を「塔2」から「塔3」に移動する。

「塔2」はバッファとしてのみ使われることに注意しよう。

円盤がみっつのとき

先ほどと同じく、小さい方から円盤を「円盤1」「円盤2」「円盤3」と呼ぶことにしよう。

  1. 「円盤1」を「塔1」から「塔3」に移動する。
  2. 「円盤2」を「塔1」から「塔2」に移動する。
  3. 「円盤1」を「塔3」から「塔2」に移動する。
  4. 「円盤3」を「塔1」から「塔3」に移動する。

この先の仕事は「円盤がふたつのとき」と酷似している。

この時点での円盤の状態は次のようになっている。

# 塔の頂点方向 →
塔1: []
塔2: [円盤2, 円盤1]
塔3: [円盤3]

後は、「塔2」の円盤を「塔1」をバッファに「塔3」に移動するだけだ。

円盤がN

これを一般化して、「円盤がN個のときの移動」について考えてみよう。

  1. 「N – 1」枚の円盤をまずバッファとなる塔へ移動する。
  2. N枚目の円盤を移動先となる塔へ移動する。
  3. バッファとなる塔に積んである「N – 1」枚の円盤を、移動先となる塔へ移動する (余っている塔はバッファとして使う)。

どうやら、N枚の円盤の移動を「N – 1」枚の円盤の移動を使って再帰的に表現できそうだ。

実装

再帰的な実装を Python で書いた。3つの塔は意味が通るように srcdestbuf という名前で表現した。

コメントを残す

コメントを投稿するには、以下のいずれかでログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中