--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2008/10/15

Project Euler: Problem 15

Problem 15

f(0,y) = 1
f(x,0) = 1
f(x,y) = f(x-1,y) + f(x,y-1)

という性質を使っている。ただし計算量がバカみたいに増えるので、メモ化して高速化している。State モナドでも使ってみりゃよかったかな。

実行結果

$ time runhaskell 15.hs
407575348

real 0m0.312s
user 0m0.280s
sys 0m0.040s

プログラム

 1 type Table = [((Int,Int), Int)]
 2
 3 lookupTable :: (Int,Int) -> Table -> [Int]
 4 lookupTable _ []     = []
 5 lookupTable x ((k,v):rs) | x == k    = [v]
 6                          | otherwise = lookupTable x rs
 7
 8 insertTable :: (Int,Int) -> Int -> Table -> Table
 9 insertTable k v tbl = (k,v) : tbl
10
11 memoRouteCount :: (Int,Int) -> Table -> (Int, Table)
12 memoRouteCount (0,_) tbl = (1,tbl)
13 memoRouteCount (_,0) tbl = (1,tbl)
14 memoRouteCount (x,y) tbl =
15   case lookupTable (x,y) tbl of
16     (v:_) -> (v,tbl)
17     []    -> let x'        = x - 1
18                  y'        = y - 1
19                  (v1,tbl1) = memoRouteCount (x',y) tbl
20                  (v2,tbl2) = memoRouteCount (x,y') tbl1
21                  v         = v1 + v2
22                  tbl3      = insertTable (x,y) v tbl2
23                in (v,tbl3)
24
25 routeCount :: (Int,Int) -> Int
26 routeCount = fst . flip memoRouteCount []
27
28 fn = routeCount (20,20)
29
30 main = print $ fn
スポンサーサイト

comment

post




上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。