Caminos minimales en un arbol numérico

PorJosé A. Alonso 10-marzo-201725-abril-2021

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]

1 2	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 []]

1	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

λ> putStrLn (drawTree (fmap show ej))

+- 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

/ \

5 3

| |

4 2

/ \ |

3 2 1

| |

2 1

Definir las siguientes funciones

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

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  ==  []

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

λ> putStrLn (drawTree (fmap show (arbol 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]]

1 2	λ> 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]]

λ> 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)

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)

8 Comentarios

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

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

Responder

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

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

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

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

Responder

                                                                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)

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)

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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))

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))

Responder

Caminos minimales en un arbol numérico

Soluciones

8 Comentarios

Leave a Reply to albcercidCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

8 Comentarios

Leave a Reply to albcercidCancel reply

Entradas recientes

Buscar

Correo electrónico