哈斯克尔初学者 - 递归递归

刚开始使用的Haskell，和我一起把这个难看的片片确定由数整除列表中的号码和不到它的所有号码。哈斯克尔初学者 - 递归递归

divis :: (Integral a) => a -> [a] -> [a] 
divis _ [] = [] 
divis n (x:xs) 
    | x `mod` n == 0 && n == 2 = x : divis n xs 
    | x `mod` n == 0 = divis (n-1) [x] ++ divis n xs 
    | otherwise = divis n xs

，我可以把它像...

head (divis 10 [1..])

获得该列表中的第一个号码，在这种情况下，2520然而，似乎这还不够好efficently解决使用像20

较高的号码，我怎样才能解决一个Haskell这个raskell？

来源

2011-03-09 Orbit

1为“一个Haskell的raskell” – corsiKa 2011-03-09 17:53:59

我的第一印象是，该算法可能不能够使有效的 - 每个* K *号的在列表到第一结果具有针对所有2和* N *之间的* N-1 *整数被测试，所以这看起来像至少一个二次溶液。而当你考虑到* K *至* N *的关系是超线性，这看起来像'O（N^3）'左右... – 2011-03-09 17:58:42

感谢很多采取一看，这个问题开始了我不通过[X]递归或知道如何完成它，但我已经输入了我的问题后，我能有点把它在一起，但随后运行它来解决被永远服用这个问题，所以我想我会问无论如何，以防我实施了一个糟糕的算法。 – Orbit 2011-03-09 18:04:24

这可以基本上通过使用不同的算法来提高：其可以通过一组数字的被划分的最小数目（在这种情况下，该组是[1..10]）是这些数字的最小公倍数。

哈斯克尔甚至有一个最小公倍数功能（lcm）内置您可以使用：

Prelude> foldl lcm 1 [1..10] 
2520

如果你不喜欢使用内置的LCM函数（这几乎是作弊:)），您可以通过使用Euclid's algorithm计算GCD，然后使用做到这一点：如果你需要找到一个给定的列表，它是由[1..1]整除的所有数字

lcm a b = a * b `div` gcd a b

，您可以使用任何这样的数字也可以被整除的[1..N]最小公倍数：

divis n xs = filter (\x -> x `mod` mult == 0) xs 
    where mult = foldl lcm 1 [1..n]

来源

2011-03-09 18:02:55 interjay

瞬间vs几分钟长，谢谢，还有很多东西要学 – Orbit 2011-03-09 18:06:48

比'foldl'更喜欢'foldr'（当你可以懒洋洋地流结构）或'foldl'（当最好的策略是严格评估时）。 – ephemient 2011-03-09 18:24:24

哈斯克尔初学者 - 递归递归

回答

相关问题