Árboles con n elementos
Los árboles binarios se pueden representar con
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
Definir las funciones
|
1 2 |
arboles :: Integer -> a -> [Arbol a] nArboles :: [Integer] |
tales que
- (arboles n x) es la lista de todos los árboles binarios con n elementos iguales a x. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
λ> arboles 0 7 [] λ> arboles 1 7 [H 7] λ> arboles 2 7 [] λ> arboles 3 7 [N 7 (H 7) (H 7)] λ> arboles 4 7 [] λ> arboles 5 7 [N 7 (H 7) (N 7 (H 7) (H 7)),N 7 (N 7 (H 7) (H 7)) (H 7)] λ> arboles 6 7 [] λ> arboles 7 7 [N 7 (H 7) (N 7 (H 7) (N 7 (H 7) (H 7))), N 7 (H 7) (N 7 (N 7 (H 7) (H 7)) (H 7)), N 7 (N 7 (H 7) (H 7)) (N 7 (H 7) (H 7)), N 7 (N 7 (H 7) (N 7 (H 7) (H 7))) (H 7), N 7 (N 7 (N 7 (H 7) (H 7)) (H 7)) (H 7)] |
- nArboles es la sucesión de los números de árboles con k elementos iguales a 7, con k ∈ {1,3,5,…}. Por ejemplo,
|
1 2 3 4 5 6 |
λ> take 14 nArboles [1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900] λ> nArboles !! 100 896519947090131496687170070074100632420837521538745909320 λ> length (show (nArboles !! 1000)) 598 |
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 |
import Data.List (genericLength) data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) -- 1ª definición de arboles -- ======================== arboles :: Integer -> a -> [Arbol a] arboles 0 _ = [] arboles 1 x = [H x] arboles n x = [N x i d | k <- [0..n-1], i <- arboles k x, d <- arboles (n-1-k) x] -- 2ª definición de arboles -- ======================== arboles2 :: Integer -> a -> [Arbol a] arboles2 0 _ = [] arboles2 1 x = [H x] arboles2 n x = [N x i d | k <- [1,3..n-1], i <- arboles2 k x, d <- arboles2 (n-1-k) x] -- 1ª definición de nArboles -- ========================= nArboles :: [Integer] nArboles = [genericLength (arboles2 n 7) | n <- [1,3..]] -- 2ª definición de nArboles -- ========================= -- Con la definición anterior se observa que nArboles es -- 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900 -- son los números de Catalan https://en.wikipedia.org/wiki/Catalan_number -- Una forma de calcularlos (ver https://oeis.org/A000108) es -- (2n)!/(n!(n+1)!) nArboles2 :: [Integer] nArboles2 = [factorial (2*n) `div` (factorial n * factorial (n+1)) | n <- [0..]] factorial :: Integer -> Integer factorial n = product [1..n] -- 3ª definición de nArboles -- ========================= -- 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900 -- 1 -- 1 = 1*1 -- 2 = 1*1 + 1*1 -- 5 = 1*2 + 1*1 + 2*1 -- 14 = 1*5 + 1*2 + 2*1 + 5*1 -- 42 = 1*14 + 1*5 + 2*2 + 5*1 + 14*1 nArboles3 :: [Integer] nArboles3 = 1 : aux [1] where aux cs = c : aux (c:cs) where c = sum (zipWith (*) cs (reverse cs)) -- Comparación de eficiencia -- ========================= -- λ> length (show (nArboles !! 12)) -- 6 -- (6.50 secs, 1,060,563,128 bytes) -- λ> length (show (nArboles2 !! 12)) -- 6 -- (0.01 secs, 108,520 bytes) -- λ> length (show (nArboles3 !! 12)) -- 6 -- (0.01 secs, 119,096 bytes) -- -- λ> length (show (nArboles2 !! 1000)) -- 598 -- (0.01 secs, 4,796,440 bytes) -- λ> length (show (nArboles3 !! 1000)) -- 598 -- (1.66 secs, 321,771,704 bytes) |
Pensamiento
Ni vale nada el fruto
cogido sin sazón …
Ni aunque te elogie un bruto
ha de tener razón.Antonio Machado
2 Comentarios