{"id":1162,"date":"2011-01-24T07:41:05","date_gmt":"2011-01-24T07:41:05","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1162"},"modified":"2013-03-08T05:50:03","modified_gmt":"2013-03-08T05:50:03","slug":"i1m2010-ejercicios-de-haskell-relaciones-14-y-15","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-ejercicios-de-haskell-relaciones-14-y-15\/","title":{"rendered":"I1M2010: Ejercicios de Haskell (relaciones 14 y 15)"},"content":{"rendered":"

En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos continuado con la resoluci\u00f3n de los ejercicios de la 14\u00aa relaci\u00f3n<\/a> (que comenzamos en la clase del d\u00eda 17<\/a>) y hemos comentado las soluciones de la 15\u00aa relaci\u00f3n<\/a>.<\/p>\n

Las soluciones de los restantes de la relaci\u00f3n 14 son
\n<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n\r\n--    sumaCifrasLista :: [Int] -> Int\r\n-- tal que (sumaCifrasLista xs) es la suma de las cifras de la lista de\r\n-- n\u00fameros xs. Por ejemplo, \r\n--    sumaCifrasLista [254, 61]  ==  18\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Por comprensi\u00f3n:\r\nsumaCifrasLista :: [Int] -> Int\r\nsumaCifrasLista xs = sum [sumaCifras y | y <- xs]\r\n\r\n-- Por recursi\u00f3n:\r\nsumaCifrasListaR :: [Int] -> Int\r\nsumaCifrasListaR [] = 0\r\nsumaCifrasListaR (x:xs) = sumaCifras x + sumaCifrasListaR xs\r\n\r\n-- Por plegado:\r\nsumaCifrasListaP :: [Int] -> Int\r\nsumaCifrasListaP = foldr f 0\r\n                   where f x y = sumaCifras x + y\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir la funci\u00f3n\r\n--    propiedad2 :: Int -> Bool\r\n-- tal que (propiedad2 n) se verifica si n puede expresarse como suma de\r\n-- 11 primos consecutivos y la suma de las cifras de los 11 sumandos es\r\n-- un n\u00famero primo. Por ejemplo,\r\n--    propiedad2 2011  ==  True\r\n--    propiedad2 2000  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\npropiedad2 :: Int -> Bool\r\npropiedad2 n = [xs | xs <- primosConsecutivosConSuma n, \r\n                     length xs == 11,\r\n                     esPrimo (sumaCifrasLista xs)] \r\n               \/= []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Calcular el primer a\u00f1o que cumple la propiedad1 y la\r\n-- propiedad2. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> head [n | n <- [1..], propiedad1 n, propiedad2 n]\r\n--    2011\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Definir la funci\u00f3n\r\n--    propiedad3 :: Int -> Bool\r\n-- tal que (propiedad3 n) se verifica si n puede expresarse como suma de\r\n-- tantos n\u00fameros consecutivos como indican sus dos \u00faltimas cifras. Por\r\n-- ejemplo, \r\n--    propiedad3 2011  ==  True\r\n--    propiedad3 2000  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\npropiedad3 :: Int -> Bool\r\npropiedad3 n = [xs | xs <- primosConsecutivosConSuma n,\r\n                     length xs == a]\r\n               \/= []\r\n    where a = mod n 100\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Calcular el primer a\u00f1o que cumple la propiedad1 y la\r\n-- propiedad3. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> head [n | n <- [1..], propiedad1 n, propiedad3 n]\r\n--    2011\r\n\r\n-- Hemos comprobado que 2011 es el menor n\u00famero que cumple las\r\n-- propiedades 1 y 1 y tambi\u00e9n es el menor n\u00famero que cumple las\r\n-- propiedades 1 y 3.\r\n<\/pre>\n
Las soluciones de los ejercicios de la relaci\u00f3n 15 son<\/p>\n
\r\n-- I1M 2010-11: Relaci\u00f3n 15 (18 de enero de 2010)\r\n-- Departamento de Ciencias de la Computaci\u00f3n e I.A.\r\n-- Universidad de Sevilla\r\n-- =====================================================================\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                  \r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir, usando takeWhile y map, la funci\u00f3n\r\n--    potenciasMenores :: Int -> Int -> [Int]\r\n-- tal que (potenciasMenores x y) es la lista de las potencias de x\r\n-- menores que y. Por ejemplo,\r\n--    potenciasMenores 2 1000  ==  [2,4,8,16,32,64,128,256,512]\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciasMenores :: Int -> Int -> [Int]\r\npotenciasMenores x y = takeWhile ( [a]\r\n-- tal que (repite x) es la lista infinita cuyos elementos son x. Por\r\n-- ejemplo, \r\n--    repite 5           == [5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,...\r\n--    take 3 (repite 5)  ==  [5,5,5]\r\n-- Nota: La funci\u00f3n repite es equivalente a la funci\u00f3n repeat definida en\r\n-- el preludio de Haskell.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Por recursi\u00f3n:\r\nrepite :: a -> [a]\r\nrepite x = x : repite x\r\n\r\n-- Por comprensi\u00f3n:\r\nrepite' x = [x | _ <- [1..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir, por recursi\u00f3n y por comprensi\u00f3n, la funci\u00f3n \r\n--    repiteFinita :: Int-> a -> [a]\r\n-- tal que (repite n x) es la lista con n elementos iguales a x. Por\r\n-- ejemplo, \r\n--    repiteFinita 3 5  ==  [5,5,5]\r\n-- Nota: La funci\u00f3n repite es equivalente a la funci\u00f3n replicate definida\r\n-- en el preludio de Haskell.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Por recursi\u00f3n:\r\nrepiteFinita :: Int -> a -> [a]\r\nrepiteFinita n x = take n (repite x)\r\n\r\n-- Por comprensi\u00f3n:\r\nrepiteFinita' :: Int -> a -> [a]\r\nrepiteFinita' n x = [x | _ <- [1..n]]\r\n\r\n-- Tambi\u00e9n se puede definir usando repite\r\nrepiteFinita2 :: Int -> a -> [a]\r\nrepiteFinita2 n x = take n (repite x)\r\n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Se considera la funci\u00f3n\r\n--    eco :: String -> String\r\n-- tal que (eco xs) es la cadena obtenida a partir de la cadena xs\r\n-- repitiendo cada elemento tantas veces como indica su posici\u00f3n: el\r\n-- primer elemento se repite 1 vez, el segundo 2 veces y as\u00ed\r\n-- sucesivamente. Por ejemplo, \r\n--    eco \"abcd\"  ==  \"abbcccdddd\"\r\n-- 1. Escribir una definici\u00f3n 'no recursiva' de la funci\u00f3n eco.\r\n-- 2. Escribir una definici\u00f3n 'recursiva' de la funci\u00f3n eco.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Una definici\u00f3n no recursiva es\r\necoNR :: String -> String\r\necoNR xs = concat [replicate i x | (i,x) <- zip [1..] xs]\r\n\r\n-- Una definici\u00f3n recursiva es\r\necoR :: String -> String\r\necoR xs =  \r\n    ecoRaux 1 0 xs\r\n    where\r\n      ecoRaux i n []  =  []\r\n      ecoRaux i n (c:cs) | i <= n     =  ecoRaux (i+1) 0 cs\r\n                         | otherwise  =  c : (ecoRaux i (n+1) (c:cs))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    itera :: (a -> a) -> a -> [a]\r\n-- tal que (itera f x) es la lista cuyo primer elemento es x y los\r\n-- siguientes elementos se calculan aplicando la funci\u00f3n f al elemento\r\n-- anterior. Por ejemplo, \r\n--    Main> itera (+1) 3\r\n--    [3,4,5,6,7,8,9,10,11,12,{Interrupted!}\r\n--    Main> itera (*2) 1\r\n--    [1,2,4,8,16,32,64,{Interrupted!}\r\n--    Main> itera (`div` 10) 1972\r\n--    [1972,197,19,1,0,0,0,0,0,0,{Interrupted!}\r\n-- Nota: La funci\u00f3n repite es equivalente a la funci\u00f3n iterate definida\r\n-- en el preludio de Haskell.\r\n-- ---------------------------------------------------------------------\r\n\r\nitera :: (a -> a) -> a -> [a]\r\nitera f x = x : itera f (f x)\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 6, Definir la funci\u00f3n\r\n--    agrupa :: Int -> [a] -> [[a]]\r\n-- tal que (agrupa n xs) es la lista de las sublistas de longitud n de\r\n-- la lista xs. Por ejemplo, \r\n--    Main> agrupa 2 [3,1,5,8,2,7]\r\n--    [[3,1],[5,8],[2,7]]\r\n--    Main> agrupa 2 [3,1,5,8,2,7,9] \r\n--    [[3,1],[5,8],[2,7],[9]]\r\n--    Main> agrupa 5 \"todo necio confunde valor y precio\"\r\n--    [\"todo \",\"necio\",\" conf\",\"unde \",\"valor\",\" y pr\",\"ecio\"]\r\n-- ---------------------------------------------------------------------------- \r\n\r\n-- Una definici\u00f3n no recursiva es\r\nagrupa :: Int -> [a] -> [[a]]\r\nagrupa n = takeWhile (not . null)\r\n         . map (take n)\r\n         . iterate (drop n)\r\n\r\n-- Puede verse su funcionamiento en el siguiente ejemplo,\r\n--    iterate (drop 2) [5..10]  \r\n--    ==> [[5,6,7,8,9,10],[7,8,9,10],[9,10],[],[],...\r\n--    map (take 2) (iterate (drop 2) [5..10])\r\n--    ==> [[5,6],[7,8],[9,10],[],[],[],[],...\r\n--    takeWhile (not . null) (map (take 2) (iterate (drop 2) [5..10]))\r\n--    ==> [[5,6],[7,8],[9,10]]\r\n\r\n-- Una definici\u00f3n recursiva de agrupa es\r\nagrupa' :: Int -> [a] -> [[a]]\r\nagrupa' n [] = []\r\nagrupa' n xs = take n xs : agrupa' n (drop n xs)\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 7. Definir, y comprobar, con QuickCheck las dos propiedades\r\n-- que caracterizan a la funci\u00f3n agrupa:\r\n-- * todos los grupos tienen que tener la longitud determinada (salvo el\r\n--   \u00faltimo que puede tener una longitud menor) y\r\n-- * combinando todos los grupos se obtiene la lista inicial.\r\n-- ---------------------------------------------------------------------------- \r\n\r\n-- La primera propiedad es\r\nprop_AgrupaLongitud :: Int -> [Int] -> Property\r\nprop_AgrupaLongitud n xs =\r\n    n > 0 && not (null gs) ==>\r\n      and [length g == n | g <- init gs] &&\r\n      0 < length (last gs) && length (last gs) <= n\r\n    where\r\n      gs = agrupa n xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    Main> quickCheck prop_AgrupaLongitud\r\n--    OK, passed 100 tests.\r\n\r\n-- La segunda propiedad es\r\nprop_AgrupaCombina :: Int -> [Int] -> Property\r\nprop_AgrupaCombina n xs =\r\n    n > 0 ==>\r\n      concat (agrupa n xs) == xs \r\n\r\n-- La comprobaci\u00f3n es\r\n--    Main> quickCheck prop_AgrupaCombina\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Sea la siguiente operaci\u00f3n, aplicable a cualquier n\u00famero entero\r\n-- positivo:  \r\n--    * Si el n\u00famero es par, se divide entre 2.\r\n--    * Si el n\u00famero es impar, se multiplica por 3 y se suma 1.\r\n-- Dado un n\u00famero cualquiera, podemos considerar su \u00f3rbita, es decir,\r\n-- las im\u00e1genes sucesivas al iterar la funci\u00f3n. Por ejemplo, la \u00f3rbita\r\n-- de 13 es\r\n--    13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...\r\n-- Si observamos este ejemplo, la \u00f3rbita de 13 es peri\u00f3dica, es decir,\r\n-- se repite indefinidamente a partir de un momento dado). La conjetura\r\n-- de Collatz dice que siempre alcanzaremos el 1 para cualquier n\u00famero\r\n-- con el que comencemos. Ejemplos:  \r\n--    * Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.\r\n--    * Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20,\r\n--      10, 5, 16, 8, 4, 2, 1. \r\n--    * Empezando en n = 27, la sucesi\u00f3n tiene 112 pasos, llegando hasta\r\n--      9232 antes de descender a 1:  27, 82, 41, 124, 62, 31, 94, 47,\r\n--      142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274,\r\n--      137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263,\r\n--      790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502,\r\n--      251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958,\r\n--      479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644,\r\n--      1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308,\r\n--      1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122,\r\n--      61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5,\r\n--      16, 8, 4, 2, 1. \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    siguiente :: Integer -> Integer\r\n-- tal que (siguiente n) es el siguiente de n en la sucesi\u00f3n de\r\n-- Collatz. Por ejemplo,\r\n--    siguiente 13  ==  40\r\n--    siguiente 40  ==  20\r\n-- ---------------------------------------------------------------------\r\n\r\nsiguiente n | even n    = n `div` 2\r\n            | otherwise = 3*n+1\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    collatz :: Integer -> [Integer]\r\n-- tal que (collatz n) es la \u00f3rbita de Collatz d n hasta alcanzar el\r\n-- 1. Por ejemplo,\r\n--    collatz 13  ==  [13,40,20,10,5,16,8,4,2,1]\r\n-- ---------------------------------------------------------------------\r\n\r\ncollatz :: Integer -> [Integer]\r\ncollatz 1 = [1]\r\ncollatz n = n : collatz (siguiente n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir, sin recursi\u00f3n, la funci\u00f3n \r\n--    collatz' :: Integer -> [Integer]\r\n-- tal que (collatz' n) es la \u00f3rbita de Collatz d n hasta alcanzar el\r\n-- 1. Por ejemplo,\r\n--    collatz' 13  ==  [13,40,20,10,5,16,8,4,2,1]\r\n-- Indicaci\u00f3n: Usar takeWhile e iterate.\r\n-- ---------------------------------------------------------------------\r\n\r\ncollatz' :: Integer -> [Integer]\r\ncollatz' n = (takeWhile (\/=1) (iterate siguiente n)) ++ [1]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n\r\n--    menorCollatzMayor :: Int -> Integer\r\n-- tal que (menorCollatzMayor x) es el menor n\u00famero cuya \u00f3rbita de\r\n-- Collatz tiene m\u00e1s de x elementos. Por ejemplo,\r\n--    menorCollatzMayor 100  ==  27\r\n-- ---------------------------------------------------------------------\r\n\r\nmenorCollatzMayor :: Int -> Integer\r\nmenorCollatzMayor x = head [y | y <- [1..], length (collatz y) > x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n\r\n--    menorCollatzSupera :: Integer -> Integer\r\n-- tal que (menorCollatzSupera x) es el menor n\u00famero cuya \u00f3rbita de\r\n-- Collatz tiene alg\u00fan elemento mayor que x. Por ejemplo,\r\n--    menorCollatzSupera 100  ==  15\r\n-- ---------------------------------------------------------------------\r\n\r\nmenorCollatzSupera :: Integer -> Integer\r\nmenorCollatzSupera x = \r\n    head [y | y <- [1..], maximum (collatz y) > x]\r\n\r\n-- Otra definici\u00f3n alternativa es\r\nmenorCollatzSupera' :: Integer -> Integer\r\nmenorCollatzSupera' x = head [n | n <- [1..], t <- collatz' n, t > x]\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos continuado con la resoluci\u00f3n de los ejercicios de la 14\u00aa relaci\u00f3n (que comenzamos en la clase del d\u00eda 17) y hemos comentado las soluciones de la 15\u00aa relaci\u00f3n. Las soluciones de los restantes de la relaci\u00f3n 14 son<\/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":[133],"tags":[287],"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\/1162"}],"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=1162"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1162\/revisions"}],"predecessor-version":[{"id":2942,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1162\/revisions\/2942"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1162"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1162"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1162"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}