Suma de la lista reducida
Definir las siguientes funciones
1 2 3 |
transformada :: Integral a => [a] -> [a] reducida :: Integral a => [a] -> [a] sumaReducida :: Integral a => [a] -> a |
tales que
- (transformada xs) es la lista obtenida sustituyendo en el primer de elementos consecutivos de xs el mayor por su diferencia, donde se supone que xs es una lista de enteros positivos. Por ejemplo,
1 2 3 4 |
transformada [7,2,6] == [5,2,6] transformada [2,7,6] == [2,5,6] transformada [2,2,6] == [2,2,4] transformada [2,2,2] == [2,2,2] |
- (reducida xs) es la lista obtenida aplicando la transformación anterior mientras sea posible (es decir, mientras tenga elementos distintos), donde se supone que xs es una lista de enteros positivos. Por ejemplo,
1 2 |
reducida [7,2,6] == [1,1,1] reducida [6,9,21] == [3,3,3] |
- (sumaReducida xs) es la suma de la reducida de la lista xs. Por ejemplo,
1 2 |
sumaReducida1 [7,2,6] == 3 sumaReducida1 [6,9,21] == 9 |
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 56 57 58 59 60 61 62 63 64 65 66 67 68 |
import Data.List (genericLength) -- Definición de transformada -- ========================== transformada :: Integral a => [a] -> [a] transformada [] = [] transformada [x] = [x] transformada (x:y:zs) | x > y = x-y : y : zs | x < y = x : y-x : zs | otherwise = x : transformada (y:zs) -- 1ª definición de reducida -- ========================= reducida1 :: Integral a => [a] -> [a] reducida1 xs | xs == ys = xs | otherwise = reducida ys where ys = transformada xs -- 2ª definición de reducida -- ========================= reducida2 :: Integral a => [a] -> [a] reducida2 xs = replicate (length xs) (foldl1 gcd xs) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sum (reducida1 [2,4..4*10^6]) -- 4000000 -- (1.97 secs, 1,277,797,888 bytes) -- λ> sum (reducida2 [2,4..4*10^6]) -- 4000000 -- (1.92 secs, 1,277,798,344 bytes) -- Definición de reducida -- ======================= reducida :: Integral a => [a] -> [a] reducida = reducida2 -- 1ª definición de sumaReducida -- ============================= sumaReducida1 :: Integral a => [a] -> a sumaReducida1 = sum . reducida -- 2ª solución -- =========== sumaReducida2 :: Integral a => [a] -> a sumaReducida2 xs = genericLength xs * foldl1 gcd xs -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sumaReducida1 [2,4..4*10^6] -- 4000000 -- (2.53 secs, 1,277,796,760 bytes) -- λ> sumaReducida2 [2,4..4*10^6] -- 4000000 -- (1.89 secs, 1,214,376,960 bytes) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
4 Comentarios