我的一个朋友向我展示了他在参加的C++课程中的家庭练习。由于我已经知道C++,但刚开始学习Haskell,我尝试用“Haskell方法”解决这个问题。
以下是练习说明(我翻译了我们的母语,请评论是否清晰):
编写一个程序,从用户那里读取非零系数(A、B、C、D),并将它们放在以下方程式中:A*x + B*y + C*z = D 该程序还应该从用户那里读取N,表示范围。该程序应在范围为-N/2到N/2的所有可能整数解中找到解。
例如:
最直观的算法是尝试所有可能性,即暴力破解。我用Haskell实现了它,代码如下:
到目前为止还不错,但是练习说明指出可以实现更有效的算法,所以我想如何使它更好。由于方程是线性的,基于假设Z总是第一个被增加的,一旦找到解决方案,就没有必要增加Z。相反,我应该增加Y,将Z设置为范围的最小值并继续进行。这样我就可以节省冗余执行。
由于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中实现比愚蠢算法更好的算法呢?
(此外,我很乐意听取关于我的编码风格的一般反馈)