Menu Close

Máximo producto de pares en la lista

Definir la función

  maximoProducto :: [Int] -> Maybe Int

tal que (maximoProducto xs) es el mayor elemento de xs que se puede escribir
como producto de dos elementos distintos de xs o Nothing, en el caso de que
ningún elemento de xs se pueda escribir como producto de dos elementos
distintos de xs, donde xs es una lista de números mayores que 0. Por ejemplo,

   maximoProducto [10, 3, 5, 30, 35]       ==  Just 30
   maximoProducto [10, 2, 2, 4, 30, 35]    ==  Just 4
   maximoProducto [17, 2, 1, 35, 30]       ==  Just 35
   maximoProducto [2,4]                    ==  Nothing
   maximoProducto [2, 5, 7, 8]             ==  Nothing
   maximoProducto [10, 2, 4, 30, 35]       ==  Nothing
   maximoProducto [1+2^n | n <- [1..10^6]] ==  Just 4611686018427387905

En el primer ejemplo, 30 es el producto de 10 y 3; en el segundo, 4 es el producto de 2 y 2 y en el tercero, 35 es el producto de 1 y 35.

Soluciones

import Data.List (delete, nub, sort)
 
-- 1ª solución
-- ===========
 
maximoProducto1 :: [Int] -> Maybe Int
maximoProducto1 xs
  | null zs   = Nothing
  | otherwise = Just (head zs)
  where
    ys = reverse (sort xs)
    zs = [y | y <- ys, y `elem` productos xs]
 
-- (productos xs) es la lista de los números que son productos de dos
-- elementos de xs. Por ejemplo, 
--   productos [4,3,5,2]  ==  [12,20,8,15,6,10]
productos :: [Int] -> [Int]
productos xs =
  nub [y * z | y <- xs, z <- delete y xs]
 
-- 2ª solución
-- ===========
 
maximoProducto2 :: [Int] -> Maybe Int
maximoProducto2 xs = aux (reverse (sort xs))
  where aux []     = Nothing
        aux (y:ys) | esProducto y xs = Just y
                   | otherwise       = aux ys
 
esProducto :: Int -> [Int] -> Bool
esProducto y []     = False
esProducto y (x:xs) = 
  (m == 0 && d `elem` xs) || esProducto y xs
  where (d,m) = divMod y x  
 
-- Comparación de eficiencia
-- =========================
 
--    λ> maximoProducto1 [1..10^4]
--    Just 10000
--    (2.60 secs, 0 bytes)
--    λ> maximoProducto2 [1..10^4]
--    Just 10000
--    (0.01 secs, 0 bytes)

4 soluciones de “Máximo producto de pares en la lista

  1. enrnarbej
    maximoProducto :: [Int] -> Maybe Int
    maximoProducto xs = aux ((reverse . sort) xs)
      where
        aux [] = Nothing
        aux (x:xs) | divide x (x:xs) = Just x
                   | otherwise       = aux xs
     
    divide :: Int -> [Int] -> Bool
    divide _ []     = False 
    divide n (x:ns)
      | n `mod` x == 0 && (n `div` x) `elem` ns = True
      | otherwise                               = divide n ns
  2. Pablo Rabán
    maximoProducto :: [Int] -> Maybe Int
    maximoProducto xs | null ([ x | x <- xs , x `elem` productorio xs]) = Nothing 
                      | otherwise = Just (maximum [ x | x <- xs , x `elem` productorio xs])
     
    productorio xs = [ x*y | x <- xs , y <- delete x xs]
  3. albcercid
    maximoProducto :: [Int] -> Maybe Int
    maximoProducto xs = aux (reverse p) p
      where p = sort xs
            aux [] _ = Nothing
            aux (x:xs) ys | propt x ys = Just x
                          | otherwise = aux xs ys
            propt x ys = not (null [a | a <- takeWhile (div x 2>=) ys
                                      , rem x a == 0
                                      , elem (div x a) ys
                                      , a^2 /= x || rep a ys 0])
            rep a ys 2 = True
            rep a (y:ys) t | a == y = rep a ys (t+1)
                           | otherwise = rep a ys t
            rep _ [] t = False
  4. Juanjo Ortega (juaorture)
     
    import Data.List
     
    maximoProducto :: [Int] -> Maybe Int
    maximoProducto xs = find (esProducto xs) (reverse $ sort xs)
     
    esProducto :: [Int] -> Int -> Bool
    esProducto xs n = not $ null [ (a,b) | a <- xs
                                         , let b = n `div` a
                                         , n `mod` a == 0
                                         , b `elem` xs\[a]]

Escribe tu solución

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