{"id":5634,"date":"2016-11-30T16:07:35","date_gmt":"2016-11-30T15:07:35","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5634"},"modified":"2016-12-06T07:08:48","modified_gmt":"2016-12-06T06:08:48","slug":"i1m2016-2o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2016-2o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2016: 2\u00ba examen de programaci\u00f3n con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 2\u00ba examen del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-16\">Inform\u00e1tica<\/a> (de 1\u00ba de Grado en Matem\u00e1ticas). Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/p>\n<p><!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.List\nimport Data.Numbers.Primes \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. [2 puntos] La persistencia multiplicativa de un n\u00famero \n-- es la cantidad de pasos requeridos para reducirlo a una d\u00edgito\n-- multiplicando sus d\u00edgitos. Por ejemplo, la persistencia de 39 es 3\n-- porque 3*9 = 27, 2*7 = 14 y 1*4 = 4. \n--\n-- Definir la funci\u00f3n\n--    persistencia     :: Integer -> Integer\n-- tale que (persistencia x) es la persistencia de x. Por ejemplo,\n--      persistencia 39                             ==   3\n--      persistencia 2677889                        ==   8\n--      persistencia 26888999                       ==   9\n--      persistencia 3778888999                     ==  10\n--      persistencia 277777788888899                ==  11\n--      persistencia 77777733332222222222222222222  ==  11\n-- ---------------------------------------------------------------------\n\npersistencia :: Integer -> Integer\npersistencia x\n  | x < 10    = 0\n  | otherwise = 1 + persistencia (productoDigitos x)\n\nproductoDigitos :: Integer -> Integer\nproductoDigitos x \n  | x < 10    = x\n  | otherwise = r * productoDigitos y\n  where (y,r) = quotRem x 10\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. [2 puntos] Definir la funci\u00f3n\n--    intercala :: [a] -> [a] -> [[a]]\n-- tal que (intercala xs ys) es la lista obtenida intercalando los\n-- elementos de ys entre los de xs. Por ejemplo, \n--    ghci> intercala \"79\" \"15\"\n--    [\"719\",\"759\"]\n--    ghci> intercala \"79\" \"154\"\n--    [\"719\",\"759\",\"749\"]\n--    ghci> intercala \"796\" \"15\"\n--    [\"71916\",\"71956\",\"75916\",\"75956\"]\n--    ghci> intercala \"796\" \"154\"\n--    [\"71916\",\"71956\",\"71946\",\n--     \"75916\",\"75956\",\"75946\",\n--     \"74916\",\"74956\",\"74946\"]\n-- ---------------------------------------------------------------------\n\nintercala :: [a] -> [a] -> [[a]]\nintercala []     _  = []\nintercala [x]    _  = [[x]]\nintercala (x:xs) ys = [x:y:zs | y <- ys\n                              , zs <- intercala xs ys] \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. [2 puntos] Un n\u00famero primo se dice que es un primo de\n-- Kamenetsky  si al anteponerlo cualquier d\u00edgito se obtiene un n\u00famero\n-- compuesto. Por ejemplo, el 5 es un primo de Kamenetsky ya que 15, 25,\n-- 35, 45, 55, 65, 75, 85 y 95 son compuestos. Tambi\u00e9n lo es 149 ya que\n-- 1149, 2149, 3149, 4149, 5149, 6149, 7149, 8149 y 9149 son compuestos. \n--\n-- Definir la sucesi\u00f3n\n--    primosKamenetsky :: [Integer]\n-- tal que sus elementos son los n\u00fameros primos de Kamenetsky. Por\n-- ejemplo, \n--    take 5 primosKamenetsky  ==  [2,5,149,401,509]\n-- ---------------------------------------------------------------------\n\nprimosKamenetsky :: [Integer]\nprimosKamenetsky =\n  [x | x <- primes\n     , esKamenetsky x] \n\nesKamenetsky :: Integer -> Bool\nesKamenetsky x =\n  all (not . isPrime) [read (d:xs) | d <- \"123456789\"]\n  where xs = show x\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. [2 puntos] Representamos los \u00e1rboles binarios con\n-- elementos en las hojas y en los nodos mediante el tipo de dato \n--    data Arbol a = H a\n--                 | N a (Arbol a) (Arbol a) \n--                 deriving Show\n-- Por ejemplo,\n--    ej1 :: Arbol Int\n--    ej1 = N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))\n-- \n-- Definir la funci\u00f3n\n--    ramasCon :: Eq a => Arbol a -> a -> [[a]]\n-- tal que (ramasCon a x) es la lista de las ramas del \u00e1rbol a en las\n-- que aparece el elemento x. Por ejemplo,\n--   ramasCon ej1 2 ==  [[5,2,1],[5,2,2],[5,3,2]]\n-- ---------------------------------------------------------------------\n\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a) \n             deriving Show\n \nej1 :: Arbol Int\nej1 = N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))\n \nramasCon :: Eq a => Arbol a -> a -> [[a]]\nramasCon a x = [ys | ys <- ramas a, x `elem` ys]\n \nramas :: Arbol a -> [[a]]\nramas (H x)     = [[x]]\nramas (N x i d) = [x:ys | ys <- ramas i ++ ramas d]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. [2 puntos] El valor m\u00e1ximo de la suma de elementos\n-- consecutivos de la lista [3,-4,4,1] es 5 obtenido sumando los\n-- elementos del segmento [4,1] y para la lista [-2,1,4,-3,5,-7,6] es 7\n-- obtenido sumando los elementos del segmento [1,4,-3,5].\n-- \n-- Definir la funci\u00f3n\n--    sumaMaxima :: [Integer] -> Integer\n-- tal que (sumaMaxima xs) es el valor m\u00e1ximo de la suma de elementos\n-- consecutivos de la lista xs. Por ejemplo,\n--    sumaMaxima1 [3,-4,4,1]          ==  5\n--    sumaMaxima1 [-2,1,4,-3,5,-7,6]  ==  7\n--    sumaMaxima []                   ==  0\n--    sumaMaxima [2,-2,3,-3,4]        ==  4\n--    sumaMaxima [-1,-2,-3]           ==  0\n--    sumaMaxima [2,-1,3,-2,3]        ==  5\n--    sumaMaxima [1,-1,3,-2,4]        ==  5\n--    sumaMaxima [2,-1,3,-2,4]        ==  6\n--    sumaMaxima [1..10^6]            ==  500000500000\n-- ----------------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nsumaMaxima1 :: [Integer] -> Integer\nsumaMaxima1 [] = 0\nsumaMaxima1 xs =\n    maximum (0 : map sum [sublista xs i j | i <- [0..length xs - 1],\n                                            j <- [i..length xs - 1]])\n\nsublista :: [Integer] -> Int -> Int -> [Integer]\nsublista xs i j =\n    [xs!!k | k <- [i..j]]\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nsumaMaxima2 :: [Integer] -> Integer\nsumaMaxima2 [] = 0\nsumaMaxima2 xs = sumaMaximaAux 0 0 xs\n    where m = maximum xs\n\nsumaMaximaAux :: Integer -> Integer -> [Integer] -> Integer\nsumaMaximaAux m v [] = max m v\nsumaMaximaAux m v (x:xs)\n    | x >= 0    = sumaMaximaAux m (v+x) xs\n    | v+x > 0   = sumaMaximaAux (max m v) (v+x) xs\n    | otherwise = sumaMaximaAux (max m v) 0 xs\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\nsumaMaxima3 :: [Integer] -> Integer\nsumaMaxima3 [] = 0\nsumaMaxima3 xs = maximum (map sum (segmentos xs))\n\n-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo \n--    segmentos \"abc\"  ==  [\"\", \"a\",\"ab\",\"abc\",\"b\",\"bc\",\"c\"]\nsegmentos :: [a] -> [[a]]\nsegmentos xs =\n    [] : concat [tail (inits ys) | ys <- init (tails xs)]\n\n-- 4\u00aa definici\u00f3n\n-- =============\n\nsumaMaxima4 :: [Integer] -> Integer\nsumaMaxima4 [] = 0\nsumaMaxima4 xs = \n    maximum (concat [scanl (+) 0 ys | ys <- tails xs])\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> let n = 10^2 in sumaMaxima1 [-n..n] \n--    5050\n--    (2.10 secs, 390,399,104 bytes)\n--    \u03bb> let n = 10^2 in sumaMaxima2 [-n..n] \n--    5050\n--    (0.02 secs, 0 bytes)\n--    \u03bb> let n = 10^2 in sumaMaxima3 [-n..n] \n--    5050\n--    (0.27 secs, 147,705,184 bytes)\n--    \u03bb> let n = 10^2 in sumaMaxima4 [-n..n] \n--    5050\n--    (0.04 secs, 11,582,520 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 2\u00ba examen del curso de Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas). Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/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":[260],"tags":[270,313],"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\/5634"}],"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=5634"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5634\/revisions"}],"predecessor-version":[{"id":5635,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5634\/revisions\/5635"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5634"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5634"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5634"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}