En el siguiente gr\u00e1fico se representa en una cuadr\u00edcula el plano de Manhattan. Cada l\u00ednea es una opci\u00f3n a seguir; el n\u00famero representa las atracciones que se pueden visitar si se elige esa opci\u00f3n.<\/p>\n
\n 3 2 4 0\n * ------- * ------- * ------- * ------- *\n | | | | |\n |1 |0 |2 |4 |3\n | 3 | 2 | 4 | 2 |\n * ------- * ------- * ------- * ------- *\n | | | | |\n |4 |6 |5 |2 |1\n | 0 | 7 | 3 | 4 |\n * ------- * ------- * ------- * ------- *\n | | | | |\n |4 |4 |5 |2 |1\n | 3 | 3 | 0 | 2 |\n * ------- * ------- * ------- * ------- *\n | | | | |\n |5 |6 |8 |5 |3\n | 1 | 3 | 2 | 2 |\n * ------- * ------- * ------- * ------- *\n<\/pre>\nEl turista entra por el extremo superior izquierda y sale por el extremo inferior derecha. S\u00f3lo puede moverse en las direcciones Sur y Este (es decir, hacia abajo o hacia la derecha).<\/p>\n
Representamos el mapa mediante una matriz p tal que p(i,j) = (a,b), donde a = n\u00ba de atracciones si se va hacia el sur y b = n\u00ba de atracciones si se va al este. Adem\u00e1s, ponemos un 0 en el valor del n\u00famero de atracciones por un camino que no se puede elegir. De esta forma, el mapa anterior se representa por la matriz siguiente:<\/p>\n
\n ( (1,3) (0,2) (2,4) (4,0) (3,0) )\n ( (4,3) (6,2) (5,4) (2,2) (1,0) )\n ( (4,0) (4,7) (5,3) (2,4) (1,0) )\n ( (5,3) (6,3) (8,0) (5,2) (3,0) )\n ( (0,1) (0,3) (0,2) (0,2) (0,0) )\n<\/pre>\nEn este caso, si se hace el recorrido<\/p>\n
\n [S, E, S, E, S, S, E, E],\n<\/pre>\nel n\u00famero de atracciones es<\/p>\n
\n 1 3 6 7 5 8 2 2\n<\/pre>\ncuya suma es 34.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n mayorNumeroV:: M.Matrix (Int,Int) -> Int\n<\/pre>\ntal que (mayorNumeroV p) es el m\u00e1ximo n\u00famero de atracciones que se pueden visitar en el plano representado por la matriz p. Por ejemplo, si se define la matriz anterior por<\/p>\n
\n ejMapa :: M.Matrix (Int,Int)\n ejMapa = M.fromLists [[(1,3),(0,2),(2,4),(4,0),(3,0)], \n [(4,3),(6,2),(5,4),(2,2),(1,0)],\n [(4,0),(4,7),(5,3),(2,4),(1,0)],\n [(5,3),(6,3),(8,0),(5,2),(3,0)],\n [(0,1),(0,3),(0,2),(0,2),(0,0)]]\n<\/pre>\nentonces<\/p>\n
\n mayorNumeroV ejMapa == 34\n mayorNumeroV (fromLists [[(1,3),(0,0)],[(0,3),(0,0)]]) == 4\n mayorNumeroV (fromLists [[(1,3),(6,0)],[(0,3),(0,0)]]) == 9\n<\/pre>\nPara los siguientes ejemplos se define un generador de mapas<\/p>\n
\n genMapa :: Int -> Matrix (Int,Int)\n genMapa n =\n extendTo (0,0) n n (fromList (n-1) (n-1) [(k,k+1) | k <- [1..]])\n<\/pre>\nEntonces,<\/p>\n
\n mayorNumeroV (genMapa 10) == 962\n mayorNumeroV (genMapa 500) == 185880992\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Matrix\n\nejMapa :: Matrix (Int,Int)\nejMapa = fromLists [[(1,3),(0,2),(2,4),(4,0),(3,0)], \n [(4,3),(6,2),(5,4),(2,2),(1,0)],\n [(4,0),(4,7),(5,3),(2,4),(1,0)],\n [(5,3),(6,3),(8,0),(5,2),(3,0)],\n [(0,1),(0,3),(0,2),(0,2),(0,0)]]\n\ngenMapa :: Int -> Matrix (Int,Int)\ngenMapa n =\n extendTo (0,0) n n (fromList (n-1) (n-1) [(k,k+1) | k <- [1..]])\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\nmayorNumeroV1 :: Matrix (Int,Int) -> Int\nmayorNumeroV1 p = aux m n\n where m = nrows p\n n = ncols p\n aux 1 1 = 0\n aux 1 j = sum [snd (p !(1,k)) | k <- [1..j-1]]\n aux i 1 = sum [fst (p !(k,1)) | k <- [1..i-1]]\n aux i j = max ((aux (i-1) j) + fst (p !(i-1,j)))\n ((aux i (j-1)) + snd (p !(i,j-1)))\n\n-- 2\u00aa soluci\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =======================================\n\nmayorNumeroV2 :: Matrix (Int,Int) -> Int\nmayorNumeroV2 p = (matrizNumeroV p) ! (m,n)\n where m = nrows p\n n = ncols p\n\nmatrizNumeroV :: Matrix (Int,Int) -> Matrix Int\nmatrizNumeroV p = q\n where m = nrows p\n n = ncols p\n q = matrix m n f\n f (1,1) = 0\n f (1,j) = snd (p!(1,j-1)) + q!(1,j-1)\n f (i,1) = fst (p!(i-1,1)) + q!(i-1,1)\n f (i,j) = max (fst (p!(i-1,j)) + q!(i-1,j))\n (snd (p!(i,j-1)) + q!(i,j-1))\n\n-- 3\u00aa soluci\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =======================================\n\nmayorNumeroV3 :: Matrix (Int, Int) -> Int\nmayorNumeroV3 mapa = m ! (1,1)\n where m = matrix r c f\n r = nrows mapa\n c = ncols mapa\n f (i,j) | i == r && j == c = 0\n | i == r = e + m !(r,j+1)\n | j == c = s + m !(i+1,c)\n | otherwise = max (e + m !(i, j+1)) (s + m !(i+1, j))\n where (s,e) = mapa ! (i,j)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> mayorNumeroV1 (genMapa 11)\n-- 1334\n-- (2.07 secs, 352,208,752 bytes)\n-- \u03bb> mayorNumeroV2 (genMapa 11)\n-- 1334\n-- (0.01 secs, 319,792 bytes)\n-- \u03bb> mayorNumeroV3 (genMapa 11)\n-- 1334\n-- (0.01 secs, 299,936 bytes)\n-- \n-- \u03bb> mayorNumeroV2 (genMapa 500)\n-- 185880992\n-- (2.26 secs, 374,557,416 bytes)\n-- \u03bb> mayorNumeroV3 (genMapa 500)\n-- 185880992\n-- (3.15 secs, 401,098,336 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"En el siguiente gr\u00e1fico se representa en una cuadr\u00edcula el plano de Manhattan. Cada l\u00ednea es una opci\u00f3n a seguir; el n\u00famero representa las atracciones que se pueden visitar si se elige esa opci\u00f3n. 3 2 4 0 * ——- * ——- * ——- * ——- * | | | | | |1 |0 |2…<\/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":[7],"tags":[8,286,80,42,97,99,98,6,16,40],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4050"}],"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=4050"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4050\/revisions"}],"predecessor-version":[{"id":4081,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4050\/revisions\/4081"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4050"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4050"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4050"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}