Menu Close

Caminos minimales en un árbol numérico

José A. Alonso,

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

Posted in Medio
Tagged , , , , , , , , , , , , ,

6 Comments

  1. frahidzam
    Responder 
    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
    Responder 
    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
    Responder 
    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
    Responder 
    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
    Responder 
    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
    Responder 
    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]

Escribe tu solución

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