ハノイの塔のルールと最短手数
更新
段のハノイの塔の最短手数は
「ハノイの塔」というゲームのルールと解き方を紹介します。
ハノイの塔のルール
ハノイの塔のルール
3本の柱がある。そのうちの1本に 段の塔がある(下段ほど大きい,図は の場合)。
-
目標: 段の塔を別の柱に移したい。
-
できること:「ある柱の一番上の段を別の柱(の一番上)に移動させる」という操作を何度でもできる。
-
条件:途中で「小さい段の上に大きい段がある」という状況を作ってはいけない。
以上がハノイの塔のルールです。この記事ではハノイの塔の目標達成に必要な手数の最小値,および実際に最小値を達成する方法を考えてみます。
漸化式を立てる
漸化式を立てる
段の塔を移動させるのに必要な最小手数を とします。 についての漸化式を立てます。
「 段を移動する」という作業は以下の3つの作業により達成できる。
-
段を別の柱に移動する
-
最下段を(空いている柱が1本あるのでそこに)移動する
-
段を最下段の上に移動する
逆に「 段を移動する」ためにはこの3つの作業が絶対に必要である。
よって,
つまり,
漸化式を解く
漸化式を解く
初期条件 を使ってさきほどの漸化式を解きます。
漸化式は
と変形できるので,
という数列は,初項が ,公比が の等比数列である。
よって,
したがって,
最短手数を達成する方法
最短手数を達成する方法
「漸化式の導出」から最短手数を達成する再帰的なアルゴリズムを構成できます。
段のハノイの塔に対するアルゴリズム
-
なら1段目を移動するだけ
-
なら を用いて 段を移動する 段目(最下段)を移動する を用いて 段を 段目の上に移動する
高校数学で習う漸化式が役立つ身近な例です。