2015/12/11

ハノイの塔のルールと最短手数

分野: 数列  レベル: 入試対策

$n$ 段のハノイの塔の最短手数は $2^n-1$

ハノイの塔のルール

3本の柱がある。そのうちの1本に $n$ 段の塔がある(下段ほど大きい,図は $n=3$ の場合)。

ハノイの塔

目標:
「ある柱の一番上の段を別の柱(の一番上)に移動させる」という操作を繰り返して $n$ 段の塔を別の柱に移したい。

条件:
途中で「小さい段の上に大きい段がある」という状況を作ってはいけない。

以上がハノイの塔のルールです。この記事ではハノイの塔の目標達成に必要な手数の最小値,および実際に最小値を達成する方法を考えてみます。

漸化式を立てる

$n$ 段の塔を移動させるのに必要な最小手数を $a_n$ とします。 $a_n$ についての漸化式を立てます。

漸化式の導出

「 $n$ 段を移動する」という作業は以下の3つの作業により達成できる。

  1. $n-1$ 段を別の柱に移動する
  2. 最下段を(空いている柱が1本あるのでそこに)移動する
  3. $n-1$ 段を最下段の上に移動する

逆に「 $n$ 段を移動する」ためにはこの3つの作業が絶対に必要である。

よって,$a_n=a_{n-1}+1+a_{n-1}$
つまり, $a_n=2a_{n-1}+1$

漸化式を解く

初期条件 $a_1=1$ を使って先ほどの漸化式を解きます。

漸化式は
$a_n+1=2(a_{n-1}+1)$
と変形できるので,

$a_n+1$ という数列は,初項が $a_1+1=2$,公比が $2$ の等比数列である。
よって,$a_n+1=2^n$
したがって,$a_n=2^n-1$

最短手数を達成する方法

「漸化式の導出」から最短手数を達成する再帰的なアルゴリズムを構成することができます。

$n$ 段のハノイの塔に対するアルゴリズム $A(n)$

  • $n=1$ なら1段目を移動するだけ
  • $n\geq 2$ なら
    $A(n-1)$ を用いて $n-1$ 段を移動する
    $n$ 段目(最下段)を移動する
    $A(n-1)$ を用いて $n-1$ 段を $n$ 段目の上に移動する
wordpress更新に伴い,表示が崩れたり目的のページに遷移できない状況が発生しています。見つけた場合はご連絡下さい。
分野: 数列  レベル: 入試対策