{"id":2085,"date":"2012-06-29T19:20:53","date_gmt":"2012-06-29T19:20:53","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2085"},"modified":"2013-03-08T05:48:14","modified_gmt":"2013-03-08T05:48:14","slug":"i1m2011-examen-final","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-examen-final\/","title":{"rendered":"I1M2011: Examen final"},"content":{"rendered":"<p>Hoy se ha realizado el examen de la convocatoria de julio 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 1\u00aa convocatoria (29 de junio de 2012)\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List\r\nimport Data.Array\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. [2 puntos] Definir la funci\u00f3n\r\n--    paresOrdenados :: [a] -> [(a,a)]\r\n-- tal que (paresOrdenados xs) es la lista de todos los pares de\r\n-- elementos (x,y) de xs, tales que x ocurren en xs antes que y. Por\r\n-- ejemplo,  \r\n--    paresOrdenados [3,2,5,4] == [(3,2),(3,5),(3,4),(2,5),(2,4),(5,4)]\r\n--    paresOrdenados [3,2,5,3] == [(3,2),(3,5),(3,3),(2,5),(2,3),(5,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa definici\u00f3n:\r\nparesOrdenados :: [a] -> [(a,a)]\r\nparesOrdenados []     = []\r\nparesOrdenados (x:xs) = [(x,y) | y <- xs] ++ paresOrdenados xs\r\n\r\n-- 2\u00aa definici\u00f3n:\r\nparesOrdenados2 :: [a] -> [(a,a)]\r\nparesOrdenados2 [] = []\r\nparesOrdenados2 (x:xs) = \r\n    foldr (\\y ac -> (x,y):ac) (paresOrdenados2 xs) xs\r\n\r\n-- 3\u00aa definici\u00f3n (con repeat):\r\nparesOrdenados3 :: [a] -> [(a,a)]\r\nparesOrdenados3 []     = []\r\nparesOrdenados3 (x:xs) = zip (repeat x) xs ++ paresOrdenados3 xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. [2 puntos] Definir la funci\u00f3n \r\n--    sumaDeDos :: Int -> [Int] -> Maybe (Int,Int)\r\n-- tal que (sumaDeDos x ys) decide si x puede expresarse como suma de\r\n-- dos elementos de ys y, en su caso, devuelve un par de elementos de ys\r\n-- cuya suma es x. Por ejemplo,\r\n--    sumaDeDos 9 [7,4,6,2,5]  ==  Just (7,2)\r\n--    sumaDeDos 5 [7,4,6,2,5]  ==  Nothing\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaDeDos :: Int -> [Int] -> Maybe (Int,Int)\r\nsumaDeDos _ []  =  Nothing\r\nsumaDeDos _ [_] =  Nothing\r\nsumaDeDos y (x:xs) | y-x `elem` xs = Just (x,y-x)\r\n                   | otherwise     = sumaDeDos y xs\r\n\r\n-- 2\u00aa definici\u00f3n (usando paresOrdenados):\r\nsumaDeDos2 :: Int -> [Int] -> Maybe (Int,Int)\r\nsumaDeDos2 x xs \r\n    | null ys   = Nothing\r\n    | otherwise = Just (head ys)\r\n    where ys = [(a,b) | (a,b) <- paresOrdenados xs , a+b == x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. [2 puntos] Definir la funci\u00f3n\r\n--    esProductoDeDosPrimos :: Int -> Bool\r\n-- tal que (esProductoDeDosPrimos n) se verifica si n es el producto de\r\n-- dos primos distintos. Por ejemplo,\r\n--    esProductoDeDosPrimos 6  ==  True\r\n--    esProductoDeDosPrimos 9  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesProductoDeDosPrimos :: Int -> Bool\r\nesProductoDeDosPrimos n =\r\n    [x | x <- primosN, \r\n         mod n x == 0, \r\n         div n x \/= x, \r\n         elem (div n x) primosN] \/= []\r\n    where primosN = takeWhile (<=n) primos\r\n\r\nprimos :: [Int]\r\nprimos = criba [2..]\r\n    where criba []     = []\r\n          criba (n:ns) = n : criba (elimina n ns)\r\n          elimina n xs = [x | x <- xs, x `mod` n \/= 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. [2 puntos] La expresiones aritm\u00e9ticas se pueden\r\n-- representar mediante el siguiente tipo \r\n--    data Expr = V Char \r\n--              | N Int \r\n--              | S Expr Expr\r\n--              | P Expr Expr\r\n--              deriving Show\r\n-- por ejemplo, representa la expresi\u00f3n \"z*(3+x)\" se representa por\r\n-- (P (V 'z') (S (N 3) (V 'x'))). \r\n--\r\n-- Definir la funci\u00f3n\r\n--    sustitucion :: Expr -> [(Char, Int)] -> Expr\r\n-- tal que (sustitucion e s) es la expresi\u00f3n obtenida sustituyendo las\r\n-- variables de la expresi\u00f3n e seg\u00fan se indica en la sustituci\u00f3n s. Por\r\n-- ejemplo, \r\n--    ghci> sustitucion (P (V 'z') (S (N 3) (V 'x'))) [('x',7),('z',9)]\r\n--    P (N 9) (S (N 3) (N 7))\r\n--    ghci> sustitucion (P (V 'z') (S (N 3) (V 'y'))) [('x',7),('z',9)]\r\n--    P (N 9) (S (N 3) (V 'y'))\r\n-- ---------------------------------------------------------------------\r\n                   \r\ndata Expr = V Char \r\n          | N Int \r\n          | S Expr Expr\r\n          | P Expr Expr\r\n          deriving Show\r\n\r\nsustitucion :: Expr -> [(Char, Int)] -> Expr\r\nsustitucion e [] = e\r\nsustitucion (V c) ((d,n):ps) | c == d = N n\r\n                             | otherwise = sustitucion (V c) ps\r\nsustitucion (N n) _ = N n                                 \r\nsustitucion (S e1 e2) ps = S (sustitucion e1 ps) (sustitucion e2 ps)\r\nsustitucion (P e1 e2) ps = P (sustitucion e1 ps) (sustitucion e2 ps)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. [2 puntos] (Problema 345 del proyecto Euler) Las\r\n-- matrices puede representarse mediante tablas cuyos \u00edndices son pares\r\n-- de n\u00fameros naturales:   \r\n--    type Matriz = Array (Int,Int) Int\r\n-- Definir la funci\u00f3n \r\n--    maximaSuma :: Matriz -> Int\r\n-- tal que (maximaSuma p) es el m\u00e1ximo de las sumas de las listas de\r\n-- elementos de la matriz p tales que cada elemento pertenece s\u00f3lo a una\r\n-- fila y a una columna. Por ejemplo, \r\n--    ghci> maximaSuma (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])\r\n--    17\r\n-- ya que las selecciones, y sus sumas, de la matriz\r\n--    |1 2 3|\r\n--    |8 4 9|\r\n--    |5 6 7|\r\n-- son\r\n--    [1,4,7] --> 12\r\n--    [1,9,6] --> 16\r\n--    [2,8,7] --> 17\r\n--    [2,9,5] --> 16\r\n--    [3,8,6] --> 17\r\n--    [3,4,5] --> 12\r\n-- Hay dos selecciones con m\u00e1xima suma: [2,8,7] y [3,8,6].\r\n-- ---------------------------------------------------------------------\r\n\r\ntype Matriz = Array (Int,Int) Int\r\n\r\nmaximaSuma :: Matriz -> Int\r\nmaximaSuma p = maximum [sum xs | xs <- selecciones p]\r\n\r\n-- (selecciones p) es la lista de las selecciones en las que cada\r\n-- elemento pertenece a un \u00fanica fila y a una \u00fanica columna de la matriz\r\n-- p. Por ejemplo,\r\n--    ghci> selecciones (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])\r\n--    [[1,4,7],[2,8,7],[3,4,5],[2,9,5],[3,8,6],[1,9,6]]\r\nselecciones :: Matriz -> [[Int]]\r\nselecciones p = \r\n    [[p!(i,j) | (i,j) <- ijs] | \r\n     ijs <- [zip [1..n] xs | xs <- permutations [1..n]]] \r\n    where (_,(m,n)) = bounds p\r\n\r\n-- Nota: En la anterior definici\u00f3n se ha usado la funci\u00f3n pernutations\r\n-- de Data.List. Tambi\u00e9n se puede definir mediante\r\npermutaciones :: [a] -> [[a]]\r\npermutaciones []     = [[]]\r\npermutaciones (x:xs) = \r\n    concat [intercala x ys | ys <- permutaciones xs]\r\n\r\n-- (intercala x ys) es la lista de las listas obtenidas intercalando x\r\n-- entre los elementos de ys. Por ejemplo, \r\n--    intercala 1 [2,3]  ==  [[1,2,3],[2,1,3],[2,3,1]]\r\nintercala :: a -> [a] -> [[a]]\r\nintercala x [] = [[x]]\r\nintercala x (y:ys) = (x:y:ys) : [y:zs | zs <- intercala x ys]\r\n\r\n-- 2\u00aa soluci\u00f3n (mediante submatrices):\r\nmaximaSuma2 :: Matriz -> Int\r\nmaximaSuma2 p \r\n    | (m,n) == (1,1) = p!(1,1)\r\n    | otherwise = maximum [p!(1,j) + maximaSuma2 (submatriz 1 j p) | j <- [1..n]]\r\n    where (m,n) = dimension p\r\n\r\n-- (dimension p) es la dimensi\u00f3n de la matriz p.\r\ndimension :: Matriz -> (Int,Int)\r\ndimension = snd . bounds\r\n\r\n-- (submatriz i j p) es la matriz obtenida a partir de la p eliminando\r\n-- la fila i y la columna j. Por ejemplo, \r\n--    ghci> submatriz 2 3 (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])\r\n--    array ((1,1),(2,2)) [((1,1),1),((1,2),2),((2,1),5),((2,2),6)]\r\nsubmatriz :: Int -> Int -> Matriz -> Matriz\r\nsubmatriz i j p = \r\n    array ((1,1), (m-1,n -1))\r\n          [((k,l), p ! f k l) | k <- [1..m-1], l <- [1.. n-1]]\r\n    where (m,n) = dimension p\r\n          f k l | k < i  &#038;&#038; l < j  = (k,l)\r\n                | k >= i && l < j  = (k+1,l)\r\n                | k < i  &#038;&#038; l >= j = (k,l+1)\r\n                | otherwise        = (k+1,l+1)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el examen de la convocatoria de julio 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\/2085"}],"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=2085"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2085\/revisions"}],"predecessor-version":[{"id":2808,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2085\/revisions\/2808"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2085"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2085"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2085"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}