Menu Close

Reducción de opuestos

José A. Alonso,

Se considera el siguiente procedimiento de reducción de listas: busca un par de elementos consecutivos iguales pero con signos opuestos, se eliminan dichos elementos y se continúa el proceso hasta que no se encuentren pares de elementos consecutivos iguales pero con signos opuestos. Por ejemplo, la reducción de [-2,1,-1,2,3,4,-3] es

   [-2,1,-1,2,3,4,-3]    (se elimina el par (1,-1))
   -> [-2,2,3,4,-3]      (se elimina el par (-2,2))
   -> [3,4,-3]           (el par (3,-3) no son consecutivos)

Definir la función

   reducida :: [Int] -> [Int]

tal que (reducida xs) es la lista obtenida aplicando a xs el de eliminación de pares de elementos consecutivos opuestos. Por ejemplo,

   reducida [-2,1,-1,2,3,4,-3]           == [3,4,-3]
   reducida [-2,1,-1,2,3,-4,4,-3]        == []
   reducida [-2,1,-1,2,5,3,-4,4,-3]      == [5]
   reducida [-2,1,-1,2,5,3,-4,4,-3,-5]   == []

Soluciones

-- 1ª solución
-- ===========
 
reducida :: [Int] -> [Int]
reducida xs | xs == ys  = xs
            | otherwise = reducida ys
            where ys = paso xs
 
paso :: [Int] -> [Int]
paso [] = []
paso [x] = [x]
paso (x:y:zs) | x == -y   = paso zs
              | otherwise = x : paso (y:zs)
 
-- 2ª solución
-- ===========
 
reducida2 :: [Int] -> [Int]
reducida2 xs = aux xs []
    where aux [] ys                   = reverse ys
          aux (x:xs) (y:ys) | x == -y = aux xs ys
          aux (x:xs) ys               = aux xs (x:ys)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> reducida (take (10^7) (cycle [1,-1]))
--    []
--    (9.40 secs, 1,280,127,720 bytes)
--    λ> reducida2 (take (10^7) (cycle [1,-1]))
--    []
--    (12.16 secs, 2,080,127,560 bytes)
Inicial
,

4 soluciones de “Reducción de opuestos”

  1. Responder
    alerodrod5 
    reducida :: [Int] -> [Int]
reducida xs = head (filter p (iterate aux xs))
 
  where aux [] = []
        aux [x] = [x]
        aux (x:y:xs) | x == -y = xs
                     | otherwise = x: aux(y:xs)
        p xs = aux xs == xs
  2. Responder
    menvealer 
     
reducida :: [Int] -> [Int]
reducida = until aceptable elimConsOpuestos 
  where aceptable = noHayConsOpuestos
 
elimConsOpuestos :: [Int] -> [Int]
elimConsOpuestos [] = []
elimConsOpuestos [x] = [x]
elimConsOpuestos (x:y:xs)
  | x == -y = elimConsOpuestos xs
  | otherwise = x: elimConsOpuestos (y:xs)
 
noHayConsOpuestos :: [Int] -> Bool
noHayConsOpuestos xs = elimConsOpuestos xs == xs
  3. Responder
    agumaragu1 
    reducida :: [Int] -> [Int]
reducida xs = paso xs []
  where paso (y:ys) [] = paso ys [y]
        paso (y:ys) zzs@(z:zs) | y == -z = paso ys zs
                               | otherwise = paso ys (y:zzs)
        paso _ zs = reverse zs
  4. Responder
    esppercab 
     
reducida :: [Int] -> [Int]
reducida xs |ultimaRed xs    = xs
            |otherwise       = reducida (reducir xs)
 
ultimaRed :: [Int] -> Bool
ultimaRed xs = (reducir xs) == xs
 
reducir :: [Int] -> [Int]
reducir [] = []
reducir (x:[]) = [x]
reducir (x:y:xs) |x == -y        = reducida xs
                  |otherwise      = x:(reducida (y:xs))

Escribe tu solución

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