{"id":7008,"date":"2020-01-23T08:36:28","date_gmt":"2020-01-23T07:36:28","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7008"},"modified":"2020-02-15T08:37:44","modified_gmt":"2020-02-15T07:37:44","slug":"7008-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/7008-2\/","title":{"rendered":"I1M2019: 3\u00ba examen de programaci\u00f3n funcional con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 3\u00ba examen del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-19\">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\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Un n\u00famero de Munchausen es un n\u00famero entero positivo\n-- que es igual a la suma de sus d\u00edgitos elevados a s\u00ed mismo. Por\n-- ejemplo, 3435 es un n\u00famero de Munchausen ya qu e \n--    3\u00b3 + 4\u2074 + 3\u00b3 + 5\u2075 = 27 + 256 + 27 + 3125 = 3435\n--\n-- Definir la funci\u00f3n\n--    esMunchausen :: Integer -> Bool\n-- tal que (esMunchausen n) se verifica si n es un n\u00famero de\n-- Munchausen. Por ejemplo,\n--    esMunchausen 3435  ==  True\n--    esMunchausen 2020  ==  False\n-- ---------------------------------------------------------------------\n\nesMunchausen :: Integer -> Bool\nesMunchausen n =\n  n == sum [x^x | x <- digitos n]\n\n-- (digitos n) es la lista de los d\u00edgitos de n. Por ejemplo,\n--    digitos 3435  ==  [3,4,3,5]\ndigitos :: Integer -> [Integer]\ndigitos n = [read [c] | c <- show n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Comprobar con QuickCheck que que los \u00fanicos n\u00fameros de\n-- Munchausen son 1 y 3435.\n--\n-- Nota: No usar la propiedad en la definici\u00f3n de esMunchausen.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_Munchausen :: Integer -> Property\nprop_Munchausen n =\n  n > 0\n  ==>\n  esMunchausen n == elem n [1, 3435]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_Munchausen\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. La lista ps = [p(1),...,p(k)] es una sucesi\u00f3n de Grim\n-- para la lista xs = [x(1),...,x(k)] si los p(i) son n\u00fameros primos\n-- distintos y p(i) divide a x(i), para 1 \u2264 i \u2264 k. Por ejemplo, 2, 5,\n-- 13, 3, 7 es una sucesi\u00f3n de Grim de 24, 25, 26, 27, 28.\n--\n-- Definir la funci\u00f3n\n--    sucesionesDeGrim :: [Integer] -> [[Integer]]\n-- tal que (sucesionesDeGrim xs) es la lista de las sucesiones de Grim\n-- de xs. Por ejemplo, \n--    sucesionesDeGrim [15,16]          == [[3,2],[5,2]]\n--    sucesionesDeGrim [8,9,10]         == [[2,3,5]]\n--    sucesionesDeGrim [9,10]           == [[3,2],[3,5]]\n--    sucesionesDeGrim [24,25,26,27,28] == [[2,5,13,3,7]]\n--    sucesionesDeGrim [25,26,27,28]    == [[5,2,3,7],[5,13,3,2],[5,13,3,7]]\n-- ---------------------------------------------------------------------\n\nsucesionesDeGrim :: [Integer] -> [[Integer]]\nsucesionesDeGrim [] = [[]]\nsucesionesDeGrim (x:xs) =\n  [y:ys | y <- divisoresPrimos x\n        , ys <- sucesionesDeGrim xs\n        , y `notElem` ys]\n\n-- (divisoresPrimos n) es la lista de los divisores primos de n. Por\n-- ejemplo, \n--    divisoresPrimos 60  ==  [2,3,5]\ndivisoresPrimos :: Integer -> [Integer]\ndivisoresPrimos = nub . primeFactors\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Las primeras sumas alternas de los factoriales son\n-- n\u00fameros primos; en efecto, \n--    3! - 2! + 1! = 5\n--    4! - 3! + 2! - 1! = 19\n--    5! - 4! + 3! - 2! + 1! = 101\n--    6! - 5! + 4! - 3! + 2! - 1! = 619\n--    7! - 6! + 5! - 4! + 3! - 2! + 1! = 4421\n--    8! - 7! + 6! - 5! + 4! - 3! + 2! - 1! = 35899\n-- son primos, pero\n--    9! - 8! + 7! - 6! + 5! - 4! + 3! - 2! + 1! = 326981\n-- no es primo.\n--\n-- Definir la funci\u00f3n\n--    sumaAlterna         :: Integer -> Integer\n-- tal que (sumaAlterna n) es la suma alterna de los factoriales desde n hasta\n-- 1. Por ejemplo,\n--    sumaAlterna 3  ==  5\n--    sumaAlterna 4  ==  19\n--    sumaAlterna 5  ==  101\n--    sumaAlterna 6  ==  619\n--    sumaAlterna 7  ==  4421\n--    sumaAlterna 8  ==  35899\n--    sumaAlterna 9  ==  326981\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsumaAlterna1 :: Integer -> Integer\nsumaAlterna1 1 = 1\nsumaAlterna1 n = factorial n - sumaAlterna1 (n-1)\n\nfactorial :: Integer -> Integer\nfactorial n = product [1..n]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsumaAlterna2 :: Integer -> Integer\nsumaAlterna2 n = sum (zipWith (*) signos (tail factoriales))\n  where\n    signos | odd n     = 1 : concat (replicate (m `div` 2) [-1,1])\n           | otherwise = concat (replicate (m `div` 2) [-1,1])\n    m = fromIntegral n\n\n-- factoriales es la lista de los factoriales. Por ejemplo,\n--    take 7 factoriales  ==  [1,1,2,6,24,120,720]\nfactoriales :: [Integer]\nfactoriales = 1 : scanl1 (*) [1..]\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\nsumaAlterna3 :: Integer -> Integer\nsumaAlterna3 n = \n  sum (genericTake n (zipWith (*) signos (tail factoriales)))\n  where signos | odd n     = cycle [1,-1]\n               | otherwise = cycle [-1,1]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> sumaAlterna1 3000 `mod` (10^6)\n--    577019\n--    (5.33 secs, 7,025,937,760 bytes)\n--    \u03bb> sumaAlterna2 3000 `mod` (10^6)\n--    577019\n--    (0.03 secs, 15,738,480 bytes)\n--    \u03bb> sumaAlterna3 3000 `mod` (10^6)\n--    577019\n--    (0.05 secs, 16,520,896 bytes)\n\n-- En lo que sigue se usa la 2\u00aa definici\u00f3n\nsumaAlterna :: Integer -> Integer\nsumaAlterna = sumaAlterna2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Definir la funci\u00f3n\n--    conSumaAlternaPrima :: [Integer]\n-- tal que conSumaAlternaPrima es la sucesi\u00f3n de los n\u00fameros cuya suma\n-- alterna de factoriales es prima. Por ejemplo, \n--    \u03bb> take 8 conSumaAlternaPrima\n--    [3,4,5,6,7,8,10,15]\n-- ---------------------------------------------------------------------\n\nconSumaAlternaPrima :: [Integer]\nconSumaAlternaPrima =\n  [n | n <- [0..], isPrime (sumaAlterna n)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Los \u00e1rboles se pueden representar mediante el siguiente\n-- tipo de datos \n--    data Arbol a = N a [Arbol a]\n--                   deriving Show\n-- Por ejemplo, los \u00e1rboles\n--      1               3\n--     \/ \\             \/|\\ \n--    6   3           \/ | \\\n--        |          5  4  7\n--        5          |     \/\\ \n--                   6    2  1\n-- se representan por\n--    ej1, ej2 :: Arbol Int\n--    ej1 = N 1 [N 6 [],N 3 [N 5 []]]\n--    ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]\n-- \n-- Definir la funci\u00f3n\n--    emparejaArboles :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c\n-- tal que (emparejaArboles f a1 a2) es el \u00e1rbol obtenido aplicando la\n-- funci\u00f3n f a los elementos de los \u00e1rboles a1 y a2 que se encuentran en\n-- la misma posici\u00f3n. Por ejemplo,\n--    ghci> emparejaArboles (+) (N 1 [N 2 [], N 3[]]) (N 1 [N 6 []])\n--    N 2 [N 8 []]\n--    ghci> emparejaArboles (+) ej1 ej2\n--    N 4 [N 11 [],N 7 []]\n--    ghci> emparejaArboles2 (*) ej1 ej2\n--    N 3 [N 30 [],N 12 []]\n-- ---------------------------------------------------------------------\n\ndata Arbol a = N a [Arbol a]\n  deriving (Show, Eq)\n\nej1, ej2 :: Arbol Int\nej1 = N 1 [N 6 [],N 3 [N 5 []]]\nej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]\n\n-- 1\u00aa soluci\u00f3n\nemparejaArboles :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c\nemparejaArboles f (N x l1) (N y l2) = \n  N (f x y) (zipWith (emparejaArboles f) l1 l2)\n\n-- 2\u00aa soluci\u00f3n\nemparejaArboles2 :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c\nemparejaArboles2 f (N x l1) (N y l2) = \n  N (f x y) [emparejaArboles f xs ys | (xs,ys) <- zip l1 l2]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 3\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":[331],"tags":[],"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\/7008"}],"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=7008"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7008\/revisions"}],"predecessor-version":[{"id":7010,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7008\/revisions\/7010"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7008"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7008"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7008"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}