Menu Close

Potencias de dos más cercanas

Definir la función

   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,

   potenciasDeDosMasCercanas2 [6,7,8,9,2021]  ==  [4,8,8,8,2048]

Soluciones

-- 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>
Ejercicio, Inicial

4 soluciones de “Potencias de dos más cercanas

  1. Rubén Muñoz Mkrtchian
    potenciasDeDosMasCercanas :: [Integer] -> [Integer]
    potenciasDeDosMasCercanas xs = map aux xs
      where aux n
              | n <= 1    = 1
              | otherwise = head [x | x <- map (2^) [0..], abs (n-x) <= div x 2]
  2. Inés Mora Caro
     
    potenciasDeDosMasCercanas :: [Integer] -> [Integer]
    potenciasDeDosMasCercanas xs = map convertirPotencia2 xs
     
    convertirPotencia2 :: Integer -> Integer
    convertirPotencia2 n | minimum diferencia == head diferencia
                                     = menor
                         | otherwise = mayor
                              where diferencia = map abs $ (menor-n):[mayor-n]
                                    menor = last $ takeWhile (<=n) ys
                                    mayor = head $ dropWhile (<=n) ys
                                    ys = [2^x | x <- [0..]]
  3. Ángel Ruiz
    import Data.List       (minimumBy)
    import Data.Bits       (countLeadingZeros,testBit,popCount)
    import Test.QuickCheck (quickCheck)
     
    -- (menorDistancia z xs) es el elemento de xs más cercano a z respecto
    -- del valor absoluto. Por ejemplo,
    --    menorDistancia 6 [1,2,4,8]  ==  4
    --    menorDistancia 7 [1,2,4,8]  ==  8
    menorDistancia :: Integer -> [Integer] -> Integer
    menorDistancia z = minimumBy (x y -> compare (abs (z-x)) (abs (z-y)))
     
    -- 1ª definición
    potenciasDeDosMasCercanas1 :: [Integer] -> [Integer]
    potenciasDeDosMasCercanas1 = map aux
      where aux x | x <= 0    = 1
                  | otherwise =
                    let n = logBase 2 (fromInteger x) in
                      menorDistancia x [2^(floor n),2^(ceiling n)]
     
    -- (potenciaDeDosMasCercana1 x) es la potencia de dos más cercana a x.
    -- Por ejemplo,
    --    potenciaDeDosMasCercana1 6     ==  4
    --    potenciaDeDosMasCercana1 7     ==  8
    --    potenciaDeDosMasCercana1 2021  ==  2048
    potenciaDeDosMasCercana1 :: Int -> Int
    potenciaDeDosMasCercana1 x
      | x <= 0    = 1
      | otherwise =
        let n = countLeadingZeros x in
          case testBit x (62 - n) of
            True -> case popCount x of
                      2 -> 2^(63 - n)
                      _ -> 2^(64 - n)
            _    -> 2^(63 - n)
     
    -- 2ª definición (con bits y restringida a Int)
    potenciasDeDosMasCercanas2 :: [Int] -> [Int]
    potenciasDeDosMasCercanas2 = map potenciaDeDosMasCercana1
     
    -- Equivalencia de las soluciones
    -- ==============================
     
    -- La propiedad es
    prop_equiv :: [Integer] -> Bool
    prop_equiv xs =
      potenciasDeDosMasCercanas1 xs ==
      map toInteger (potenciasDeDosMasCercanas2 (map fromInteger xs))
     
    -- La comprobación es
    --    λ> quickCheck prop_equiv
    --    +++ OK, passed 100 tests.
    --
    -- Sin embargo,
    --    let a = 2^62 + 2^61 + 1
    --    potenciasDeDosMasCercanas1 [a]  ==  [9223372036854775808]
    --    potenciasDeDosMasCercanas2 [a]  ==  [-9223372036854775808]
     
    -- 3ª definición (mezclando las anteriores)
    potenciasDeDosMasCercanas3 :: [Integer] -> [Integer]
    potenciasDeDosMasCercanas3 = map aux
      where aux x
              | x < 6917529027641081857 =
                toInteger (potenciaDeDosMasCercana1 (fromInteger x))
              | otherwise               =
                let n = logBase 2 (fromInteger x) in
                  menorDistancia x [2^(floor n),2^(ceiling n)]
     
    -- (potenciaDeDosMasCercana2 x) es la potencia de dos más cercana a x.
    -- Por ejemplo,
    --    potenciaDeDosMasCercana2 6     ==  4
    --    potenciaDeDosMasCercana2 7     ==  8
    --    potenciaDeDosMasCercana2 2021  ==  2048
    potenciaDeDosMasCercana2 :: Integer -> Integer
    potenciaDeDosMasCercana2 x
      | x <= 0    = 1
      | otherwise =
        let n = floor (logBase 2 (fromInteger x)) in
          case testBit x (n - 1) of
            True -> case popCount x of
                      2 -> 2^n
                      _ -> 2^(n+1)
            _    -> 2^n
     
    -- 4ª definición (con bits y logBase)
    potenciasDeDosMasCercanas4 :: [Integer] -> [Integer]
    potenciasDeDosMasCercanas4 = map potenciaDeDosMasCercana2
     
    -- (potenciasDeNMasCercanas n xs) es la lista sustituyendo cada elemento
    -- de xs por su potencia de n más cercana (en el caso de que haya dos
    -- equidistantes se elige la menor). Por ejemplo,
    --    potenciasDeNMasCercanas 2 [6,7,8,9,2021]  ==  [4,8,8,8,2048]
    --    potenciasDeNMasCercanas 3 [6,7,8,9,2021]  ==  [3,9,9,9,2187]
    potenciasDeNMasCercanas :: Integer -> [Integer] -> [Integer]
    potenciasDeNMasCercanas n = map (aux n)
      where aux n x | x <= 0    = 1
                    | otherwise =
                      let m = logBase (fromInteger n) (fromInteger x) in
                        menorDistancia x [n^(floor m),n^(ceiling m)]
     
    -- 5ª definición
    potenciasDeDosMasCercanas5 :: [Integer] -> [Integer]
    potenciasDeDosMasCercanas5 = potenciasDeNMasCercanas 2
     
    -- Equivalencia de las soluciones
    -- ==============================
     
    -- La propiedad es
    prop_equiv2 :: [Integer] -> Bool
    prop_equiv2 xs =
      potenciasDeDosMasCercanas1 xs == potenciasDeDosMasCercanas3 xs &&
      potenciasDeDosMasCercanas3 xs == potenciasDeDosMasCercanas4 xs &&
      potenciasDeDosMasCercanas4 xs == potenciasDeDosMasCercanas5 xs
     
    -- La comprobación es
    --    λ> quickCheck prop_equiv2
    --    +++ OK, passed 100 tests.
     
    -- Comparación de eficiencia
    -- =========================
     
    -- λ> last (potenciasDeDosMasCercanas1 [1..2^23])
    -- 8388608
    -- (2.83 secs, 1,342,267,992 bytes)
    -- λ> last (potenciasDeDosMasCercanas2 [1..2^23])
    -- 8388608
    -- (1.38 secs, 1,409,375,112 bytes)
    -- λ> last (potenciasDeDosMasCercanas3 [1..2^23])
    -- 8388608
    -- (2.85 secs, 1,342,268,000 bytes)
    -- λ> last (potenciasDeDosMasCercanas4 [1..2^23])
    -- 8388608
    -- (2.87 secs, 1,342,267,808 bytes)
    -- λ> last (potenciasDeDosMasCercanas5 [1..2^23])
    -- 8388608
    -- (2.85 secs, 1,342,268,040 bytes)
  4. Joaquín Infante Rodríguez
    import Data.List
     
    potenciasDeDos :: [Integer]
    potenciasDeDos = [2^x | x<-[0..]]
     
    potenciaDeDosMasCercana :: Integer -> Integer
    potenciaDeDosMasCercana x
      | elem x (takeWhile (<=x) potenciasDeDos)                                                                                                 = x
      | abs (last(takeWhile (<=x) potenciasDeDos) - x) <= abs ((head (dropWhile (<=x) potenciasDeDos) - x)) = last(takeWhile (<=x) potenciasDeDos)
      | otherwise                                                                                                                                                    = head (dropWhile (<=x) potenciasDeDos)
     
     
    potenciasDeDosMasCercanas :: [Integer] -> [Integer]
    potenciasDeDosMasCercanas [] = []
    potenciasDeDosMasCercanas (x:xs) = potenciaDeDosMasCercana x : potenciasDeDosMasCercanas xs

Leave a Reply to Inés Mora Caro Cancel reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.