Исключая вычисленные результаты из карты [1 ..]? - PullRequest
Новая
       49

Исключая вычисленные результаты из карты [1 ..]?

3 голосов
/ 31 мая 2011

В настоящее время я работаю над программой, которая вычисляет дружные пары (Project Euler Задача 21 ). Я уже нашел решение, однако я заметил, что недостаток в моей программе заключался в том, что она оценивает все числа множества [1 ..], независимо от того, нашли ли мы уже пару.

т.е. Если в настоящее время выясняется, что 220 и 284 являются его парой, однако, если функция карты достигает значения 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 и функциональном программировании, так что простите, если это очевидное решение.

Ответы [ 2 ]

5 голосов
/ 31 мая 2011

Ваша проблема в том, что вы пытаетесь безопасно работать, выводя оба дружных числа. Но на самом деле вы не очень надежны, потому что ваша функция по-прежнему рассчитывает для обоих чисел, являются ли они дружественными. Почему бы не сделать это так: 

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..]
2 голосов
/ 31 мая 2011

Возможно, небольшое изменение в getAmicablePair поможет? 

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

... так что вы просто получите пары с меньшим первым элементом

...