Árbol binario de divisores
El árbol binario de los divisores de 24 es
|
1 2 3 4 5 6 7 |
90 /\ 2 45 /\ 3 15 /\ 3 5 |
Se puede representar por
|
1 |
N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5))) |
usando el tipo de dato definido por
|
1 2 3 |
data Arbol = H Int | N Int Arbol Arbol deriving (Eq, Show) |
Análogamente se obtiene el árbol binario de cualquier número x: se comienza en x y en cada paso se tiene dos hijos (su menor divisor y su cociente) hasta obtener números primos en las hojas.
Definir las funciones
|
1 2 |
arbolDivisores :: Int -> Arbol hojasArbolDivisores :: Int -> [Int] |
tales que
- (arbolDivisores x) es el árbol binario de los divisores de x. Por ejemplo,
|
1 2 3 4 5 6 |
λ> arbolDivisores 90 N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5))) λ> arbolDivisores 24 N 24 (H 2) (N 12 (H 2) (N 6 (H 2) (H 3))) λ> arbolDivisores 300 N 300 (H 2) (N 150 (H 2) (N 75 (H 3) (N 25 (H 5) (H 5)))) |
- (hojasArbolDivisores x) es la lista de las hohas del árbol binario de los divisores de x. Por ejemplo
|
1 2 3 |
hojasArbolDivisores 90 == [2,3,3,5] hojasArbolDivisores 24 == [2,2,2,3] hojasArbolDivisores 300 == [2,2,3,5,5] |
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 |
import Data.Numbers.Primes (isPrime, primeFactors) data Arbol = H Int | N Int Arbol Arbol deriving (Eq, Show) -- 1ª solución -- =========== arbolDivisores :: Int -> Arbol arbolDivisores x | y == x = H x | otherwise = N x (H y) (arbolDivisores (x `div` y)) where y = menorDivisor x -- (menorDivisor x) es el menor divisor primo de x. Por ejemplo, -- menorDivisor 45 == 3 -- menorDivisor 5 == 5 menorDivisor :: Int -> Int menorDivisor x = head [y | y <- [2..x], x `mod` y == 0] hojasArbolDivisores :: Int -> [Int] hojasArbolDivisores = hojas . arbolDivisores -- (hojas a) es la lista de las hojas del árbol a. Por ejemplo, -- hojas (N 3 (H 4) (N 5 (H 7) (H 2))) == [4,7,2] hojas :: Arbol -> [Int] hojas (H x) = [x] hojas (N _ i d) = hojas i ++ hojas d -- 2ª solución -- =========== arbolDivisores2 :: Int -> Arbol arbolDivisores2 x | y == x = H x | otherwise = N x (H y) (arbolDivisores (x `div` y)) where (y:_) = primeFactors x hojasArbolDivisores2 :: Int -> [Int] hojasArbolDivisores2 = primeFactors |
Pensamiento
Cuando el Ser que se es hizo la nada
y reposó que bien lo merecía,
ya tuvo el día noche, y compañía
tuvo el amante en la ausencia de la amada.Antonio Machado
Un comentario