Producto de los elementos de la diagonal principal
Las matrices se pueden representar como lista de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.
Definir la función
1 |
productoDiagonalPrincipal :: Num a => [[a]] -> a |
tal que (productoDiagonalPrincipal xss) es el producto de los elementos de la diagonal principal de la matriz cuadrada xss. Por ejemplo,
1 2 3 |
productoDiagonal [[3,5,2],[4,7,1],[6,9,8]] == 168 productoDiagonal (replicate 5 [1..5]) == 120 length (show (productoDiagonal (replicate 30000 [1..30000]))) == 121288 |
1. Soluciones en Haskell
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 Producto_de_los_elementos_de_la_diagonal_principal where import Data.List (genericReplicate) import Test.Hspec (Spec, describe, hspec, it, shouldBe) -- 1ª solución -- =========== productoDiagonal1 :: Num a => [[a]] -> a productoDiagonal1 xss = product (diagonal1 xss) -- (diagonal1 xss) es la diagonal de la matriz xss. Por ejemplo, -- diagonal1 [[3,5,2],[4,7,1],[6,9,0]] == [3,7,0] -- diagonal1 [[3,5],[4,7],[6,9]] == [3,7] -- diagonal1 [[3,5,2],[4,7,1]] == [3,7] diagonal1 :: [[a]] -> [a] diagonal1 ((x:_):xss) = x : diagonal1 (map tail xss) diagonal1 _ = [] -- 2ª solución -- =========== productoDiagonal2 :: Num a => [[a]] -> a productoDiagonal2 = product . diagonal1 -- 3ª solución -- =========== productoDiagonal3 :: Num a => [[a]] -> a productoDiagonal3 = product . diagonal3 diagonal3 :: [[a]] -> [a] diagonal3 xss = [xs !! k | (xs,k) <- zip xss [0..n]] where n = length (head xss) - 1 -- 4ª solución -- =========== productoDiagonal4 :: Num a => [[a]] -> a productoDiagonal4 [] = 1 productoDiagonal4 [[]] = 1 productoDiagonal4 ((x:_):xss) = x * productoDiagonal4 (map tail xss) -- 5ª solución -- =========== productoDiagonal5 :: Num a => [[a]] -> a productoDiagonal5 xss = product (zipWith (!!) xss [0..k]) where m = length xss n = length (head xss) k = min m n - 1 -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: ([[Integer]] -> Integer) -> Spec specG productoDiagonal = do it "e1" $ productoDiagonal [[3,5,2],[4,7,1],[6,9,8]] `shouldBe` 168 it "e2" $ productoDiagonal (replicate 5 [1..5]) `shouldBe` 120 spec :: Spec spec = do describe "def. 1" $ specG productoDiagonal1 describe "def. 2" $ specG productoDiagonal2 describe "def. 3" $ specG productoDiagonal3 describe "def. 4" $ specG productoDiagonal4 describe "def. 5" $ specG productoDiagonal5 -- La verificación es -- λ> verifica -- -- 10 examples, 0 failures -- Comparación de eficiencia -- ========================= ejemplo :: Integer -> [[Integer]] ejemplo n = genericReplicate n [1..n] -- La comparación es -- λ> length (show (productoDiagonal1 (ejemplo 7000))) -- 23878 -- (1.23 secs, 3,396,129,424 bytes) -- λ> length (show (productoDiagonal2 (ejemplo 7000))) -- 23878 -- (0.94 secs, 3,396,127,680 bytes) -- λ> length (show (productoDiagonal3 (ejemplo 7000))) -- 23878 -- (0.09 secs, 44,841,864 bytes) -- λ> length (show (productoDiagonal4 (ejemplo 7000))) -- 23878 -- (0.96 secs, 3,614,137,840 bytes) -- λ> length (show (productoDiagonal5 (ejemplo 7000))) -- 23878 -- (0.07 secs, 44,168,984 bytes) -- -- λ> length (show (productoDiagonal3 (ejemplo 70000))) -- 308760 -- (8.26 secs, 5,359,752,408 bytes) -- λ> length (show (productoDiagonal5 (ejemplo 70000))) -- 308760 -- (9.34 secs, 5,353,035,656 bytes) |
2. 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 |
from functools import reduce from operator import mul from sys import set_int_max_str_digits, setrecursionlimit from timeit import Timer, default_timer set_int_max_str_digits(10**6) setrecursionlimit(10**6) # 1ª solución # =========== # diagonal1(xss) es la diagonal de la matriz xss. Por ejemplo, # diagonal1([[3,5,2],[4,7,1],[6,9,0]]) == [3,7,0] # diagonal1([[3,5],[4,7],[6,9]]) == [3,7] # diagonal1([[3,5,2],[4,7,1]]) == [3,7] def diagonal1(xss: list[list[int]]) -> list[int]: if not xss: return [] if not xss[0]: return [] return [xss[0][0]] + diagonal1(list(map((lambda ys : ys[1:]), xss[1:]))) def producto(xs: list[int]) -> int: return reduce(mul, xs) def productoDiagonal1(xss: list[list[int]]) -> int: return producto(diagonal1(xss)) # 2ª solución # =========== def diagonal2(xss: list[list[int]]) -> list[int]: n = min(len(xss), len(xss[0])) return [xss[k][k] for k in range(n)] def productoDiagonal2(xss: list[list[int]]) -> int: return producto(diagonal2(xss)) # 3ª solución # =========== def productoDiagonal3(xss: list[list[int]]) -> int: if not xss: return 1 if not xss[0]: return 1 return xss[0][0] * productoDiagonal3(list(map((lambda ys : ys[1:]), xss[1:]))) # Verificación # ============ def test_productoDiagonal() -> None: for productoDiagonal in [productoDiagonal1, productoDiagonal2, productoDiagonal3]: assert productoDiagonal([[3,5,2],[4,7,1],[6,9,8]]) == 168 assert productoDiagonal([[1, 2, 3, 4, 5]]*5) == 120 print("Verificado") # La verificación es # >>> test_productoDiagonal() # Verificado # Comparación de eficiencia # ========================= # ejemplo(n) es la matriz con n filas formadas por los números de 1 a # n. Por ejemplo, # >>> ejemplo(3) # [[1, 2, 3], [1, 2, 3], [1, 2, 3]] def ejemplo(n: int) -> list[list[int]]: return [list(range(1, n+1))]*n 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('productoDiagonal1(ejemplo(1200))') # 1.97 segundos # >>> tiempo('productoDiagonal2(ejemplo(1200))') # 0.00 segundos # >>> tiempo('productoDiagonal3(ejemplo(1200))') # 1.56 segundos |