{"id":4751,"date":"2015-01-23T16:16:12","date_gmt":"2015-01-23T15:16:12","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4751"},"modified":"2015-02-01T11:17:36","modified_gmt":"2015-02-01T10:17:36","slug":"i1m2014-3o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-3o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2014: 3\u00ba examen de programaci\u00f3n 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-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: 3\u00ba examen de evaluaci\u00f3n continua (23 de enero de 2015)\n-- ---------------------------------------------------------------------\n\nimport Data.List \nimport Data.Array\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    divisiblesPorAlguno :: [Int] -> [Int]\n-- tal que (divisiblesPorAlguno xs) es la lista de los n\u00fameros que son\n-- divisibles por alg\u00fan elemento de xs. Por ejemplo, \n--    take 10 (divisiblesPorAlguno [2,3])    ==  [2,3,4,6,8,9,10,12,14,15]\n--    take 10 (divisiblesPorAlguno [2,4,3])  ==  [2,3,4,6,8,9,10,12,14,15]\n--    take 10 (divisiblesPorAlguno [2,5,3])  ==  [2,3,4,5,6,8,9,10,12,14]\n-- ---------------------------------------------------------------------\n\ndivisiblesPorAlguno :: [Int] -> [Int]\ndivisiblesPorAlguno xs = [n | n <- [1..], divisiblePorAlguno xs n]\n\n-- 1\u00aa definici\u00f3n (con any)\ndivisiblePorAlguno :: [Int] -> Int -> Bool\ndivisiblePorAlguno xs n = any (\\x -> n `mod` x == 0) xs\n\n-- 2\u00aa definici\u00f3n (por comprensi\u00f3n)\ndivisiblePorAlguno1 :: [Int] -> Int -> Bool\ndivisiblePorAlguno1 xs n = or [n `mod` x == 0 | x <- xs]\n\n-- 3\u00aa definici\u00f3n (por recursi\u00f3n)\ndivisiblePorAlguno2 :: [Int] -> Int -> Bool\ndivisiblePorAlguno2 [] _     = False\ndivisiblePorAlguno2 (x:xs) n = n `mod` x == 0 || divisiblePorAlguno2 xs n\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Las matrices pueden representarse mediante tablas cuyos\n-- \u00edndices son pares de n\u00fameros naturales:    \n--    type Matriz = Array (Int,Int) Int\n--\n-- Definir la funci\u00f3n \n--    ampliada :: Matriz -> Matriz\n-- tal que (ampliada p) es la matriz obtenida ampliando p a\u00f1adi\u00e9ndole\n-- al final una columna con la suma de los elementos de cada fila y\n-- a\u00f1adi\u00e9ndole al final una fila con la suma de los elementos de cada\n-- columna. Por ejemplo, al ampliar las matrices\n--    |1 2 3|      |1 2|\n--    |4 5 6|      |3 4|\n--                 |5 6|\n-- se obtienen, respectivamente\n--    |1 2 3  6|   |1  2  3|\n--    |4 5 6 15|   |3  4  7|\n--    |5 7 9 21|   |5  6 11|\n--                 |9 12 21|\n-- En Haskell,\n--    ghci> ampliada (listArray ((1,1),(2,3)) [1,2,3, 4,5,6])\n--    array ((1,1),(3,4)) [((1,1),1),((1,2),2),((1,3),3),((1,4),6),\n--                         ((2,1),4),((2,2),5),((2,3),6),((2,4),15),\n--                         ((3,1),5),((3,2),7),((3,3),9),((3,4),21)]\n--    ghci> ampliada (listArray ((1,1),(3,2)) [1,2, 3,4, 5,6])\n--    array ((1,1),(4,3)) [((1,1),1),((1,2),2),((1,3),3),\n--                         ((2,1),3),((2,2),4),((2,3),7),\n--                         ((3,1),5),((3,2),6),((3,3),11),\n--                         ((4,1),9),((4,2),12),((4,3),21)]\n-- ---------------------------------------------------------------------\n\ntype Matriz = Array (Int,Int) Int\n\nampliada :: Matriz -> Matriz\nampliada p = array ((1,1),(m+1,n+1)) \n                   [((i,j),f i j) | i <- [1..m+1], j <- [1..n+1]]\n    where \n      (_,(m,n)) = bounds p\n      f i j | i <= m   &#038;&#038; j <= n   = p ! (i,j)\n            | i <= m   &#038;&#038; j == n+1 = sum [p!(i,j) | j <- [1..n]]\n            | i == m+1 &#038;&#038; j <= n   = sum [p!(i,j) | i <- [1..m]]\n            | i == m+1 &#038;&#038; j == n+1 = sum [p!(i,j) | i <- [1..m], j <- [1..n]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. El siguiente tipo de dato representa expresiones\n-- construidas con variables, sumas y productos\n--    data Expr = Var String\n--              | S Expr Expr\n--              | P Expr Expre\n--              deriving (Eq, Show)\n-- Por ejemplo, x*(y+z) se representa por (P (V \"x\") (S (V \"y\") (V \"z\"))) \n-- \n-- Una expresi\u00f3n est\u00e1 en forma normal si es una suma de t\u00e9rminos. Por\n-- ejemplo, x*(y*z) y x+(y*z) est\u00e1 en forma normal; pero x*(y+z) y\n-- (x+y)*(x+z) no lo est\u00e1n. \n-- \n-- Definir la funci\u00f3n \n--    normal :: Expr -> Expr\n-- tal que (normal e) es la forma normal de la expresi\u00f3n e obtenida\n-- aplicando, mientras que sea posible, las propiedades distributivas:\n--    (a+b)*c = a*c+b*c\n--    c*(a+b) = c*a+c*b\n-- Por ejemplo,\n--    ghci> normal (P (S (V \"x\") (V \"y\")) (V \"z\"))\n--    S (P (V \"x\") (V \"z\")) (P (V \"y\") (V \"z\"))\n--    ghci> normal (P (V \"z\") (S (V \"x\") (V \"y\")))\n--    S (P (V \"z\") (V \"x\")) (P (V \"z\") (V \"y\"))\n--    ghci> normal (P (S (V \"x\") (V \"y\")) (S (V \"u\") (V \"v\")))\n--    S (S (P (V \"x\") (V \"u\")) (P (V \"x\") (V \"v\"))) \n--      (S (P (V \"y\") (V \"u\")) (P (V \"y\") (V \"v\")))\n--    ghci> normal (S (P (V \"x\") (V \"y\")) (V \"z\"))\n--    S (P (V \"x\") (V \"y\")) (V \"z\")\n--    ghci> normal (V \"x\")\n--    V \"x\"\n-- ---------------------------------------------------------------------\n\ndata Expr = V String\n          | S Expr Expr\n          | P Expr Expr\n          deriving (Eq, Show)\n\nnormal :: Expr -> Expr\nnormal (V v)   = V v\nnormal (S a b) = S (normal a) (normal b)\nnormal (P a b) = p (normal a) (normal b)\n    where p (S a b) c = S (p a c) (p b c)\n          p a (S b c) = S (p a b) (p a c)\n          p a b       = P a b\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Los primeros n\u00fameros de Fibonacci son\n--    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...\n-- tales que los dos primeros son iguales a 1 y los siguientes se\n-- obtienen sumando los dos anteriores. \n-- \n-- El teorema de Zeckendorf establece que todo entero positivo n se\n-- puede representar, de manera \u00fanica, como la suma de n\u00fameros de\n-- Fibonacci no consecutivos decrecientes. Dicha suma se llama la\n-- representaci\u00f3n de Zeckendorf de n. Por ejemplo, la representaci\u00f3n de\n-- Zeckendorf de 100 es  \n--    100 = 89 + 8 + 3\n-- Hay otras formas de representar 100 como sumas de n\u00fameros de\n-- Fibonacci; por ejemplo,\n--    100 = 89 +  8 + 2 + 1\n--    100 = 55 + 34 + 8 + 3\n-- pero no son representaciones de Zeckendorf porque 1 y 2 son n\u00fameros\n-- de Fibonacci consecutivos, al igual que 34 y 55.\n-- \n-- Definir la funci\u00f3n\n--    zeckendorf :: Integer -> [Integer]\n-- tal que (zeckendorf n) es la representaci\u00f3n de Zeckendorf de n. Por\n-- ejemplo, \n--    zeckendorf 100       == [89,8,3]\n--    zeckendorf 2014      == [1597,377,34,5,1]\n--    zeckendorf 28656     == [17711,6765,2584,987,377,144,55,21,8,3,1]\n--    zeckendorf 14930396  == [14930352,34,8,2]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\nzeckendorf1 :: Integer -> [Integer]\nzeckendorf1 n = reverse (head (aux n (tail fibs)))\n    where aux 0 _ = [[]]\n          aux n (x:y:zs) \n              | x <= n     = [x:xs | xs <- aux (n-x) zs] ++ aux n (y:zs)\n              | otherwise  = []\n\n-- fibs es la sucesi\u00f3n de los n\u00fameros de Fibonacci. Por ejemplo,\n--    take 14 fibs  == [1,1,2,3,5,8,13,21,34,55,89,144,233,377]\nfibs :: [Integer]\nfibs = 1 : scanl (+) 1 fibs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\nzeckendorf2 :: Integer -> [Integer]\nzeckendorf2 n = aux n (reverse (takeWhile (<= n) fibs))\n    where aux 0 _ = []\n          aux n (x:xs) = x : aux (n-x) (dropWhile (>n-x) xs)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\nzeckendorf3 :: Integer -> [Integer]\nzeckendorf3 0 = []\nzeckendorf3 n = x : zeckendorf3 (n - x) \n    where x = last (takeWhile (<= n) fibs)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    ghci> zeckendorf1 300000\n--    [196418,75025,17711,6765,2584,987,377,89,34,8,2]\n--    (0.72 secs, 58478576 bytes)\n--    ghci> zeckendorf2 300000\n--    [196418,75025,17711,6765,2584,987,377,89,34,8,2]\n--    (0.00 secs, 517852 bytes)\n--    ghci> zeckendorf3 300000\n--    [196418,75025,17711,6765,2584,987,377,89,34,8,2]\n--    (0.00 secs, 515360 bytes)\n-- Se observa que las definiciones m\u00e1s eficientes son la 2\u00aa y la 3\u00aa.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    maximoIntercambio :: Int -> Int\n-- tal que (maximoIntercambio x) es el m\u00e1ximo n\u00famero que se puede\n-- obtener intercambiando dos d\u00edgitos de x. Por ejemplo, \n--    maximoIntercambio 983562  ==  986532\n--    maximoIntercambio 31524   ==  51324\n--    maximoIntercambio 897     ==  987\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\n-- =============\nmaximoIntercambio :: Int -> Int\nmaximoIntercambio = maximum . intercambios\n\n-- (intercambios x) es la lista de los n\u00fameros obtenidos intercambiando\n-- dos d\u00edgitos de x. Por ejemplo,\n--    intercambios 1234  ==  [2134,3214,4231,1324,1432,1243]\nintercambios :: Int -> [Int]\nintercambios x = [intercambio i j x | i <- [0..n-2], j <- [i+1..n-1]]\n    where n = length (show x)\n\n-- (intercambio i j x) es el n\u00famero obtenido intercambiando las cifras\n-- que ocupan las posiciones i y j (empezando a contar en cero) del\n-- n\u00famero x. Por ejemplo,\n--    intercambio 2 5 123456789  ==  126453789\nintercambio :: Int -> Int -> Int -> Int\nintercambio i j x = read (concat [as,[d],cs,[b],ds])\n    where xs        = show x\n          (as,b:bs) = splitAt i xs \n          (cs,d:ds) = splitAt (j-i-1) bs\n\n-- 2\u00aa definici\u00f3n (con vectores)\n-- ============================\n\nmaximoIntercambio2 :: Int -> Int\nmaximoIntercambio2 = read . elems . maximum . intercambios2\n\n-- (intercambios2 x) es la lista de los vectores obtenidos\n-- intercambiando dos elementos del vector de d\u00edgitos de x. Por ejemplo, \n--    ghci> intercambios2 1234\n--    [array (0,3) [(0,'2'),(1,'1'),(2,'3'),(3,'4')],\n--     array (0,3) [(0,'3'),(1,'2'),(2,'1'),(3,'4')],\n--     array (0,3) [(0,'4'),(1,'2'),(2,'3'),(3,'1')],\n--     array (0,3) [(0,'1'),(1,'3'),(2,'2'),(3,'4')],\n--     array (0,3) [(0,'1'),(1,'4'),(2,'3'),(3,'2')],\n--     array (0,3) [(0,'1'),(1,'2'),(2,'4'),(3,'3')]]\nintercambios2 :: Int -> [Array Int Char]\nintercambios2 x = [intercambioV i j v | i <- [0..n-2], j <- [i+1..n-1]]\n    where xs = show x\n          n  = length xs\n          v  = listArray (0,n-1) xs\n\n-- (intercambioV i j v) es el vector obtenido intercambiando los\n-- elementos de v que ocupan las posiciones i y j. Por ejemplo,\n--    ghci> intercambioV 2 4 (listArray (0,4) [3..8])\n--    array (0,4) [(0,3),(1,4),(2,7),(3,6),(4,5)]\nintercambioV i j v = v \/\/ [(i,v!j),(j,v!i)]\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":"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\/4751"}],"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=4751"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4751\/revisions"}],"predecessor-version":[{"id":4752,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4751\/revisions\/4752"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}