ハノイの塔をHaskellで書いた
さっきまで理解してなかったので書いてみた。Wikipediaの書き方もわかりづらいし検索上位にわりと酷いのばっかりひっかかるんですがそれは…
import Debug.Trace moveAtoC :: ([Int], [Int], [Int]) -> ([Int], [Int], [Int]) moveAtoC ((a:as), bs, cs) = (as, bs, a:cs) solveHanoi n = solveHanoi' n ([1..n], [], []) solveHanoi' :: Int -> ([Int], [Int], [Int]) -> ([Int], [Int], [Int]) -- Aにある円盤n個を、Bを使いながらCに移動する solveHanoi' 1 t = moveAtoC t solveHanoi' n (as, bs, cs) = (as''', bs''', cs''') where (as' , cs' , bs' ) = solveHanoi' (n - 1) (as, cs, bs) (as'' , bs'' , cs'' ) = moveAtoC (as', bs', cs') (bs''', as''', cs''') = solveHanoi' (n - 1) (bs'', as'', cs'')
A → Bに一番下を除いて移動させて、一番下をA→Cに移動させた上で、B→Cの移動をする。これを再帰的に定義する。
コードに落とす時は、棒を入れ替えたとして考えるのがポイントらしい。