3

我目前正在开发一个计算友好对的程序（Project Euler Problem 21）。我已经找到了解决方案，但是我注意到我的程序中的一个缺陷是它评估了集合 [1..] 的所有数字，无论我们是否已经找到该数字是一对。

即，如果当前评估 220 和 284 被发现是它的对，但是当 map 函数到达 284 时继续它不应该再次评估它。

import Data.List

properDivisors :: (Integral a) => a -> [a]
properDivisors n = [x | x <- [1..n `div` 2],
                        n `mod` x == 0 ]

amicablePairOf :: (Integral a) => a -> Maybe a
amicablePairOf a
    | a == b = Nothing
    | a == dOf b = Just b
    | otherwise = Nothing
        where dOf x = sum (properDivisors x)
              b = dOf a

getAmicablePair :: (Integral a) => a -> [a]
getAmicablePair a = case amicablePairOf a of
            Just b -> [a,b]
            Nothing -> []


amicables = foldr (++) [] ams
    where ams = map getAmicablePair [1..]

举个例子：

take 4 amicables

返回：

[220,284,284,220]

我对 Haskell 和函数式编程还很陌生，所以如果它是一个明显的解决方案，请原谅我。

4

2 回答 2

5

您的问题是，您尝试通过输出两个友好数字来确保工作安全。但实际上，您并不十分安全，因为您的函数仍然计算这两个数字，无论它们是否友好。为什么不这样做：

import Data.List

divSum :: (Integral a) => a -> [a]
divSum n = sum (filter (\a -> a `mod` n == 0) [1..n `div` 2])

isAmicable :: (Integral a) => a -> Bool
isAmicable a = a /= b && a == c where
  b = divSum a
  c = divSum b

amicables = filter isAmicable [1..]
于 2011-05-31T11:37:49.190 回答
2

也许在帮助中稍作修改getAmicablePair？

getAmicablePair :: (Integral a) => a -> [a]
getAmicablePair a = case amicablePairOf a of
            Just b -> if a < b then [a,b] else []
            Nothing -> []

...所以你只会得到具有较小第一个元素的对

于 2011-05-31T11:34:42.653 回答