{"id":1831,"date":"2012-01-11T20:05:30","date_gmt":"2012-01-11T20:05:30","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1831"},"modified":"2013-03-08T05:48:56","modified_gmt":"2013-03-08T05:48:56","slug":"i1m2011-resolucion-de-problemas-matematicos-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-resolucion-de-problemas-matematicos-con-haskell\/","title":{"rendered":"I1M2011: Resoluci\u00f3n de problemas matem\u00e1ticos con Haskell"},"content":{"rendered":"<p>La clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los 6 primeros ejercicios de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_12.hs\">12\u00aa relaci\u00f3n<\/a> en  la que se plantea la resoluci\u00f3n de distintos problemas matem\u00e1ticos. En concreto,<\/p>\n<ul>\n<li>el problema de Ullman sobre la existencia de subconjunto del tama\u00f1o dado y con su suma acotada,\n<li>las descomposiciones de un n\u00famero como suma de dos cuadrados,\n<li>el problema 145 del proyecto Euler,\n<li>el grafo de una funci\u00f3n sobre los elementos que cumplen una propiedad,\n<li>los n\u00fameros semiperfectos,\n<\/ul>\n<p>Adem\u00e1s, de los 2 primeros se presentan distintas definiciones y se compara su eficiencia.<\/p>\n<p>Estos ejercicios corresponden a los temas <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-5.pdf\">5<\/a>, <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-6.pdf\">6<\/a> y <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-7.pdf\">7<\/a>.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n \r\n--    ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\n-- tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k \r\n-- elementos cuya suma sea menor que t. Por ejemplo,\r\n--    ullman 9 3 [1..10] == True\r\n--    ullman 5 3 [1..10] == False\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa soluci\u00f3n (corta y eficiente)\r\nullman :: (Ord a, Num a) => a -> Int -> [a] -> Bool\r\nullman t k xs = sum (take k (sort xs)) < t\r\n\r\n-- 2\u00aa soluci\u00f3n (larga e ineficiente)\r\nullman2 :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\nullman2 t k xs = \r\n    [ys | ys <- subconjuntos xs, length ys == k, sum ys < t] \/= []\r\n\r\n-- (subconjuntos xs) es la lista de los subconjuntos de xs. Por \r\n-- ejemplo,\r\n--    subconjuntos \"bc\"  ==  [\"\",\"c\",\"b\",\"bc\"]\r\n--    subconjuntos \"abc\" ==  [\"\",\"c\",\"b\",\"bc\",\"a\",\"ac\",\"ab\",\"abc\"]\r\nsubconjuntos :: [a] -> [[a]]\r\nsubconjuntos [] = [[]]\r\nsubconjuntos (x:xs) = zss++[x:ys | ys <- zss]\r\n    where zss = subconjuntos xs\r\n\r\n-- Los siguientes ejemplos muestran la diferencia en la eficencia:\r\n--    *Main> ullman 9 3 [1..20]\r\n--    True\r\n--    (0.02 secs, 528380 bytes)\r\n--    *Main> ullman2 9 3 [1..20]\r\n--    True\r\n--    (4.08 secs, 135267904 bytes)\r\n--    *Main> ullman 9 3 [1..100]\r\n--    True\r\n--    (0.02 secs, 526360 bytes)\r\n--    *Main> ullman2 9 3 [1..100]\r\n--      C-c C-cInterrupted.\r\n--    Agotado\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]\r\n-- tal que (sumasDe2Cuadrados n) es la lista de los pares de n\u00fameros\r\n-- tales que la suma de sus cuadrados es n y el primer elemento del par\r\n-- es mayor o igual que el segundo. Por ejemplo,\r\n--    sumasDe2Cuadrados 25  ==  [(5,0),(4,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Primera definici\u00f3n:\r\nsumasDe2Cuadrados_1 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_1 n = \r\n    [(x,y) | x <- [n,n-1..0],\r\n             y <- [0..x],\r\n             x*x+y*y == n]\r\n\r\n-- Segunda definici\u00f3n:\r\nsumasDe2Cuadrados_2 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_2 n = \r\n    [(x,y) | x <- [a,a-1..0],\r\n             y <- [0..x],\r\n             x*x+y*y == n]\r\n    where a = ceiling (sqrt (fromIntegral n))\r\n\r\n-- Tercera definici\u00f3n:\r\nsumasDe2Cuadrados_3 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_3 n = aux (ceiling (sqrt (fromIntegral n))) 0 where\r\n    aux x y | x < y          = [] \r\n            | x*x + y*y <  n = aux x (y+1)\r\n            | x*x + y*y == n = (x,y) : aux (x-1) (y+1)\r\n            | otherwise      = aux (x-1) y\r\n\r\n-- Comparaci\u00f3n\r\n--    +----------+---------------+---------------+---------------+\r\n--    | n        | 1\u00aa definici\u00f3n | 2\u00aa definici\u00f3n | 3\u00aa definici\u00f3n |\r\n--    +----------+---------------+---------------+---------------+\r\n--    |      999 | 2.17 segs     |   0.02 segs   | 0.01 segs     |  \r\n--    | 48612265 |               | 140.38 segs   | 0.13 segs     |\r\n--    +----------+---------------+---------------+---------------+\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. (Basado en el problema 145 del Proyecto Euler). Se dice\r\n-- que un n\u00famero n es reversible si su \u00faltima cifra es distinta de 0 y\r\n-- la suma de n y el n\u00famero obtenido escribiendo las cifras de n en\r\n-- orden inverso es un n\u00famero que tiene todas sus cifras impares. Por\r\n-- ejemplo, 36 es reversible porque 36+63=99 tiene todas sus cifras\r\n-- impares, 409 es reversible porque 409+904=1313 tiene todas sus cifras\r\n-- impares,  243 no es reversible porque 243+342=585 no tiene todas sus\r\n-- cifras impares. \r\n-- Definir la funci\u00f3n \r\n--    reversiblesMenores :: Int -> Int\r\n-- tal que (reversiblesMenores n) es la cantidad de n\u00fameros reversibles\r\n-- menores que n. Por ejemplo,\r\n--    reversiblesMenores 10   == 0\r\n--    reversiblesMenores 100  == 20\r\n--    reversiblesMenores 1000 == 120\r\n-- ---------------------------------------------------------------------\r\n\r\nreversiblesMenores :: Int -> Int\r\nreversiblesMenores n = length [x | x <- [1..n-1], esReversible x]\r\n\r\n-- (esReversible n) se verifica si n es reversible; es decir, si su\r\n-- \u00faltima cifra es distinta de 0 y la suma de n y el n\u00famero obtenido\r\n-- escribiendo las cifras de n en orden inverso es un n\u00famero que tiene\r\n-- todas sus cifras impares. Por ejemplo,\r\n--    esReversible 36  == True\r\n--    esReversible 409 == True\r\nesReversible :: Int -> Bool\r\nesReversible n = rem n 10 \/= 0 && impares (cifras (n + (inverso n)))\r\n\r\n-- (impares xs) se verifica si xs es una lista de n\u00fameros impares. Por\r\n-- ejemplo, \r\n--    impares [3,5,1] == True\r\n--    impares [3,4,1] == False\r\nimpares :: [Int] -> Bool\r\nimpares xs = and [odd x | x <- xs]\r\n\r\n-- (inverso n) es el n\u00famero obtenido escribiendo las cifras de n en\r\n-- orden inverso. Por ejemplo,\r\n--    inverso 3034 == 4303\r\ninverso :: Int -> Int\r\ninverso n = read (reverse (show n))\r\n\r\n-- (cifras n) es la lista de las cifras del n\u00famero n. Por ejemplo,\r\n--    cifras 3034 == [3,0,3,4]\r\ncifras :: Int -> [Int]\r\ncifras n = [read [x] | x <- show n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir, usando funciones de orden superior, la funci\u00f3n\r\n--    grafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]\r\n-- tal que (grafoReducido f p xs) es la lista (sin repeticiones) de los\r\n-- pares formados por los elementos de xs que verifican el predicado p\r\n-- y sus im\u00e1genes. Por ejemplo, \r\n--    grafoReducido (^2) even [1..9]  ==  [(2,4),(4,16),(6,36),(8,64)]\r\n--    grafoReducido (+4) even (replicate 40 1) == []\r\n--    grafoReducido (*5) even (replicate 40 2) == [(2,10)]\r\n-- ---------------------------------------------------------------------\r\n\r\ngrafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]\r\ngrafoReducido f p xs = [(x,f x) | x <- nub xs, p x]\r\n\r\n-- -------------------------------------------------------------------\r\n-- Ejercicio 6.1. Un n\u00famero natural n se denomina semiperfecto si es la\r\n-- suma de algunos de sus divisores propios. Por ejemplo, 18 es\r\n-- semiperfecto ya que sus divisores son 1, 2, 3, 6, 9 y se cumple que\r\n-- 3+6+9=18.  \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    esSemiPerfecto :: Int -> Bool\r\n-- tal que (esSemiPerfecto n) se verifica si n es semiperfecto. Por\r\n-- ejemplo, \r\n--    esSemiPerfecto 18 == True\r\n--    esSemiPerfecto 9  == False\r\n--    esSemiPerfecto 24 == True\r\n-- ---------------------------------------------------------------------\r\n\r\nesSemiPerfecto :: Int -> Bool\r\nesSemiPerfecto n =\r\n    or [sum ys == n | ys <- subconjuntos (divisores n)]\r\n\r\n-- (divisores n) es la lista de los divisores propios de n. Por ejemplo,\r\n--    divisores 18 == [1,2,3,6,9]\r\ndivisores :: Int -> [Int]\r\ndivisores n = [x | x <- [1..n-1], mod n x == 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6.2. Definir la constante primerSemiPerfecto tal que su\r\n-- valor es el primer n\u00famero semiperfecto. \r\n-- ---------------------------------------------------------------------\r\n\r\nprimerSemiPerfecto :: Int\r\nprimerSemiPerfecto = head [n | n <- [1..], esSemiPerfecto n]\r\n\r\n-- La evaluaci\u00f3n es\r\n--    *Main> primerSemiPerfecto\r\n--    6\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6.3. Definir la funci\u00f3n \r\n--    semiPerfecto :: Int -> Int\r\n-- tal que (semiPerfecto n) es el n-\u00e9simo n\u00famero semiperfecto. Por\r\n-- ejemplo, \r\n--    semiPerfecto 1   == 6\r\n--    semiPerfecto 4   == 20\r\n--    semiPerfecto 100 == 414\r\n-- ---------------------------------------------------------------------\r\n\r\nsemiPerfecto :: Int -> Int\r\nsemiPerfecto n = semiPerfectos !! n\r\n\r\n-- semiPerfectos es la lista de los n\u00fameros semiPerfectos. Por ejemplo, \r\n--    take 4 semiPerfectos  ==  [6,12,18,20]\r\nsemiPerfectos = [n | n <- [1..], esSemiPerfecto n]\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los 6 primeros ejercicios de la 12\u00aa relaci\u00f3n en la que se plantea la resoluci\u00f3n de distintos problemas matem\u00e1ticos. En concreto, el problema de Ullman sobre la existencia de subconjunto del tama\u00f1o dado y con su suma&#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":[186],"tags":[295],"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\/1831"}],"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=1831"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1831\/revisions"}],"predecessor-version":[{"id":2871,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1831\/revisions\/2871"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1831"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1831"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1831"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}