haskell beginner - recursive recursion

그냥 하스켈로 시작하고,이 못생긴 조각을 조합하여 목록에서 숫자로 나눌 수있는 숫자와 그 이하의 모든 숫자를 결정합니다.haskell beginner - recursive recursion

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 년, 목록의 첫 번째 번호를 얻을,이과 효과적으로 해결하기 위해 충분하지 않습니다 보인다 20과 같이 더 높은 숫자를 사용하십시오.

어떻게이 raskell을 haskell로 고칠 수 있습니까?

출처

2011-03-09 Orbit

+1은 – corsiKa

내 첫 인상 알고리즘이 효율적으로하는 것이 가능하지 않을 수 있다는 것이다 목록에서 첫 번째 결과까지는 2와 * n * 사이의 모든 * n-1 * 정수에 대해 테스트해야하므로 적어도 2 차 해법처럼 보입니다. 그리고 당신이 * k *와 * n *의 관계가 초 선형 적이라고 생각할 때, 이것은'O (n^3)'처럼 보입니다. ... –

한 번 보아 주셔서 고맙습니다. [x]를 반복하거나 그것을 수행하는 방법을 알고 있지만, 내 질문을 타이핑 한 후에는 그것을 함께 정렬 할 수 있었지만, 문제를 해결하기 위해 실행하면 영원히 걸리고 나는 어쨌든 물어볼 것이라고 생각했다. , 만약 내가 가난한 알고리즘을 구현했다. – Orbit

이것은 다른 알고리즘을 사용하여 상당히 향상 될 수 있습니다. 숫자 집합으로 나눌 수있는 최소 수 (이 경우 집합 [1..10])는 그 수의 최소 공배수입니다 .

하스켈도 최소 공배수 기능 (lcm) 내장하는 당신은 사용할 수 있습니다

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

당신이 빌드 - LCM 기능을 사용하지 않으려면 (즉 거의 속임수로 :)) , 당신은 GCD를 계산하는 Euclid's algorithm를 사용하고 사용하여 작업을 수행 할 수 있습니다

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

당신이 [1..N]로 나눌 수 있습니다 주어진 목록에있는 모든 번호를 찾을 필요가 있다면, 당신은 사용할 수 있습니다 그러한 숫자가 다음과 같이 나눌 수 있다는 사실 [1..N]의 최소 공배수 - * 표시 K * 각 숫자의 "하스켈 raskell"에 대한

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

출처

2011-03-09 18:02:55 interjay

순식간 대 몇 분, 고마워, 아직도 배울 점이 많다. – Orbit

'foldl' (lazily stream 구조가 가능할 때) 또는'foldl' ('foldl'을 통해''bestltest가 엄격한 평가 일 때)''을 선호한다. – ephemient

haskell beginner - recursive recursion

답변

관련 문제