我的一个朋友在他参加的 C++ 课程中向我展示了一个家庭练习。由于我已经了解 C++,但刚开始学习 Haskell,我尝试以“Haskell 方式”解决练习。
这些是练习说明(我是从我们的母语翻译的,所以如果说明不清楚,请发表评论):
编写一个程序,从用户那里读取非零系数 (A,B,C,D) 并将它们放在以下等式中: A*x + B*y + C*z = D 程序还应该从用户那里读取N,代表一个范围。程序应在 -N/2 到 N/2 范围内找到方程的所有可能积分解。
例如:
Input: A = 2,B = -3,C = -1, D = 5, N = 4
Output: (-1,-2,-1), (0,-2, 1), (0,-1,-2), (1,-1, 0), (2,-1,2), (2,0, -1)
最直接的算法是通过蛮力尝试所有可能性。我通过以下方式在 Haskell 中实现它:
triSolve :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)]
triSolve a b c d n =
let equation x y z = (a * x + b * y + c * z) == d
minN = div (-n) 2
maxN = div n 2
in [(x,y,z) | x <- [minN..maxN], y <- [minN..maxN], z <- [minN..maxN], equation x y z]
到目前为止一切都很好,但是练习说明指出可以实现更有效的算法,所以我想如何让它变得更好。由于方程是线性的,基于 Z 始终是第一个递增的假设,一旦找到解决方案,就没有必要递增 Z。相反,我应该递增 Y,将 Z 设置为范围的最小值和继续。这样我可以节省多余的执行。由于 Haskell 中没有循环(至少据我所知),我意识到应该使用递归来实现这种算法。我通过以下方式实现了算法:
solutions :: (Integer -> Integer -> Integer -> Bool) -> Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)]
solutions f maxN minN x y z
| solved = (x,y,z):nextCall x (y + 1) minN
| x >= maxN && y >= maxN && z >= maxN = []
| z >= maxN && y >= maxN = nextCall (x + 1) minN minN
| z >= maxN = nextCall x (y + 1) minN
| otherwise = nextCall x y (z + 1)
where solved = f x y z
nextCall = solutions f maxN minN
triSolve' :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)]
triSolve' a b c d n =
let equation x y z = (a * x + b * y + c * z) == d
minN = div (-n) 2
maxN = div n 2
in solutions equation maxN minN minN minN minN
两者产生相同的结果。但是,尝试测量执行时间会产生以下结果:
*Main> length $ triSolve' 2 (-3) (-1) 5 100
3398
(2.81 secs, 971648320 bytes)
*Main> length $ triSolve 2 (-3) (-1) 5 100
3398
(1.73 secs, 621862528 bytes)
这意味着愚蠢的算法实际上比更复杂的算法执行得更好。基于我的算法是正确的假设(我希望不会出错:)),我假设第二个算法受到递归产生的开销的影响,而第一个算法不是因为它是使用实现的列表理解。有没有办法在 Haskell 中实现比愚蠢的算法更好的算法?(另外,我很高兴收到关于我的编码风格的一般反馈)