{"id":1001,"date":"2010-12-17T10:32:53","date_gmt":"2010-12-17T10:32:53","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1001"},"modified":"2013-03-08T05:50:05","modified_gmt":"2013-03-08T05:50:05","slug":"i1m2010-examen-de-la-convocatoria-de-diciembre","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-examen-de-la-convocatoria-de-diciembre\/","title":{"rendered":"I1M2010: Examen de la convocatoria de diciembre"},"content":{"rendered":"

Hoy se ha celebrado el examen de la convocatoria de diciembre de la asignatura de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a>.<\/p>\n

A continuaci\u00f3n se muestra el examen junto con su soluci\u00f3n:
\n<\/p>\n

\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. [2 puntos] Definir la funci\u00f3n \r\n--    ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\n-- tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k \r\n-- elementos cuya suma sea menor que t. Por ejemplo,\r\n--    ullman 9 3 [1..10] == True\r\n--    ullman 5 3 [1..10] == False\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa soluci\u00f3n (corta y eficiente)\r\nullman :: (Ord a, Num a) => a -> Int -> [a] -> Bool\r\nullman t k xs = sum (take k (sort xs)) < t\r\n\r\n-- 2\u00aa soluci\u00f3n (larga e ineficiente)\r\nullman2 :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\nullman2 t k xs = \r\n    [ys | ys <- subconjuntos xs, length ys == k, sum ys < t] \/= []\r\n\r\n-- (subconjuntos xs) es la lista de los subconjuntos de xs. Por \r\n-- ejemplo,\r\n--    subconjuntos \"bc\"  ==  [\"\",\"c\",\"b\",\"bc\"]\r\n--    subconjuntos \"abc\" ==  [\"\",\"c\",\"b\",\"bc\",\"a\",\"ac\",\"ab\",\"abc\"]\r\nsubconjuntos :: [a] -> [[a]]\r\nsubconjuntos [] = [[]]\r\nsubconjuntos (x:xs) = zss++[x:ys | ys <- zss]\r\n    where zss = subconjuntos xs\r\n\r\n-- Los siguientes ejemplos muestran la diferencia en la eficencia:\r\n--    *Main> ullman 9 3 [1..20]\r\n--    True\r\n--    (0.02 secs, 528380 bytes)\r\n--    *Main> ullman2 9 3 [1..20]\r\n--    True\r\n--    (4.08 secs, 135267904 bytes)\r\n--    *Main> ullman 9 3 [1..100]\r\n--    True\r\n--    (0.02 secs, 526360 bytes)\r\n--    *Main> ullman2 9 3 [1..100]\r\n--      C-c C-cInterrupted.\r\n--    Agotado\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. [2 puntos] Definir la funci\u00f3n\r\n--    sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]\r\n-- tal que (sumasDe2Cuadrados n) es la lista de los pares de n\u00fameros\r\n-- tales que la suma de sus cuadrados es n y el primer elemento del par\r\n-- es mayor o igual que el segundo. Por ejemplo,\r\n--    sumasDe2Cuadrados 25  ==  [(5,0),(4,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Primera definici\u00f3n:\r\nsumasDe2Cuadrados_1 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_1 n = \r\n    [(x,y) | x <- [n,n-1..0],\r\n             y <- [0..x],\r\n             x*x+y*y == n]\r\n\r\n-- Segunda definici\u00f3n:\r\nsumasDe2Cuadrados_2 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_2 n = \r\n    [(x,y) | x <- [a,a-1..0],\r\n             y <- [0..x],\r\n             x*x+y*y == n]\r\n    where a = ceiling (sqrt (fromIntegral n))\r\n\r\n-- Tercera definici\u00f3n:\r\nsumasDe2Cuadrados_3 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_3 n = aux (ceiling (sqrt (fromIntegral n))) 0 where\r\n    aux x y | x < y          = [] \r\n            | x*x + y*y <  n = aux x (y+1)\r\n            | x*x + y*y == n = (x,y) : aux (x-1) (y+1)\r\n            | otherwise      = aux (x-1) y\r\n\r\n-- Comparaci\u00f3n\r\n--    +----------+---------------+---------------+---------------+\r\n--    | n        | 1\u00aa definici\u00f3n | 2\u00aa definici\u00f3n | 3\u00aa definici\u00f3n |\r\n--    +----------+---------------+---------------+---------------+\r\n--    |      999 | 2.17 segs     |   0.02 segs   | 0.01 segs     |  \r\n--    | 48612265 |               | 140.38 segs   | 0.13 segs     |\r\n--    +----------+---------------+---------------+---------------+\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. [2 puntos] Los \u00e1rboles binarios pueden representarse\r\n-- mediante el tipo de datos Arbol definido por\r\n--    data Arbol a = Nodo (Arbol a) (Arbol a) \r\n--                 | Hoja a\r\n--                 deriving Show\r\n-- Por ejemplo, los \u00e1rboles \r\n--    \u00e1rbol1          \u00e1rbol2       \u00e1rbol3     \u00e1rbol4 \r\n--       o              o           o\t        o    \r\n--      \/ \\            \/ \\         \/ \\\t       \/ \\   \r\n--     1   o          o   3       o   3\t      o   1  \r\n--        \/ \\        \/ \\         \/ \\\t     \/ \\     \r\n--       2   3      1   2       1   4\t    2   3    \r\n-- se representan por\r\n--    arbol1, arbol2, arbol3, arbol4 :: Arbol Int\r\n--    arbol1 = Nodo (Hoja 1) (Nodo (Hoja 2) (Hoja 3))\r\n--    arbol2 = Nodo (Nodo (Hoja 1) (Hoja 2)) (Hoja 3)\r\n--    arbol3 = Nodo (Nodo (Hoja 1) (Hoja 4)) (Hoja 3)\r\n--    arbol4 = Nodo (Nodo (Hoja 2) (Hoja 3)) (Hoja 1)\r\n-- Definir la funci\u00f3n\r\n--    igualBorde :: Eq a => Arbol a -> Arbol a -> Bool\r\n-- tal que (igualBorde t1 t2) se verifica si los bordes de los \u00e1rboles\r\n-- t1 y t2 son iguales. Por ejemplo,\r\n--    igualBorde arbol1 arbol2  ==  True\r\n--    igualBorde arbol1 arbol3  ==  False\r\n--    igualBorde arbol1 arbol4  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Arbol a = Nodo (Arbol a) (Arbol a) \r\n             | Hoja a\r\n             deriving Show\r\n\r\narbol1, arbol2, arbol3, arbol4 :: Arbol Int\r\narbol1 = Nodo (Hoja 1) (Nodo (Hoja 2) (Hoja 3))\r\narbol2 = Nodo (Nodo (Hoja 1) (Hoja 2)) (Hoja 3)\r\narbol3 = Nodo (Nodo (Hoja 1) (Hoja 4)) (Hoja 3)\r\narbol4 = Nodo (Nodo (Hoja 2) (Hoja 3)) (Hoja 1)\r\n\r\nigualBorde :: Eq a => Arbol a -> Arbol a -> Bool\r\nigualBorde t1 t2 = borde t1 == borde t2\r\n\r\n-- (borde t) es el borde del \u00e1rbol t; es decir, la lista de las hojas\r\n-- del \u00e1rbol t le\u00eddas de izquierda a derecha. Por ejemplo, \r\n--    borde arbol4  ==  [2,3,1]\r\nborde :: Arbol a -> [a]\r\nborde (Nodo i d) = borde i ++ borde d\r\nborde (Hoja x)   = [x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. [2 puntos] (Basado en el problema 145 del Proyecto\r\n-- Euler). Se dice que un n\u00famero n es reversible si su \u00faltima cifra es\r\n-- distinta de 0 y la suma de n y el n\u00famero obtenido escribiendo las\r\n-- cifras de n en orden inverso es un n\u00famero que tiene todas sus cifras\r\n-- impares. Por ejemplo, \r\n-- 36 es reversible porque 36+63=99 tiene todas sus cifras impares, \r\n-- 409 es reversible porque 409+904=1313 tiene todas sus cifras impares,  \r\n-- 243 no es reversible porque 243+342=585 no tiene todas sus cifras impares, \r\n-- Definir la funci\u00f3n \r\n--    reversiblesMenores :: Int -> Int\r\n-- tal que (reversiblesMenores n) es la cantidad de n\u00fameros reversibles\r\n-- menores que n. Por ejemplo,\r\n--    reversiblesMenores 10   == 0\r\n--    reversiblesMenores 100  == 20\r\n--    reversiblesMenores 1000 == 120\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (reversiblesMenores n) es la cantidad de n\u00fameros reversibles menores\r\n-- que n. Por ejemplo,\r\n--    reversiblesMenores 10   == 0\r\n--    reversiblesMenores 100  == 20\r\n--    reversiblesMenores 1000 == 120\r\nreversiblesMenores :: Int -> Int\r\nreversiblesMenores n = length [x | x <- [1..n-1], esReversible x]\r\n\r\n-- (esReversible n) se verifica si n es reversible; es decir, si su\r\n-- \u00faltima cifra es distinta de 0 y la suma de n y el n\u00famero obtenido\r\n-- escribiendo las cifras de n en orden inverso es un n\u00famero que tiene\r\n-- todas sus cifras impares. Por ejemplo,\r\n--    esReversible 36  == True\r\n--    esReversible 409 == True\r\nesReversible :: Int -> Bool\r\nesReversible n = rem n 10 \/= 0 && impares (cifras (n + (inverso n)))\r\n\r\n-- (impares xs) se verifica si xs es una lista de n\u00fameros impares. Por\r\n-- ejemplo, \r\n--    impares [3,5,1] == True\r\n--    impares [3,4,1] == False\r\nimpares :: [Int] -> Bool\r\nimpares xs = and [odd x | x <- xs]\r\n\r\n-- (inverso n) es el n\u00famero obtenido escribiendo las cifras de n en\r\n-- orden inverso. Por ejemplo,\r\n--    inverso 3034 == 4303\r\ninverso :: Int -> Int\r\ninverso n = read (reverse (show n))\r\n\r\n-- (cifras n) es la lista de las cifras del n\u00famero n. Por ejemplo,\r\n--    cifras 3034 == [3,0,3,4]\r\ncifras :: Int -> [Int]\r\ncifras n = [read [x] | x <- show n]\r\n\r\n{-\r\n\/* ---------------------------------------------------------------------\r\n * Ejercicio 5. [2 puntos] Definir en Maxima la funci\u00f3n\r\n * sumasDe2Cuadrados tal que sumasDe2Cuadrados(n) es la lista de los\r\n * pares de n\u00fameros tales que la suma de sus cuadrados es n y el primer\r\n * elemento del par es menor o igual que el segundo. Por ejemplo,\r\n *   sumasDe2Cuadrados(25) = [[3,4],[0,5]]\r\n * -------------------------------------------------------------------*\/\r\n\r\nsumasDe2Cuadrados(n) := block ([sol:[],x,y],\r\n  for x:0 thru n do\r\n    for y:x thru n do\r\n      if x^2+y^2 = n then sol : cons([x,y],sol),\r\n    sol)$\r\n-}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Hoy se ha celebrado el examen de la convocatoria de diciembre de la asignatura 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":[133],"tags":[270,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\/1001"}],"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=1001"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1001\/revisions"}],"predecessor-version":[{"id":2960,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1001\/revisions\/2960"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1001"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1001"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1001"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}