{"id":7053,"date":"2022-05-26T13:14:07","date_gmt":"2022-05-26T11:14:07","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7053"},"modified":"2022-05-26T13:14:07","modified_gmt":"2022-05-26T11:14:07","slug":"el-triangulo-de-floyd","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/el-triangulo-de-floyd\/","title":{"rendered":"El tri\u00e1ngulo de Floyd"},"content":{"rendered":"<p>El <a href=\"http:\/\/bit.ly\/1D6ZF4q\">tri\u00e1ngulo de Floyd<\/a>, llamado as\u00ed en honor a Robert Floyd, es un tri\u00e1ngulo rect\u00e1ngulo formado con n\u00fameros naturales. Para crear un tri\u00e1ngulo de Floyd, se comienza con un 1 en la esquina superior izquierda, y se contin\u00faa escribiendo la secuencia de los n\u00fameros naturales de manera que cada l\u00ednea contenga un n\u00famero m\u00e1s que la anterior. Las 5 primeras l\u00edneas del tri\u00e1ngulo de Floyd son<\/p>\n<pre lang=\"text\">\n    1\n    2   3\n    4   5   6\n    7   8   9  10\n   11  12  13  14  15\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   trianguloFloyd :: [[Integer]]\n<\/pre>\n<p>tal que <code>trianguloFloyd<\/code> es el tri\u00e1ngulo de Floyd. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 4 trianguloFloyd\n   [[1],\n    [2,3],\n    [4,5,6],\n    [7,8,9,10]]\n  (trianguloFloyd !! (10^5)) !! 0  ==  5000050001\n  (trianguloFloyd !! (10^6)) !! 0  ==  500000500001\n  (trianguloFloyd !! (10^7)) !! 0  ==  50000005000001\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntrianguloFloyd1 :: [[Integer]]\ntrianguloFloyd1 = floyd 1 [1..]\n  where floyd n xs = i : floyd (n+1) r\n          where (i,r) = splitAt n xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntrianguloFloyd2 :: [[Integer]]\ntrianguloFloyd2 = iterate siguienteF [1]\n\n-- (siguienteF xs) es la lista de los elementos de la l\u00ednea xs en el\n-- tri\u00e1ngulo de Floyd. Por ejemplo,\n--    siguienteF [2,3]    ==  [4,5,6]\n--    siguienteF [4,5,6]  ==  [7,8,9,10]\nsiguienteF :: [Integer] -> [Integer]\nsiguienteF xs = [a..a+n]\n    where a = 1 + last xs\n          n = genericLength xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntrianguloFloyd3 :: [[Integer]]\ntrianguloFloyd3 =\n  [[(n*(n-1) `div` 2) + 1 .. (n*(n+1) `div` 2)] | n <- [1..]]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ntrianguloFloyd4 :: [[Integer]]\ntrianguloFloyd4 =\n  scanl (\\(x:_) y -> [x+y..x+2*y]) [1] [1..]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_trianguloFloyd :: Positive Int -> Bool\nprop_trianguloFloyd (Positive n) =\n  all (== (trianguloFloyd1 !! n))\n      [trianguloFloyd2 !! n,\n       trianguloFloyd3 !! n,\n       trianguloFloyd4 !! n]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_trianguloFloyd\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> (trianguloFloyd1 !! 5000) !! 5000\n--    12507501\n--    (1.47 secs, 2,505,005,752 bytes)\n--    \u03bb> (trianguloFloyd2 !! 5000) !! 5000\n--    12507501\n--    (0.79 secs, 2,416,259,176 bytes)\n--    \u03bb> (trianguloFloyd3 !! 5000) !! 5000\n--    12507501\n--    (0.00 secs, 1,809,152 bytes)\n--    \u03bb> (trianguloFloyd4 !! 5000) !! 5000\n--    12507501\n--    (0.01 secs, 3,517,896 bytes)\n--\n--    \u03bb> (trianguloFloyd3 !! (10^7)) !! 0\n--    50000005000001\n--    (2.45 secs, 1,656,534,080 bytes)\n--    \u03bb> (trianguloFloyd4 !! (10^7)) !! 0\n--    50000005000001\n--    (10.86 secs, 5,302,760,752 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/El_triangulo_de_Floyd.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>El tri\u00e1ngulo de Floyd, llamado as\u00ed en honor a Robert Floyd, es un tri\u00e1ngulo rect\u00e1ngulo formado con n\u00fameros naturales. Para crear un tri\u00e1ngulo de Floyd, se comienza con un 1 en la esquina superior izquierda, y se contin\u00faa escribiendo la secuencia de los n\u00fameros naturales de manera que cada l\u00ednea contenga un n\u00famero m\u00e1s que&#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":[2],"tags":[521],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7053"}],"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=7053"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7053\/revisions"}],"predecessor-version":[{"id":7054,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7053\/revisions\/7054"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7053"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7053"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7053"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}