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 camino de m\u00e1xima suma es el segundo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n caminoMaxSuma :: Matrix Int -> [Int]\n<\/pre>\ntal que (caminoMaxSuma m) es un camino de m\u00e1xima suma 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> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n [1,7,12,8,4,9]\n \u03bb> sum (caminoMaxSuma (fromList 800 800 [1..]))\n 766721999\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Matrix\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\ncaminoMaxSuma1 :: Matrix Int -> [Int]\ncaminoMaxSuma1 m =\n head [c | c <- cs, sum c == k] \n where cs = caminos1 m\n k = maximum (map sum cs)\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\ncaminoMaxSuma2 :: Matrix Int -> [Int]\ncaminoMaxSuma2 m =\n head [c | c <- cs, sum c == k] \n where cs = caminos2 m\n k = maximum (map sum cs)\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 definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\ncaminoMaxSuma3 :: Matrix Int -> [Int]\ncaminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))\n where nf = nrows m\n nc = ncols m\n q = caminoMaxSumaAux m\n\ncaminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])\ncaminoMaxSumaAux m = q \n where\n nf = nrows m\n nc = ncols m\n q = matrix nf nc f\n where\n f (1,1) = (m!(1,1),[m!(1,1)])\n f (1,j) = (k + m!(1,j), m!(1,j):xs)\n where (k,xs) = q!(1,j-1)\n f (i,1) = (k + m!(i,1), m!(i,1):xs)\n where (k,xs) = q!(i-1,1) \n f (i,j) | k1 > k2 = (k1 + m!(i,j), m!(i,j):xs)\n | otherwise = (k2 + m!(i,j), m!(i,j):ys)\n where (k1,xs) = q!(i,j-1)\n (k2,ys) = q!(i-1,j)\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- El generador es\ninstance Arbitrary a => Arbitrary (Matrix a) where\n arbitrary = do\n m <- choose (1,7)\n n <- choose (1,7)\n xs <- Test.QuickCheck.vector (n*m)\n return (fromList m n xs)\n\n\n-- Por ejemplo,\n-- \u03bb> sample' (arbitrary :: Gen (Matrix Int))\n-- [( 0 )\n-- ( 0 )\n-- ( 0 )\n-- ( 0 )\n-- ,( 1 2 )\n-- ( -1 1 )\n-- ( -1 -2 )\n-- ( 1 -1 )\n-- ( 1 0 )\n-- ( 2 0 )\n-- ( 2 -2 )\n-- ,( -4 4 -2 )\n-- ( -2 0 -2 )\n-- ( 0 -1 -2 )\n-- ( -4 -1 2 )\n-- ,( -2 7 -3 1 -5 -3 5 )\n-- ( 0 2 7 -1 -5 7 -6 )\n-- ( 1 7 -8 1 6 -7 5 )\n-- ( -4 7 -2 -7 -5 5 -8 )\n-- ...\n\n-- La propiedad es\nprop_caminoMaxSuma :: Matrix Int -> Bool\nprop_caminoMaxSuma m =\n x1 == x2 && x2 == x3\n where x1 = sum (caminoMaxSuma1 m)\n x2 = sum (caminoMaxSuma2 m)\n x3 = sum (caminoMaxSuma1 m)\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_caminoMaxSuma\n-- +++ OK, passed 100 tests.\n\n\n-- Comparaci\u00f3n de eficiencia\n-- -------------------------\n\n-- \u03bb> length (caminoMaxSuma1 (fromList 11 11 [1..]))\n-- 21\n-- (10.00 secs, 1,510,120,328 bytes)\n-- \u03bb> length (caminoMaxSuma2 (fromList 11 11 [1..]))\n-- 21\n-- (3.84 secs, 745,918,544 bytes)\n-- \u03bb> length (caminoMaxSuma3 (fromList 11 11 [1..]))\n-- 21\n-- (0.01 secs, 0 bytes)\n<\/pre>\nPensamiento<\/h4>\n\nCaminante, no hay camino,
\nsino estelas en la mar.<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\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":[7],"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\/4805"}],"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=4805"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4805\/revisions"}],"predecessor-version":[{"id":4834,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4805\/revisions\/4834"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4805"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4805"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4805"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}