{"id":3103,"date":"2013-03-07T17:02:40","date_gmt":"2013-03-07T17:02:40","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3103"},"modified":"2013-03-15T15:39:48","modified_gmt":"2013-03-15T15:39:48","slug":"i1m2012-ejercicios-de-evaluacion-perezosa-y-listas-infinitas-3","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-ejercicios-de-evaluacion-perezosa-y-listas-infinitas-3\/","title":{"rendered":"I1M2012: Ejercicios de evaluaci\u00f3n perezosa y listas infinitas (3)"},"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 comentando soluciones de los sguientes ejercicios de la relaci\u00f3n 17 (sobre evaluaci\u00f3n perezosa y listas infinitas):<\/p>\n<ul>\n<li>8. Menor n\u00famero triangular con m\u00e1s de n divisores.\n<li>9. N\u00fameros primos consecutivos con d\u00edgitos con igual media.\n<li>10. Decisi\u00f3n de pertenencia al rango de una funci\u00f3n creciente\n<li>11. Pares ordenados por posici\u00f3n.\n<li>12. Aplicaci\u00f3n iterada de una funci\u00f3n.\n<li>13. La bicicleta de Turing.\n<li>14. La sucesi\u00f3n de Golomb.\n<\/ul>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. (Problema 12 del Proyecto Euler) La sucesi\u00f3n de los\r\n-- n\u00fameros triangulares se obtiene sumando los n\u00fameros naturales. As\u00ed,\r\n-- el 7\u00ba n\u00famero triangular es  \r\n--    1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. \r\n-- Los primeros 10 n\u00fameros triangulares son\r\n--    1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\r\n-- Los divisores de los primeros 7 n\u00fameros triangulares son:\r\n--     1: 1\r\n--     3: 1,3\r\n--     6: 1,2,3,6\r\n--    10: 1,2,5,10\r\n--    15: 1,3,5,15\r\n--    21: 1,3,7,21\r\n--    28: 1,2,4,7,14,28\r\n-- Como se puede observar, 28 es el menor n\u00famero triangular con m\u00e1s de 5\r\n-- divisores. \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    euler12 :: Int -> Integer\r\n-- tal que (euler12 n) es el menor n\u00famero triangular con m\u00e1s de n\r\n-- divisores. Por ejemplo,\r\n--    euler12 5  ==  28\r\n-- ---------------------------------------------------------------------\r\n\r\neuler12 :: Int -> Integer\r\neuler12 n = head [x | x <- triangulares, nDivisores x > n]\r\n\r\n-- triangulares es la lista de los n\u00fameros triangulares\r\n--    take 10 triangulares  ==  [1,3,6,10,15,21,28,36,45,55]\r\ntriangulares :: [Integer]\r\ntriangulares = 1:[x+y | (x,y) <- zip [2..] triangulares]\r\n\r\n-- Otra definici\u00f3n de triangulares es\r\ntriangulares' :: [Integer]\r\ntriangulares' = scanl (+) 1 [2..]\r\n\r\n-- (divisores n) es la lista de los divisores de n. Por ejemplo,\r\n--    divisores 28  ==  [1,2,4,7,14,28]\r\ndivisores :: Integer -> [Integer]\r\ndivisores x = [y | y <- [1..x], mod x y == 0]\r\n\r\n-- (nDivisores n) es el n\u00famero de los divisores de n. Por ejemplo,\r\n--    nDivisores 28  ==  6\r\nnDivisores :: Integer -> Int\r\nnDivisores x = length (divisores x)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9.1. Dos n\u00fameros son equivalentes si la media de sus cifras\r\n-- son iguales. Por ejemplo, 3205 y 41 son equvalentes ya que \r\n-- (3+2+0+5)\/4 = (4+1)\/2. Definir la funci\u00f3n \r\n--    equivalentes :: Int -> Int -> Bool\r\n-- tal que (equivalentes x y) se verifica si los n\u00fameros x e y son\r\n-- equivalentes. Por ejemplo,\r\n--    equivalentes 3205 41  ==  True\r\n--    equivalentes 3205 25  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nequivalentes :: Int -> Int -> Bool\r\nequivalentes x y = media (cifras x) == media (cifras y)\r\n\r\n-- (cifras n) es la lista de las cifras de n. Por ejemplo,\r\n--    cifras 3205  ==  [3,2,0,5]\r\ncifras :: Int -> [Int]\r\ncifras n = [read [y] | y <- show n]\r\n\r\n-- (media xs) es la media de la lista xs. Por ejemplo,\r\n--    media [3,2,0,5]  ==  2.5\r\nmedia :: [Int] -> Float\r\nmedia xs = (fromIntegral (sum xs)) \/ (fromIntegral (length xs))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9.2. Definir la funci\u00f3n\r\n--    relacionados :: (a -> a -> Bool) -> [a] -> Bool\r\n-- tal que (relacionados r xs) se verifica si para todo par (x,y) de\r\n-- elementos consecutivos de xs se cumple la relaci\u00f3n r. Por ejemplo,\r\n--    relacionados (<) [2,3,7,9]                ==  True\r\n--    relacionados (<) [2,3,1,9]                ==  False\r\n--    relacionados equivalentes [3205,50,5014]  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nrelacionados :: (a -> a -> Bool) -> [a] -> Bool\r\nrelacionados r (x:y:zs) = (r x y) && relacionados r (y:zs)\r\nrelacionados _ _ = True\r\n\r\n-- Una definici\u00f3n alternativa es\r\nrelacionados' :: (a -> a -> Bool) -> [a] -> Bool\r\nrelacionados' r xs = and [r x y | (x,y) <- zip xs (tail xs)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9.3. Definir la funci\u00f3n\r\n--    primosEquivalentes :: Int -> [[Int]]\r\n-- tal que (primosEquivalentes n) es la lista de las sucesiones de n\r\n-- n\u00fameros primos consecutivos equivalentes. Por ejemplo,\r\n--    take 2 (primosEquivalentes 2)  ==  [[523,541],[1069,1087]]\r\n--    head (primosEquivalentes 3)    ==  [22193,22229,22247]\r\n-- ---------------------------------------------------------------------\r\n\r\nprimosEquivalentes :: Int -> [[Int]]\r\nprimosEquivalentes n = aux primos\r\n    where aux (x:xs) | relacionados equivalentes ys = ys : aux xs\r\n                     | otherwise                    = aux xs\r\n                     where ys = take n (x:xs)               \r\n\r\nprimos :: Integral a => [a]\r\nprimos = criba [2..]\r\n    where criba []     = []\r\n          criba (n:ns) = n : criba (elimina n ns)\r\n          elimina n xs = [x | x <- xs, x `mod` n \/= 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    perteneceRango:: Int -> (Int -> Int) -> Bool\r\n-- tal que (perteneceRango x f) se verifica si x pertenece al rango de\r\n-- la funci\u00f3n f, suponiendo que f es una funci\u00f3n creciente cuyo dominio\r\n-- es el conjunto de los n\u00fameros naturales. Por ejemplo,\r\n--    perteneceRango 5 (\\x -> 2*x+1)     ==  True\r\n--    perteneceRango 1234 (\\x -> 2*x+1)  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nperteneceRango:: Int -> (Int -> Int) -> Bool\r\nperteneceRango y f = elem y (takeWhile (<=y) (imagenes f))\r\n    where imagenes f = [f x | x <- [0..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11.1. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    paresOrdenados :: [a] -> [(a,a)]\r\n-- tal que (paresOrdenados xs) es la lista de todos los pares de\r\n-- elementos (x,y) de xs, tales que x ocurren en xs antes que y. Por\r\n-- ejemplo,  \r\n--    paresOrdenados [3,2,5,4] == [(3,2),(3,5),(3,4),(2,5),(2,4),(5,4)]\r\n--    paresOrdenados [3,2,5,3] == [(3,2),(3,5),(3,3),(2,5),(2,3),(5,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\nparesOrdenados :: [a] -> [(a,a)]\r\nparesOrdenados []     = []\r\nparesOrdenados (x:xs) = [(x,y) | y <- xs] ++ paresOrdenados xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11.2. Definir, por plegado, la funci\u00f3n\r\n--    paresOrdenados2 :: [a] -> [(a,a)]\r\n-- tal que (paresOrdenados2 xs) es la lista de todos los pares de\r\n-- elementos (x,y) de xs, tales que x ocurren en xs antes que y. Por\r\n-- ejemplo,  \r\n--    paresOrdenados2 [3,2,5,4] == [(3,2),(3,5),(3,4),(2,5),(2,4),(5,4)]\r\n--    paresOrdenados2 [3,2,5,3] == [(3,2),(3,5),(3,3),(2,5),(2,3),(5,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\nparesOrdenados2 :: [a] -> [(a,a)]\r\nparesOrdenados2 [] = []\r\nparesOrdenados2 (x:xs) = \r\n    foldr (\\y ac -> (x,y):ac) (paresOrdenados2 xs) xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11.3. Definir, usando repeat, la funci\u00f3n\r\n--    paresOrdenados3 :: [a] -> [(a,a)]\r\n-- tal que (paresOrdenados3 xs) es la lista de todos los pares de\r\n-- elementos (x,y) de xs, tales que x ocurren en xs antes que y. Por\r\n-- ejemplo,  \r\n--    paresOrdenados3 [3,2,5,4] == [(3,2),(3,5),(3,4),(2,5),(2,4),(5,4)]\r\n--    paresOrdenados3 [3,2,5,3] == [(3,2),(3,5),(3,3),(2,5),(2,3),(5,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\nparesOrdenados3 :: [a] -> [(a,a)]\r\nparesOrdenados3 []     = []\r\nparesOrdenados3 (x:xs) = zip (repeat x) xs ++ paresOrdenados3 xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12.1. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    potenciaFunc :: Int -> (a -> a) -> a -> a\r\n-- tal que (potenciaFunc n f x) es el resultado de aplicar n veces la\r\n-- funci\u00f3n f a x. Por ejemplo,\r\n--    potenciaFunc 3 (*10) 5  ==  5000\r\n--    potenciaFunc 4 (+10) 5  ==  45\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciaFunc :: Int -> (a -> a) -> a -> a\r\npotenciaFunc 0 _ x = x\r\npotenciaFunc n f x = potenciaFunc (n-1) f (f x)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12.2. Definir, sin recursi\u00f3n, la funci\u00f3n\r\n--    potenciaFunc2 :: Int -> (a -> a) -> a -> a\r\n-- tal que (potenciaFunc2 n f x) es el resultado de aplicar n veces la\r\n-- funci\u00f3n f a x. Por ejemplo,\r\n--    potenciaFunc2 3 (*10) 5  ==  5000\r\n--    potenciaFunc2 4 (+10) 5  ==  45\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciaFunc2 :: Int -> (a -> a) -> a -> a\r\npotenciaFunc2 n f x = last (take (n+1) (iterate f x)) \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13.1. Cuentan que Alan Turing ten\u00eda una bicicleta vieja,\r\n-- que ten\u00eda una cadena con un eslab\u00f3n d\u00e9bil y adem\u00e1s uno de los radios\r\n-- de la rueda estaba doblado. Cuando el radio doblado coincid\u00eda con el\r\n-- eslab\u00f3n d\u00e9bil, entonces la cadena se romp\u00eda.   \r\n--\r\n-- La bicicleta se identifica por los par\u00e1metros (i,d,n) donde \r\n-- * i es el n\u00famero del eslab\u00f3n que coincide con el radio doblado al\r\n--   empezar a andar,\r\n-- * d es el n\u00famero de eslabones que se desplaza la cadena en cada\r\n--   vuelta de la rueda y  \r\n-- * n es el n\u00famero de eslabones de la cadena (el n\u00famero n es el d\u00e9bil).\r\n-- Si i=2 y d=7 y n=25, entonces la lista con el n\u00famero de eslab\u00f3n que \r\n-- toca el radio doblado en cada vuelta es \r\n--    [2,9,16,23,5,12,19,1,8,15,22,4,11,18,0,7,14,21,3,10,17,24,6,...\r\n-- Con lo que la cadena se rompe en la vuelta n\u00famero 14.\r\n-- \r\n-- Definir la funci\u00f3n\r\n--    eslabones :: Int -> Int -> Int -> [Int]\r\n-- tal que (eslabones i d n) es la lista con los n\u00fameros de eslabones \r\n-- que tocan el radio doblado en cada vuelta en una bicicleta de tipo \r\n-- (i,d,n). Por ejemplo, \r\n--    take 10 (eslabones 2 7 25)  ==  [2,9,16,23,5,12,19,1,8,15]\r\n-- ---------------------------------------------------------------------\r\n\r\neslabones :: Int -> Int -> Int -> [Int]\r\neslabones i d n = [(i+d*j) `mod` n | j <- [0..]]\r\n\r\n-- 2\u00aa definici\u00f3n (con iterate):\r\neslabones2 :: Int -> Int -> Int -> [Int]\r\neslabones2 i d n = map (\\x-> mod x n) (iterate (+d) i)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13.2. Definir la funci\u00f3n\r\n--    numeroVueltas :: Int -> Int -> Int -> Int \r\n-- tal que (numeroVueltas i d n) es el n\u00famero de vueltas que pasar\u00e1n \r\n-- hasta que la cadena se rompa en una bicicleta de tipo (i,d,n). Por \r\n-- ejemplo,\r\n--    numeroVueltas 2 7 25  ==  14\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroVueltas :: Int -> Int -> Int -> Int\r\nnumeroVueltas i d n = length (takeWhile (\/=0) (eslabones i d n)) \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.1. [Basado en el problema 341 del proyecto Euler]. La\r\n-- sucesi\u00f3n de Golomb {G(n)} es una sucesi\u00f3n auto descriptiva: es la\r\n-- \u00fanica sucesi\u00f3n no decreciente de n\u00fameros naturales tal que el n\u00famero\r\n-- n aparece G(n) veces en la sucesi\u00f3n. Los valores de G(n) para los\r\n-- primeros n\u00fameros son los siguientes:\r\n--    n       1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...\r\n--    G(n)    1 2 2 3 3 4 4 4 5  5  5  6  6  6  6 ...\r\n-- En los apartados de este ejercicio se definir\u00e1 una funci\u00f3n para\r\n-- calcular los t\u00e9rminos de la sucesi\u00f3n de Golomb. \r\n-- \r\n-- Definir la funci\u00f3n\r\n--    golomb :: Int -> Int\r\n-- tal que (golomb n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Golomb. \r\n-- Por ejemplo,\r\n--    golomb 5  ==  3\r\n--    golomb 9  ==  5\r\n-- Indicaci\u00f3n: Se puede usar la funci\u00f3n sucGolomb del apartado 2.\r\n-- ---------------------------------------------------------------------\r\n\r\ngolomb :: Int -> Int\r\ngolomb n = sucGolomb !! (n-1)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.2. Definir la funci\u00f3n\r\n--    sucGolomb :: [Int]\r\n-- tal que sucGolomb es la lista de los t\u00e9rminos de la sucesi\u00f3n de\r\n-- Golomb. Por ejemplo,\r\n--    take 15 sucGolomb  ==  [1,2,2,3,3,4,4,4,5,5,5,6,6,6,6]\r\n-- Indicaci\u00f3n: Se puede usar la funci\u00f3n subSucGolomb del apartado 3.\r\n-- ---------------------------------------------------------------------\r\n\r\nsucGolomb :: [Int]\r\nsucGolomb = subSucGolomb 1\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14.3. Definir la funci\u00f3n\r\n--    subSucGolomb :: Int -> [Int]\r\n-- tal que (subSucGolomb x) es la lista de los t\u00e9rminos de la sucesi\u00f3n\r\n-- de Golomb a partir de la primera ocurrencia de x. Por ejemplo,\r\n--    take 10 (subSucGolomb 4)  ==  [4,4,4,5,5,5,6,6,6,6]\r\n-- Indicaci\u00f3n: Se puede usar la funci\u00f3n golomb del apartado 1.\r\n-- ---------------------------------------------------------------------\r\n\r\nsubSucGolomb :: Int -> [Int]\r\nsubSucGolomb 1 = [1] ++ subSucGolomb 2\r\nsubSucGolomb 2 = [2,2] ++ subSucGolomb 3\r\nsubSucGolomb x = (replicate (golomb x) x) ++ subSucGolomb (x+1) \r\n\r\n-- Nota: La sucesi\u00f3n de Golomb puede definirse de forma m\u00e1s compacta\r\n-- como se muestra a continuaci\u00f3n.\r\nsucGolomb' :: [Int]\r\nsucGolomb' = 1 : 2 : 2 : g 3\r\n    where g x      = replicate (golomb x) x ++ g (x+1) \r\n          golomb n = sucGolomb !! (n-1)\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 comentando soluciones de los sguientes ejercicios de la relaci\u00f3n 17 (sobre evaluaci\u00f3n perezosa y listas infinitas): 8. Menor n\u00famero triangular con m\u00e1s de n divisores. 9. N\u00fameros primos consecutivos con d\u00edgitos con igual media. 10. Decisi\u00f3n de pertenencia al rango de&#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],"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\/3103"}],"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=3103"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3103\/revisions"}],"predecessor-version":[{"id":3120,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3103\/revisions\/3120"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3103"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3103"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3103"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}