Ir al contenido principal

Árbol binario de divisores

El árbol binario de los divisores de 24 es

 90
 /\
2  45
   /\
  3  15
     /\
    3  5

Se puede representar por

N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))

usando el tipo de dato definido por

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

arbolDivisores      :: Int -> Arbol
hojasArbolDivisores :: Int -> [Int]

tales que

  • (arbolDivisores x) es el árbol binario de los divisores de x. Por ejemplo,
λ> 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
hojasArbolDivisores 90   ==  [2,3,3,5]
hojasArbolDivisores 24   ==  [2,2,2,3]
hojasArbolDivisores 300  ==  [2,2,3,5,5]

Soluciones

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