{"id":1223,"date":"2015-03-24T06:00:24","date_gmt":"2015-03-24T04:00:24","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1223"},"modified":"2015-05-01T08:57:09","modified_gmt":"2015-05-01T06:57:09","slug":"matrices-cruzadas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/matrices-cruzadas\/","title":{"rendered":"Matrices cruzadas"},"content":{"rendered":"<p>Consideramos las matrices representadas como tablas cuyos \u00edndices son pares de n\u00fameros naturales.<\/p>\n<pre lang=\"text\">\n   type Matriz a = Array (Int,Int) a  \n<\/pre>\n<p>Una matriz cruzada es una matriz cuadrada en la que s\u00f3lo hay elementos distintos de 0 en las diagonales principal y secundaria. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   | 1 0 0 0 3 |     | 1 0 0 3 |\n   | 0 2 0 1 0 |     | 0 2 3 0 |\n   | 0 0 3 0 0 |     | 0 4 5 0 |\n   | 0 2 0 1 0 |     | 2 0 0 3 |\n   | 1 0 0 0 3 |\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   creaCruzada :: Int -> Matriz Int\n<\/pre>\n<p>tal que (creaCruzada n) es la siguiente matriz cruzada con n filas y n columnas:<\/p>\n<pre lang=\"text\">\n   | 1  0   0  ...  0   0  1 |\n   | 0  2   0  ...  0   2  0 |\n   | 0  0   3  ...  3   0  0 |\n   | ....................... |\n   | 0  0  n-2 ... n-2  0  0 |\n   | 0 n-1  0  ...  0  n-1 0 |\n   | n  0   0  ...  0   0  n |\n<\/pre>\n<p>Es decir, los elementos de la diagonal principal son [1,&#8230;,n], en orden desde la primera fila hasta la \u00faltima; y los elementos de la diagonal secundaria son [1,&#8230;,n], en orden desde la primera fila hasta la \u00faltima. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ghci> elems (creaCruzada 3)\n   [1,0,1, 0,2,0, 3,0,3]\n   ghci> elems (creaCruzada 4)\n   [1,0,0,1, 0,2,2,0, 0,3,3,0, 4,0,0,4]\n   ghci> elems (creaCruzada 5)\n   [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]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array\n\ntype Matriz a = Array (Int,Int) a\n\n-- 1\u00aa soluci\u00f3n\ncreaCruzada1 :: Int -> Matriz Int\ncreaCruzada1 n =\n    array ((1,1),(n,n))\n          [((i,j),f i j) | i <- [1..n], j <- [1..n]]\n    where f i j | i == j     = i\n                | i+j == n+1 = i\n                | otherwise  = 0\n\n-- 2\u00aa soluci\u00f3n\ncreaCruzada2 :: Int -> Matriz Int\ncreaCruzada2 n = listArray t [f i j| (i,j) <- range t]\n    where t = ((1,1),(n,n))\n          f i j | i == j     = i\n                | i+j == n+1 = i\n                | otherwise  = 0\n\n-- 3\u00aa soluci\u00f3n\ncreaCruzada3 :: Int -> Matriz Int\ncreaCruzada3 n = \n    listArray ((1,1),(n,n)) \n              (replicate (n^2) 0) \/\/ ([((i,i),i) | i <- [1..n]] ++ \n                                     [((i,n-i+1),i)| i <- [n,n-1..1]])\n\ncreaCruzada4 :: Int -> Matriz Int\ncreaCruzada4 n = \n    accumArray (\\x y -> y) 0 ((1,1),(n,n))\n               (concat [[((i,i),i),((i,n+1-i),i)] | i <- [1..n]])\n\n-- Comparaci\u00f3n de eficiencia\n--    ghci> let n = 2000 in creaCruzada1 n ! (n,n)\n--    2000\n--    (6.13 secs, 896997468 bytes)\n--    \n--    ghci> let n = 2000 in creaCruzada2 n ! (n,n)\n--    2000\n--    (3.83 secs, 433675668 bytes)\n--    \n--    ghci> let n = 2000 in creaCruzada3 n ! (n,n)\n--    2000\n--    (0.56 secs, 145741748 bytes)\n--    \n--    ghci> let n = 2000 in creaCruzada4 n ! (n,n)\n--    2000\n--    (0.27 secs, 37373392 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Consideramos las matrices representadas como tablas cuyos \u00edndices son pares de n\u00fameros naturales. type Matriz a = Array (Int,Int) a Una matriz cruzada es una matriz cuadrada en la que s\u00f3lo hay elementos distintos de 0 en las diagonales principal y secundaria. Por ejemplo, | 1 0 0 0 3 | | 1 0 0&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[250,8,42],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1223"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=1223"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1223\/revisions"}],"predecessor-version":[{"id":1278,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1223\/revisions\/1278"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1223"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}