El mes de octubre en Exercitium (Ejercicios con Haskell y Python)
Durante el mes de octubre he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. La distancia Levenshtein (con programación dinámica)
- 2. Caminos en una retícula (con programación dinámica)
- 3. Caminos en una matriz (con programación dinámica)
- 4. Máxima suma de los caminos en una matriz
- 5. Camino de máxima suma en una matriz
- 6. Método de Herón para calcular la raíz cuadrada
A continuación se muestran las soluciones.
1. La distancia Levenshtein (con programación dinámica)
La distancia de Levenshtein (o distancia de edición) es el mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edición que se pueden hacer son:
- insertar un carácter (por ejemplo, de “abc” a “abca”)
- eliminar un carácter (por ejemplo, de “abc” a “ac”)
- sustituir un carácter (por ejemplo, de “abc” a “adc”)
Por ejemplo, la distancia de Levenshtein entre “casa” y “calle” es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro:
1 2 3 |
"casa" --> "cala" (sustitución de 's' por 'l') "cala" --> "calla" (inserción de 'l' entre 'l' y 'a') "calla" --> "calle" (sustitución de 'a' por 'e') |
Definir la función
1 |
levenshtein :: String -> String -> Int |
tal que levenshtein xs ys
es la distancia de Levenshtein entre xs
e ys
. Por ejemplo,
1 2 3 4 5 |
levenshtein "casa" "calle" == 3 levenshtein "calle" "casa" == 3 levenshtein "casa" "casa" == 0 levenshtein "ana" "maria" == 3 levenshtein "agua" "manantial" == 7 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 |
module Levenshtein where import Data.Array(Array, (!), array) import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª definición (por recursión) -- ============================= levenshtein1 :: String -> String -> Int levenshtein1 "" ys = length ys levenshtein1 xs "" = length xs levenshtein1 c1@(x:xs) c2@(y:ys) | x == y = levenshtein1 xs ys | otherwise = 1 + minimum [ levenshtein1 xs c2 , levenshtein1 c1 ys , levenshtein1 xs ys] -- 2ª definición (con programación dinámica) -- ========================================= levenshtein2 :: String -> String -> Int levenshtein2 xs ys = matrizLevenshtein xs ys ! (m,n) where m = length xs n = length ys -- (matrizLevenshtein xs ys) es la matriz cuyo número de filas es la -- longitud de xs, cuyo número de columnas es la longitud de ys y en -- valor en la posición (i,j) es la distancia de Levenshtein entre los -- primeros i caracteres de xs y los j primeros caracteres de ys. Por -- ejemplo, -- λ> elems (matrizLevenshtein "casa" "calle") -- [0,1,2,3,4,5,1,0,1,2,3,4,2,1,0,1,2,3,3,2,1,1,2,3,4,3,2,2,2,3] -- Gráficamente, -- c a l l e -- 0,1,2,3,4,5, -- c 1,0,1,2,3,4, -- a 2,1,0,1,2,3, -- s 3,2,1,1,2,3, -- a 4,3,2,2,2,3 matrizLevenshtein :: String -> String -> Array (Int,Int) Int matrizLevenshtein xs ys = q where q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m], j <- [0..n]] m = length xs n = length ys f 0 j = j f i 0 = i f i j | xs !! (i-1) == ys !! (j-1) = q ! (i-1,j-1) | otherwise = 1 + minimum [ q ! (i-1,j) , q ! (i,j-1) , q ! (i-1,j-1)] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> levenshtein1 (show (2^33)) (show (3^33)) -- 12 -- (16.19 secs, 11,766,254,536 bytes) -- λ> levenshtein2 (show (2^33)) (show (3^33)) -- 12 -- (0.02 secs, 0 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "ej1" $ levenshtein1 "casa" "calle" `shouldBe` 3 it "ej2" $ levenshtein1 "calle" "casa" `shouldBe` 3 it "ej3" $ levenshtein1 "casa" "casa" `shouldBe` 0 it "ej4" $ levenshtein1 "ana" "maria" `shouldBe` 3 it "ej5" $ levenshtein1 "agua" "manantial" `shouldBe` 7 it "ej6" $ levenshtein2 "casa" "calle" `shouldBe` 3 it "ej7" $ levenshtein2 "calle" "casa" `shouldBe` 3 it "ej8" $ levenshtein2 "casa" "casa" `shouldBe` 0 it "ej9" $ levenshtein2 "ana" "maria" `shouldBe` 3 it "ej10" $ levenshtein2 "agua" "manantial" `shouldBe` 7 -- La verificación es -- λ> verifica -- -- ej1 -- ej2 -- ej3 -- ej4 -- ej5 -- ej6 -- ej7 -- ej8 -- ej9 -- ej10 -- -- Finished in 0.0024 seconds -- 10 examples, 0 failures |
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 |
from sys import setrecursionlimit from timeit import Timer, default_timer setrecursionlimit(10**6) # 1ª definición (por recursión) # ============================= def levenshtein1(xs: str, ys: str) -> int: if not xs: return len(ys) if not ys: return len(xs) if xs[0] == ys[0]: return levenshtein1(xs[1:], ys[1:]) return 1 + min([levenshtein1(xs[1:], ys), levenshtein1(xs, ys[1:]), levenshtein1(xs[1:], ys[1:])]) # 2ª definición (con programación dinámica) # ========================================= # matrizLevenshtein(xs, ys) es la matriz cuyo número de filas es la # longitud de xs, cuyo número de columnas es la longitud de ys y en # valor en la posición (i,j) es la distancia de Levenshtein entre los # primeros i caracteres de xs y los j primeros caracteres de ys. Por # ejemplo, # >>> matrizLevenshtein("casa", "calle") # [[0, 1, 2, 3, 4, 5], # [1, 0, 1, 2, 3, 4], # [2, 1, 0, 1, 2, 3], # [3, 2, 1, 1, 2, 3], # [4, 3, 2, 2, 2, 3]] # Gráficamente, # c a l l e # 0,1,2,3,4,5, # c 1,0,1,2,3,4, # a 2,1,0,1,2,3, # s 3,2,1,1,2,3, # a 4,3,2,2,2,3 def matrizLevenshtein(xs: str, ys: str) -> list[list[int]]: n = len(xs) m = len(ys) q = [[0 for _ in range(m + 1)] for _ in range(n + 1)] for i in range(n + 1): q[i][0] = i for j in range(m + 1): q[0][j] = j for i in range(1,n + 1): for j in range(1, m + 1): if xs[i - 1] == ys[j - 1]: q[i][j] = q[i - 1][j - 1] else: q[i][j] = 1 + min([q[i-1][j], q[i][j-1], q[i-1][j-1]]) return q def levenshtein2(xs: str, ys: str) -> int: m = len(xs) n = len(ys) return matrizLevenshtein(xs, ys)[m][n] # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('levenshtein1(str(2**33), str(3**33))') # 13.78 segundos # >>> tiempo('levenshtein2(str(2**33), str(3**33))') # 0.00 segundos # Verificación # ============ def test_levenshtein() -> None: assert levenshtein1("casa", "calle") == 3 assert levenshtein1("calle", "casa") == 3 assert levenshtein1("casa", "casa") == 0 assert levenshtein1("ana", "maria") == 3 assert levenshtein1("agua", "manantial") == 7 assert levenshtein2("casa", "calle") == 3 assert levenshtein2("calle", "casa") == 3 assert levenshtein2("casa", "casa") == 0 assert levenshtein2("ana", "maria") == 3 assert levenshtein2("agua", "manantial") == 7 print("Verificado") |
2. Caminos en una retícula (con programación dinámica)
Se considera una retícula con sus posiciones numeradas, desde el vértice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la retícula de dimensión 3×4 se numera como sigue:
1 2 3 4 5 |
|-------+-------+-------+-------| | (1,1) | (1,2) | (1,3) | (1,4) | | (2,1) | (2,2) | (2,3) | (2,4) | | (3,1) | (3,2) | (3,3) | (3,4) | |-------+-------+-------+-------| |
Definir la función
1 |
caminos :: (Int,Int) -> [[(Int,Int)]] |
tal que caminos (m,n)
es la lista de los caminos en la retícula de dimensión mxn desde (1,1) hasta (m,n). Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
λ> caminos (2,3) [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] λ> mapM_ print (caminos (3,4)) [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)] [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)] [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)] [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)] [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)] [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)] [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)] [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)] [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)] [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 |
module Programacion_dinamica_Caminos_en_una_reticula where import Data.Array (Array, (!), array) import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª solución (por recursión) -- =========================== caminos1 :: (Int,Int) -> [[(Int,Int)]] caminos1 p = map reverse (caminos1Aux p) where caminos1Aux (1,y) = [[(1,z) | z <- [y,y-1..1]]] caminos1Aux (x,1) = [[(z,1) | z <- [x,x-1..1]]] caminos1Aux (x,y) = [(x,y) : cs | cs <- caminos1Aux (x-1,y) ++ caminos1Aux (x,y-1)] -- 2ª solución (con programación dinámica) -- ======================================= caminos2 :: (Int,Int) -> [[(Int,Int)]] caminos2 p = map reverse (matrizCaminos p ! p) matrizCaminos :: (Int,Int) -> Array (Int,Int) [[(Int,Int)]] matrizCaminos (m,n) = q where q = array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]] f 1 y = [[(1,z) | z <- [y,y-1..1]]] f x 1 = [[(z,1) | z <- [x,x-1..1]]] f x y = [(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> maximum (head (caminos1 (2000,2000))) -- (2000,2000) -- (0.01 secs, 3,459,576 bytes) -- λ> maximum (head (caminos2 (2000,2000))) -- (2000,2000) -- (2.79 secs, 1,507,636,688 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ caminos1 (2,3) `shouldBe` [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] it "e2" $ caminos2 (2,3) `shouldBe` [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0010 seconds -- 2 examples, 0 failures |
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 |
from collections import defaultdict from sys import setrecursionlimit from timeit import Timer, default_timer setrecursionlimit(10**6) # 1ª solución (por recursión) # =========================== def caminos1(p: tuple[int, int]) -> list[list[tuple[int, int]]]: def aux(p: tuple[int, int]) -> list[list[tuple[int, int]]]: (x, y) = p if x == 1: return [[(1,z) for z in range(y, 0, -1)]] if y == 1: return [[(z,1) for z in range(x, 0, -1)]] return [[(x,y)] + cs for cs in aux((x-1,y)) + aux((x,y-1))] return [list(reversed(ps)) for ps in aux(p)] # 2ª solución (con programación dinámica) # ======================================= def caminos2(p: tuple[int, int]) -> list[list[tuple[int, int]]]: return [list(reversed(ps)) for ps in diccionarioCaminos(p)[p]] # diccionarioCaminos((m,n)) es el diccionario cuyas claves son los # puntos de la retícula mxn y sus valores son los caminos a dichos # puntos. Por ejemplo, # >>> diccionarioCaminos((2,3)) # defaultdict(<class 'list'>, # {(1,1): [[(1,1)]], # (1,2): [[(1,2),(1,1)]], # (1,3): [[(1,3),(1,2),(1,1)]], # (2,1): [[(2,1),(1,1)]], # (2,2): [[(2,2),(1,2),(1,1)], # [(2,2),(2,1),(1,1)]], # (2,3): [[(2,3),(1,3),(1,2),(1,1)], # [(2,3),(2,2),(1,2),(1,1)], # [(2,3),(2,2),(2,1),(1,1)]]}) def diccionarioCaminos(p: tuple[int, int]) -> dict[tuple[int, int], list[list[tuple[int, int]]]]: m, n = p q = defaultdict(list) for i in range(1, m + 1): for j in range(1, n + 1): if i == 1: q[(i, j)] = [[(1, z) for z in range(j, 0, -1)]] elif j == 1: q[(i, j)] = [[(z, 1) for z in range(i, 0, -1)]] else: q[(i, j)] = [[(i, j)] + cs for cs in q[(i-1, j)] + q[(i, j-1)]] return q # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('max(caminos1((13,13))[0])') # 26.75 segundos # >>> tiempo('max(caminos2((13,13))[0])') # 7.40 segundos # Verificación # ============ def test_caminos() -> None: assert caminos1((2,3)) == \ [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] assert caminos2((2,3)) == \ [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] print("Verificado") # La verificación es # >>> test_caminos() # Verificado |
3. Caminos en una matriz (con programación dinámica)
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia la derecha o abajo, son los siguientes:
1 2 3 4 5 6 7 8 9 10 |
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9] |
Definir la función
1 |
caminos :: Matrix Int -> [[Int]] |
tal que caminos m
es la lista de los caminos en la matriz m
desde extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia la derecha o abajo. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) [[1,6,11,2,8,9], [1,6,11,3,8,9], [1,6,12,3,8,9], [1,7,12,3,8,9], [1,6,11,3,4,9], [1,6,12,3,4,9], [1,7,12,3,4,9], [1,6,12,8,4,9], [1,7,12,8,4,9], [1,7, 3,8,4,9]] λ> length (caminos (fromList 12 12 [1..])) 705432 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 |
module Caminos_en_una_matriz where import Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols) import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª definición (por recursión) -- ============================= caminos1 :: Matrix Int -> [[Int]] caminos1 m = reverse (map reverse (caminos1Aux m (nf,nc))) where nf = nrows m nc = ncols m -- (caminos1Aux m p) es la lista de los caminos invertidos en la matriz m -- desde la posición (1,1) hasta la posición p. Por ejemplo, caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]] caminos1Aux m (1,1) = [[m!(1,1)]] caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]] caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]] caminos1Aux m (i,j) = [m!(i,j) : xs | xs <- caminos1Aux m (i,j-1) ++ caminos1Aux m (i-1,j)] -- 2ª solución (mediante programación dinámica) -- ============================================ caminos2 :: Matrix Int -> [[Int]] caminos2 m = map reverse (matrizCaminos m ! (nrows m, ncols m)) matrizCaminos :: Matrix Int -> Matrix [[Int]] matrizCaminos m = q where q = matrix (nrows m) (ncols m) f f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]] f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]] f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (caminos1 (fromList 11 11 [1..])) -- 184756 -- (3.64 secs, 667,727,568 bytes) -- λ> length (caminos2 (fromList 11 11 [1..])) -- 184756 -- (0.82 secs, 129,181,072 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ caminos1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` r it "e2" $ caminos2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` r where r = [[1,6,11,2,8,9], [1,6,11,3,8,9], [1,6,12,3,8,9], [1,7,12,3,8,9], [1,6,11,3,4,9], [1,6,12,3,4,9], [1,7,12,3,4,9], [1,6,12,8,4,9], [1,7,12,8,4,9], [1,7, 3,8,4,9]] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0010 seconds -- 2 examples, 0 failures |
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 |
from collections import defaultdict from sys import setrecursionlimit from timeit import Timer, default_timer setrecursionlimit(10**6) # 1ª definición (por recursión) # ============================= def caminos1(m: list[list[int]]) -> list[list[int]]: nf = len(m) nc = len(m[0]) return list(reversed([list(reversed(xs)) for xs in caminos1Aux(m, (nf,nc))])) # caminos1Aux(m, p) es la lista de los caminos invertidos en la matriz m # desde la posición (1,1) hasta la posición p. Por ejemplo, def caminos1Aux(m: list[list[int]], p: tuple[int, int]) -> list[list[int]]: (i, j) = p if p == (1,1): return [[m[0][0]]] if i == 1: return [[m[0][k-1] for k in range(j, 0, -1)]] if j == 1: return [[m[k-1][0] for k in range(i, 0, -1)]] return [[m[i-1][j-1]] + xs for xs in caminos1Aux(m, (i,j-1)) + caminos1Aux(m, (i-1,j))] # 2ª solución (mediante programación dinámica) # ============================================ def caminos2(p: list[list[int]]) -> list[list[int]]: m = len(p) n = len(p[0]) return [list(reversed(xs)) for xs in diccionarioCaminos(p)[(m, n)]] # diccionarioCaminos(p) es el diccionario cuyas claves son los # puntos de la matriz p y sus valores son los caminos a dichos # puntos. Por ejemplo, # >>> diccionarioCaminos([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) # defaultdict(<class 'list'>, # {(1, 1): [[1]], # (1, 2): [[6, 1]], # (1, 3): [[11, 6, 1]], # (1, 4): [[2, 11, 6, 1]], # (2, 1): [[7, 1]], # (2, 2): [[12, 6, 1], [12, 7, 1]], # (2, 3): [[3, 11, 6, 1], [3, 12, 6, 1], [3, 12, 7, 1]], # (2, 4): [[8, 2, 11, 6, 1], [8, 3, 11, 6, 1], # [8, 3, 12, 6, 1], [8, 3, 12, 7, 1]], # (3, 1): [[3, 7, 1]], # (3, 2): [[8, 12, 6, 1], [8, 12, 7, 1], [8, 3, 7, 1]], # (3, 3): [[4, 3, 11, 6, 1], [4, 3, 12, 6, 1], # [4, 3, 12, 7, 1], [4, 8, 12, 6, 1], # [4, 8, 12, 7, 1], [4, 8, 3, 7, 1]], # (3, 4): [[9, 8, 2, 11, 6, 1], [9, 8, 3, 11, 6, 1], # [9, 8, 3, 12, 6, 1], [9, 8, 3, 12, 7, 1], # [9, 4, 3, 11, 6, 1], [9, 4, 3, 12, 6, 1], # [9, 4, 3, 12, 7, 1], [9, 4, 8, 12, 6, 1], # [9, 4, 8, 12, 7, 1], [9, 4, 8, 3, 7, 1]]}) def diccionarioCaminos(p: list[list[int]]) -> dict[tuple[int, int], list[list[int]]]: m = len(p) n = len(p[0]) q = defaultdict(list) for i in range(1, m + 1): for j in range(1, n + 1): if i == 1: q[(i, j)] = [[p[0][z-1] for z in range(j, 0, -1)]] elif j == 1: q[(i, j)] = [[p[z-1][0] for z in range(i, 0, -1)]] else: q[(i, j)] = [[p[i-1][j-1]] + cs for cs in q[(i-1, j)] + q[(i, j-1)]] return q # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('caminos1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])') # 2.20 segundos # >>> tiempo('caminos2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])') # 0.64 segundos # Verificación # ============ def test_caminos() -> None: r = [[1, 6, 11, 2, 8, 9], [1, 6, 11, 3, 8, 9], [1, 6, 12, 3, 8, 9], [1, 7, 12, 3, 8, 9], [1, 6, 11, 3, 4, 9], [1, 6, 12, 3, 4, 9], [1, 7, 12, 3, 4, 9], [1, 6, 12, 8, 4, 9], [1, 7, 12, 8, 4, 9], [1, 7, 3, 8, 4, 9]] assert caminos1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == r assert caminos2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == r print("Verificado") # La verificación es # >>> test_caminos() # Verificado |
4. Máxima suma de los caminos en una matriz
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:
1 2 3 4 5 6 7 8 9 10 |
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9] |
La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.
Definir la función
1 |
maximaSuma :: Matrix Int -> Int |
tal que maximaSuma m
es el máximo de las sumas de los caminos en la matriz m
desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia a derecha. Por ejemplo,
1 2 3 4 |
λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) 41 λ> maximaSuma (fromList 800 800 [1..]) 766721999 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 |
module Maxima_suma_de_los_caminos_en_una_matriz where import Data.Matrix (Matrix, (!), fromList, fromLists, matrix, nrows, ncols) import Test.Hspec (Spec, hspec, it, shouldBe) import Caminos_en_una_matriz (caminos1, caminos2) -- 1ª definicion de maximaSuma (con caminos1) -- ========================================== maximaSuma1 :: Matrix Int -> Int maximaSuma1 = maximum . map sum . caminos1 -- Se usa la función caminos1 del ejercicio -- "Caminos en una matriz" que se encuentra en -- https://bit.ly/45bYoYE -- 2ª definición de maximaSuma (con caminos2) -- ========================================== maximaSuma2 :: Matrix Int -> Int maximaSuma2 = maximum . map sum . caminos2 -- Se usa la función caminos2 del ejercicio -- "Caminos en una matriz" que se encuentra en -- https://bit.ly/45bYoYE -- 3ª definicion de maximaSuma (por recursión) -- =========================================== maximaSuma3 :: Matrix Int -> Int maximaSuma3 m = maximaSuma3Aux m (nf,nc) where nf = nrows m nc = ncols m -- (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la -- posición p. Por ejemplo, -- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4) -- 41 -- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3) -- 32 -- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4) -- 31 maximaSuma3Aux :: Matrix Int -> (Int,Int) -> Int maximaSuma3Aux m (1,1) = m ! (1,1) maximaSuma3Aux m (1,j) = maximaSuma3Aux m (1,j-1) + m ! (1,j) maximaSuma3Aux m (i,1) = maximaSuma3Aux m (i-1,1) + m ! (i,1) maximaSuma3Aux m (i,j) = max (maximaSuma3Aux m (i,j-1)) (maximaSuma3Aux m (i-1,j)) + m ! (i,j) -- 4ª solución (mediante programación dinámica) -- ============================================ maximaSuma4 :: Matrix Int -> Int maximaSuma4 m = q ! (nf,nc) where nf = nrows m nc = ncols m q = matrizMaximaSuma m -- (matrizMaximaSuma m) es la matriz donde en cada posición p se -- encuentra el máxima de las sumas de los caminos desde (1,1) a p en la -- matriz m. Por ejemplo, -- λ> matrizMaximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) -- ( 1 7 18 20 ) -- ( 8 20 23 31 ) -- ( 11 28 32 41 ) matrizMaximaSuma :: Matrix Int -> Matrix Int matrizMaximaSuma m = q where nf = nrows m nc = ncols m q = matrix nf nc f where f (1,1) = m ! (1,1) f (1,j) = q ! (1,j-1) + m ! (1,j) f (i,1) = q ! (i-1,1) + m ! (i,1) f (i,j) = max (q ! (i,j-1)) (q ! (i-1,j)) + m ! (i,j) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> maximaSuma1 (fromList 11 11 [1..]) -- 1781 -- (3.88 secs, 1,525,812,680 bytes) -- λ> maximaSuma2 (fromList 11 11 [1..]) -- 1781 -- (1.08 secs, 546,144,264 bytes) -- λ> maximaSuma3 (fromList 11 11 [1..]) -- 1781 -- (0.55 secs, 217,712,280 bytes) -- λ> maximaSuma4 (fromList 11 11 [1..]) -- 1781 -- (0.01 secs, 643,832 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ maximaSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41 it "e2" $ maximaSuma1 (fromList 4 4 [1..]) `shouldBe` 73 it "e3" $ maximaSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41 it "e4" $ maximaSuma2 (fromList 4 4 [1..]) `shouldBe` 73 it "e5" $ maximaSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41 it "e6" $ maximaSuma3 (fromList 4 4 [1..]) `shouldBe` 73 it "e7" $ maximaSuma4 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41 it "e8" $ maximaSuma4 (fromList 4 4 [1..]) `shouldBe` 73 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- e7 -- e8 -- -- Finished in 0.0034 seconds -- 8 examples, 0 failures |
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 |
from collections import defaultdict from sys import setrecursionlimit from timeit import Timer, default_timer from src.Caminos_en_una_matriz import caminos1, caminos2 setrecursionlimit(10**6) # 1ª definicion de maximaSuma (con caminos1) # ========================================== def maximaSuma1(m: list[list[int]]) -> int: return max((sum(xs) for xs in caminos1(m))) # Se usa la función caminos1 del ejercicio # "Caminos en una matriz" que se encuentra en # https://bit.ly/45bYoYE # 2ª definición de maximaSuma (con caminos2) # ========================================== def maximaSuma2(m: list[list[int]]) -> int: return max((sum(xs) for xs in caminos2(m))) # Se usa la función caminos2 del ejercicio # "Caminos en una matriz" que se encuentra en # https://bit.ly/45bYoYE # 3ª definicion de maximaSuma (por recursión) # =========================================== def maximaSuma3(m: list[list[int]]) -> int: nf = len(m) nc = len(m[0]) return maximaSuma3Aux(m, (nf,nc)) # (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la # posición p. Por ejemplo, # λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4) # 41 # λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3) # 32 # λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4) # 31 def maximaSuma3Aux(m: list[list[int]], p: tuple[int, int]) -> int: (i, j) = p if (i, j) == (1, 1): return m[0][0] if i == 1: return maximaSuma3Aux(m, (1,j-1)) + m[0][j-1] if j == 1: return maximaSuma3Aux(m, (i-1,1)) + m[i-1][0] return max(maximaSuma3Aux(m, (i,j-1)), maximaSuma3Aux(m, (i-1,j))) + m[i-1][j-1] # 4ª solución (mediante programación dinámica) # ============================================ def maximaSuma4(p: list[list[int]]) -> int: m = len(p) n = len(p[0]) return diccionarioMaxSuma(p)[(m,n)] # diccionarioMaxSuma(p) es el diccionario cuyas claves son los # puntos de la matriz p y sus valores son las máximas sumas de los # caminos a dichos puntos. Por ejemplo, # diccionarioMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) # defaultdict(<class 'int'>, # {(1, 0): 0, # (1, 1): 1, (1, 2): 7, (1, 3): 18, (1, 4): 20, # (2, 1): 8, (2, 2): 20, (2, 3): 23, (2, 4): 31, # (3, 1): 11, (3, 2): 28, (3, 3): 32, (3, 4): 41}) def diccionarioMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], int]: m = len(p) n = len(p[0]) q: dict[tuple[int, int], int] = defaultdict(int) for i in range(1, m + 1): for j in range(1, n + 1): if i == 1: q[(i, j)] = q[(1,j-1)] + p[0][j-1] elif j == 1: q[(i, j)] = q[(i-1,1)] + p[i-1][0] else: q[(i, j)] = max(q[(i,j-1)], q[(i-1,j)]) + p[i-1][j-1] return q # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('maximaSuma1([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])') # 4.95 segundos # >>> tiempo('maximaSuma2([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])') # 1.49 segundos # >>> tiempo('maximaSuma3([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])') # 0.85 segundos # >>> tiempo('maximaSuma4([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])') # 0.00 segundos # Verificación # ============ def test_maximaSuma() -> None: assert maximaSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41 assert maximaSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41 assert maximaSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41 assert maximaSuma4([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41 print("Verificado") # La verificación es # >>> test_maximaSuma() # Verificado |
5. Camino de máxima suma en una matriz
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:
1 2 3 4 5 6 7 8 9 10 |
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9] |
La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.
Definir la función
1 |
caminoMaxSuma :: Matrix Int -> [Int] |
tal que caminoMaxSuma m
es un camino de máxima suma en la matriz m
desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,
1 2 3 4 |
λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) [1,7,12,8,4,9] λ> sum (caminoMaxSuma (fromList 500 500 [1..])) 187001249 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 |
module Camino_de_maxima_suma_en_una_matriz where import Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols) import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª definición de caminoMaxSuma (con caminos1) -- ============================================= caminoMaxSuma1 :: Matrix Int -> [Int] caminoMaxSuma1 m = head [c | c <- cs, sum c == k] where cs = caminos1 m k = maximum (map sum cs) caminos1 :: Matrix Int -> [[Int]] caminos1 m = reverse (map reverse (caminos1Aux m (nf,nc))) where nf = nrows m nc = ncols m -- (caminos1Aux m p) es la lista de los caminos invertidos en la matriz m -- desde la posición (1,1) hasta la posición p. Por ejemplo, caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]] caminos1Aux m (1,1) = [[m!(1,1)]] caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]] caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]] caminos1Aux m (i,j) = [m!(i,j) : xs | xs <- caminos1Aux m (i,j-1) ++ caminos1Aux m (i-1,j)] -- 2ª definición de caminoMaxSuma (con caminos2) -- ============================================= caminoMaxSuma2 :: Matrix Int -> [Int] caminoMaxSuma2 m = head [c | c <- cs, sum c == k] where cs = caminos2 m k = maximum (map sum cs) caminos2 :: Matrix Int -> [[Int]] caminos2 m = map reverse (matrizCaminos m ! (nrows m, ncols m)) matrizCaminos :: Matrix Int -> Matrix [[Int]] matrizCaminos m = q where q = matrix (nrows m) (ncols m) f f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]] f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]] f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)] -- 3ª definición de caminoMaxSuma (con programación dinámica) -- ========================================================== caminoMaxSuma3 :: Matrix Int -> [Int] caminoMaxSuma3 m = reverse (snd (q ! (nf,nc))) where nf = nrows m nc = ncols m q = caminoMaxSumaAux m caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int]) caminoMaxSumaAux m = q where nf = nrows m nc = ncols m q = matrix nf nc f where f (1,1) = (m!(1,1),[m!(1,1)]) f (1,j) = (k + m!(1,j), m!(1,j):xs) where (k,xs) = q!(1,j-1) f (i,1) = (k + m!(i,1), m!(i,1):xs) where (k,xs) = q!(i-1,1) f (i,j) | k1 > k2 = (k1 + m!(i,j), m!(i,j):xs) | otherwise = (k2 + m!(i,j), m!(i,j):ys) where (k1,xs) = q!(i,j-1) (k2,ys) = q!(i-1,j) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (caminoMaxSuma1 (fromList 11 11 [1..])) -- 21 -- (3.92 secs, 1,778,557,904 bytes) -- λ> length (caminoMaxSuma2 (fromList 11 11 [1..])) -- 21 -- (1.16 secs, 798,889,488 bytes) -- λ> length (caminoMaxSuma3 (fromList 11 11 [1..])) -- 21 -- (0.00 secs, 680,256 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ caminoMaxSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` [1,7,12,8,4,9] it "e2" $ caminoMaxSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` [1,7,12,8,4,9] it "e3" $ caminoMaxSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` [1,7,12,8,4,9] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0007 seconds -- 3 examples, 0 failures |
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 |
from collections import defaultdict from sys import setrecursionlimit from timeit import Timer, default_timer from src.Caminos_en_una_matriz import caminos1, caminos2 setrecursionlimit(10**6) # 1ª definición de caminoMaxSuma (con caminos1) # ============================================= def caminoMaxSuma1(m: list[list[int]]) -> list[int]: cs = caminos1(m) k = max((sum(c) for c in cs)) return [c for c in cs if sum(c) == k][0] # Se usa la función caminos1 del ejercicio # "Caminos en una matriz" que se encuentra en # https://bit.ly/45bYoYE # 2ª definición de caminoMaxSuma (con caminos2) # ============================================= def caminoMaxSuma2(m: list[list[int]]) -> list[int]: cs = caminos2(m) k = max((sum(c) for c in cs)) return [c for c in cs if sum(c) == k][0] # Se usa la función caminos2 del ejercicio # "Caminos en una matriz" que se encuentra en # https://bit.ly/45bYoYE # 3ª definición de caminoMaxSuma (con programación dinámica) # ========================================================== def caminoMaxSuma3(m: list[list[int]]) -> list[int]: nf = len(m) nc = len(m[0]) return list(reversed(diccionarioCaminoMaxSuma(m)[(nf, nc)][1])) # diccionarioCaminoMaxSuma(p) es el diccionario cuyas claves son los # puntos de la matriz p y sus valores son los pares formados por la # máxima suma de los caminos hasta dicho punto y uno de los caminos con # esa suma. Por ejemplo, # >>> diccionarioCaminoMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) # {(1, 1): (1, [1]), # (1, 2): (7, [6, 1]), # (1, 3): (18, [11, 6, 1]), # (1, 4): (20, [2, 11, 6, 1]), # (2, 1): (8, [7, 1]), # (3, 1): (11, [3, 7, 1]), # (2, 2): (20, [12, 7, 1]), # (2, 3): (23, [3, 12, 7, 1]), # (2, 4): (31, [8, 3, 12, 7, 1]), # (3, 2): (28, [8, 12, 7, 1]), # (3, 3): (32, [4, 8, 12, 7, 1]), # (3, 4): (41, [9, 4, 8, 12, 7, 1])} def diccionarioCaminoMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], tuple[int, list[int]]]: m = len(p) n = len(p[0]) q: dict[tuple[int, int], tuple[int, list[int]]] = {} q[(1, 1)] = (p[0][0], [p[0][0]]) for j in range(2, n + 1): (k, xs) = q[(1, j-1)] q[(1, j)] = (k + p[0][j-1], [p[0][j-1]] + xs) for i in range(2, m + 1): (k,xs) = q[(i-1,1)] q[(i, 1)] = (k + p[i-1][0], [p[i-1][0]] + xs) for i in range(2, m + 1): for j in range(2, n + 1): (k1,xs) = q[(i,j-1)] (k2,ys) = q[(i-1,j)] if k1 > k2: q[(i,j)] = (k1 + p[i-1][j-1], [p[i-1][j-1]] + xs) else: q[(i,j)] = (k2 + p[i-1][j-1], [p[i-1][j-1]] + ys) return q # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('caminoMaxSuma1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])') # 1.92 segundos # >>> tiempo('caminoMaxSuma2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])') # 0.65 segundos # >>> tiempo('caminoMaxSuma3([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])') # 0.00 segundos # # Verificación # # ============ def test_caminoMaxSuma() -> None: assert caminoMaxSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \ [1, 7, 12, 8, 4, 9] assert caminoMaxSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \ [1, 7, 12, 8, 4, 9] assert caminoMaxSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \ [1, 7, 12, 8, 4, 9] print("Verificado") # La verificación es # >>> test_caminoMaxSuma() # Verificado |
6. Método de Herón para calcular la raíz cuadrada
El método de Herón para calcular la raíz cuadrada de un número se basa en las siguientes propiedades:
- Si \(y\) es una aproximación de la raíz cuadrada de \(x\), entonces
\[\frac{y+\frac{x}{y}}{2}\] es una aproximación mejor. - El límite de la sucesión definida por
\begin{align}
x_{0} &= 1 \\
x_{n+1} &= \frac{x_n+\frac{x}{x_n}}{2}
\end{align}
es la raíz cuadrada de x.
Definir la función
1 |
raiz :: Double -> Double |
tal que raiz x
es la raíz cuadrada de x
calculada usando la propiedad anterior con una aproximación de 0.00001 y tomando como valor inicial 1. Por ejemplo,
1 |
raiz 9 == 3.000000001396984 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 |
module Metodo_de_Heron_para_calcular_la_raiz_cuadrada where import Test.QuickCheck import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª solución -- =========== raiz :: Double -> Double raiz x = raizAux 1 where raizAux y | aceptable y = y | otherwise = raizAux (mejora y) aceptable y = abs(y*y-x) < 0.00001 mejora y = 0.5*(y+x/y) -- 2ª solución -- =========== raiz2 :: Double -> Double raiz2 x = until aceptable mejora 1 where aceptable y = abs(y*y-x) < 0.00001 mejora y = 0.5*(y+x/y) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_raiz :: Positive Double -> Bool prop_raiz (Positive x) = raiz x ~= sqrt x && raiz2 x ~= sqrt x where a ~= b = abs (a-b) < 0.001 -- La comprobación es -- λ> quickCheck prop_raiz -- +++ OK, passed 100 tests. -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ raiz 9 `shouldBe` 3.000000001396984 it "e2" $ raiz2 9 `shouldBe` 3.000000001396984 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0008 seconds -- 2 examples, 0 failures |
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 |
# 1ª solución # =========== def raiz(x : float) -> float: def aceptable(y: float) -> bool: return abs(y*y-x) < 0.00001 def mejora(y: float) -> float: return 0.5*(y+x/y) def raizAux(y: float) -> float: if aceptable(y): return y return raizAux(mejora(y)) return raizAux(1) # 2ª solución # =========== def raiz2(x: float) -> float: def aceptable(y: float) -> bool: return abs(y*y-x) < 0.00001 def mejora(y: float) -> float: return 0.5*(y+x/y) y = 1.0 while not aceptable(y): y = mejora(y) return y # Verificación # ============ def test_raiz() -> None: assert raiz(9) == 3.000000001396984 assert raiz2(9) == 3.000000001396984 print("Verificado") # La verificación es # >>> test_raiz() # Verificado |