てきとうなさいと べぇたばん

【数学】 ハノイの塔について

ハノイの塔。一番最初の状態。これを全部Bに移動。一番上の円盤を1枚だけ移動できる。 緑3枚分をCへ移動、赤の一番下の円盤をBへ移動させる。 移動させた後。 緑2枚分をAへ移動、赤の一番下の円盤をBへ移動。 移動させた後。 緑1枚分をCへ移動、赤1枚分をBへ移動。 移動させた後。 赤1枚分をBへ移動。 移動完了。 終わったので、これを漸化式にしてみよう H(4)とは、H(3)+1+H(2)+1+H(1)+1+1となっている。 前の式を用いてH(1)からH(3)を解いてみる。 H(1)からH(3)までがわかったので、H(4)を解く

プログラマの数学を読んでいる

プログラマの数学を読んでいる。ハノイの塔の漸化式がわからなかったので、自分なりの解釈で解いてみた。

ハノイの塔

3本の柱がある。そこに円盤があり、その円盤は上に自分より小さいのを、下に自分より大きいのを置ける。

移動は一番上にある円盤を1枚ずつ移動できる。

1枚ずつ移動した時、真ん中の柱Bへ移動する。

法則がある

移動したあとで気がついたんだけど、円盤の塔に法則を見つけた。

H(n) = H(n - 1) + 1 + H(n - 2) + 1 ... H(1) + 1 + 1

H(n - 1) + 1の部分はH(n - 1)がBではない柱へ移動させ、+ 1の部分が柱Bへ移動させる一番下の円盤。これをH(n - 1)の部分を1ずつ小さくしながらn - 1回繰り返していく。

一番最後の+ 1は一番小さな円盤を1回だけ動かすため必要。

これでn個の円盤を1から数えて法則に当てはめていけば最小移動回数が求められる。

プログラムで

Rubyで書いてみた。

#!ruby -Ks

def hanoi(i)
  if i == 0
    return 0
  elsif i > 0
    k = 0
    (i - 1).downto(1) {|j| k += hanoi(j) + 1 }
    return k + 1
  end
end

p hanoi(1)
p hanoi(2)
p hanoi(3)
p hanoi(4)
p hanoi(5)
p hanoi(6)