Menu Close

Caminos minimales en un árbol numérico

En la librería Data.Tree se definen los tipos de árboles y bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u.v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

       6
      / \
     5   3 
     |   |
     4   2
    / \  |
   3   2 1 
   |   | 
   2   1
   |
   1

Definir las siguientes funciones

   mayoresDivisores :: Int -> [Int]
   arbol            :: Int -> Tree Int
   caminos          :: Int -> [[Int]]
   caminosMinimales :: Int -> [[Int]]

tales que
+ (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

     mayoresDivisores 24  ==  [12,8,6]
     mayoresDivisores 16  ==  [8,4]
     mayoresDivisores 10  ==  [5]
     mayoresDivisores 17  ==  []
  • (arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
     λ> putStrLn (drawTree (fmap show (arbol 6)))
     6
     |
     +- 5
     |  |
     |  `- 4
     |     |
     |     +- 3
     |     |  |
     |     |  `- 2
     |     |     |
     |     |     `- 1
     |     |
     |     `- 2
     |        |
     |        `- 1
     |
     `- 3
        |
        `- 2
           |
           `- 1
  • (caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
     λ> caminos 6
     [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
  • (caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
     λ> caminosMinimales 6
     [[6,3,2,1]]
     λ> caminosMinimales 17
     [[17,16,4,2,1]]
     λ> caminosMinimales 50
     [[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Soluciones

import Data.Tree
import Test.QuickCheck
 
mayoresDivisores :: Int -> [Int]
mayoresDivisores x =
  [max u v | u <- [2..floor (sqrt (fromIntegral x))]
           , x `mod` u == 0
           , let v = x `div` u]  
 
arbol :: Int -> Tree Int
arbol 1 = Node 1 []
arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])
 
caminos :: Int -> [[Int]]
caminos = caminosArbol . arbol
 
--    λ> caminosArbol (arbol 6)
--    [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
caminosArbol :: Tree a -> [[a]]
caminosArbol (Node x []) = [[x]]
caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]
 
caminosBosque :: Forest a -> [[a]]
caminosBosque = concatMap caminosArbol
 
caminosMinimales :: Int -> [[Int]]
caminosMinimales x = [ys | ys <- yss, length ys == m]
  where yss = caminos x
        m   = minimum (map length yss)

Pensamiento

Tras el vivir y el soñar,
está lo que más importa:
despertar.

Antonio Machado

6 soluciones de “Caminos minimales en un árbol numérico

  1. frahidzam
    import Data.Tree
    import Data.Numbers.Primes (isPrime)
     
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores n | isPrime n = []
                       | otherwise = [div n u| u <- [2..raizEntera n], mod n u == 0]
     
    raizEntera = floor . sqrt. fromIntegral
     
    arbol :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol n = Node n (concat [[arbol (n-1)], map arbol (mayoresDivisores n)])
     
    caminos :: Int -> [[Int]]
    caminos n = caminosAux (arbol n)
     
    caminosAux :: Tree Int -> [[Int]]
    caminosAux (Node n []) = [[n]]
    caminosAux (Node x as) = map (x:) (concatMap caminosAux as)
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales n = filter (xs -> length xs == m) xs
      where xs = caminos n
            m = minimum $ map length $ caminos n
  2. adogargon
    import Data.Tree
     
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores x = [ n | n <- [1..x-1] , or [ n * k == x | k <- [1..n]]]
     
    arbol :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol x = Node x [ arbol k | k <- ((x-1):mayoresDivisores x)]
     
    caminos :: Int -> [[Int]]
    caminos x = ramas ( arbol x)
      where ramas (Node x []) = [[x]]
            ramas (Node x xs) = map (x:) (concatMap ramas xs)
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales x = [ xs | xs <- yss , length xs == n ]
      where yss = caminos x
            n = minimum (map length yss)
  3. luipromor
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores x  =  [ y  | y <- factores  , elem (div x y) (takeWhile (<=y) factores) ]
      where factores  = [ y | y <- [2..div x 2] , mod x y == 0]
     
    arbol            :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol x = Node x (arbol (x-1):[ arbol y | y <- mayoresDivisores x])
     
    caminos          :: Int -> [[Int]]
    caminos x = aux (arbol x)
      where aux (Node x []) = [[x]]
            aux (Node x xs ) = concat  [ map (x:) (aux y) | y <- xs]
     
    caminosMinimales  :: Int -> [[Int]]
    caminosMinimales  = aux.caminos
      where aux (xs:xss) = aux1 xss [(xs,length xs)]
              where aux1 [] ys = map fst ys
                    aux1 (xs:xss) ys | x < y  = aux1 xss [(xs,x)]
                                     | x == y =  aux1 xss ((xs,x):ys)
                                     | otherwise = aux1 xss ys
                      where x = length xs
                            y = snd (head ys)
  4. ireprirod
    import Data.Tree
     
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores x = map f (menoresDivisores x)
      where f a = div x a
     
    menoresDivisores x = [ n | n<-[2..raizEntera x], mod x n == 0]
      where raizEntera = floor . sqrt . fromIntegral
     
    arbol :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol x = Node x (arbol (x-1):( map arbol (mayoresDivisores x)))
     
    caminos :: Int -> [[Int]]
    caminos n = aux (arbol n)
      where aux (Node x []) = [[x]]
            aux (Node x as) = map (x:) (concatMap aux as)
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales x = [ xs | xs<-caminos x, length xs == min]
      where min = minimum (map length (caminos x))
  5. javmarcha1
    import Data.Tree
     
    mayoresdivisores :: Int -> [Int]
    mayoresdivisores x = [ y | y <- [1..(x-1)], rem x y == 0 , (div x y)<y]
     
    mayoresdivisoresextra x = [x-1] ++  mayoresdivisores x 
     
    arbol :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol x = Node x [arbol y | y <- (mayoresdivisoresextra x)]
     
    caminosextra :: Tree Int -> [[Int]]
    caminosextra (Node n []) = [[n]]
    caminosextra (Node x xs) = map (x:) (concat(map caminosextra xs))
     
    caminos :: Int -> [[Int]]
    caminos x = caminosextra (arbol x)
     
    caminosminimalesextra :: Int -> [(Int,Int,[Int])]
    caminosminimalesextra x =[(length xs,(length [y| y <- xs,elem y (mayoresdivisores x)]),xs) | xs <- (caminos x)]
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales x = [xs | (a,b,xs) <- z, b == (minimum[h | (g,h,ns) <- z])]
       where z = [(c,d,ys) | (c,d,ys) <- (caminosminimalesextra x),
                c == (minimum[e | (e,f,ms) <- caminosminimalesextra x])]
  6. marlimand
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores n = [snd (x,y) | x<- divisores n, y<-divisores n , x>1,y>x, x*y==n]
     
    divisores :: Int -> [Int]
    divisores n = [ x | x<-[1..n], mod n x ==0]

Leave a Reply

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