Posts Tagged ‘ euler

Euler-{18,67}

http://projecteuler.net/index.php?section=problems&id=67
典型的动态规划。
原先在手机里写的,
跟机器一起丢了……
补上一个 T^T

?View Code PYTHON
#Python的解
dat_lines =  [ map(int, l.split(' ')) for l in open('triangle.txt').readlines() ]
dat_lines.reverse()
 
for i, l in enumerate(dat_lines):
    if not i:
        continue
    else:
        for ei, ev in enumerate(dat_lines[i]):
            dat_lines[i][ei] += max(dat_lines[i-1][ei], dat_lines[i-1][ei+1])
 
print dat_lines[i][0]
?View Code HASKELL
module Main where
 
acc_l [] (o1:[]) = []
acc_l (c1:cs) (o1:o2:os) = ((max o1 o2) + c1) : acc_l cs (o2:os)
 
main = do 
    lns <- readFile "triangle.txt"
 
    let real_lns = map (\l -> [ read x::Int | x <- words l ]) (lines lns)
 
    --Haskell里头列表项的值是不可变的,用foldr做累加。
    print $ head $ foldr (\nl ol-> acc_l nl ol) (last real_lns) (init real_lns)
 
    return ()