Grafo de divisibilidad
El grafo de divisibilidad de orden n es el grafo cuyos nodos son los números naturales entre 1 y n, cuyas aristas son los pares (x,y) tales que x divide a y o y divide a x. El coste de cada arista es el cociente entre su mayor y menor elemento.
Definir las siguientes funciones:
1 2 |
grafoDivisibilidad :: Int -> Grafo Int Int coste :: Int -> Int |
tales que
- (grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
λ> grafoDivisibilidad 12 G ND (array (1,12) [(1,[(2,2),(3,3),(4,4),(5,5),(6,6),(7,7), (8,8),(9,9),(10,10),(11,11),(12,12)]), (2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]), (3,[(1,3),(6,2),(9,3),(12,4)]), (4,[(1,4),(2,2),(8,2),(12,3)]), (5,[(1,5),(10,2)]), (6,[(1,6),(2,3),(3,2),(12,2)]), (7,[(1,7)]), (8,[(1,8),(2,4),(4,2)]), (9,[(1,9),(3,3)]), (10,[(1,10),(2,5),(5,2)]), (11,[(1,11)]), (12,[(1,12),(2,6),(3,4),(4,3),(6,2)])]) |
- (coste n) es el coste del árbol de expansión mínimo del grafo de divisibilidad de orden n. Por ejemplo,
1 2 3 |
coste 12 == 41 coste 3000 == 605305 coste (2*10^5) == 1711798835 |
Soluciones
[schedule expon=’2019-06-10′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 10 de junio.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
Malos sueños he.
Me despertaré.Antonio Machado
[/schedule]
[schedule on=’2019-06-10′ at=»06:00″]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
import Data.Ix import Data.List (delete, sort) import qualified Data.Set as S import I1M.Grafo import I1M.Tabla import Data.Numbers.Primes (primeFactors) -- Definición de grafoDivisibilidad -- ================================ grafoDivisibilidad :: Int -> Grafo Int Int grafoDivisibilidad n = creaGrafo ND (1,n) [(x,y,y `div` x) | y <- [1..n] , x <- [1..y-1] , y `mod` x == 0] -- 1ª definición de coste (con el algoritmo de Kruskal) -- ==================================================== coste1 :: Int -> Int coste1 n = sum [p | (p,x,y) <- kruskal (grafoDivisibilidad n)] -- (kruskal g) es el árbol de expansión mínimo del grafo g calculado -- mediante el algoritmo de Kruskal. Por ejemplo, -- λ> kruskal (grafoDivisibilidad 12) -- [(11,1,11),(7,1,7),(5,1,5),(3,3,9),(3,1,3),(2,6,12),(2,5,10), -- (2,4,8),(2,3,6),(2,2,4),(2,1,2)] kruskal :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] kruskal g = kruskal' cola -- Cola ordenada (tabla [(x,x) | x <- nodos g]) -- Tabla de raices [] -- Árbol de expansión (length (nodos g) - 1) -- Aristas por -- colocar where cola = sort [(p,x,y) | (x,y,p) <- aristas g] kruskal' ((p,x,y):as) t ae n | n == 0 = ae | actualizado = kruskal' as t' ((p,x,y):ae) (n-1) | otherwise = kruskal' as t ae n where (actualizado,t') = buscaActualiza (x,y) t -- (raiz t n) es la raíz de n en la tabla t. Por ejemplo, -- raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 5 == 1 -- raiz (crea [(1,1),(3,1),(4,3),(5,4),(2,6),(6,6)]) 2 == 6 raiz:: Eq n => Tabla n n -> n -> n raiz t x | v == x = v | otherwise = raiz t v where v = valor t x -- (buscaActualiza a t) es el par formado por False y la tabla t, si los -- dos vértices de la arista a tienen la misma raíz en t y el par -- formado por True y la tabla obtenida añadiéndole a t la arista -- formada por el vértice de a de mayor raíz y la raíz del vértice de -- a de menor raíz. Por ejemplo, -- ghci> let t = crea [(1,1),(2,2),(3,1),(4,1)] -- ghci> buscaActualiza (2,3) t -- (True,Tbl [(1,1),(2,1),(3,1),(4,1)]) -- ghci> buscaActualiza (3,4) t -- (False,Tbl [(1,1),(2,2),(3,1),(4,1)]) buscaActualiza :: (Eq n, Ord n) => (n,n) -> Tabla n n -> (Bool,Tabla n n) buscaActualiza (x,y) t | x' == y' = (False, t) | y' < x' = (True, modifica (x,y') t) | otherwise = (True, modifica (y,x') t) where x' = raiz t x y' = raiz t y -- 2ª definición de coste (con el algoritmo de Prim) -- ================================================= coste2 :: Int -> Int coste2 n = sum [p | (p,x,y) <- prim (grafoDivisibilidad n)] -- (prim g) es el árbol de expansión mínimo del grafo g calculado -- mediante el algoritmo de Prim. Por ejemplo, -- λ> prim (grafoDivisibilidad 12) -- [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6), -- (3,1,3),(2,4,8),(2,2,4),(2,1,2)] prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] prim g = prim' [n] -- Nodos colocados ns -- Nodos por colocar [] -- Árbol de expansión (aristas g) -- Aristas del grafo where (n:ns) = nodos g prim' t [] ae as = ae prim' t r ae as = prim' (v':t) (delete v' r) (e:ae) as where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as, u `elem` t, v `elem` r] -- 3ª definición de coste (con el algoritmo de Prim con conjuntos) -- =============================================================== coste3 :: Int -> Int coste3 n = sum [p | (p,x,y) <- prim2 (grafoDivisibilidad n)] -- (prim2 g) es el árbol de expansión mínimo del grafo g calculado -- mediante el algoritmo de Prim. Por ejemplo, -- λ> prim2 (grafoDivisibilidad 12) -- [(11,1,11),(7,1,7),(2,5,10),(5,1,5),(3,3,9),(2,6,12),(2,3,6), -- (3,1,3),(2,4,8),(2,2,4),(2,1,2)] prim2 :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] prim2 g = prim2' (S.singleton n) -- Nodos colocados (S.fromList ns) -- Nodos por colocar [] -- Árbol de expansión (aristas g) -- Aristas del grafo where (n:ns) = nodos g prim2' t r ae as | S.null r = ae | otherwise = prim2' (S.insert v' t) (S.delete v' r) (e:ae) as where e@(c,u', v') = minimum [(c,u,v)| (u,v,c) <- as, S.member u t, S.member v r] -- 4ª definición de coste -- ====================== coste4 :: Int -> Int coste4 n = sum [head (primeFactors x) | x <- [2..n]] -- Comparación de eficiencia -- ========================= -- λ> coste1 400 -- 14923 -- (0.08 secs, 31,336,440 bytes) -- λ> coste2 400 -- 14923 -- (4.54 secs, 220,745,608 bytes) -- λ> coste3 400 -- 14923 -- (0.69 secs, 217,031,144 bytes) -- λ> coste4 400 -- 14923 -- (0.01 secs, 2,192,336 bytes) -- -- λ> coste1 2000 -- 284105 -- (2.09 secs, 842,601,904 bytes) -- λ> coste4 2000 -- 284105 -- (0.02 secs, 14,586,888 bytes) |
[/schedule]
3 Comentarios