{"id":4890,"date":"2015-04-29T16:24:36","date_gmt":"2015-04-29T14:24:36","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4890"},"modified":"2015-05-05T11:25:40","modified_gmt":"2015-05-05T09:25:40","slug":"i1m2014-5o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-5o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2014: 5\u00ba examen de programaci\u00f3n con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 5\u00ba examen del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">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-- Inform\u00e1tica: 5\u00ba examen de evaluaci\u00f3n continua (29 de abril de 2015)\n-- ---------------------------------------------------------------------\n\nimport Data.Array \nimport Data.List\nimport Data.Numbers.Primes\nimport I1M.Grafo\nimport I1M.Monticulo\nimport I1M.PolOperaciones\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Una propiedad del 2015 es que la suma de sus d\u00edgitos\n-- coincide con el n\u00famero de sus divisores; en efecto, la suma de sus\n-- d\u00edgitos es 2+0+1+5=8 y tiene 8 divisores (1, 5, 13, 31, 65, 155, 403\n-- y 2015). \n--    \n-- Definir la sucesi\u00f3n\n--    especiales :: [Int]\n-- formada por los n\u00fameros n tales que la suma de los d\u00edgitos de n\n-- coincide con el n\u00famero de divisores de n. Por ejemplo,\n--    take 12 especiales == [1,2,11,22,36,84,101,152,156,170,202,208]\n--\n-- Calcular la posici\u00f3n de 2015 en la sucesi\u00f3n de especiales.\n-- ---------------------------------------------------------------------\n\nespeciales :: [Int]\nespeciales = [n | n <- [1..], sum (digitos n) == length (divisores n)]\n\ndigitos :: Int -> [Int]\ndigitos n = [read [d] | d <- show n]\n\ndivisores :: Int -> [Int]\ndivisores n = n : [x | x <- [1..n `div` 2], n `mod` x == 0]\n\n-- El c\u00e1lculo de n\u00famero de a\u00f1os hasta el 2015 inclusive que han cumplido\n-- la propiedad es\n--    ghci> length (takeWhile (<=2015) especiales)\n--    59\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n \n--    posicion :: Array Int Bool -> Maybe Int\n-- tal que (posicion v) es la menor posici\u00f3n del vector de booleanos v\n-- cuyo valor es falso y es Nothing si todos los valores son\n-- verdaderos. Por ejemplo,\n--    posicion (listArray (0,4) [True,True,False,True,False]) == Just 2\n--    posicion (listArray (0,4) [i <= 2 | i <- [0..4]])       == Just 3\n--    posicion (listArray (0,4) [i <= 7 | i <- [0..4]])       == Nothing\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\nposicion :: Array Int Bool -> Maybe Int\nposicion v | p > n     = Nothing\n           | otherwise = Just p\n    where p = (length . takeWhile id . elems) v\n          (_,n) = bounds v \n\n-- 2\u00aa soluci\u00f3n:\nposicion2 :: Array Int Bool -> Maybe Int\nposicion2 v | null xs   = Nothing\n            | otherwise = Just (head xs)\n    where xs = [i | i <- indices v, v!i]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    todos :: Ord a => (a -> Bool) -> Monticulo a -> Bool\n-- tal que (todos p m) se verifica si todos los elementos del mont\u00edculo\n-- m cumple la propiedad p, Por ejemplo,\n--    todos (>2) (foldr inserta vacio [6,3,4,8])  ==  True\n--    todos even (foldr inserta vacio [6,3,4,8])  ==  False\n-- ---------------------------------------------------------------------\n\ntodos :: Ord a => (a -> Bool) -> Monticulo a -> Bool\ntodos p m\n    | esVacio m = True\n    | otherwise = p (menor m) && todos p (resto m)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. El complementario del grafo G es un grafo G' del mismo\n-- tipo que G (dirigido o no dirigido), con el mismo conjunto de nodos y\n-- tal que dos nodos de G' son adyacentes si y s\u00f3lo si no son adyacentes\n-- en G. Los pesos de todas las aristas del complementario es igual a 0.\n--    ghci> complementario (creaGrafo D (1,3) [(1,3,0),(3,2,0),(2,2,0),(2,1,0)])\n--    G D (array (1,3) [(1,[(1,0),(2,0)]),(2,[(3,0)]),(3,[(1,0),(3,0)])])\n--    ghci> complementario (creaGrafo D (1,3) [(3,2,0),(2,2,0),(2,1,0)])\n--    G D (array (1,3) [(1,[(1,0),(2,0),(3,0)]),(2,[(3,0)]),(3,[(1,0),(3,0)])])\n-- ---------------------------------------------------------------------\n\ncomplementario :: Grafo Int Int -> Grafo Int Int\ncomplementario g = \n    creaGrafo d (1,n) [(x,y,0) | x <- xs, y <- xs, not (aristaEn g (x,y))]\n    where d  = if dirigido g then D else ND\n          xs = nodos g\n          n  = length xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. En 1772, Euler public\u00f3 que el polinomio n\u00b2 + n + 41\n-- genera 40 n\u00fameros primos para todos los valores de n entre 0 y\n-- 39. Sin embargo, cuando n=40, 40\u00b2+40+41 = 40(40+1)+41 es divisible\n-- por 41.  \n-- \n-- Definir la funci\u00f3n\n--    generadoresMaximales :: Integer -> (Int,[(Integer,Integer)])\n-- tal que (generadoresMaximales n) es el par (m,xs) donde \n--    + xs es la lista de pares (x,y) tales que n\u00b2+xn+y es uno de los\n--      polinomios que genera un n\u00famero m\u00e1ximo de n\u00fameros primos\n--      consecutivos a partir de cero entre todos los polinomios de la\n--      forma n\u00b2+an+b, con |a| \u2264 n y |b| \u2264 n y\n--    + m es dicho n\u00famero m\u00e1ximo.\n-- Por ejemplo,\n--    generadoresMaximales    4  ==  ( 3,[(-2,3),(-1,3),(3,3)])\n--    generadoresMaximales    6  ==  ( 5,[(-1,5),(5,5)])\n--    generadoresMaximales   50  ==  (43,[(-5,47)])\n--    generadoresMaximales  100  ==  (48,[(-15,97)])\n--    generadoresMaximales  200  ==  (53,[(-25,197)])\n--    generadoresMaximales 1650  ==  (80,[(-79,1601)])\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ngeneradoresMaximales1 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales1 n = \n    (m,[((a,b)) | a <- [-n..n], b <- [-n..n], nPrimos a b == m])\n    where m = maximum $ [nPrimos a b | a <- [-n..n], b <- [-n..n]]\n\n-- (nPrimos a b) es el n\u00famero de primos consecutivos generados por el\n-- polinomio n\u00b2 + an + b a partir de n=0. Por ejemplo,\n--    nPrimos 1 41        ==  40\n--    nPrimos (-79) 1601  ==  80\nnPrimos :: Integer -> Integer -> Int\nnPrimos a b =\n    length $ takeWhile isPrime [n*n+a*n+b | n <- [0..]]\n\n-- 2\u00aa soluci\u00f3n (reduciendo las cotas)\n-- ==================================\n\n-- Notas: \n-- 1. Se tiene que b es primo, ya que para n=0, se tiene que 0\u00b2+a*0+b =\n--    b es primo. \n-- 2. Se tiene que 1+a+b es primo, ya que es el valor del polinomio para\n--    n=1. \n\ngeneradoresMaximales2 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales2 n = (m,map snd zs)\n    where xs = [(nPrimos a b,(a,b)) | b <- takeWhile (<=n) primes,\n                                      a <- [-n..n],\n                                      isPrime(1+a+b)]\n          ys = reverse (sort xs)\n          m  = fst (head ys)\n          zs = takeWhile (\\(k,_) -> k == m) ys\n\n-- 3\u00aa soluci\u00f3n (con la librer\u00eda de polinomios)\n-- ===========================================\n\ngeneradoresMaximales3 :: Integer -> (Int,[(Integer,Integer)])\ngeneradoresMaximales3 n = (m,map snd zs)\n    where xs = [(nPrimos2 a b,(a,b)) | b <- takeWhile (<=n) primes,\n                                      a <- [-n..n],\n                                      isPrime(1+a+b)]\n          ys = reverse (sort xs)\n          m  = fst (head ys)\n          zs = takeWhile (\\(k,_) -> k == m) ys\n\n-- (nPrimos2 a b) es el n\u00famero de primos consecutivos generados por el\n-- polinomio n\u00b2 + an + b a partir de n=0. Por ejemplo,\n--    nPrimos2 1 41        ==  40\n--    nPrimos2 (-79) 1601  ==  80\nnPrimos2 :: Integer -> Integer -> Int\nnPrimos2 a b =\n    length $ takeWhile isPrime [valor p n | n <- [0..]]\n    where p = consPol 2 1 (consPol 1 a (consPol 0 b polCero))\n\n-- Comparaci\u00f3n de eficiencia\n--    ghci> generadoresMaximales1 200\n--    (53,[(-25,197)])\n--    (3.06 secs, 720683776 bytes)\n--    ghci> generadoresMaximales1 300\n--    (56,[(-31,281)])\n--    (6.65 secs, 1649274220 bytes)\n--    \n--    ghci> generadoresMaximales2 200\n--    (53,[(-25,197)])\n--    (0.25 secs, 94783464 bytes)\n--    ghci> generadoresMaximales2 300\n--    (56,[(-31,281)])\n--    (0.51 secs, 194776708 bytes)\n--\n--    ghci> generadoresMaximales3 200\n--    (53,[(-25,197)])\n--    (0.20 secs, 105941096 bytes)\n--    ghci> generadoresMaximales3 300\n--    (56,[(-31,281)])\n--    (0.35 secs, 194858344 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 5\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":"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":[238],"tags":[270,305],"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\/4890"}],"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=4890"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4890\/revisions"}],"predecessor-version":[{"id":4891,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4890\/revisions\/4891"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4890"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4890"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4890"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}