Matrices cruzadas
Consideramos las matrices representadas como tablas cuyos índices son pares de números naturales.
|
1 |
type Matriz a = Array (Int,Int) a |
Una matriz cruzada es una matriz cuadrada en la que sólo hay elementos distintos de 0 en las diagonales principal y secundaria. Por ejemplo,
|
1 2 3 4 5 |
| 1 0 0 0 3 | | 1 0 0 3 | | 0 2 0 1 0 | | 0 2 3 0 | | 0 0 3 0 0 | | 0 4 5 0 | | 0 2 0 1 0 | | 2 0 0 3 | | 1 0 0 0 3 | |
Definir la función
|
1 |
creaCruzada :: Int -> Matriz Int |
tal que (creaCruzada n) es la siguiente matriz cruzada con n filas y n columnas:
|
1 2 3 4 5 6 7 |
| 1 0 0 ... 0 0 1 | | 0 2 0 ... 0 2 0 | | 0 0 3 ... 3 0 0 | | ....................... | | 0 0 n-2 ... n-2 0 0 | | 0 n-1 0 ... 0 n-1 0 | | n 0 0 ... 0 0 n | |
Es decir, los elementos de la diagonal principal son [1,…,n], en orden desde la primera fila hasta la última; y los elementos de la diagonal secundaria son [1,…,n], en orden desde la primera fila hasta la última. Por ejemplo,
|
1 2 3 4 5 6 |
ghci> elems (creaCruzada 3) [1,0,1, 0,2,0, 3,0,3] ghci> elems (creaCruzada 4) [1,0,0,1, 0,2,2,0, 0,3,3,0, 4,0,0,4] ghci> elems (creaCruzada 5) [1,0,0,0,1, 0,2,0,2,0, 0,0,3,0,0, 0,4,0,4,0, 5,0,0,0,5] |
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 43 44 45 46 47 48 49 |
import Data.Array type Matriz a = Array (Int,Int) a -- 1ª solución creaCruzada1 :: Int -> Matriz Int creaCruzada1 n = array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]] where f i j | i == j = i | i+j == n+1 = i | otherwise = 0 -- 2ª solución creaCruzada2 :: Int -> Matriz Int creaCruzada2 n = listArray t [f i j| (i,j) <- range t] where t = ((1,1),(n,n)) f i j | i == j = i | i+j == n+1 = i | otherwise = 0 -- 3ª solución creaCruzada3 :: Int -> Matriz Int creaCruzada3 n = listArray ((1,1),(n,n)) (replicate (n^2) 0) // ([((i,i),i) | i <- [1..n]] ++ [((i,n-i+1),i)| i <- [n,n-1..1]]) creaCruzada4 :: Int -> Matriz Int creaCruzada4 n = accumArray (\x y -> y) 0 ((1,1),(n,n)) (concat [[((i,i),i),((i,n+1-i),i)] | i <- [1..n]]) -- Comparación de eficiencia -- ghci> let n = 2000 in creaCruzada1 n ! (n,n) -- 2000 -- (6.13 secs, 896997468 bytes) -- -- ghci> let n = 2000 in creaCruzada2 n ! (n,n) -- 2000 -- (3.83 secs, 433675668 bytes) -- -- ghci> let n = 2000 in creaCruzada3 n ! (n,n) -- 2000 -- (0.56 secs, 145741748 bytes) -- -- ghci> let n = 2000 in creaCruzada4 n ! (n,n) -- 2000 -- (0.27 secs, 37373392 bytes) |
Esta es más eficiente, pues a la mayoría de los índices les asocia directamente el valor cero sin tener que hacer comprobaciones.