GarbageCompany

満つらざるとも屈せず

ハノイの塔

先日「ハノイの塔」の模型を見かけて、そういえば俺あの問題解いてないなと思い出す。で夜眠れなかったので、布団でロジックを考えた(より眠れなくなった)。

うろ覚えだけど再帰問題で、条件分岐をいくつも作るようなことをせず数行のプログラムで出来てたような気がするので、ロジックは出来るだけ短い物として、3時間くらいアレコレ考えて、

①3本の塔(棒)のうち、最上段が最も小さい物を残り2本のいずれかに移動する

②移動先は「自分より段数が大きく、奇遇(数)が異なる段の上」、無ければ地面

③同じ物は2度続けては移動しない

で出来そう。最後の条件は「1段目とそれ以外が交互に動く」でも出来そうだけどどっちがシンプルかな。③を加味して①を探し、②に移動する関数を組んで、最初の塔が無くなるまで呼び続ければたぶん移動出来る。②とか③の条件も消したいんだけど思いつかなかった。定義部除いて3行くらい?まだ長いかな。

まぁ問題が「塔を移動せよ」だったかどうかも怪しいんだけど、ググって全部分かっちゃうのも趣が無いんで。