Menu Close

Mayor producto de las ramas de un árbol

 

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol a = N a [Arbol a]
                  deriving Show

Por ejemplo, los árboles

      1              3
    /  \            /|\ 
   2   3           / | \
       |          5  4  7
       4          |     /\ 
                  6    2  1

se representan por

   ej1, ej2 :: Arbol Int
   ej1 = N 1 [N 2 [],N 3 [N 4 []]]
   ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]

Definir la función

   mayorProducto :: (Ord a, Num a) => Arbol a -> a

tal que (mayorProducto a) es el mayor producto de las ramas del árbol a. Por ejemplo,

   λ> mayorProducto (N 1 [N 2 [], N  3 []])
   3
   λ> mayorProducto (N 1 [N 8 [], N  4 [N 3 []]])
   12
   λ> mayorProducto (N 1 [N 2 [],N 3 [N 4 []]])
   12
   λ> mayorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
   90
   λ> mayorProducto (N (-8) [N 0 [N (-9) []],N 6 []])
   0
   λ> a = N (-4) [N (-7) [],N 14 [N 19 []],N (-1) [N (-6) [],N 21 []],N (-4) []]
   λ> mayorProducto a
   84

Soluciones

data Arbol a = N a [Arbol a]
  deriving Show
 
-- 1º definición.
mayorProducto :: (Ord a, Num a) => Arbol a -> a
mayorProducto a = maximum (productosRamas a)
 
-- (productosRamas a) es la lista de los productos de las ramas
-- del árbol a. Por ejemplo,
--    λ> productosRamas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
--    [90,12,42,21]
productosRamas :: (Ord a, Num a) => Arbol a -> [a]
productosRamas (N x []) = [x]
productosRamas (N x xs) = [x * y | a <- xs, y <- productosRamas a]
 
-- 2ª definición.
mayorProducto2 :: (Ord a, Num a) => Arbol a -> a
mayorProducto2 (N x []) = x
mayorProducto2 (N x xs)
  | x > 0     = x * maximum (map mayorProducto2 xs)
  | x == 0    = 0
  | otherwise = x * minimum (map menorProducto xs)
 
-- (menorProducto a) es el menor producto de las ramas del árbol
-- a. Por ejemplo,
--    λ> menorProducto (N 1 [N 2 [], N  3 []])
--    2
--    λ> menorProducto (N 1 [N 8 [], N  4 [N 3 []]])
--    8
--    λ> menorProducto (N 1 [N 2 [],N 3 [N 4 []]])
--    2
--    λ> menorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
--    12
menorProducto :: (Ord a, Num a) => Arbol a -> a
menorProducto (N x []) = x
menorProducto (N x xs)
  | x > 0     = x * minimum (map menorProducto xs)
  | x == 0    = 0
  | otherwise = x * maximum (map mayorProducto2 xs)
 
-- 3ª definición.
mayorProducto3 :: (Ord a, Num a) => Arbol a -> a
mayorProducto3 a = maximum [product xs | xs <- ramas a]
 
-- (ramas a) es la lista de las ramas del árbol a. Por ejemplo,
--    λ> ramas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
--    [[3,5,6],[3,4],[3,7,2],[3,7,1]]
ramas :: Arbol b -> [[b]]
ramas (N x []) = [[x]]
ramas (N x as) = [x : xs | a <- as, xs <- ramas a]
 
-- 4ª definición.
mayorProducto4 :: (Ord a, Num a) => Arbol a -> a
mayorProducto4 a = maximum (map product (ramas a))
 
-- 5ª definición.
mayorProducto5 :: (Ord a, Num a) => Arbol a -> a
mayorProducto5 = maximum . map product . ramas
 
-- 6ª definición.
mayorProducto6 :: (Ord a, Num a) => Arbol a -> a
mayorProducto6 = maximum . aux
  where aux (N a []) = [a]
        aux (N a b)  = [v,u]
          where u = maximum g
                v = minimum g
                g = map (*a) (concat (map aux b))
Medio

