{"id":3850,"date":"2018-03-09T06:00:09","date_gmt":"2018-03-09T04:00:09","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3850"},"modified":"2018-03-16T07:11:35","modified_gmt":"2018-03-16T05:11:35","slug":"matrices-de-pascal","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/matrices-de-pascal\/","title":{"rendered":"Matrices de Pascal"},"content":{"rendered":"<p>El tri\u00e1ngulo de Pascal es un tri\u00e1ngulo de n\u00fameros<\/p>\n<pre lang=\"text\">\n         1\n        1 1\n       1 2 1\n     1  3 3  1\n    1 4  6  4 1\n   1 5 10 10 5 1\n  ...............\n<\/pre>\n<p>construido de la siguiente forma<\/p>\n<ul>\n<li>la primera fila est\u00e1 formada por el n\u00famero 1;<\/li>\n<li>las filas siguientes se construyen sumando los n\u00fameros adyacentes de la fila superior y a\u00f1adiendo un 1 al principio y al final de la fila. <\/li>\n<\/ul>\n<p>La matriz de Pascal es la matriz cuyas filas son los elementos de la<br \/>\ncorrespondiente fila del tri\u00e1ngulo de Pascal completadas con ceros. Por ejemplo, la matriz de Pascal de orden 6 es<\/p>\n<pre lang=\"text\">\n   |1 0  0  0 0 0|\n   |1 1  0  0 0 0|\n   |1 2  1  0 0 0|\n   |1 3  3  1 0 0|\n   |1 4  6  4 1 0|\n   |1 5 10 10 5 1|\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   matrizPascal :: Int -> Matrix Integer \n<\/pre>\n<p>tal que (matrizPascal n) es la matriz de Pascal de orden n. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> matrizPascal 6\n   (  1  0  0  0  0  0 )\n   (  1  1  0  0  0  0 )\n   (  1  2  1  0  0  0 )\n   (  1  3  3  1  0  0 )\n   (  1  4  6  4  1  0 )\n   (  1  5 10 10  5  1 )\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Matrix\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmatrizPascal :: Int -> Matrix Integer \nmatrizPascal 1 = fromList 1 1 [1]\nmatrizPascal n = matrix n n f \n  where f (i,j) | i < n &#038;&#038; j <  n  = p!(i,j)\n                | i < n &#038;&#038; j == n  = 0\n                | j == 1 || j == n = 1\n                | otherwise        = p!(i-1,j-1) + p!(i-1,j)\n        p = matrizPascal (n-1)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmatrizPascal2 :: Int -> Matrix Integer\nmatrizPascal2 n = fromLists xss\n  where yss = take n pascal\n        xss = map (take n) (map (++ repeat 0) yss)\n        \npascal :: [[Integer]]\npascal = [1] : map f pascal\n    where f xs = zipWith (+) (0:xs) (xs ++ [0])\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmatrizPascal3 :: Int -> Matrix Integer\nmatrizPascal3 n =  matrix n n f\n  where f (i,j) | i >=  j   = comb (i-1) (j-1)\n                | otherwise = 0\n\n-- (comb n k) es el n\u00famero de combinaciones (o coeficiente binomial) de\n-- n sobre k. Por ejemplo,\ncomb :: Int -> Int -> Integer\ncomb n k = product [n',n'-1..n'-k'+1] `div` product [1..k']\n  where n' = fromIntegral n\n        k' = fromIntegral k\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nmatrizPascal4 :: Int -> Matrix Integer\nmatrizPascal4 n = p\n  where p = matrix n n (\\(i,j) -> f i j)\n        f i 1 = 1\n        f i j\n          | j >  i    = 0\n          | i == j    = 1\n          | otherwise = p!(i-1,j) + p!(i-1,j-1)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> maximum (matrizPascal 150)\n--    46413034868354394849492907436302560970058760\n--    (2.58 secs, 394,030,504 bytes)\n--    \u03bb> maximum (matrizPascal2 150)\n--    46413034868354394849492907436302560970058760\n--    (0.03 secs, 8,326,784 bytes)\n--    \u03bb> maximum (matrizPascal3 150)\n--    46413034868354394849492907436302560970058760\n--    (0.38 secs, 250,072,360 bytes)\n--    \u03bb> maximum (matrizPascal4 150)\n--    46413034868354394849492907436302560970058760\n--    (0.10 secs, 13,356,360 bytes)\n--    \n--    \u03bb> length (show (maximum (matrizPascal2 300)))\n--    89\n--    (0.06 secs, 27,286,296 bytes)\n--    \u03bb> length (show (maximum (matrizPascal3 300)))\n--    89\n--    (2.74 secs, 2,367,037,536 bytes)\n--    \u03bb> length (show (maximum (matrizPascal4 300)))\n--    89\n--    (0.36 secs, 53,934,792 bytes)\n--    \n--    \u03bb> length (show (maximum (matrizPascal2 700)))\n--    209\n--    (0.83 secs, 207,241,080 bytes)\n--    \u03bb> length (show (maximum (matrizPascal4 700)))\n--    209\n--    (2.22 secs, 311,413,008 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El tri\u00e1ngulo de Pascal es un tri\u00e1ngulo de n\u00fameros 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 &#8230;&#8230;&#8230;&#8230;&#8230; construido de la siguiente forma la primera fila est\u00e1 formada por el n\u00famero 1; las filas siguientes se construyen sumando los n\u00fameros adyacentes de&#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":[5],"tags":[286,183,441,442,415,10,42,97,11,157,49,47,76],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3850"}],"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=3850"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3850\/revisions"}],"predecessor-version":[{"id":3875,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3850\/revisions\/3875"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3850"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3850"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3850"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}