{"id":2179,"date":"2012-09-10T17:00:14","date_gmt":"2012-09-10T17:00:14","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2179"},"modified":"2013-03-08T05:48:12","modified_gmt":"2013-03-08T05:48:12","slug":"i1m2011-examen-de-septiembre","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-examen-de-septiembre\/","title":{"rendered":"I1M2011: Examen de septiembre"},"content":{"rendered":"<p>Hoy se ha realizado el examen de la convocatoria de septiembre de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> <\/p>\n<p>\nA continuaci\u00f3n se muestra el examen junto con su soluci\u00f3n:<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- Inform\u00e1tica (1\u00ba del Grado en Matem\u00e1ticas)\r\n-- Examen de la convocatoria de Septiembre (10 de septiembre de 2012)\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.Array\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. [1.7 puntos] El enunciado de uno de los problemas de la\r\n-- IMO de 1966 es\r\n--    Calcular el n\u00famero de maneras de obtener 500 coomo suma de n\u00fameros\r\n--    naturales consecutivos.\r\n-- Definir la funci\u00f3n\r\n--    sucesionesConSuma :: Int -> [(Int,Int)]\r\n-- tal que (sucesionesConSuma n) es la lista de las sucesiones de\r\n-- n\u00fameros naturales consecutivos con suma n. Por ejemplo,\r\n--    sucesionesConSuma 15  == [(1,5),(4,6),(7,8),(15,15)]\r\n-- ya que 15 = 1+2+3+4+5 = 4+5+6 = 7+8 = 15.\r\n--\r\n-- Calcular la soluci\u00f3n del problema usando sucesionesConSuma. \r\n-- ---------------------------------------------------------------------\r\n\r\nsucesionesConSuma :: Int -> [(Int,Int)]\r\nsucesionesConSuma n =\r\n    [(x,y) | y <- [1..n], x <- [1..y], sum [x..y] == n]\r\n\r\n-- La soluci\u00f3n del problema es\r\n--    ghci> length (sucesionesConSuma 500)\r\n--    4\r\n\r\n-- Otra definci\u00f3n, usando la f\u00f3rmula de la suma es\r\nsucesionesConSuma2 :: Int -> [(Int,Int)]\r\nsucesionesConSuma2 n = \r\n    [(x,y) | y <- [1..n], x <- [1..y], (x+y)*(y-x+1) == 2*n]\r\n\r\n-- La 2\u00aa definici\u00f3n es m\u00e1s eficiente\r\n--    ghci> :set +s\r\n--    ghci> sucesionesConSuma 500\r\n--    [(8,32),(59,66),(98,102),(500,500)]\r\n--    (1.47 secs, 1452551760 bytes)\r\n--    ghci> sucesionesConSuma2 500\r\n--    [(8,32),(59,66),(98,102),(500,500)]\r\n--    (0.31 secs, 31791148 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2 [1.7 puntos] Definir la funci\u00f3n\r\n--    inversiones :: Ord a => [a] -> [(a,Int)]\r\n-- tal que (inversiones xs) es la lista de pares formados por los\r\n-- elementos x de xs junto con el n\u00famero de elementos de xs que aparecen\r\n-- a la derecha de x y son mayores que x. Por ejemplo,\r\n--    inversiones [7,4,8,9,6]  == [(7,2),(4,3),(8,1),(9,0),(6,0)]\r\n-- ---------------------------------------------------------------------\r\n\r\ninversiones :: Ord a => [a] -> [(a,Int)]\r\ninversiones []     = []\r\ninversiones (x:xs) = (x,length (filter (>x) xs)) : inversiones xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3 [1.7 puntos] Se considera el siguiente procedimiento de\r\n-- reducci\u00f3n de listas: Se busca un par de elementos consecutivos\r\n-- iguales pero con signos opuestos, se eliminan dichos elementos y se\r\n-- contin\u00faa el proceso hasta que no se encuentren pares de elementos\r\n-- consecutivos iguales pero con signos opuestos. Por ejemplo, la\r\n-- reducci\u00f3n de [-2,1,-1,2,3,4,-3] es\r\n--    [-2,1,-1,2,3,4,-3]    (se elimina el par (1,-1))\r\n--    -> [-2,2,3,4,-3]      (se elimina el par (-2,2))\r\n--    -> [3,4,-3]           (el par (3,-3) no son consecutivos)\r\n-- Definir la funci\u00f3n\r\n--    reducida :: [Int] -> [Int]\r\n-- tal que (reducida xs) es la lista obtenida aplicando a xs el proceso\r\n-- de eliminaci\u00f3n de pares de elementos consecutivos opuestos. Por\r\n-- ejemplo,\r\n--    reducida [-2,1,-1,2,3,4,-3]           == [3,4,-3]\r\n--    reducida [-2,1,-1,2,3,-4,4,-3]        == []\r\n--    reducida [-2,1,-1,2,5,3,-4,4,-3]      == [5]\r\n--    reducida [-2,1,-1,2,5,3,-4,4,-3,-5]   == []\r\n-- ---------------------------------------------------------------------\r\n\r\npaso :: [Int] -> [Int]\r\npaso [] = []\r\npaso [x] = [x]\r\npaso (x:y:zs) | x == -y   = paso zs\r\n              | otherwise = x : paso (y:zs)\r\n\r\nreducida :: [Int] -> [Int]\r\nreducida xs | xs == ys  = xs\r\n            | otherwise = reducida ys\r\n            where ys = paso xs\r\n\r\nreducida2 :: [Int] -> [Int]\r\nreducida2 xs = aux xs []\r\n    where aux [] ys                   = reverse ys\r\n          aux (x:xs) (y:ys) | x == -y = aux xs ys\r\n          aux (x:xs) ys               = aux xs (x:ys)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. [1.7 puntos] Las variaciones con repetici\u00f3n de una lista\r\n-- xs se puede ordenar por su longitud y las de la misma longitud\r\n-- lexicogr\u00e1ficamente. Por ejemplo, las variaciones con repetici\u00f3n de\r\n-- \"ab\" son\r\n--    \"\",\"a\",\"b\",\"aa\",\"ab\",\"ba\",\"bb\",\"aaa\",\"aab\",\"aba\",\"abb\",\"baa\",...\r\n-- y las de \"abc\" son\r\n--    \"\",\"a\",\"b\",\"c\",\"aa\",\"ab\",\"ac\",\"ba\",\"bb\",\"bc\",\"ca\",\"cb\",...\r\n-- Definir la funci\u00f3n \r\n--    posicion :: Eq a => [a] -> [a] -> Int\r\n-- tal que (posicion xs ys) es posici\u00f3n de xs en la lista ordenada de\r\n-- las variaciones con repetici\u00f3n de los elementos de ys. Por ejemplo,\r\n--    posicion \"ba\" \"ab\"       == 5\r\n--    posicion \"ba\" \"abc\"      == 7\r\n--    posicion \"abccba\" \"abc\"  == 520\r\n-- ---------------------------------------------------------------------\r\n\r\nposicion :: Eq a => [a] -> [a] -> Int\r\nposicion xs ys =\r\n    length (takeWhile (\/=xs) (variaciones ys))\r\n\r\nvariaciones :: [a] -> [[a]]\r\nvariaciones xs = concat aux  \r\n    where aux = [[]] : [[x:ys | x <- xs, ys <- yss] | yss <- aux] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. [1.6 puntos] Un \u00e1rbol ordenado es un \u00e1rbol binario tal\r\n-- que para cada nodo, los elementos de su sub\u00e1rbol izquierdo son\r\n-- menores y los de su sub\u00e1rbol derecho son mayores. Por ejemplo,\r\n--         5\r\n--        \/ \\\r\n--       \/   \\\r\n--      3     7\r\n--     \/ \\   \/ \\\r\n--    1   4 6   9 \r\n-- El tipo de los \u00e1rboles binarios se define por\r\n--    data Arbol = H Int\r\n--               | N Int Arbol Arbol\r\n-- con lo que el ejemplo anterior se define por\r\n--    ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))\r\n-- Definir la funci\u00f3n\r\n--    ancestroMasProximo :: Int -> Int -> Int\r\n-- tal que (ancestroMasProximo x y a) es el ancestro m\u00e1s pr\u00f3ximo de los\r\n-- nodos x e y en el \u00e1rbol a. Por ejemplo, \r\n--    ancestroMasProximo 4 1 ejArbol  == 3\r\n--    ancestroMasProximo 4 6 ejArbol  == 5\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Arbol = H Int\r\n           | N Int Arbol Arbol\r\n\r\nejArbol :: Arbol\r\nejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))\r\n\r\nancestroMasProximo :: Int -> Int -> Arbol -> Int\r\nancestroMasProximo x y (N z i d)\r\n    | x < z &#038;&#038; y < z = ancestroMasProximo x y i\r\n    | x > z && y > z = ancestroMasProximo x y d\r\n    | otherwise      = z\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. [1.6 puntos] Las matrices puede representarse mediante\r\n-- tablas cuyos \u00edndices son pares de n\u00fameros naturales:   \r\n--    type Matriz = Array (Int,Int) Int\r\n-- Definir la funci\u00f3n \r\n--    maximos :: Matriz -> [Int]\r\n-- tal que (maximos p) es la lista de los m\u00e1ximos locales de la matriz\r\n-- p; es decir de los elementos de p que son mayores que todos sus\r\n-- vecinos. Por ejemplo,  \r\n--    ghci> maximos (listArray ((1,1),(3,4)) [9,4,6,5,8,1,7,3,0,2,5,4])\r\n--    [9,7]\r\n-- ya que los m\u00e1ximos locales de la matriz\r\n--    |9 4 6 5|\r\n--    |8 1 7 3|\r\n--    |0 2 5 4|\r\n-- son 9 y 7.\r\n-- ---------------------------------------------------------------------\r\n\r\ntype Matriz = Array (Int,Int) Int\r\n\r\nmaximos :: Matriz -> [Int]\r\nmaximos p = \r\n    [p!(i,j) | (i,j) <- indices p,\r\n               and [p!(a,b) < p!(i,j) | (a,b) <- vecinos (i,j)]] \r\n    where (_,(m,n)) = bounds p\r\n          vecinos (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],\r\n                                   b <- [max 1 (j-1)..min n (j+1)],\r\n                                   (a,b) \/= (i,j)]\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el examen de la convocatoria de septiembre de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas A continuaci\u00f3n se muestra el examen junto con su soluci\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":[186],"tags":[295],"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\/2179"}],"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=2179"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2179\/revisions"}],"predecessor-version":[{"id":2779,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2179\/revisions\/2779"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}