{"id":4053,"date":"2014-01-23T20:32:56","date_gmt":"2014-01-23T19:32:56","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4053"},"modified":"2014-01-24T07:35:07","modified_gmt":"2014-01-24T06:35:07","slug":"i1m2013-3o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-3o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2013: 3\u00ba examen de programaci\u00f3n con Haskell"},"content":{"rendered":"<p>En la clase de hoy del curso <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas)<\/a> se ha realizado el 3\u00ba examen del curso en dos turnos.<\/p>\n<p>Los ejercicios y soluciones del primer turno se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Librer\u00edas auxiliares                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.1. Definir la funci\u00f3n\r\n--    divisoresConUno :: Integer -> Bool\r\n-- tal que (divisoresConUno n) se verifica si todos sus divisores\r\n-- contienen el d\u00edgito 1. Por ejemplo,\r\n--    divisoresConUno 671  ==  True\r\n--    divisoresConUno 100  ==  False\r\n-- ya que los divisores de 671 son 1, 11, 61 y 671 y todos contienen el\r\n-- n\u00famero 1; en cambio, 25 es un divisor de 100 que no contiene el\r\n-- d\u00edgito 1. \r\n-- ---------------------------------------------------------------------\r\n\r\ndivisoresConUno :: Integer -> Bool\r\ndivisoresConUno n = all contieneUno (divisores n)\r\n\r\n-- 2\u00aa definici\u00f3n (sin all) \r\ndivisoresConUno2 :: Integer -> Bool\r\ndivisoresConUno2 n = and [contieneUno x | x <- divisores n]\r\n\r\n-- 3\u00aa definici\u00f3n (por recursi\u00f3n)\r\ndivisoresConUno3 :: Integer -> Bool\r\ndivisoresConUno3 n = aux (divisores n)\r\n    where aux []     = True\r\n          aux (x:xs) = contieneUno x && aux xs\r\n\r\n-- 4\u00aa definici\u00f3n (por plegado)\r\ndivisoresConUno4 :: Integer -> Bool\r\ndivisoresConUno4 n = foldr f True (divisores n)\r\n    where f x y = contieneUno x && y\r\n\r\n-- 5\u00aa definici\u00f3n (por plegado y lambda)\r\ndivisoresConUno5 :: Integer -> Bool\r\ndivisoresConUno5 n = \r\n    foldr (\\x y -> contieneUno x && y) True (divisores n)\r\n\r\n-- (divisores n) es la lista de los divisores de n. Por ejemplo,\r\n--    divisores 12  ==  [1,2,3,4,6,12]\r\ndivisores :: Integer -> [Integer]\r\ndivisores n = [x | x <- [1..n], rem n x == 0]\r\n\r\n-- (contienUno n) se verifica si n contiene el d\u00edgito 1. Por ejemplo, \r\n--    contieneUno 214  ==  True\r\n--    contieneUno 234  ==  False\r\ncontieneUno :: Integer -> Bool\r\ncontieneUno n = elem '1' (show n)\r\n\r\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n sin show)\r\ncontieneUno2 :: Integer -> Bool\r\ncontieneUno2 1 = True\r\ncontieneUno2 n | n < 10          = False\r\n               | n `rem` 10 == 1 = True\r\n               | otherwise       = contieneUno2 (n `div` 10)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.2. \u00bfCu\u00e1l ser\u00e1 el pr\u00f3ximo a\u00f1o en el que todos sus divisores\r\n-- contienen el d\u00edgito 1? \u00bfy el anterior?\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> head [n | n <- [2014..], divisoresConUno n]\r\n--    2017\r\n--    ghci> head [n | n <- [2014,2013..], divisoresConUno n]\r\n--    2011\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.1. Un elemento de una lista es permanente si ninguno de\r\n-- los siguientes es mayor que \u00e9l. \r\n-- \r\n-- Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    permanentesR :: [Int] -> [Int]\r\n-- tal que (permanentesR xs) es la lista de los elementos permanentes de\r\n-- xs. Por ejemplo,\r\n--    permanentesR [80,1,7,8,4]  ==  [80,8,4]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa definici\u00f3n:\r\npermanentesR :: [Int] -> [Int]\r\npermanentesR [] = []\r\npermanentesR (x:xs) | x == maximum (x:xs) = x:permanentesR xs\r\n                    | otherwise           = permanentesR xs\r\n\r\n-- 2\u00aa definici\u00f3n (sin usar maximum):\r\npermanentesR2 :: [Int] -> [Int]\r\npermanentesR2 [] = []\r\npermanentesR2 (x:xs) | and [x>=y|y<-xs] = x:permanentesR2 xs\r\n                     | otherwise        = permanentesR2 xs\r\n\r\n-- Nota: Comparaci\u00f3n de eficiencia\r\n--    ghci> let xs = [1..1000] in last (permanentesR (xs ++ reverse xs))\r\n--    1\r\n--    (0.22 secs, 41105812 bytes)\r\n--    ghci> let xs = [1..1000] in last (permanentesR2 (xs ++ reverse xs))\r\n--    1\r\n--    (0.96 secs, 31421308 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.2. Definir, por plegado, la funci\u00f3n \r\n--    permanentesP :: [Int] -> [Int]\r\n-- tal que (permanentesP xs) es la lista de los elementos permanentes de\r\n-- xs. Por ejemplo,\r\n--    permanentesP [80,1,7,8,4]  ==  [80,8,4]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa definici\u00f3n:\r\npermanentesP :: [Int] -> [Int]\r\npermanentesP = foldr f []\r\n    where f x ys | x == maximum (x:ys) = x:ys\r\n                 | otherwise           = ys\r\n\r\n-- 2\u00aa definici\u00f3n:\r\npermanentesP2 :: [Int] -> [Int]\r\npermanentesP2 xs = foldl f [] (reverse xs)\r\n    where f ac x | x == maximum (x:ac) = x:ac\r\n                 | otherwise           = ac\r\n\r\n-- Nota: Comparaci\u00f3n de eficiencia\r\n--    ghci> let xs = [1..1000] in last (permanentesP (xs ++ reverse xs))\r\n--    1\r\n--    (0.22 secs, 52622056 bytes)\r\n--    ghci> let xs = [1..1000] in last (permanentesP2 (xs ++ reverse xs))\r\n--    1\r\n--    (0.23 secs, 52918324 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    especial :: Int -> [[Int]] -> Bool\r\n-- tal que (especial k xss) se verifica si cada uno de los diez d\u00edgitos\r\n-- 0, 1, 2,..., 9 aparece k veces entre todas las listas de xss. Por\r\n-- ejemplo, \r\n--    especial 1 [[12,40],[5,79,86,3]]                          == True\r\n--    especial 2 [[107,32,89],[58,76,94],[63,120,45]]           == True\r\n--    especial 3 [[1329,276,996],[534,867,1200],[738,1458,405]] == True\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa definici\u00f3n (por comprensi\u00f3n):\r\nespecial :: Int -> [[Int]] -> Bool\r\nespecial k xss =\r\n    sort (concat [show n | xs <- xss, n <- xs])\r\n    == concat [replicate k d | d <- ['0'..'9']]\r\n\r\n-- 2\u00aa definici\u00f3n (con map)\r\nespecial2 :: Int -> [[Int]] -> Bool\r\nespecial2 k xss = \r\n    sort (concat (concat (map (map cifras) xss))) \r\n    == concat [replicate k d | d <- [0..9]]\r\n\r\ncifras:: Int -> [Int]\r\ncifras n = [read [x] | x <-show n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n \r\n--    primosConsecutivosConIgualFinal :: Int -> [Integer]\r\n-- tal que (primosConsecutivosConIgualFinal n) es la lista de los\r\n-- primeros n primos consecutivos que terminan en el  mismo d\u00edgito. Por\r\n-- ejemplo, \r\n--    primosConsecutivosConIgualFinal 2 == [139, 149]\r\n--    primosConsecutivosConIgualFinal 3 == [1627, 1637, 1657]\r\n-- ---------------------------------------------------------------------\r\n\r\nprimosConsecutivosConIgualFinal :: Int -> [Integer]\r\nprimosConsecutivosConIgualFinal n = consecutivosConPropiedad p n primos\r\n    where p []     = True\r\n          p (x:xs) = and [r == rem y 10 | y <- xs]\r\n              where r = rem x 10\r\n\r\n-- (consecutivosConPropiedad p n xs) es la lista con los n primeros\r\n-- elementos consecutivos de zs que verifican la propiedad p. Por\r\n-- ejemplo, \r\n--    ghci> consecutivosConPropiedad (\\xs -> sum xs > 20) 2 [5,2,1,17,4,25]\r\n--    [17,4]\r\nconsecutivosConPropiedad :: ([a] -> Bool) -> Int -> [a] -> [a]\r\nconsecutivosConPropiedad p n zs = \r\n    head [xs | xs <- [take n ys | ys <- tails zs], p xs]\r\n\r\n-- primos es la lista de los n\u00fameros primos. Por ejemplo,\r\n--    ghci> take 20 primos\r\n--    [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]\r\nprimos :: [Integer]\r\nprimos = [n | n <- 2:[3,5..], primo n]\r\n\r\n-- (primo n) se verifica si n es un n\u00famero primo. Por ejemplo,\r\n--    primo 7  ==  True\r\n--    primo 8  ==  False\r\nprimo :: Integer -> Bool\r\nprimo n = [x | x <- [1..n], rem n x == 0] == [1,n]\r\n<\/pre>\n<p>Los ejercicios y soluciones del segundo turno se muestran a continuaci\u00f3n<\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. El factorial de 7 es\r\n--    7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040\r\n-- por tanto, el \u00faltimo d\u00edgito no nulo del factorial de 7 es 4.\r\n-- \r\n-- Definir la funci\u00f3n\r\n--    ultimoNoNuloFactorial :: Integer -> Integer\r\n-- tal que (ultimoNoNuloFactorial n) es el \u00faltimo d\u00edgito no nulo del\r\n-- factorial de n. Por ejemplo,\r\n--    ultimoNoNuloFactorial 7  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nultimoNoNuloFactorial :: Integer -> Integer\r\nultimoNoNuloFactorial n = ultimoNoNulo (factorial n)\r\n\r\n-- (ultimoNoNulo n) es el \u00faltimo d\u00edgito no nulo de n. Por ejemplo,\r\n--    ultimoNoNulo 5040  ==  4\r\nultimoNoNulo :: Integer -> Integer\r\nultimoNoNulo n | m \/= 0    = m\r\n               | otherwise = ultimoNoNulo (n `div` 10)\r\n               where m = n `rem` 10\r\n\r\n-- 2\u00aa definici\u00f3n (por comprensi\u00f3n)\r\nultimoNoNulo2 :: Integer -> Integer\r\nultimoNoNulo2 n = read [head (dropWhile (=='0') (reverse (show n)))]\r\n\r\n-- (factorial n) es el factorial de n. Por ejemplo,\r\n--    factorial 7  ==  5040\r\nfactorial :: Integer -> Integer\r\nfactorial n = product [1..n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.1. Una lista se puede comprimir indicando el n\u00famero de\r\n-- veces consecutivas que aparece cada elemento. Por ejemplo, la lista \r\n-- comprimida de [1,1,7,7,7,5,5,7,7,7,7] es [(2,1),(3,7),(2,5),(4,7)],\r\n-- indicando que comienza con dos 1, seguido de tres 7, dos 5 y cuatro\r\n-- 7. \r\n--\r\n-- Definir, por comprensi\u00f3n, la funci\u00f3n \r\n--    expandidaC :: [(Int,a)] -> [a]\r\n-- tal que (expandidaC ps) es la lista expandida correspondiente a ps\r\n-- (es decir, es la lista xs tal que la comprimida de xs es ps). Por\r\n-- ejemplo, \r\n--    expandidaC [(2,1),(3,7),(2,5),(4,7)]  ==  [1,1,7,7,7,5,5,7,7,7,7]\r\n-- ---------------------------------------------------------------------\r\n\r\nexpandidaC :: [(Int,a)] -> [a]\r\nexpandidaC ps = concat [replicate k x | (k,x) <- ps]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.2. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    expandidaR :: [(Int,a)] -> [a]\r\n-- tal que (expandidaR ps) es la lista expandida correspondiente a ps\r\n-- (es decir, es la lista xs tal que la comprimida de xs es ps). Por\r\n-- ejemplo, \r\n--    expandidaR [(2,1),(3,7),(2,5),(4,7)]  ==  [1,1,7,7,7,5,5,7,7,7,7]\r\n-- ---------------------------------------------------------------------\r\n\r\nexpandidaR :: [(Int,a)] -> [a]\r\nexpandidaR []         = []\r\nexpandidaR ((n,x):ps) = replicate n x ++ expandidaR ps\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.1. Un n\u00famero n es de Angelini si n y 2n tienen alg\u00fan\r\n-- d\u00edgito com\u00fan. Por ejemplo, 2014 es un n\u00famero de Angelini ya que 2014\r\n-- y su doble (4028) comparten los d\u00edgitos 4 y 0.\r\n--\r\n-- Definir la funci\u00f3n\r\n--    angelini :: Integer -> Bool\r\n-- tal que (angelini n) se verifica si n es un n\u00famero de Angelini. Por\r\n-- ejemplo, \r\n--    angelini 2014  ==  True\r\n--    angelini 2067  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa definici\u00f3n (con any)\r\nangelini :: Integer -> Bool\r\nangelini n = any (`elem` (show (2*n))) (show n)  \r\n\r\n-- 2\u00aa definici\u00f3n (por comprensi\u00f3n)\r\nangelini2 :: Integer -> Bool\r\nangelini2 n = not (null [x | x <- show n, x `elem` show (2*n)])\r\n\r\n-- 3\u00aa definici\u00f3n (por recursi\u00f3n)\r\nangelini3 :: Integer -> Bool\r\nangelini3 n = aux (show n) (show (2*n))\r\n    where aux [] _      = False\r\n          aux (x:xs) ys = x `elem` ys || aux xs ys\r\n\r\n-- 4\u00aa definici\u00f3n (por plegado)\r\nangelini4 :: Integer -> Bool\r\nangelini4 n = aux (show n) \r\n    where aux   = foldr f False\r\n          f x y = x `elem` show (2*n) || y\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.2. \u00bfCu\u00e1l es el primer a\u00f1o que no ser\u00e1 de Angelini?\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> head [n | n <- [2014..], not (angelini n)]\r\n--    2057\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4.1. El n\u00famero 37 es primo y se puede escribir como suma de\r\n-- primos menores distintos (en efecto, los n\u00fameros 3, 11 y 23 son\r\n-- primos y su suma es 37.\r\n--\r\n-- Definir la funci\u00f3n\r\n--    primoSumaDePrimos :: Integer -> Bool\r\n-- tal que (primoSumaDePrimos n) se verifica si n es primo y se puede\r\n-- escribir como suma de primos menores que n. Por ejemplo,\r\n--    primoSumaDePrimos 37  ==  True\r\n--    primoSumaDePrimos 39  ==  False\r\n--    primoSumaDePrimos 11  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nprimoSumaDePrimos :: Integer -> Bool\r\nprimoSumaDePrimos n = primo n && esSumaDePrimos n\r\n\r\n-- (esSumaDePrimos n) se verifica si n es una suma de primos menores que\r\n-- n. Por ejemplo,\r\n--    esSumaDePrimos 37  ==  True\r\n--    esSumaDePrimos 11  ==  False\r\nesSumaDePrimos :: Integer -> Bool\r\nesSumaDePrimos n = esSuma n [x | x <- 2:[3,5..n-1], primo x]\r\n\r\n-- (primo n) se verifica si n es primo. Por ejemplo,\r\n--    primo 37  ==  True\r\n--    primo 38  ==  False\r\nprimo :: Integer -> Bool\r\nprimo n = [x | x <- [1..n], n `rem` x == 0] == [1,n]\r\n\r\n-- (esSuma n xs) s verifica si n es suma de elementos de xs. Por ejemplo,\r\n--    esSuma 20 [4,2,7,9]  ==  True\r\n--    esSuma 21 [4,2,7,9]  ==  False\r\nesSuma :: Integer -> [Integer] -> Bool\r\nesSuma 0 _                  = True                    \r\nesSuma n []                 = False \r\nesSuma n (x:xs) | n == x    = True\r\n                | n > x     = esSuma n xs || esSuma (n-x) xs\r\n                | otherwise = esSuma n xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4.2. \u00bfCu\u00e1l ser\u00e1 el pr\u00f3ximo a\u00f1o primo suma de primos? \u00bfy el\r\n-- anterior? \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es \r\n--    ghci> head [p | p <- [2014..], primoSumaDePrimos p]\r\n--    2017\r\n--    ghci> head [p | p <- [2014,2013..], primoSumaDePrimos p]\r\n--    2011\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy del curso Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas) se ha realizado el 3\u00ba examen del curso en dos turnos. Los ejercicios y soluciones del primer turno se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"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":[222],"tags":[233,300],"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\/4053"}],"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=4053"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4053\/revisions"}],"predecessor-version":[{"id":4055,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4053\/revisions\/4055"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4053"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4053"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4053"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}