Menu Close

Caminos minimales en un arbol numérico

En la librería Data.Tree se definen los árboles y los 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
 
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)
Avanzado

8 soluciones de “Caminos minimales en un arbol numérico

  1. albcercid
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores x = [ div x n | n <- [2..div x 2], div x n >= n, mod x n == 0]
     
     
    arbol :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol x = Node x (map arbol ((x-1):mayoresDivisores x))
     
    caminos :: Int -> [[Int]]
    caminos 1 = [[1]]
    caminos x = map (x:) (concatMap caminos ((x-1):mayoresDivisores x))
     
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales x = aux (length n) xs [n]
       where (n:xs) = caminos x
             aux _ [] ys = reverse ys
             aux a (b:zs) ys | p == a = aux a zs (b:ys)
                             | p < a = aux p zs [b]
                             | otherwise = aux a zs ys
                        where p = length b
  2. enrnarbej
    divI :: Int -> [Int]
    divI = tail . reverse . sort . map product . nub . subsequences . primeFactors
     
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores n = take (length d `div` 2) d
                       where d = divI n
     
    ramas 1 = []
    ramas x | null d    =  [x - 1]
            | otherwise =  [x-1, head d] 
             where d = mayoresDivisores x
     
    arbol :: Int -> Tree Int
    arbol n = unfoldTree (a -> (a, ramas a)) n
     
    caminos2 :: Int -> [[Int]]
    caminos2 1 = [[1]]
    caminos2 n = (map (n:) . concatMap (caminos2) . ramas) n
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales n = [xs | xs <- c, length xs == ml]
                       where
                        c = caminos2 n
                        ml = maximum $ map length c
    • enrnarbej
      divI :: Int -> [Int]
      divI = tail . reverse . sort . map product . nub . subsequences . primeFactors
       
      mayoresDivisores :: Int -> [Int]
      mayoresDivisores n = take (length d `div` 2) d
                         where d = divI n
       
      arbol :: Int -> Tree Int
      arbol n = unfoldTree (a -> if a == 1 then (1, []) else (a , a-1 : mayoresDivisores a)) n
       
      caminos2 :: Int -> [[Int]]
      caminos2 1 = [[1]]
      caminos2 x = (map (x:) . concatMap (caminos2) . (x-1 :) . mayoresDivisores) x
       
      caminosMinimales :: Int -> [[Int]]
      caminosMinimales n = [xs | xs <- c, length xs == ml]
                         where
                          c = caminos2 n
                          ml = minimum $ map length c
  3. paumacpar
                                                                    mayoresDivisores :: Int -> [Int]
    mayoresDivisores x = nub (map ((a,b)-> max a b) ((filter ((a,b) -> a*b == x))((,) <$> divisores x <*> divisores x)))
     
    divisores :: Int -> [Int]
    divisores x = [y | y <- [2..(x-1)], mod x y == 0]
     
    arbol :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol x = Node x (map arbol ((x-1):mayoresDivisores x))
     
     
    caminos :: Int -> [[Int]]
    caminos 1 = [[1]]
    caminos x = map (x:) (concatMap caminos ((x-1):mayoresDivisores x))
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales x = [a | (a,b) <- zip (caminos x) ys, b == minimum ys]
      where ys = map length (caminos x)
  4. Juanjo Ortega (juaorture)
    import Data.Tree
    import Data.List
     
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores x | l `mod` 2 == 0 = take l' xs
                       | otherwise      = take (l' + 1) xs
                     where xs = [ a | a <- [x-1,x-2..2], x `mod` a == 0]
                           l  = length xs
                           l' = l `div` 2
     
    arbol :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol x = Node x (map arbol ((x-1):mayoresDivisores x)) 
     
    caminos :: Int -> [[Int]]
    caminos = aux . arbol
            where aux (Node a []) = [[a]]
                  aux (Node a xs) = map (a:) (concatMap aux xs)
     
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales x = [ xs | xs <- xss
                              , and (map (>= length xs) (map length (xss\[xs])))]
                     where xss = caminos x
  5. eliguivil
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores x = [n | n <- [1..div x 2]
                            , x `mod` n == 0
                            , x `div` n <=  n]
     
    arbol :: Int -> T.Tree Int
    arbol 1 = T.Node 1 []
    arbol n | null $ mayoresDivisores n = T.Node n [arbol (n-1)]
            | otherwise = T.Node n [arbol (n-1), aux (mayoresDivisores n)]
      where
        aux (u:[]) = T.Node u [arbol (u-1)]
        aux (u:us) = T.Node u [arbol (u-1), aux us]
     
    caminos :: Int -> [[Int]]
    caminos 1 = [[1]]
    caminos x = map (x:) (concatMap caminos ((x-1):mayoresDivisores x))
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales n = (filter ((==m).length) . caminos) n
      where
        m = minimum $ map length $ caminos n

    Nota: la definición de caminos es la de albcerdcid, puesto que no he conseguido averiguar por qué la mía no funcionaba

  6. cescarde
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores x | isPrime x = []
                       | otherwise = [n | n <- [1..b 2], a n == 0, b n <= n]
                       where a = rem x
                             b = div x
     
    arbol :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol n = Node n (map arbol ((n-1):mayoresDivisores n))
     
    caminos :: Int -> [[Int]]
    caminos 1 = [[1]]
    caminos n = map (n:) (concatMap caminos ((n-1):mayoresDivisores n))
     
    caminosMinimales :: Int -> [[Int]]
    caminosMinimales n = [xs | xs <- c, length xs == x]
                     where c = caminos n
                           x = minimum $ map length c
  7. Álvaro Fernández
    import Data.Tree
     
    mayoresDivisores :: Int -> [Int]
    mayoresDivisores x | l `rem` 2 == 0 = take l1 xs
                       | otherwise      = take (l1+1) xs
      where xs = reverse [n | n <- [2..x-1] , x `rem` n == 0]
            l  = length xs
            l1 = l `div` 2
     
    arbol :: Int -> Tree Int
    arbol 1 = Node 1 []
    arbol x = Node x (map arbol ((x-1) : mayoresDivisores x))

Escribe tu solución

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