Menu Close

Árbol binario de divisores

José A. Alonso,

El árbol binario de los divisores de 90 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 (primeFactors)
 
data Arbol = H Int
           | N Int Arbol Arbol
  deriving (Eq, Show)
 
-- Definición de arbolDivisores
-- ============================
 
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]
 
-- 1ª definición de hojasArbolDivisores
-- ====================================
 
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ª definición de hojasArbolDivisores
-- ====================================
 
hojasArbolDivisores2 :: Int -> [Int]
hojasArbolDivisores2 = primeFactors

Pensamiento

Entre las brevas soy blando;
entre las rocas, de piedra.
¡Malo!

Antonio Machado

Inicial
, , , , , ,

5 soluciones de “Árbol binario de divisores”

  1. Responder
    frahidzam 
    import Data.Numbers.Primes (isPrime, primeFactors)
 
data Arbol = H Int
           | N Int Arbol Arbol
  deriving (Eq, Show)
 
arbolDivisores :: Int -> Arbol
arbolDivisores n
  | isPrime n = H n
  | otherwise = N n (H b) (arbolDivisores (div n b))
  where b = head (primeFactors n)
 
hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores n = primeFactors n
  2. Responder
    luipromor 
    import Data.Numbers.Primes (isPrime, primeFactors)
 
data Arbol = H Int
           | N Int Arbol Arbol
  deriving (Eq, Show)
 
arbolDivisores :: Int -> Arbol
arbolDivisores n = aux n $ primeFactors n
  where aux n [x]    = H n
        aux n (x:xs) = N n (H x) $! aux (div n x) xs
 
hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores = primeFactors
  3. Responder
    rafasidia 
    data Arbol = H Int
           | N Int Arbol Arbol
  deriving (Eq, Show)
 
arbolDivisores :: Int -> Arbol
arbolDivisores x
  | esPrimo x = H x
  | otherwise = N x (H y) (arbolDivisores (div x y))
  where y = primerDivisor x
 
esPrimo :: Int -> Bool
esPrimo x = divisores x == [1,x]
 
divisores :: Int -> [Int]
divisores x = [z | z <- [1..x] , rem x z == 0]
 
primerDivisor :: Int -> Int
primerDivisor x = head [z | z <- divisores x, z /= 1]
 
hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores x
  | esPrimo x = [x]
  | otherwise = [y] ++ hojasArbolDivisores (div x y) 
  where y = primerDivisor x
  4. Responder
    marlimand 
    import Data.Numbers.Primes
data Arbol = H Int
              | N Int Arbol Arbol
     deriving (Eq, Show)
 
arbolDivisores  :: Int -> Arbol
arbolDivisores x | isPrime x = H x
                 | otherwise = N x (H y) (arbolDivisores z)
                   where y = menorDivisor x
                         z = rem x y
 
menorDivisor x = head [n | n<-[2..x] , mod x n ==0]
 
hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores = primeFactors
  5. Responder
    javmarcha1 
    import Data.Numbers.Primes
 
data Arbol = H Int
              | N Int Arbol Arbol
     deriving (Eq, Show)
 
arbolDivisores :: Int -> Arbol
arbolDivisores x | isPrime x = H x
arbolDivisores x = N x (arbolDivisores (a x)) (arbolDivisores (b x))
  where a x = head [y | y <- [2..(div x 2)], rem x y == 0]
        b x = last [y | y <- [2..(div x 2)], rem x y == 0]
 
hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores x | isPrime x = [x]
                      | otherwise = (a x):(hojasArbolDivisores (b x))
  where a x = head [y | y <- [2..(div x 2)], rem x y == 0]
        b x = last [y | y <- [2..(div x 2)], rem x y == 0]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.