Posiciones de las diagonales principales
Las posiciones de una matriz con 3 filas y 4 columnas son
|
1 2 3 |
(1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) |
La posiciones de sus 6 diagonales principales son
|
1 2 3 4 5 6 |
[(3,1)] [(2,1),(3,2)] [(1,1),(2,2),(3,3)] [(1,2),(2,3),(3,4)] [(1,3),(2,4)] [(1,4)] |
Definir la función
|
1 |
posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]] |
tal que (posicionesdiagonalesprincipales m n) es la lista de las posiciones de las diagonales principales de una matriz con m filas y n columnas. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
λ> mapM_ print (posicionesDiagonalesPrincipales 3 4) [(3,1)] [(2,1),(3,2)] [(1,1),(2,2),(3,3)] [(1,2),(2,3),(3,4)] [(1,3),(2,4)] [(1,4)] λ> mapM_ print (posicionesDiagonalesPrincipales 4 4) [(4,1)] [(3,1),(4,2)] [(2,1),(3,2),(4,3)] [(1,1),(2,2),(3,3),(4,4)] [(1,2),(2,3),(3,4)] [(1,3),(2,4)] [(1,4)] λ> mapM_ print (posicionesDiagonalesPrincipales 4 3) [(4,1)] [(3,1),(4,2)] [(2,1),(3,2),(4,3)] [(1,1),(2,2),(3,3)] [(1,2),(2,3)] [(1,3)] |
Soluciones
|
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 |
import Test.QuickCheck -- 1ª solución -- =========== posicionesDiagonalesPrincipales1 :: Int -> Int -> [[(Int, Int)]] posicionesDiagonalesPrincipales1 m n = [extension ij | ij <- iniciales] where iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]] extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]] -- 2ª solución -- =========== posicionesDiagonalesPrincipales2 :: Int -> Int -> [[(Int, Int)]] posicionesDiagonalesPrincipales2 m n = [zip [i..m] [1..n] | i <- [m,m-1..1]] ++ [zip [1..m] [j..n] | j <- [2..n]] -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_posicionesDiagonalesPrincipales :: Positive Int -> Positive Int -> Bool prop_posicionesDiagonalesPrincipales (Positive m) (Positive n) = posicionesDiagonalesPrincipales1 m n == posicionesDiagonalesPrincipales2 m n -- La comprobación es -- λ> quickCheck prop_posicionesDiagonalesPrincipales -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (posicionesDiagonalesPrincipales1 (10^7) (10^6)) -- 10999999 -- (6.14 secs, 3,984,469,440 bytes) -- λ> length (posicionesDiagonalesPrincipales2 (10^7) (10^6)) -- 10999999 -- (3.07 secs, 2,840,469,440 bytes) |
El código se encuentra en GitHub