我正在尝试解决项目欧拉第 15 个问题,晶格路径(http://projecteuler.net/problem=15)。
我的第一次尝试是逐行解决问题,然后在最后一行中取最后一个元素。
number_of_ways_new_line last_line = foldl calculate_values [] last_line
where
calculate_values lst x = lst ++ [(if length lst > 0 then (last lst) + x else head last_line)]
count_ways x = foldl (\ lst _ -> number_of_ways_new_line lst) (take x [1,1..]) [1..x-1]
result_15 = last $ count_ways 21
这行得通而且速度很快,但我认为它真的很难看。所以我想了一会儿,想出了一个更惯用的函数(如果我弄错了,请纠正我),它使用递归来解决问题:
lattice :: Int -> Int -> Int
lattice 0 0 = 1
lattice x 0 = lattice (x-1) 0
lattice 0 y = lattice (y-1) 0
lattice x y
| x >= y = (lattice (x-1) y) + (lattice x (y-1))
| otherwise = (lattice y (x-1)) + (lattice (y-1) x)
这适用于短数字,但它根本无法扩展。lattice 1 2
我通过使用和lattice 2 1
将永远相同的事实对其进行了一点优化。为什么这么慢?Haskell 不是在记忆以前的结果,所以无论何时lattice 2 1
调用它都会记住旧的结果?