Menu Close

Caminos minimales en un arbol numérico

José A. Alonso,

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. Responder
    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. Responder
    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
    • Responder
      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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    Á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.