Potencias de dos más cercanas
Definir la función
1 |
potenciasDeDosMasCercanas :: [Integer] -> [Integer] |
tal que (potenciasDeDosMasCercanas xs) es la lista sustituyendo cada elemento de xs por su potencia de dos más cercana (en el caso de que haya dos equidistantes se elige la menor). Por ejemplo,
1 |
potenciasDeDosMasCercanas2 [6,7,8,9,2021] == [4,8,8,8,2048] |
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 69 |
-- 1ª solución -- =========== potenciasDeDosMasCercanas :: [Integer] -> [Integer] potenciasDeDosMasCercanas = map potenciaDeDosMasCercana -- (potenciaDeDosMasCercana n) es la potencia de dos más cercana (en el -- caso de que haya dos equidistantes se elige la menor). Por ejemplo, -- potenciaDeDosMasCercana 6 == 4 -- potenciaDeDosMasCercana 7 == 8 -- potenciaDeDosMasCercana 8 == 8 -- potenciaDeDosMasCercana 9 == 8 potenciaDeDosMasCercana :: Integer -> Integer potenciaDeDosMasCercana n | dx <= dy = x | otherwise = y where (x,y) = potenciasDeDosCercanas n dx = n - x dy = y - n -- (potenciasDeDosMasCercanas n) es par formado por las dos potencias de -- dos más cercana a n. Por ejemplo, -- potenciasDeDosCercanas 6 == (4,8) -- potenciasDeDosCercanas 7 == (4,8) -- potenciasDeDosCercanas 8 == (4,8) -- potenciasDeDosCercanas 9 == (8,16) potenciasDeDosCercanas :: Integer -> (Integer, Integer) potenciasDeDosCercanas n = (x `div` 2, x) where x = menorPotenciaDeDosMayorOIgual n -- (menorPotenciaDeDosMayorOIgual n) es la menor potencia de dos mayor o -- igual que n. Por ejemplo, -- menorPotenciaDeDosMayorOIgual 6 == 8 -- menorPotenciaDeDosMayorOIgual 8 == 8 menorPotenciaDeDosMayorOIgual :: Integer -> Integer menorPotenciaDeDosMayorOIgual n = head [2^x | x <- [0..], 2^x >= n] -- 2ª solución -- =========== potenciasDeDosMasCercanas2 :: [Integer] -> [Integer] potenciasDeDosMasCercanas2 = map potenciaDeDosMasCercana2 potenciaDeDosMasCercana2 :: Integer -> Integer potenciaDeDosMasCercana2 n = snd (min (n-x,x) (y-n,y)) where (x,y) = potenciasDeDosCercanas2 n potenciasDeDosCercanas2 :: Integer -> (Integer, Integer) potenciasDeDosCercanas2 n = (x `div` 2, x) where (x:_) = dropWhile (<n) potenciasDeDos -- potenciasDeDos es la lista de las potencias de dos. Por ejemplo, -- take 11 potenciasDeDos == [1,2,4,8,16,32,64,128,256,512,1024] potenciasDeDos :: [Integer] potenciasDeDos = iterate (*2) 1 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> maximum (potenciasDeDosMasCercanas [10^5..10^6]) -- 1048576 -- (18.28 secs, 20,835,181,624 bytes) -- λ> maximum (potenciasDeDosMasCercanas2 [10^5..10^6]) -- 1048576 -- (2.44 secs, 830,307,736 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>