{"id":4881,"date":"2019-03-29T06:00:39","date_gmt":"2019-03-29T04:00:39","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4881"},"modified":"2019-04-05T07:00:40","modified_gmt":"2019-04-05T05:00:40","slug":"triangulo-de-euler","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/triangulo-de-euler\/","title":{"rendered":"Tri\u00e1ngulo de Euler"},"content":{"rendered":"

El tri\u00e1ngulo de Euler se construye a partir de las siguientes relaciones<\/p>\n

 \n   A(n,1) = A(n,n) = 1\n   A(n,m) = (n-m)A(n-1,m-1) + (m+1)A(n-1,m).\n<\/pre>\n
Sus primeros t\u00e9rminos son<\/p>\n
 \n   1 \n   1 1                                                       \n   1 4   1                                            \n   1 11  11    1                                    \n   1 26  66    26    1                             \n   1 57  302   302   57     1                    \n   1 120 1191  2416  1191   120   1            \n   1 247 4293  15619 15619  4293  247   1   \n   1 502 14608 88234 156190 88234 14608 502 1 \n<\/pre>\n
Definir las siguientes funciones:<\/p>\n
 \n  numeroEuler        :: Integer -> Integer -> Integer\n  filaTrianguloEuler :: Integer -> [Integer]\n  trianguloEuler     :: [[Integer]]\n<\/pre>\n
tales que<\/p>\n
    \n
  • (numeroEuler n k) es el n\u00famero de Euler A(n,k). Por ejemplo, <\/li>\n<\/ul>\n
     \n     numeroEuler 8 3  == 15619\n     numeroEuler 20 6 == 21598596303099900\n     length (show (numeroEuler 1000 500)) == 2567\n<\/pre>\n
      \n
    • (filaTrianguloEuler n) es la n-\u00e9sima fila del tri\u00e1ngulo de Euler. Por ejemplo,<\/li>\n<\/ul>\n
         \n     filaTrianguloEuler 7  ==  [1,120,1191,2416,1191,120,1]\n     filaTrianguloEuler 8  ==  [1,247,4293,15619,15619,4293,247,1]\n     length (show (maximum (filaTrianguloEuler 1000)))  ==  2567\n<\/pre>\n
        \n
      • trianguloEuler es la lista con las filas del tri\u00e1ngulo de Euler<\/li>\n<\/ul>\n
         \n     \u03bb> take 6 trianguloEuler\n     [[1],[1,1],[1,4,1],[1,11,11,1],[1,26,66,26,1],[1,57,302,302,57,1]]\n     \u03bb> length (show (maximum (trianguloEuler !! 999)))\n     2567\n<\/pre>\n
        Soluciones<\/h4>\n
        \nimport Data.List  (genericLength, genericIndex)\nimport Data.Array (Array, (!), array)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntrianguloEuler :: [[Integer]]\ntrianguloEuler = iterate siguiente [1]\n\n-- (siguiente xs) es la fila siguiente a la xs en el tri\u00e1ngulo de\n-- Euler. Por ejemplo,\n--    \u03bb> siguiente [1]\n--    [1,1]\n--    \u03bb> siguiente it\n--    [1,4,1]\n--    \u03bb> siguiente it\n--    [1,11,11,1]\nsiguiente :: [Integer] -> [Integer]\nsiguiente xs = zipWith (+) us vs\n  where n = genericLength xs\n        us = zipWith (*) (0:xs) [n+1,n..1]\n        vs = zipWith (*) (xs++[0]) [1..n+1]\n\nfilaTrianguloEuler :: Integer -> [Integer]\nfilaTrianguloEuler n = trianguloEuler `genericIndex` (n-1)\n\nnumeroEuler :: Integer -> Integer -> Integer\nnumeroEuler n k = filaTrianguloEuler n `genericIndex` k\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nnumeroEuler2 :: Integer -> Integer -> Integer\nnumeroEuler2 n 0 = 1\nnumeroEuler2 n m \n  | n == m    = 0\n  | otherwise = (n-m) * numeroEuler2 (n-1) (m-1) + (m+1) * numeroEuler2 (n-1) m\n\nfilaTrianguloEuler2 :: Integer -> [Integer]\nfilaTrianguloEuler2 n = map (numeroEuler2 n) [0..n-1]\n\ntrianguloEuler2 :: [[Integer]]\ntrianguloEuler2 = map filaTrianguloEuler2 [1..]\n                  \n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nnumeroEuler3 :: Integer -> Integer -> Integer\nnumeroEuler3 n k = (matrizEuler n k) ! (n,k)\n\n-- (matrizEuler n m) es la matriz de n+1 filas y m+1 columnsa formada\n-- por los n\u00fameros de Euler. Por ejemplo,\n--   \u03bb> [[matrizEuler 6 6 ! (i,j) | j <- [0..i-1]] | i <- [1..6]]\n--   [[1],[1,1],[1,4,1],[1,11,11,1],[1,26,66,26,1],[1,57,302,302,57,1]]\nmatrizEuler :: Integer -> Integer -> Array (Integer,Integer) Integer\nmatrizEuler n m = q\n  where q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]\n        f i 0 = 1\n        f i j\n          | i == j    = 0\n          | otherwise = (i-j) * q!(i-1,j-1) + (j+1)* q!(i-1,j)\n\nfilaTrianguloEuler3 :: Integer -> [Integer]\nfilaTrianguloEuler3 n = map (numeroEuler3 n) [0..n-1]\n\ntrianguloEuler3 :: [[Integer]]\ntrianguloEuler3 = map filaTrianguloEuler3 [1..]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--   \u03bb> numeroEuler 22 11\n--   301958232385734088196\n--   (0.01 secs, 118,760 bytes)\n--   \u03bb> numeroEuler2 22 11\n--   301958232385734088196\n--   (3.96 secs, 524,955,384 bytes)\n--   \u03bb> numeroEuler3 22 11\n--   301958232385734088196\n--   (0.01 secs, 356,296 bytes)\n--   \n--   \u03bb> length (show (numeroEuler 800 400))\n--   1976\n--   (0.01 secs, 383,080 bytes)\n--   \u03bb> length (show (numeroEuler3 800 400))\n--   1976\n--   (2.13 secs, 508,780,696 bytes)\n<\/pre>\n
        Pensamiento<\/h4>\n
        \nSe\u00f1or San Jer\u00f3nimo,
        \nsuelte usted la piedra
        \ncon que se machaca.
        \nMe peg\u00f3 con ella.<\/p>\n
        Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
        El tri\u00e1ngulo de Euler se construye a partir de las siguientes relaciones A(n,1) = A(n,n) = 1 A(n,m) = (n-m)A(n-1,m-1) + (m+1)A(n-1,m). Sus primeros t\u00e9rminos son 1 1 1 1 4 1 1 11 11 1 1 26 66 26 1 1 57 302 302 57 1 1 120 1191 2416 1191 120 1 1…<\/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":[250,8,286,256,258,50,10,42,11,6,467],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4881"}],"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=4881"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4881\/revisions"}],"predecessor-version":[{"id":4920,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4881\/revisions\/4920"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4881"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4881"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4881"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}