Cambios de signo
En una lista xs se produce un cambio de signo por cada elemento x de la lista junto el primero de los elementos de xs con signo opuesto al de x. Por ejemplo,en la lista [6,5,-4,0,-2,-7,0,-8,-1,4] hay 2 cambios de signo (entre (5,-4) y (-1,4)) y en la lista [6,5,-4,0, 2,-7,0,-8,-1,4] hay 4 cambios de signo (entre (5,-4), (-4,2), (2,-7) y(-1,4)).
Definir la función
|
1 |
nCambios :: (Num a, Ord a) => [a] -> Int |
tal que (nCambios xs) es el número de cambios de signos de la lista xs. Por ejemplo,
|
1 2 3 |
nCambios [] == 0 nCambios [6,5,-4,0,-2,-7,0,-8,-1,4] == 2 nCambios [6,5,-4,0, 2,-7,0,-8,-1,4] == 4 |
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 |
import Data.List (group) -- 1ª definición nCambios1 :: (Num a, Ord a) => [a] -> Int nCambios1 = length . cambios -- (cambios xs) es la lista de los pares de elementos de xs entre los -- que se producen cambios de signo. Por ejemplo, -- cambios [6,5,-4,0,-2,-7,0,-8,-1,4] == [(5,-4),(-1,4)] -- cambios [6,5,-4,0, 2,-7,0,-8,-1,4] == [(5,-4),(-4,2),(2,-7),(-1,4)] cambios :: (Num a, Ord a) => [a] -> [(a,a)] cambios xs = [(x,y) | (x,y) <- zip ys (tail ys), x*y < 0] where ys = filter (/=0) xs -- 2ª definición nCambios2 :: (Num a, Ord a) => [a] -> Int nCambios2 [] = 0 nCambios2 xs = length (group (filter (/=0) (map signum xs))) - 1 -- 3ª definición nCambios3 :: (Num a, Ord a) => [a] -> Int nCambios3 = pred . length . group . filter (/=0) . map signum -- Comparación de eficiencia -- ========================= -- λ> nCambios1 (take (2*10^6) (cycle [3,0,-3])) -- 1333332 -- (3.84 secs, 679,805,392 bytes) -- λ> nCambios2 (take (2*10^6) (cycle [3,0,-3])) -- 1333332 -- (0.98 secs, 694,247,368 bytes) -- λ> nCambios3 (take (2*10^6) (cycle [3,0,-3])) -- 1333332 -- (0.95 secs, 708,118,976 bytes) |
2 Comentarios