Problem 155

http://projecteuler.net/index.php?section=problems&id=155

メモリ不足になったりした。

素直なアルゴリズム。

import Data.Array
import qualified Data.Set as S
n = 18
main = print.sum.map S.size.elems$ caps
caps = listArray (1,n) $ (S.singleton 1) : map c' [2..n] :: Array Int (S.Set Rational)
where c n = S.fromList $ do k <-[1..div n 2]
c1 <- S.toList$caps!k
c2 <- S.toList$caps!(n-k)
c <- [c1+c2,(c1*c2)/(c1+c2)]
return c
c' n =  foldl (S.) (c n) $ map (caps!) [1..n-1]

遅いけど、このアルゴリズムをjavaで実装するのは面倒だ。

有理数クラスあるのかな？