{"id":4354,"date":"2014-07-04T21:46:32","date_gmt":"2014-07-04T19:46:32","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4354"},"modified":"2014-07-06T21:47:32","modified_gmt":"2014-07-06T19:47:32","slug":"i1m2013-examen-de-la-1a-convocatoria","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-examen-de-la-1a-convocatoria\/","title":{"rendered":"I1M2013: Examen de la 1\u00aa convocatoria"},"content":{"rendered":"<p>Hoy se ha realizado el examen de la 1\u00aa convocatoria del curso <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica<\/a> (de 1\u00ba de Grado en Matem\u00e1ticas). A continuaci\u00f3n se muestran los ejercicios y sus soluciones.<\/p>\n<p><!--more--><\/p>\n<pre lang=\"haskell\">\n-- Inform\u00e1tica: Examen de la 1\u00aa convocatoria (4 de julio de 2014)\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.List\nimport Data.Array\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. [2 puntos] Una lista de longitud n > 0 es completa si el\n-- valor absoluto de las diferencias de sus elementos consecutivos toma\n-- todos los valores entre 1 y n-1 (s\u00f3lo una vez). Por ejemplo,\n-- [4,1,2,4] es completa porque los valores absolutos de las diferencias\n-- de sus elementos consecutivos es [3,1,2]. \n--\n-- Definir la funci\u00f3n\n--    esCompleta :: [Int] -> Bool\n-- tal que (esCompleta xs) se verifica si xs es completa. Por ejemplo,\n--    esCompleta [4,1,2,4]  ==  True\n--    esCompleta [6]        ==  True\n--    esCompleta [6,7]      ==  True\n--    esCompleta [6,8]      ==  False\n--    esCompleta [6,7,9]    ==  True\n--    esCompleta [8,7,5]    ==  True\n-- ---------------------------------------------------------------------\n\nesCompleta :: [Int] -> Bool\nesCompleta xs = \n    sort [abs (x-y) | (x,y) <- zip xs (tail xs)] == [1..length xs - 1]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n \n--    unionG :: Ord a => [[a]] -> [a]\n-- tal que (unionG xss) es la uni\u00f3n de xss cuyos elementos son listas\n-- estrictamente crecientes (posiblemente infinitas). Por ejemplo,\n--    ghci> take 10 (unionG [[2,4..],[3,6..],[5,10..]])\n--    [2,3,4,5,6,8,9,10,12,14]\n--    ghci> take 10 (unionG [[2,5..],[3,8..],[4,10..],[16..]])\n--    [2,3,4,5,8,10,11,13,14,16]\n--    ghci> unionG [[3,8],[4,10],[2,5],[16]]\n--    [2,3,4,5,8,10,16]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\nunionG1 :: Ord a => [[a]] -> [a]\nunionG1 []          = []\nunionG1 [xs]        = xs\nunionG1 (xs:ys:zss) = xs `unionB` unionG1 (ys:zss)\n\nunionB :: Ord a => [a] -> [a] -> [a]\nunionB [] ys = ys\nunionB xs [] = xs\nunionB (x:xs) (y:ys) | x < y     = x : unionB xs (y:ys)\n                     | x > y     = y : unionB (x:xs) ys\n                     | otherwise = x : unionB xs ys\n\n-- 2\u00aa definici\u00f3n (por plegado)\n-- ===========================\nunionG2 :: Ord a => [[a]] -> [a]\nunionG2 = foldr unionB []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. [2 puntos] Definir la funci\u00f3n\n--    noEsSuma :: [Integer] -> Integer\n-- tal que (noEsSuma xs) es el menor entero positivo que no se puede\n-- expresar como suma de elementos de la lista creciente de n\u00fameros\n-- positivos xs (ning\u00fan elemento se puede usar m\u00e1s de una vez). Por\n-- ejemplo, \n--    noEsSuma [1,2,3,8]      ==  7\n--    noEsSuma (1:[2,4..10])  ==  32\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\nnoEsSuma1 :: [Integer] -> Integer\nnoEsSuma1 xs = head [n | n <- [1..], n `notElem` sumas1 xs]\n\n-- (sumas1 xs) es la lista de las sumas con los elementos de xs, donde\n-- cada elemento se puede sumar como m\u00e1ximo una vez. Por ejemplo,\n--    sumas1 [3,8]      ==  [11,3,8,0]\n--    sumas1 [3,8,17]   ==  [28,11,20,3,25,8,17,0]\n--    sumas1 [1,2,3,8]  ==  [14,6,11,3,12,4,9,1,13,5,10,2,11,3,8,0]\nsumas1 :: [Integer] -> [Integer]\nsumas1 [] = [0]\nsumas1 (x:xs) = [x+y | y <- ys] ++ ys\n    where ys = sumas1 xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\nnoEsSuma2 :: [Integer] -> Integer\nnoEsSuma2 xs = head [n | n <- [1..], not (esSuma n xs)]\n\nesSuma :: Integer -> [Integer] -> Bool\nesSuma n [] = n == 0\nesSuma n (x:xs) | n < x     = False\n                | n == x    = True\n                | otherwise = esSuma (n-x) xs || esSuma n xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\nnoEsSuma3 :: [Integer] -> Integer\nnoEsSuma3 xs = aux xs 0\n    where aux [] n     = n+1\n          aux (x:xs) n | x <= n+1  = aux xs (n+x)\n                       | otherwise = n+1\n\n-- Comparaciones de eficiencia\n-- ===========================\n\n-- Las comparaciones son\n--    ghci> noEsSuma1 ([1..10]++[12..20])\n--    200\n--    (8.28 secs, 946961604 bytes)\n--    ghci> noEsSuma2 ([1..10]++[12..20])\n--    200\n--    (2.52 secs, 204156056 bytes)\n--    ghci> noEsSuma3 ([1..10]++[12..20])\n--    200\n--    (0.01 secs, 520348 bytes)\n--\n--    ghci> noEsSuma2 (1:[2,4..30])\n--    242\n--    (4.97 secs, 399205788 bytes)\n--    ghci> noEsSuma3 (1:[2,4..30])\n--    242\n--    (0.01 secs, 514340 bytes)\n-- \n--    ghci> noEsSuma3 (1:[2,4..2014])\n--    1015058\n--    (0.01 secs, 1063600 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. [2 puntos] Los divisores medios de un n\u00famero son los que\n-- ocupan la posici\u00f3n media entre los divisores de n, ordenados de menor\n-- a mayor. Por ejemplo, los divisores de 60 son\n-- [1,2,3,4,5,6,10,12,15,20,30,60] y sus divisores medios son 6 y 10.\n-- \n-- El \u00e1rbol de factorizaci\u00f3n de un n\u00famero compuesto n se construye de la\n-- siguiente manera: \n--    * la ra\u00edz es el n\u00famero n, \n--    * la rama izquierda es el \u00e1rbol de factorizaci\u00f3n de su divisor\n--      medio menor y\n--    * la rama derecha es el \u00e1rbol de factorizaci\u00f3n de su divisor\n--      medio mayor\n-- Si el n\u00famero es primo, su \u00e1rbol de factorizaci\u00f3n s\u00f3lo tiene una hoja\n-- con dicho n\u00famero. Por ejemplo, el \u00e1rbol de factorizaci\u00f3n de 60 es\n--        60\n--       \/  \\\n--      6    10\n--     \/ \\   \/ \\\n--    2   3 2   5\n--\n-- Los \u00e1rboles se representar\u00e1n por\n--    data Arbol = H Int\n--               | N Int Arbol Arbol\n--               deriving Show\n--\n-- Definir la funci\u00f3n\n--    arbolFactorizacion :: Int -> Arbol\n-- tal que (arbolFactorizacion n) es el \u00e1rbol de factorizaci\u00f3n de n. Por\n-- ejemplo, \n--    ghci> arbolFactorizacion 60\n--    N 60 (N 6 (H 2) (H 3)) (N 10 (H 2) (H 5))\n--    ghci> arbolFactorizacion 45\n--    N 45 (H 5) (N 9 (H 3) (H 3))\n--    ghci> arbolFactorizacion 7\n--    H 7\n--    ghci> arbolFactorizacion 14\n--    N 14 (H 2) (H 7)\n--    ghci> arbolFactorizacion 28\n--    N 28 (N 4 (H 2) (H 2)) (H 7)\n--    ghci> arbolFactorizacion 84\n--    N 84 (H 7) (N 12 (H 3) (N 4 (H 2) (H 2)))\n-- ---------------------------------------------------------------------\n\ndata Arbol = H Int\n           | N Int Arbol Arbol\n           deriving Show\n\n-- 1\u00aa definici\u00f3n\n-- =============\narbolFactorizacion :: Int -> Arbol\narbolFactorizacion n \n    | esPrimo n = H n\n    | otherwise = N n (arbolFactorizacion x) (arbolFactorizacion y)\n    where (x,y) = divisoresMedio n\n\n-- (esPrimo n) se verifica si n es primo. Por ejemplo,\n--    esPrimo 7  ==  True\n--    esPrimo 9  ==  False\nesPrimo :: Int -> Bool\nesPrimo n = divisores n == [1,n]\n\n-- (divisoresMedio n) es el par formado por los divisores medios de\n-- n. Por ejemplo,\n--    divisoresMedio 30  ==  (5,6)\n--    divisoresMedio  7  ==  (1,7)\ndivisoresMedio :: Int -> (Int,Int)\ndivisoresMedio n = (n `div` x,x)\n    where xs = divisores n\n          x  = xs !! (length xs `div` 2)\n\n-- (divisores n) es la lista de los divisores de n. Por ejemplo,\n--    divisores 30  ==  [1,2,3,5,6,10,15,30]\ndivisores :: Int -> [Int]\ndivisores n = [x | x <- [1..n], n `rem` x == 0]\n\n-- 2\u00aa definici\u00f3n\n-- =============\narbolFactorizacion2 :: Int -> Arbol\narbolFactorizacion2 n\n    | x == 1    = H n\n    | otherwise = N n (arbolFactorizacion x) (arbolFactorizacion y)\n    where (x,y) = divisoresMedio n\n\n-- (divisoresMedio2 n) es el par formado por los divisores medios de\n-- n. Por ejemplo,\n--    divisoresMedio2 30  ==  (5,6)\n--    divisoresMedio2  7  ==  (1,7)\ndivisoresMedio2 :: Int -> (Int,Int)\ndivisoresMedio2 n = (n `div` x,x)\n    where m  = ceiling (sqrt (fromIntegral n))\n          x = head [y | y <- [m..n], n `rem` y == 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. [2 puntos] El tri\u00e1ngulo de Pascal es un tri\u00e1ngulo de\n-- n\u00fameros \n--          1\n--         1 1\n--        1 2 1\n--      1  3 3  1\n--     1 4  6  4 1\n--    1 5 10 10 5 1\n--   ...............\n-- construido de la siguiente forma\n-- * la primera fila est\u00e1 formada por el n\u00famero 1;\n-- * las filas siguientes se construyen sumando los n\u00fameros adyacentes\n--   de la fila superior y a\u00f1adiendo un 1 al principio y al final de la\n--   fila. \n--\n-- La matriz de Pascal es la matriz cuyas filas son los elementos de la\n-- correspondiente fila del tri\u00e1ngulo de Pascal completadas con\n-- ceros. Por ejemplo, la matriz de Pascal de orden 6 es\n--    |1 0  0  0 0 0|\n--    |1 1  0  0 0 0|\n--    |1 2  1  0 0 0|\n--    |1 3  3  1 0 0|\n--    |1 4  6  4 1 0|\n--    |1 5 10 10 5 1|\n-- \n-- Las matrices se definen mediante el tipo\n--    type Matriz = Array (Int,Int) Int\n--\n-- Definir la funci\u00f3n\n--    matrizPascal :: Int -> Matriz \n-- tal que (matrizPascal n) es la matriz de Pascal de orden n. Por\n-- ejemplo, \n--    ghci> matrizPascal 5\n--    array ((1,1),(5,5)) \n--          [((1,1),1),((1,2),0),((1,3),0),((1,4),0),((1,5),0),\n--           ((2,1),1),((2,2),1),((2,3),0),((2,4),0),((2,5),0),\n--           ((3,1),1),((3,2),2),((3,3),1),((3,4),0),((3,5),0),\n--           ((4,1),1),((4,2),3),((4,3),3),((4,4),1),((4,5),0),\n--           ((5,1),1),((5,2),4),((5,3),6),((5,4),4),((5,5),1)]\n-- ---------------------------------------------------------------------\n\ntype Matriz = Array (Int,Int) Int\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmatrizPascal1 :: Int -> Matriz \nmatrizPascal1 1 = array ((1,1),(1,1)) [((1,1),1)]\nmatrizPascal1 n = \n    array ((1,1),(n,n)) [((i,j), f i j) | i <- [1..n], j <- [1..n]]\n    where f i j | i < n &#038;&#038; j <  n  = p!(i,j)\n                | i < n &#038;&#038; j == n  = 0\n                | j == 1 || j == n = 1\n                | otherwise        = p!(i-1,j-1) + p!(i-1,j)\n          p = matrizPascal2 (n-1)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmatrizPascal2 :: Int -> Matriz\nmatrizPascal2 n = listArray ((1,1),(n,n)) (concat xss)\n    where yss = take n pascal\n          xss = map (take n) (map (++ (repeat 0)) yss)\n        \npascal :: [[Int]]\npascal = [1] : map f pascal\n    where f xs = zipWith (+) (0:xs) (xs++[0])\n\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmatrizPascal3 :: Int -> Matriz\nmatrizPascal3 n = \n    array ((1,1),(n,n)) [((i,j), f i j) | i <- [1..n], j <- [1..n]]\n    where f i j | i >=  j   = comb (i-1) (j-1)\n                | otherwise = 0\n\n-- (comb n k) es el n\u00famero de combinaciones (o coeficiente binomial) de\n-- n sobre k. Por ejemplo,\ncomb :: Int -> Int -> Int\ncomb n k = product [n,n-1..n-k+1] `div` product [1..k]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el examen de la 1\u00aa convocatoria del curso Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas). A continuaci\u00f3n se muestran los ejercicios y sus soluciones.<\/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":[222],"tags":[270,300],"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\/4354"}],"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=4354"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4354\/revisions"}],"predecessor-version":[{"id":4355,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4354\/revisions\/4355"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4354"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4354"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4354"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}