ハノイの塔
1、隣接2項間の漸化式
ハノイの塔を解くにあたってまずは隣接2項間の漸化式の解説から始める。漸化式とは数列において前の項から次の項を決めるための関係式のことである。そして、隣り合う2つの項からなる漸化式を隣接2項間の漸化式という。隣り合う2項間の関係式が1次式で表せる時、隣接2項間の漸化式は数列$${｛a_{n}｝ = a_{1},a_{2},a_{3}…}$$に対して$${a_{n+1} = p {a_n}+q}$$と書くことができ、$${a_{n+1},{a_{n}}}$$の代わりに$${\alpha}$$とおいた方程式$${\alpha = p \alpha+q}$$を特性方程式と呼ぶ。隣接2項間の漸化式から特性方程式の辺々を引くと
$${a_{n+1}-\alpha = p({a_n}-\alpha)}$$と変形できる。
ここで、$${b_{n} = a_{n}-\alpha}$$とすると、$${b_{n+1} = a_{n+1}-\alpha = p(a_{n}-\alpha)}$$となり$${b_{1} = a_{1}-\alpha}$$なので$${b_{n}}$$は初項$${a_{1}-\alpha}$$、公比$${p}$$の等比数列になる。
したがって、$${b_{n} = (a_{1}-\alpha) p^{n - 1}}$$と表すことができる。
$${b_{n} = a_{n}-\alpha}$$なので、
$${a_{n} - \alpha = (a_{1}-\alpha) p^{n - 1}}$$より、
$${a_{n} = (a_{1}-\alpha) p^{n - 1}+\alpha}$$が成り立つ。
2、ハノイの塔のルール
ハノイの塔は3本の杭と、中央に穴の開いた大きさの異なるn枚の円盤から構成される。最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。以下のルールに従ってすべての円盤を右端の杭に移動させられればクリアである。
・円盤を1回に1枚ずつどれかの杭に移動させる
・ただし、小さな円盤の上に大きな円盤を乗せることはできない
参考:
3、ハノイの塔の最小手数と解き方
n段のハノイの塔を解くにはまずn-1段のハノイの塔を作る必要がある。n段を解くためにn-1段、n-1段を解くためにn-2段…という風に考えていくと、最終的に1段のハノイの塔に行きつく。文字だけだと分かりづらいので例として3段のハノイの塔について考えてみる。
3段のハノイの塔を解くには3段目を1番右のポールに移動させる必要がある。そのためには真ん中に2段のハノイの塔を作る必要があり、2段のハノイの塔を作るためには1段のハノイの塔(1段目を移動させるだけ)を作る必要がある。実際の手順を見せると次のようになる。
真ん中に2段のハノイの塔を作ったことによって3段目を1番右の杭に動かせるようになった。後はその上にもう一度2段のハノイの塔を作ればよい。
これと同じことがn段のハノイの塔にも言える。n段のハノイの塔を解くのにかかる最小手数を$${a_{n}}$$とすると
$${a_{1} = 1}$$
$${a_{2} = 2a_{1} + 1}$$
$${a_{3} = 2a_{2} + 1}$$
…
$${a_{n+1} = 2a_{n} + 1}$$
という式が成り立つ。この式の意味を言葉で説明すると、
「n段のハノイの塔を解くのにかかる最小手数$${a_{n}}$$=n-1段のハノイの塔を真ん中に作る時にかかる手数$${a_{n-1}}$$+n段目を左端の杭から右端の杭に動かす時にかかる手数$${1}$$+n段目の上にもう一度n-1段のハノイの塔を作る手数$${a_{n-1}}$$」
である。これは隣接2項間の漸化式であり特性方程式は
$${\alpha = 2\alpha + 1}$$である。この式を解くと$${\alpha = -1}$$であることが分かる。最初に導いた公式に数値を当てはめると
$${a_{n} = (a_{1} - \alpha) p^{n - 1} + \alpha}$$
$${a_{n} = ((1-(-1))2^{n - 1} - 1)}$$
$${a_{n} = 2×2^{n - 1} -1}$$
$${a_{n} = 2^{n} - 1}$$
よってn段のハノイの塔を解くのにかかる最小手数は$${a_{n} = 2^{n} - 1}$$であることが分かる。