{"id":4661,"date":"2019-01-31T06:00:35","date_gmt":"2019-01-31T04:00:35","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4661"},"modified":"2019-02-07T08:43:02","modified_gmt":"2019-02-07T06:43:02","slug":"triangulo-de-pascal-binario","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/triangulo-de-pascal-binario\/","title":{"rendered":"Tri\u00e1ngulo de Pascal binario"},"content":{"rendered":"<p>Los tri\u00e1ngulos binarios de Pascal se formas a partir de una lista de ceros y unos usando las reglas del tri\u00e1ngulo de Pascal, donde cada uno de los n\u00fameros es suma m\u00f3dulo dos de los dos situados en diagonal por encima suyo. Por ejemplo, los tri\u00e1ngulos binarios de Pascal correspondientes a [1,0,1,1,1] y [1,0,1,1,0] son<\/p>\n<pre lang=\"text\">  \n   1 0 1 1 1   1 0 1 1 0     \n    1 1 0 0     1 1 0 1  \n     0 1 0       0 1 1   \n      1 1         1 0    \n       0           1     \n<\/pre>\n<p>Sus finales, desde el extremo inferior al extremos superior derecho, son [0,1,0,0,1] y [1,0,1,1,0], respectivamente.<\/p>\n<p>Una lista es Pascal capic\u00faa si es igual a los finales de su tri\u00e1ngulo binario de Pascal. Por ejemplo, [1,0,1,1,0] es Pascal capic\u00faa.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\"> \n   trianguloPascalBinario :: [Int] -> [[Int]]\n   pascalCapicuas         :: Int -> [[Int]]\n   nPascalCapicuas        :: Int -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(trianguloPascalBinario xs) es el tri\u00e1gulo binario de Pascal correspondiente a la lista xs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">   \n     \u03bb> trianguloPascalBinario [1,0,1,1,1]\n     [[1,0,1,1,1],[1,1,0,0],[0,1,0],[1,1],[0]]\n     \u03bb> trianguloPascalBinario [1,0,1,1,0]\n     [[1,0,1,1,0],[1,1,0,1],[0,1,1],[1,0],[1]]\n<\/pre>\n<ul>\n<li>(pascalCapicuas n) es la lista de listas de Pascal capic\u00faas de n elementos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">   \n     \u03bb> pascalCapicuas 2\n     [[0,0],[1,0]]\n     \u03bb> pascalCapicuas 3\n     [[0,0,0],[0,1,0],[1,0,0],[1,1,0]]\n     \u03bb> pascalCapicuas 4\n     [[0,0,0,0],[0,1,1,0],[1,0,0,0],[1,1,1,0]]\n<\/pre>\n<ul>\n<li>(nPascalCapicuas n) es el n\u00famero de listas de Pascal capic\u00faas de n elementos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">   \n     \u03bb> nPascalCapicuas 2\n     2\n     \u03bb> nPascalCapicuas 3\n     4\n     \u03bb> nPascalCapicuas 4\n     4\n     \u03bb> nPascalCapicuas 400\n     1606938044258990275541962092341162602522202993782792835301376\n     \u03bb> length (show (nPascalCapicuas (10^5)))\n     15052\n     \u03bb> length (show (nPascalCapicuas (10^6)))\n     150515\n     \u03bb> length (show (nPascalCapicuas (10^7)))\n     1505150\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, unfoldr)\n\n-- Definici\u00f3n de trianguloPascalBinario\n-- ====================================\n\ntrianguloPascalBinario :: [Int] -> [[Int]]\ntrianguloPascalBinario xs =\n  takeWhile (not . null) (iterate siguiente xs)\n\n-- (siguiente xs) es la l\u00ednea siguiente a la xs en el tri\u00e1ngulo binario\n-- de Pascal. Por ejemplo,\n--    \u03bb> siguiente [1,0,1,1,1]\n--    [1,1,0,0]\n--    \u03bb> siguiente it\n--    [0,1,0]\n--    \u03bb> siguiente it\n--    [1,1]\n--    \u03bb> siguiente it\n--    [0]\n--    \u03bb> siguiente it\n--    []\n--    \u03bb> siguiente it\n--    []\nsiguiente :: [Int] -> [Int]\nsiguiente xs = [(x + y) `mod` 2 | (x,y) <- zip xs (tail xs)]\n\n-- 2\u00aa definici\u00f3n de trianguloPascalBinario\n-- =======================================\n\ntrianguloPascalBinario2 :: [Int] -> [[Int]]\ntrianguloPascalBinario2 = unfoldr f \n  where f [] = Nothing\n        f xs = Just (xs, siguiente xs)\n \n-- Definici\u00f3n de pascalCapicuas\n-- ============================\n\npascalCapicuas :: Int -> [[Int]]\npascalCapicuas n =\n  [xs | xs <- inicios n\n      , esPascalCapicua xs]\n\n-- (inicios n) es la lista de longitud n formadas por ceros y unos. Por\n-- ejemplo, \n--    \u03bb> inicios 0\n--    [[]]\n--    \u03bb> inicios 1\n--    [[0],[1]]\n--    \u03bb> inicios 2\n--    [[0,0],[0,1],[1,0],[1,1]]\n--    \u03bb> inicios 3\n--    [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]\ninicios :: Int -> [[Int]]\ninicios 0 = [[]]\ninicios n = map (0:) xss ++ map (1:) xss\n  where xss = inicios (n-1)\n\n-- Otra forma de definir inicios es\ninicios2 :: Int -> [[Int]]\ninicios2 n = sucInicios !! n\n  where sucInicios    = iterate siguiente [[]]\n        siguiente xss = map (0:) xss ++ map (1:) xss\n\n-- (esPascalCapicua xs) se verifica si xs es una lista de Pascal\n-- capic\u00faa. Por ejemplo, \n--    esPascalCapicua [1,0,1,1,0]  ==  True\n--    esPascalCapicua [1,0,1,1,1]  ==  False\nesPascalCapicua :: [Int] -> Bool\nesPascalCapicua xs =\n  xs == finalesTrianguloPascalBinario xs\n\n-- (finalesTrianguloPascalBinario xs) es la inversa de la lista de los\n-- finales del tri\u00e1ngulo binarios de xs. Por ejemplo,\n--    \u03bb> finalesTrianguloPascalBinario [1,0,1,1,1]\n--    [0,1,0,0,1]\nfinalesTrianguloPascalBinario :: [Int] -> [Int]\nfinalesTrianguloPascalBinario =\n  reverse . map last . trianguloPascalBinario\n\n-- 1\u00aa definici\u00f3n de nPascalCapicuas\n-- ================================\n\nnPascalCapicuas :: Int -> Integer\nnPascalCapicuas =\n  genericLength . pascalCapicuas\n\n-- 2\u00aa definici\u00f3n de nPascalCapicuas\n-- ================================\n\nnPascalCapicuas2 :: Int -> Integer\nnPascalCapicuas2 n =\n  2 ^ ((n + 1) `div` 2)  \n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nLa envidia de la virtud<br \/>\nhizo a Ca\u00edn criminal.<br \/>\n\u00a1Gloria a Ca\u00edn! Hoy el vicio<br \/>\nes lo que se envidia m\u00e1s.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Los tri\u00e1ngulos binarios de Pascal se formas a partir de una lista de ceros y unos usando las reglas del tri\u00e1ngulo de Pascal, donde cada uno de los n\u00fameros es suma m\u00f3dulo dos de los dos situados en diagonal por encima suyo. Por ejemplo, los tri\u00e1ngulos binarios de Pascal correspondientes a [1,0,1,1,1] y [1,0,1,1,0] son&#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":[4],"tags":[8,30,258,50,134,10,89,181,141,11,6,32,45,34,9],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4661"}],"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=4661"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4661\/revisions"}],"predecessor-version":[{"id":4696,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4661\/revisions\/4696"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4661"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4661"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4661"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}