Factorizable respecto de una lista
Definir la función
|
1 |
factorizable :: Integer -> [Integer] -> Bool |
tal que (factorizable x ys) se verifica si x se puede escribir como producto de potencias de elementos de ys. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
factorizable 1 [2,5,6] == True factorizable 12 [2,5,3] == True factorizable 12 [2,5,6] == True factorizable 12 [7,5,12] == True factorizable 12 [2,3,1] == True factorizable 12 [2,3,0] == True factorizable 24 [12,4,6] == True factorizable 0 [2,3,0] == True factorizable 12 [5,6] == False factorizable 12 [2,5,1] == False factorizable 0 [2,3,5] == False factorizable (product [1..3000]) [1..100000] == True factorizable (1 + product [1..3000]) [1..100000] == False |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
-- 1ª definición factorizable1 :: Integer -> [Integer] -> Bool factorizable1 1 _ = True factorizable1 0 ys = 0 `elem` ys factorizable1 x ys = or [ factorizable1 (x `div` y) ys | y <- ys , y /= 0 && y /= 1 , x `mod` y == 0 ] -- 2ª definición factorizable2 :: Integer -> [Integer] -> Bool factorizable2 1 _ = True factorizable2 0 ys = 0 `elem` ys factorizable2 x ys = aux x [y | y <- ys, y > 1, x `mod` y == 0] where aux _ [] = False aux 1 _ = True aux x ys | null zs = False | otherwise = or [aux (x `div` z) ys | z <- zs] where zs = [y | y <- ys, x `mod` y == 0] -- 3ª definición factorizable3 :: Integer -> [Integer] -> Bool factorizable3 1 _ = True factorizable3 0 ys = 0 `elem` ys factorizable3 x ys = aux x [y | y <- ys, y > 1, x `mod` y == 0] where aux _ [] = False aux 1 _ = True aux x (y:ys) | rem x y == 0 = aux (div x y) (y:ys) || aux x ys | otherwise = aux x ys -- Comparación de eficiencia -- ========================= -- λ> factorizable1 (product [1..3000]) [1..100000] -- True -- (3.55 secs, 322,471,488 bytes) -- λ> factorizable2 (product [1..3000]) [1..100000] -- True -- (2.46 secs, 274,024,832 bytes) -- λ> factorizable3 (product [1..3000]) [1..100000] -- True -- (0.30 secs, 47,606,400 bytes) -- -- λ> factorizable1 (1 + product [1..3000]) [1..100000] -- False -- (2.41 secs, 147,221,760 bytes) -- λ> factorizable2 (1 + product [1..3000]) [1..100000] -- False -- (0.45 secs, 40,472,168 bytes) -- λ> factorizable3 (1 + product [1..3000]) [1..100000] -- False -- (0.43 secs, 29,949,680 bytes) |
Se compara el rendimiento con las anteriores (1 y 2)