哈斯克爾初學者 - 遞歸遞歸

剛開始使用的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

哈斯克爾初學者 - 遞歸遞歸

回答

相關問題