Mínima suma 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 |
1 1 1 / \ / \ / \ 8 3 5 3 5 3 | /|\ /|\ | 4 4 7 6 4 7 6 7 |
se representan por
|
1 2 3 4 |
ej1, ej2, ej3 :: Arbol Int ej1 = N 1 [N 8 [],N 3 [N 4 []]] ej2 = N 1 [N 5 [], N 3 [N 4 [], N 7 [], N 6 []]] ej3 = N 1 [N 5 [N 4 [], N 7 [], N 6 []], N 3 [N 7 []]] |
Definir la función
|
1 |
minimaSuma :: Arbol Int -> Int |
tal que (minimaSuma a) es el mínimo de las sumas de las ramas del árbol a. Por ejemplo,
|
1 2 3 |
minimaSuma ej1 == 8 minimaSuma ej2 == 6 minimaSuma ej3 == 10 |
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 |
data Arbol a = N a [Arbol a] deriving Show ej1, ej2, ej3 :: Arbol Int ej1 = N 1 [N 8 [],N 3 [N 4 []]] ej2 = N 1 [N 5 [], N 3 [N 4 [], N 7 [], N 6 []]] ej3 = N 1 [N 5 [N 4 [], N 7 [], N 6 []], N 3 [N 7 []]] -- 1ª definición -- ============= minimaSuma :: (Ord a, Num a) => Arbol a -> a minimaSuma a = minimum [sum xs | xs <- ramas a] -- (ramas a) es la lista de las ramas del árbol a. Por ejemplo, -- ghci> 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ª definición -- ============= minimaSuma2 :: Arbol Int -> Int minimaSuma2 (N x []) = x minimaSuma2 (N x as) = x + minimum (map minimaSuma2 as) |
Nota : muy parecida a la solución de albcercid