11 soluciones de “Mayor producto de las ramas de un árbol

  1. alerodrod5
     
    data Arbol a = N a [Arbol a]
                   deriving Show
     
     
    mayorProducto :: (Ord a, Num a) => Arbol a -> a
    mayorProducto (N x []) = x
    mayorProducto (N x xs ) =maximum [x*aux y | y <- xs]
      where aux (N x []) = x
            aux (N x xs) |x > 0 = maximum [(x*aux y) | y <- xs]
                         | otherwise = minimum [(x*aux y) | y <- xs]
    • angruicam1

      Buenas, la definición de mayorProducto no es correcta. Por ejemplo:

      λ> a= (N (-4) [N 14 [N 19 [N 2 [N (4) [N (-3) []]], N (-7) []]]])
      λ> mayorProducto a
      25536
      λ> mayorProducto2 a
      7448

      Donde mayorProducto2 es tu definición. Puedes comprobar dibujando el árbol que tu función calcula el producto de la rama derecha, pero es mayor el producto de la rama izquierda.

      • angruicam1

        Puedes comprobar un caso más sencillo como:

        λ> a= (N (-1) [N 1 [N 2 [N (-1) []], N (-1) []]])
        λ> mayorProducto a
        2
        λ> mayorProducto2 a
        1

  2. angruicam1
    data Arbol a = N a [Arbol a]
                   deriving Show
     
    mayorProducto :: (Ord a, Num a) => Arbol a -> a
    mayorProducto = maximum . productos
     
    productos :: (Ord a, Num a) => Arbol a -> [a]
    productos (N a []) = [a]
    productos (N a b)  = map (*a) . concat $ map productos b
    • jaibengue

      ¿Qué te parece esta definición para árboles lo suficientemente grandes?

      data Arbol a = N a [Arbol a]
                    deriving Show
       
      mayorProducto :: (Ord a, Num a) => Arbol a -> a
      mayorProducto = maximum . aux
        where aux (N a []) = [a]
              aux (N a b)  = [v,u]
                where g = map (*a) . concat $ map aux b
                      u = maximum g
                      v = minimum g
  3. antnavoro
    data Arbol a = N a [Arbol a]
                  deriving Show
     
    mayorProducto :: (Ord a, Num a) => Arbol a -> a
    mayorProducto (N a x) = a * aux x
      where aux :: (Ord a, Num a) => [Arbol a] -> a
            aux [] = 1
            aux ((N a x):xs) = max (a*aux x) (aux xs)
    • angruicam1

      Buenas, la definición no es correcta. Por ejemplo:

      λ> a = N (-4) [N (-7) [], N 14 [N 19 []], N (-1) [N (-6) [], N 21 []], N (-4) []]
      λ> mayorProducto a
      84
      λ> mayorProducto2 a
      -1064

      Donde mayorProducto2 es tu definición.

      • antnavoro

        Cierto, debí haber comprobado todos los ejemplos. Espero que esta nueva solución sea correcta aunque no sea demasiado eficiente, y corrígeme si no lo es.

        data Arbol a = N a [Arbol a]
                          deriving Show
         
        mayorProducto :: (Ord a, Num a) => Arbol a -> a
        mayorProducto (N a x) | a>= 0 = a * aux x
                              | otherwise = a * aux2 x
          where aux :: (Ord a, Num a) => [Arbol a] -> a
                aux [] = 1
                aux [N a []] = a
                aux ((N a x):xs) | a >= 0 = max (a*aux x) (aux xs)
                                 | otherwise = max (a*aux2 x) (aux xs)
                aux2 :: (Ord a, Num a) => [Arbol a] -> a
                aux2 [] = 1
                aux2 [N a []] = a
                aux2 ((N a x):xs) | a >= 0 = min (a*aux2 x) (aux2 xs)
                                  | otherwise = min (a*aux x) (aux2 xs)
        • antgongar

          Para el árbol (N (-5) [N 2 [],N (-12) [N (-11) []]]) da -5 y debería de dar -10.

Los comentarios están cerrados.