Listas hermanadas
Una lista hermanada es una lista de números estrictamente positivos en la que cada elemento tiene algún factor primo en común con el siguiente, en caso de que exista, o alguno de los dos es un 1. Por ejemplo,
- [2,6,3,9,1,5] es una lista hermanada pues 2 y 6 tienen un factor en común (2); 6 y 3 tienen un factor en común (3); 3 y 9 tienen un factor en común (3); de 9 y 1 uno es el número 1; y de 1 y 5 uno es el número 1.
- [2,3,5] no es una lista hermanada pues 2 y 3 no tienen ningún factor primo en común.
Definir la función
|
1 |
hermanada :: [Int] -> Bool |
tal que (hermanada xs) se verifica si la lista xs es hermanada según la definición anterior. Por ejemplo,
|
1 2 3 |
hermanada [2,6,3,9,1,5] == True hermanada [2,3,5] == False hermanada [2,4..1000000] == True |
Nota: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.
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 |
-- 1ª definición (por comprensión) hermanada1 :: [Int] -> Bool hermanada1 xs = and [hermanos p | p <- zip xs (tail xs)] -- (hermanos (x,y)) se verifica si x e y son hermanos; es decir, alguno es -- igual a 1 o tienen algún factor primo en común hermanos :: (Int, Int) -> Bool hermanos (x,y) = x == 1 || y == 1 || gcd x y /= 1 -- 2ª definición (con all) hermanada2 :: [Int] -> Bool hermanada2 xs = all hermanos (zip xs (tail xs)) -- 3ª definición (por recursión) hermanada3 :: [Int] -> Bool hermanada3 (x1:x:xs) = hermanos (x1,x) && hermanada3 (x:xs) hermanada3 _ = True -- 4ª definición (por plegado) hermanada4 :: [Int] -> Bool hermanada4 xs = foldl (\ws p -> hermanos p && ws) True (zip xs (tail xs)) -- Comparación de eficiencia -- λ> hermanada1 [2,4..1000000] -- True -- (2.33 secs, 476,586,552 bytes) -- λ> hermanada2 [2,4..1000000] -- True -- (1.80 secs, 422,879,072 bytes) -- λ> hermanada3 [2,4..1000000] -- True -- (2.58 secs, 477,251,896 bytes) -- λ> hermanada4 [2,4..1000000] -- True -- (2.36 secs, 440,047,520 bytes) |
2 Comentarios