Los caminos desde el extremo superior izquierdo (posici\u00f3n (1,1)) hasta el extremo inferior derecho (posici\u00f3n (3,4)) en la matriz<\/p>\n
\n ( 1 6 11 2 )\n ( 7 12 3 8 )\n ( 3 8 4 9 )\n<\/pre>\nmovi\u00e9ndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:<\/p>\n
\n 1, 7, 3, 8, 4, 9\n 1, 7, 12, 8, 4, 9\n 1, 7, 12, 3, 4, 9\n 1, 7, 12, 3, 8, 9\n 1, 6, 12, 8, 4, 9\n 1, 6, 12, 3, 4, 9\n 1, 6, 12, 3, 8, 9\n 1, 6, 11, 3, 4, 9\n 1, 6, 11, 3, 8, 9\n 1, 6, 11, 2, 8, 9\n<\/pre>\nLas sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El m\u00e1ximo de las suma de los caminos es 41.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n maximaSuma :: Matrix Int -> Int\n<\/pre>\ntal que (maximaSuma m) es el m\u00e1ximo de las sumas de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, movi\u00e9ndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,<\/p>\n
\n \u03bb> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n 41\n \u03bb> maximaSuma (fromList 800 800 [1..])\n 766721999\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Matrix\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nmaximaSuma1 :: Matrix Int -> Int\nmaximaSuma1 =\n maximum . map sum . caminos1\n\ncaminos1 :: Matrix Int -> [[Int]]\ncaminos1 m =\n map reverse (caminos1Aux m (nf,nc))\n where nf = nrows m\n nc = ncols m\n\n-- (caminos1Aux p x) es la lista de los caminos invertidos en la matriz p\n-- desde la posici\u00f3n (1,1) hasta la posici\u00f3n x. Por ejemplo,\ncaminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]\ncaminos1Aux m (1,1) = [[m!(1,1)]]\ncaminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]\ncaminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]\ncaminos1Aux m (i,j) = [m!(i,j) : xs\n | xs <- caminos1Aux m (i,j-1) ++\n caminos1Aux m (i-1,j)]\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nmaximaSuma2 :: Matrix Int -> Int\nmaximaSuma2 =\n maximum . map sum . caminos2\n\ncaminos2 :: Matrix Int -> [[Int]]\ncaminos2 m =\n map reverse (matrizCaminos m ! (nrows m, ncols m))\n\nmatrizCaminos :: Matrix Int -> Matrix [[Int]]\nmatrizCaminos m = q\n where\n q = matrix (nrows m) (ncols m) f\n f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]\n f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]\n f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)] \n\n-- 3\u00aa definicion (por recursi\u00f3n, sin calcular el camino)\n-- =====================================================\n\nmaximaSuma3 :: Matrix Int -> Int\nmaximaSuma3 m = maximaSuma3Aux m (nf,nc)\n where nf = nrows m\n nc = ncols m\n\n-- (maximaSuma3Aux m p) calcula la suma m\u00e1xima de un camino hasta la\n-- posici\u00f3n p. Por ejemplo,\n-- \u03bb> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)\n-- 41\n-- \u03bb> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)\n-- 32\n-- \u03bb> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)\n-- 31\nmaximaSuma3Aux :: Matrix Int -> (Int,Int) -> Int\nmaximaSuma3Aux m (1,1) = m ! (1,1)\nmaximaSuma3Aux m (1,j) = maximaSuma3Aux m (1,j-1) + m ! (1,j)\nmaximaSuma3Aux m (i,1) = maximaSuma3Aux m (i-1,1) + m ! (i,1)\nmaximaSuma3Aux m (i,j) =\n max (maximaSuma3Aux m (i,j-1)) (maximaSuma3Aux m (i-1,j)) + m ! (i,j)\n\n-- 4\u00aa soluci\u00f3n (mediante programaci\u00f3n din\u00e1mica)\n-- ============================================\n\nmaximaSuma4 :: Matrix Int -> Int\nmaximaSuma4 m = q ! (nf,nc)\n where nf = nrows m\n nc = ncols m\n q = matrizMaximaSuma m\n\n-- (matrizMaximaSuma m) es la matriz donde en cada posici\u00f3n p se\n-- encuentra el m\u00e1xima de las sumas de los caminos desde (1,1) a p en la\n-- matriz m. Por ejemplo, \n-- \u03bb> matrizMaximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) \n-- ( 1 7 18 20 )\n-- ( 8 20 23 31 )\n-- ( 11 28 32 41 )\nmatrizMaximaSuma :: Matrix Int -> Matrix Int\nmatrizMaximaSuma m = q \n where nf = nrows m\n nc = ncols m\n q = matrix nf nc f\n where f (1,1) = m ! (1,1)\n f (1,j) = q ! (1,j-1) + m ! (1,j)\n f (i,1) = q ! (i-1,1) + m ! (i,1)\n f (i,j) = max (q ! (i,j-1)) (q ! (i-1,j)) + m ! (i,j)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> maximaSuma1 (fromList 8 8 [1..])\n-- 659\n-- (0.11 secs, 31,853,136 bytes)\n-- \u03bb> maximaSuma1a (fromList 8 8 [1..])\n-- 659\n-- (0.09 secs, 19,952,640 bytes)\n-- \n-- \u03bb> maximaSuma1 (fromList 10 10 [1..])\n-- 1324\n-- (2.25 secs, 349,722,744 bytes)\n-- \u03bb> maximaSuma2 (fromList 10 10 [1..])\n-- 1324\n-- (0.76 secs, 151,019,296 bytes)\n-- \n-- \u03bb> maximaSuma2 (fromList 11 11 [1..])\n-- 1781\n-- (3.02 secs, 545,659,632 bytes)\n-- \u03bb> maximaSuma3 (fromList 11 11 [1..])\n-- 1781\n-- (1.57 secs, 210,124,912 bytes)\n-- \n-- \u03bb> maximaSuma3 (fromList 12 12 [1..])\n-- 2333\n-- (5.60 secs, 810,739,032 bytes)\n-- \u03bb> maximaSuma4 (fromList 12 12 [1..])\n-- 2333\n-- (0.01 secs, 23,154,776 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Los caminos desde el extremo superior izquierdo (posici\u00f3n (1,1)) hasta el extremo inferior derecho (posici\u00f3n (3,4)) en la matriz ( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) movi\u00e9ndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes: 1, 7, 3,…<\/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":[8,286,10,42,97,15,99,98,11,6,32],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3864"}],"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=3864"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3864\/revisions"}],"predecessor-version":[{"id":3903,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3864\/revisions\/3903"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3864"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3864"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3864"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}