{"id":2405,"date":"2012-12-11T17:45:23","date_gmt":"2012-12-11T17:45:23","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2405"},"modified":"2013-03-08T05:47:36","modified_gmt":"2013-03-08T05:47:36","slug":"i1m2012-suma-de-numeros-monotonos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-suma-de-numeros-monotonos\/","title":{"rendered":"I1M2012: Suma de n\u00fameros mon\u00f3tonos"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado la soluci\u00f3n con Haskell de un problema propuesto para la Olimpiada Internacional de Matem\u00e1ticas de 1982 cuyo enunciado es<\/p>\n<blockquote><p>\nCalcular la suma de todos los enteros positivos cuyos d\u00edgitos forman una sucesi\u00f3n estrictamente creciente o estrictamente decreciente.\n<\/p><\/blockquote>\n<p>Lo resolveremos generando las listas de todos los enteros positivos cuyos d\u00edgitos forman una sucesi\u00f3n estrictamente mon\u00f3tona. Para ello nos basaremos en las listas de d\u00edgitos que forman una sucesi\u00f3n estrictamente mon\u00f3tona. <\/p>\n<p>Comenzamos con los decrecientes:<\/p>\n<ul>\n<li> (listasDecrecientesDesde n) es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es n. Por ejemplo,<br \/>\n   ghci> listasDecrecientesDesde 3<br \/>\n   [[3],[3,2],[3,2,1],[3,2,1,0],[3,2,0],[3,1],[3,1,0],[3,0]]<\/p>\n<pre lang=\"haskell\">\r\nlistasDecrecientesDesde :: Integer -> [[Integer]]\r\nlistasDecrecientesDesde 0 = [[0]]\r\nlistasDecrecientesDesde n =\r\n    [n] : [n:ys | m <- [n-1,n-2..0], ys <- listasDecrecientesDesde m]\r\n<\/pre>\n<li> listasDecrecientes es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es un d\u00edgito. Por ejemplo,<br \/>\n   ghci> take 10 listasDecrecientes<br \/>\n   [[0],[1],[1,0],[2],[2,1],[2,1,0],[2,0],[3],[3,2],[3,2,1]]<\/p>\n<pre lang=\"haskell\">\r\nlistasDecrecientes :: [[Integer]]\r\nlistasDecrecientes = \r\n    concat [listasDecrecientesDesde n | n <- [0..9]]\r\n<\/pre>\n<li> (listaNumero xs) es el n\u00famero correspondiente a la lista de d\u00edgitos xs. Por ejemplo,<br \/>\n   listaNumero [3,2,5]  ==  325<\/p>\n<pre lang=\"haskell\">\r\nlistaNumero :: [Integer] -> Integer\r\nlistaNumero xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]\r\n<\/pre>\n<li> numerosDecrecientes es la lista de los enteros positivos cuyos d\u00edgitos forman una sucesi\u00f3n  estrictamente decreciente. Por ejemplo,<br \/>\n   ghci> take 17 numerosDecrecientes<br \/>\n   [0,1,10,2,21,210,20,3,32,321,3210,320,31,310,30,4,43]<\/p>\n<pre lang=\"haskell\">\r\nnumerosDecrecientes :: [Integer]\r\nnumerosDecrecientes = [listaNumero xs | xs <- listasDecrecientes]\r\n<\/pre>\n<p>An\u00e1logamente se construyen los crecientes:<\/p>\n<li> (listasCrecientesDesde n) es la lista de las sucesiones estrictamente crecientes cuyo primer elemento es n. Por ejemplo,<br \/>\n   ghci> listasCrecientesDesde 6<br \/>\n   [[6],[6,7],[6,7,8],[6,7,8,9],[6,7,9],[6,8],[6,8,9],[6,9]]<\/p>\n<pre lang=\"haskell\">\r\nlistasCrecientesDesde :: Integer -> [[Integer]]\r\nlistasCrecientesDesde 9 = [[9]]\r\nlistasCrecientesDesde n =\r\n    [n] : [n:ys | m <- [n+1..9], ys <- listasCrecientesDesde m]\r\n<\/pre>\n<li> listascrecientes es la lista de las sucesiones estrictamente crecientes cuyo primer elemento es un d\u00edgito. Por ejemplo,<br \/>\n   ghci> take 5 listasCrecientes<br \/>\n   [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]]<\/p>\n<pre lang=\"haskell\">\r\nlistasCrecientes :: [[Integer]]\r\nlistasCrecientes = \r\n    concat [listasCrecientesDesde n | n <- [1..9]]\r\n<\/pre>\n<li> numerosCrecientes es la lista de los enteros positivos cuyos d\u00edgitos forman una sucesi\u00f3n estrictamente creciente. Por ejemplo,<br \/>\n   ghci> take 5 numerosCrecientes<br \/>\n   [1,12,123,1234,12345]<\/p>\n<pre lang=\"haskell\">\r\nnumerosCrecientes :: [Integer]\r\nnumerosCrecientes = [listaNumero xs | xs <- listasCrecientes]\r\n<\/pre>\n<p>Con las definiciones anteriores la soluci\u00f3n es inmediata: <\/p>\n<pre lang=\"haskell\">\r\nsolucion :: Integer\r\nsolucion = \r\n    sum (numerosCrecientes ++ numerosDecrecientes) - sum [1..9]\r\n<\/pre>\n<p>El c\u00e1lculo de la soluci\u00f3n es<\/p>\n<pre lang=\"text\">\r\nghci> solucion\r\n25617208995\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado la soluci\u00f3n con Haskell de un problema propuesto para la Olimpiada Internacional de Matem\u00e1ticas de 1982 cuyo enunciado es Calcular la suma de todos los enteros positivos cuyos d\u00edgitos forman una sucesi\u00f3n estrictamente creciente o estrictamente decreciente. Lo resolveremos generando&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[1],"tags":[270,298,200],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2405"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=2405"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2405\/revisions"}],"predecessor-version":[{"id":2725,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2405\/revisions\/2725"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2405"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2405"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2405"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}