Mayor producto de las ramas de un árbol
Los árboles se pueden representar mediante el siguiente tipo de datos
|
1 2 |
data Arbol a = N a [Arbol a] deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
1 3 / \ /|\ 2 3 / | \ | 5 4 7 4 | /\ 6 2 1 |
se representan por
|
1 2 3 |
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
|
1 |
mayorProducto :: (Ord a, Num a) => Arbol a -> a |
tal que (mayorProducto a) es el mayor producto de las ramas del árbol a. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> 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
|
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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 |
import Test.QuickCheck data Arbol a = N a [Arbol a] deriving Show -- 1ª solución -- =========== mayorProducto1 :: (Ord a, Num a) => Arbol a -> a mayorProducto1 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] -- 2ª solución -- =========== mayorProducto2 :: (Ord a, Num a) => Arbol a -> a mayorProducto2 a = maximum (map product (ramas a)) -- 3ª solución -- =========== mayorProducto3 :: (Ord a, Num a) => Arbol a -> a mayorProducto3 = maximum . map product . ramas -- 4º solución -- =========== mayorProducto4 :: (Ord a, Num a) => Arbol a -> a mayorProducto4 = maximum . productosRamas -- (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] -- 5ª solución -- =========== mayorProducto5 :: (Ord a, Num a) => Arbol a -> a mayorProducto5 (N x []) = x mayorProducto5 (N x xs) | x > 0 = x * maximum (map mayorProducto5 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) -- 6ª solució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) (concatMap aux b) -- Comprobación de equivalencia -- ============================ -- (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo, -- > sample (arbolArbitrario 5 :: Gen (Arbol Int)) -- N 0 [N 0 []] -- N (-2) [] -- N 4 [] -- N 2 [N 4 []] -- N 8 [] -- N (-2) [N (-9) [],N 7 []] -- N 11 [] -- N (-11) [N 4 [],N 14 []] -- N 10 [N (-3) [],N 13 []] -- N 12 [N 11 []] -- N 20 [N (-18) [],N (-13) []] arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a) arbolArbitrario n = do x <- arbitrary ms <- sublistOf [0 .. n `div` 2] as <- mapM arbolArbitrario ms return (N x as) -- Arbol es una subclase de Arbitraria instance Arbitrary a => Arbitrary (Arbol a) where arbitrary = sized arbolArbitrario -- La propiedad es prop_mayorProducto :: Arbol Integer -> Bool prop_mayorProducto a = all (== mayorProducto1 a) [f a | f <- [ mayorProducto2 , mayorProducto3 , mayorProducto4 , mayorProducto5 , mayorProducto6 ]] -- La comprobación es -- λ> quickCheck prop_mayorProducto -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> ejArbol <- generate (arbolArbitrario 600 :: Gen (Arbol Integer)) -- λ> mayorProducto1 ejArbol -- 2419727651266241493467136000 -- (1.87 secs, 1,082,764,480 bytes) -- λ> mayorProducto2 ejArbol -- 2419727651266241493467136000 -- (1.57 secs, 1,023,144,008 bytes) -- λ> mayorProducto3 ejArbol -- 2419727651266241493467136000 -- (1.55 secs, 1,023,144,248 bytes) -- λ> mayorProducto4 ejArbol -- 2419727651266241493467136000 -- (1.60 secs, 824,473,800 bytes) -- λ> mayorProducto5 ejArbol -- 2419727651266241493467136000 -- (0.83 secs, 732,370,352 bytes) -- λ> mayorProducto6 ejArbol -- 2419727651266241493467136000 -- (0.98 secs, 817,473,344 bytes) -- -- λ> ejArbol2 <- generate (arbolArbitrario 700 :: Gen (Arbol Integer)) -- λ> mayorProducto5 ejArbol2 -- 1044758937398026715504640000000 -- (4.94 secs, 4,170,324,376 bytes) -- λ> mayorProducto6 ejArbol2 -- 1044758937398026715504640000000 -- (5.88 secs, 4,744,782,024 bytes) |
El código se encuentra en GitHub.
La elaboración de las soluciones se describe en el siguiente vídeo
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>