{"id":1437,"date":"2011-07-08T15:12:31","date_gmt":"2011-07-08T15:12:31","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1437"},"modified":"2011-07-09T10:13:28","modified_gmt":"2011-07-09T10:13:28","slug":"i1m2010-examen-de-julio-de-2011","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-examen-de-julio-de-2011\/","title":{"rendered":"I1M2010: Examen de julio de 2011"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se ha realizado el examen de la convocatoria de julio.<\/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 (8 de julio de 2011)\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.Array\r\nimport Data.Char\r\nimport GrafoConVectorDeAdyacencia \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.1. El enunciado de un problema de las olimpiadas rusas de\r\n-- matem\u00e1ticas es el siguiente:\r\n--    Si escribimos todos los n\u00fameros enteros empezando por el uno, uno\r\n--    al lado del otro (o sea, 1234567891011121314...), \u00bfqu\u00e9 d\u00edgito\r\n--    ocupa la posici\u00f3n 206788? \r\n-- En los distintos apartados de este ejercicios resolveremos el\r\n-- problema. \r\n-- \r\n-- Definir la constante\r\n--    cadenaDeNaturales :: String\r\n-- tal que cadenaDeNaturales es la cadena obtenida escribiendo todos los\r\n-- n\u00fameros enteros empezando por el uno. Por ejemplo,\r\n--    take 19 cadenaDeNaturales  ==  \"1234567891011121314\"\r\n-- ---------------------------------------------------------------------\r\n\r\ncadenaDeNaturales :: String\r\ncadenaDeNaturales = concat [show n | n <- [1..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.2. Definir la funci\u00f3n\r\n--    digito :: Int -> Int\r\n-- tal que (digito n) es el d\u00edgito que ocupa la posici\u00f3n n en la cadena\r\n-- de los naturales (el n\u00famero de las posiciones empieza por 1). Por\r\n-- ejemplo, \r\n--    digito 10  ==  1\r\n--    digito 11  ==  0\r\n-- ---------------------------------------------------------------------\r\n\r\ndigito :: Int -> Int\r\ndigito n = digitToInt (cadenaDeNaturales !! (n-1))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.3. Calcular el d\u00edgito que ocupa la posici\u00f3n 206788 en la\r\n-- cadena de los naturales.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es \r\n--   ghci> digito 206788\r\n--   7\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.1. El problema de esta semana de los desaf\u00edos matem\u00e1ticos\r\n-- de El Pais parte de la observaci\u00f3n de que todos los n\u00fameros naturales\r\n-- tienen al menos un m\u00faltiplo no nulo que est\u00e1 formado solamente por\r\n-- ceros y unos. Por ejemplo, 1x10=10, 2x5=10, 3x37=111, 4x25=100,\r\n-- 5x2=10, 6x185=1110; 7x143=1001; 8X125=1000; 9x12345679=111111111, ...\r\n-- y as\u00ed para cualquier n\u00famero natural.  \r\n-- \r\n-- Definir la constante \r\n--    numerosCon1y0 :: [Integer]\r\n-- tal que numerosCon1y0 es la lista de los n\u00fameros cuyos d\u00edgitos son 1\r\n-- \u00f3 0. Por ejemplo, \r\n--    ghci> take 15 numerosCon1y0\r\n--    [1,10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111]\r\n-- ---------------------------------------------------------------------\r\n\r\nnumerosCon1y0 :: [Integer]\r\nnumerosCon1y0 = 1 : concat [[10*x,10*x+1] | x <- numerosCon1y0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.2. Definir la funci\u00f3n\r\n--    multiplosCon1y0 :: Integer -> [Integer] \r\n-- tal que (multiplosCon1y0 n) es la lista de los m\u00faltiplos de n cuyos\r\n-- d\u00edgitos son 1 \u00f3 0. Por ejemplo,\r\n--    take 4 (multiplosCon1y0 3)  ==  [111,1011,1101,1110]\r\n-- ---------------------------------------------------------------------\r\n\r\nmultiplosCon1y0 :: Integer -> [Integer] \r\nmultiplosCon1y0 n = \r\n    [x | x <- numerosCon1y0, x `rem` n == 0] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.3. Comprobar con QuickCheck que todo n\u00famero natural,\r\n-- mayor que 0, tiene m\u00faltiplos cuyos d\u00edgitos son 1 \u00f3 0.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_existe_multiplosCon1y0 :: Integer -> Property\r\nprop_existe_multiplosCon1y0 n = \r\n    n > 0 ==> multiplosCon1y0 n \/= []\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_existe_multiplosCon1y0\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Una matriz permutaci\u00f3n es una matriz cuadrada con\r\n-- todos sus elementos iguales a 0, excepto uno cualquiera por cada fila\r\n-- y columna, el cual debe ser igual a 1. \r\n-- \r\n-- En este ejercicio se usar\u00e1 el tipo de las matrices definido por\r\n--    type Matriz a = Array (Int,Int) a\r\n-- y los siguientes ejemplos de matrices\r\n--    q1, q2, q3 :: Matriz Int\r\n--    q1 = array ((1,1),(2,2)) [((1,1),1),((1,2),0),((2,1),0),((2,2),1)]\r\n--    q2 = array ((1,1),(2,2)) [((1,1),0),((1,2),1),((2,1),0),((2,2),1)]\r\n--    q3 = array ((1,1),(2,2)) [((1,1),3),((1,2),0),((2,1),0),((2,2),1)]\r\n--\r\n-- Definir la funci\u00f3n\r\n--    esMatrizPermutacion :: Num a => Matriz a -> Bool\r\n-- tal que (esMatrizPermutacion p) se verifica si p es una matriz\r\n-- permutaci\u00f3n. Por ejemplo.\r\n--    esMatrizPermutacion q1  ==  True\r\n--    esMatrizPermutacion q2  ==  False\r\n--    esMatrizPermutacion q3  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\ntype Matriz a = Array (Int,Int) a\r\n\r\nq1, q2, q3 :: Matriz Int\r\nq1 = array ((1,1),(2,2)) [((1,1),1),((1,2),0),((2,1),0),((2,2),1)]\r\nq2 = array ((1,1),(2,2)) [((1,1),0),((1,2),1),((2,1),0),((2,2),1)]\r\nq3 = array ((1,1),(2,2)) [((1,1),3),((1,2),0),((2,1),0),((2,2),1)]\r\n\r\nesMatrizPermutacion :: Num a => Matriz a -> Bool\r\nesMatrizPermutacion p = \r\n    and [esListaUnitaria [p!(i,j) | i <- [1..n]] | j <- [1..n]] &#038;&#038;\r\n    and [esListaUnitaria [p!(i,j) | j <- [1..n]] | i <- [1..n]] \r\n    where ((1,1),(n,_)) = bounds p\r\n\r\n-- (esListaUnitaria xs) se verifica si xs tiene un 1 y los restantes\r\n-- elementos son 0. Por ejemplo,\r\n--    esListaUnitaria [0,1,0,0]  ==  True\r\n--    esListaUnitaria [0,1,0,1]  ==  False\r\n--    esListaUnitaria [0,2,0,0]  ==  False\r\nesListaUnitaria xs = \r\n    [x | x <- xs, x \/= 0] == [1]\r\n\r\n-- ---------------------------------------------------------------------\r\n--  Ejercicio 4. Un mapa se puede representar mediante un grafo donde\r\n--  los v\u00e9rtices son las regiones del mapa y hay una arista entre dos\r\n--  v\u00e9rtices si las correspondientes regiones son vecinas. Por ejemplo,\r\n--  el mapa siguiente \r\n--        +----------+----------+       \r\n--        |    1     |     2    |       \r\n--        +----+-----+-----+----+       \r\n--        |    |           |    |       \r\n--        | 3  |     4     | 5  |       \r\n--        |    |           |    |       \r\n--        +----+-----+-----+----+       \r\n--        |    6     |     7    |       \r\n--        +----------+----------+\r\n-- se pueden representar por\r\n--    mapa :: Grafo Int Int\r\n--    mapa = creaGrafo False (1,7)\r\n--                     [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(2,5,0),(3,4,0),\r\n--                      (3,6,0),(4,5,0),(4,6,0),(4,7,0),(5,7,0),(6,7,0)]\r\n-- Para colorear el mapa se dispone de 4 colores definidos por   \r\n--    data Color = A | B | C | D deriving (Eq, Show)\r\n-- \r\n-- Definir la funci\u00f3n\r\n--    correcta :: [(Int,Color)] -> Grafo Int Int -> Bool\r\n-- tal que (correcta ncs m) se verifica si ncs es una coloraci\u00f3n del\r\n-- mapa m tal que todos las regiones vecinas tienen colores distintos. \r\n-- Por ejemplo, \r\n--    correcta [(1,A),(2,B),(3,B),(4,C),(5,A),(6,A),(7,B)] mapa == True\r\n--    correcta [(1,A),(2,B),(3,A),(4,C),(5,A),(6,A),(7,B)] mapa == False\r\n-- ---------------------------------------------------------------------\r\n\r\nmapa :: Grafo Int Int\r\nmapa = creaGrafo False (1,7)\r\n                 [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(2,5,0),(3,4,0),\r\n                  (3,6,0),(4,5,0),(4,6,0),(4,7,0),(5,7,0),(6,7,0)]\r\n\r\ndata Color = A | B | C | D deriving (Eq, Show)\r\n\r\ncorrecta :: [(Int,Color)] -> Grafo Int Int -> Bool\r\ncorrecta ncs g = \r\n    and [and [color x \/= color y | y <- adyacentes g x] | x <- nodos g]\r\n    where color x = head [c | (y,c) <- ncs, y == x] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.1. La expansi\u00f3n decimal de un n\u00famero racional puede\r\n-- representarse mediante una lista cuyo primer elemento es la parte\r\n-- entera y el resto est\u00e1 formado por los d\u00edgitos de su parte decimal.\r\n-- \r\n-- Definir la funci\u00f3n\r\n--    expansionDec :: Integer -> Integer -> [Integer]\r\n-- tal que (expansionDec x y) es la expansi\u00f3n decimal de x\/y. Por\r\n-- ejemplo, \r\n--    take 10 (expansionDec 1 4)    ==  [0,2,5]\r\n--    take 10 (expansionDec 1 7)    ==  [0,1,4,2,8,5,7,1,4,2]\r\n--    take 12 (expansionDec 90 7)   ==  [12,8,5,7,1,4,2,8,5,7,1,4]\r\n--    take 12 (expansionDec 23 14)  ==  [1,6,4,2,8,5,7,1,4,2,8,5]\r\n-- ---------------------------------------------------------------------\r\n\r\nexpansionDec :: Integer -> Integer -> [Integer]\r\nexpansionDec x y \r\n    | r == 0    = [q]\r\n    | otherwise = q : expansionDec (r*10) y\r\n    where (q,r) = quotRem x y\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.2. La parte decimal de las expansiones decimales se puede\r\n-- dividir en la parte pura y la parte peri\u00f3dica (que es la que se\r\n-- repite). Por ejemplo, puesto que la expansi\u00f3n de 23\/14 es  \r\n--    [1,6,4,2,8,5,7,1,4,2,8,5,...\r\n-- su parte entera es 1, su parte decimal pura es [6] y su parte decimal\r\n-- peri\u00f3dica es [4,2,8,5,7,1].\r\n-- \r\n-- Definir la funci\u00f3n\r\n--    formaDecExpDec :: [Integer] -> (Integer,[Integer],[Integer])\r\n-- tal que (formaDecExpDec xs) es la forma decimal de la expresi\u00f3n\r\n-- decimal xs; es decir, la terna formada por la parte entera, la parte\r\n-- decimal pura y la parte decimal peri\u00f3dica. Por ejemplo,\r\n--    formaDecExpDec [3,1,4]               ==  (3,[1,4],[])\r\n--    formaDecExpDec [3,1,4,6,7,5,6,7,5]   ==  (3,[1,4],[6,7,5])\r\n--    formaDecExpDec (expansionDec 23 14)  ==  (1,[6],[4,2,8,5,7,1])\r\n-- ---------------------------------------------------------------------\r\n\r\nformaDecExpDec :: [Integer] -> (Integer,[Integer],[Integer])\r\nformaDecExpDec (x:xs) = (x,ys,zs)\r\n    where (ys,zs) = decimales xs\r\n\r\n-- (decimales xs) es el par formado por la parte decimal pura y la parte\r\n-- decimal peri\u00f3dica de la lista de decimales xs. Por ejemplo, \r\n--    decimales [3,1,4]            ==  ([3,1,4],[])\r\n--    decimales [3,1,6,7,5,6,7,5]  ==  ([3,1],[6,7,5])\r\ndecimales :: [Integer] -> ([Integer],[Integer])\r\ndecimales xs = decimales' xs []\r\n    where decimales' [] ys = (reverse ys, [])\r\n          decimales' (x:xs) ys \r\n              | x `elem` ys = splitAt k ys'\r\n              | otherwise   = decimales' xs (x:ys)\r\n              where ys' = reverse ys\r\n                    k   = posicion x ys'\r\n\r\n-- (posicion x ys) es la primera posici\u00f3n de x en la lista ys. Por\r\n-- ejemplo, \r\n--    posicion 2 [0,2,3,2,5]  ==  1\r\nposicion :: Eq a => a -> [a] -> Int\r\nposicion x ys = head [n | (n,y) <- zip [0..] ys, x == y]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.3. Definir la funci\u00f3n\r\n--    formaDec :: Integer -> Integer -> (Integer,[Integer],[Integer])\r\n-- tal que (formaDec x y) es la forma decimal de x\/y; es decir, la terna\r\n-- formada por la parte entera, la parte decimal pura y la parte decimal\r\n-- peri\u00f3dica. Por ejemplo, \r\n--    formaDec 1 4    ==  (0,[2,5],[])\r\n--    formaDec 23 14  ==  (1,[6],[4,2,8,5,7,1])\r\n-- ---------------------------------------------------------------------\r\n\r\nformaDec :: Integer -> Integer -> (Integer,[Integer],[Integer])\r\nformaDec x y =\r\n    formaDecExpDec (expansionDec x y)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se ha realizado el examen de la convocatoria de julio. A continuaci\u00f3n se muestra el examen junto con su soluci\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":[133],"tags":[287],"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\/1437"}],"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=1437"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1437\/revisions"}],"predecessor-version":[{"id":1438,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1437\/revisions\/1438"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1437"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1437"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1437"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}