I1M2010: 8º examen de la evaluacion continua
En la clase de hoy de Informática de 1º del Grado en Matemáticas se ha realizado el 8º examen de la evaluación continua.
A continuación se muestra el examen junto con su solución:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 |
-- Informática (1º del Grado en Matemáticas) -- 8º examen (24 de junio de 2011) -- --------------------------------------------------------------------- import Test.QuickCheck import Data.Array -- --------------------------------------------------------------------- -- Ejercicio 1. [2 puntos] Definir la función -- ordena :: (a -> a -> Bool) -> [a] -> [a] -- tal que (ordena r xs) es la lista obtenida ordenando los elementos de -- xs según la relación r. Por ejemplo, -- ghci> ordena (\x y -> abs x < abs y) [-6,3,7,-9,11] -- [3,-6,7,-9,11] -- ghci> ordena (\x y -> length x < length y) [[2,1],[3],[],[1]] -- [[],[3],[1],[2,1]] -- --------------------------------------------------------------------- ordena :: (a -> a -> Bool) -> [a] -> [a] ordena _ [] = [] ordena r (x:xs) = (ordena r menores) ++ [x] ++ (ordena r mayores) where menores = [y | y <- xs, r y x] mayores = [y | y <- xs, not (r y x)] -- --------------------------------------------------------------------- -- Ejercicio 2. [2 puntos] Se consideran el tipo de las matrices -- definido por -- type Matriz a = Array (Int,Int) a -- y, como ejemplo, la matriz q definida por -- q :: Matriz Int -- q = array ((1,1),(2,2)) [((1,1),3),((1,2),2),((2,1),3),((2,2),1)] -- Definir la función -- indicesMaximo :: (Num a, Ord a) => Matriz a -> [(Int,Int)] -- tal que (indicesMaximo p) es la lista de los índices del elemento -- máximo de la matriz p. Por ejemplo, -- indicesMaximo q == [(1,1),(2,1)] -- --------------------------------------------------------------------- type Matriz a = Array (Int,Int) a q :: Matriz Int q = array ((1,1),(2,2)) [((1,1),3),((1,2),2),((2,1),3),((2,2),1)] indicesMaximo :: (Num a, Ord a) => Matriz a -> [(Int,Int)] indicesMaximo p = [(i,j) | (i,j) <- indices p, p!(i,j) == m] where m = maximum (elems p) -- --------------------------------------------------------------------- -- Ejercicio 3. Los montículo se pueden representar mediante el -- siguiente tipo de dato algebraico. -- data Ord a => Monticulo a = Vacio -- | M a (Monticulo a) (Monticulo a) -- deriving Show -- Por ejemplo, el montículo -- 1 -- / \ -- / \ -- 5 4 -- / \ / -- 7 6 8 -- se representa por -- m1, m2, m3 :: Monticulo Int -- m1 = M 1 m2 m3 -- m2 = M 5 (M 7 Vacio Vacio) (M 6 Vacio Vacio) -- m3 = M 4 (M 8 Vacio Vacio) Vacio -- Definir las funciones -- ramaDerecha :: Ord a => Monticulo a -> [a] -- rango :: Ord a => Monticulo a -> Int -- tales que (ramaDerecha m) es la rama derecha del montículo m; por ejemplo, -- ramaDerecha m1 == [1,4] -- ramaDerecha m2 == [5,6] -- ramaDerecha m3 == [4] -- y (rango m) es el rango del montículo m; es decir, la menor distancia -- desde la raíz de m a un montículo vacío. Por ejemplo, -- rango m1 == 2 -- rango m2 == 2 -- rango m3 == 1 -- --------------------------------------------------------------------- data Ord a => Monticulo a = Vacio | M a (Monticulo a) (Monticulo a) deriving Show m1, m2, m3 :: Monticulo Int m1 = M 1 m2 m3 m2 = M 5 (M 7 Vacio Vacio) (M 6 Vacio Vacio) m3 = M 4 (M 8 Vacio Vacio) Vacio ramaDerecha :: Ord a => Monticulo a -> [a] ramaDerecha Vacio = [] ramaDerecha (M v i d) = v : ramaDerecha d rango :: Ord a => Monticulo a -> Int rango Vacio = 0 rango (M _ i d) = 1 + min (rango i) (rango d) -- --------------------------------------------------------------------- -- Ejercicio 4. [2 puntos] Los polinomios pueden representarse mediante -- listas dispersas. Por ejemplo, el polinomio x^5+3x^4-5x^2+x-7 se -- representa por [1,3,0,-5,1,-7]. En dicha lista, obviando el cero, se -- producen tres cambios de signo: del 3 al -5, del -5 al 1 y del 1 al -- -7. Llamando C(p) al número de cambios de signo en la lista de -- coeficientes del polinomio p(x), tendríamos entonces que en este caso -- C(p)=3. -- -- La regla de los signos de Descartes dice que el número de raíces -- reales positivas de una ecuación polinómica con coeficientes reales -- igualada a cero es, como mucho, igual al número de cambios de signo -- que se produzcan entre sus coeficientes (obviando los ceros). Por -- ejemplo, en el caso anterior la ecuación tendría como mucho tres -- soluciones reales positivas, ya que C(p)=3. -- -- Además, si la cota C(p) no se alcanza, entonces el número de raíces -- positivas de la ecuación difiere de ella un múltiplo de dos. En el -- ejemplo anterior esto significa que la ecuación puede tener tres -- raíces positivas o tener solamente una, pero no podría ocurrir que -- tuviera dos o que no tuviera ninguna. -- Definir, por comprensión, la función -- cambiosC :: [Int] -> [(Int,Int)] -- tal que (cambiosC xs) es la lista de los pares de elementos de xs con -- signos distintos, obviando los ceros. Por ejemplo, -- cambiosC [1,3,0,-5,1,-7] == [(3,-5),(-5,1),(1,-7)] -- y, por recursión, la función -- cambiosR :: [Int] -> [(Int,Int)] -- tal que (cambiosR xs) es la lista de los pares de elementos de xs con -- signos distintos, obviando los ceros. Por ejemplo, -- cambiosR [1,3,0,-5,1,-7] == [(3,-5),(-5,1),(1,-7)] -- Finalmente, comprobar con QuickCheck que las dos definiciones son -- equivalentes. -- -- Usando las anteriores definiciones y la regla de Descartes, definir -- la función -- nRaicesPositivas :: [Int] -> [Int] -- tal que (nRaicesPositivas p) es la lista de los posibles números de -- raíces positivas del polinomio p (representado mediante una lista -- dispersa) según la regla de los signos de Descartes. Por ejemplo, -- nRaicesPositivas [1,3,0,-5,1,-7] == [3,1] -- que significa que la ecuación x^5+3x^4-5x^2+x-7=0 puede tener 3 ó 1 -- raíz positiva. -- -- Nota: Este ejercicio está basado en el artículo de Gaussiano "La -- regla de los signos de Descartes" http://bit.ly/iZXybH -- --------------------------------------------------------------------- -- (noCeros xs) es la lista de los elementos de xs distintos de cero. -- Por ejemplo, -- noCeros [1,3,0,-5,1,-7] == [1,3,-5,1,-7] noCeros xs = filter (/=0) xs cambiosC :: [Int] -> [(Int,Int)] cambiosC xs = [(x,y) | (x,y) <- consecutivos (noCeros xs), x*y < 0] where consecutivos xs = zip xs (tail xs) cambiosR :: [Int] -> [(Int,Int)] cambiosR xs = cambiosR' (noCeros xs) where cambiosR' (x:y:xs) | x*y < 0 = (x,y) : cambiosR' (y:xs) | otherwise = cambiosR' (y:xs) cambiosR' _ = [] -- La propiedad es prop_cambios :: [Int] -> Bool prop_cambios xs = cambiosC xs == cambiosR xs -- La comprobación es -- ghci> quickCheck prop_cambios -- +++ OK, passed 100 tests. nRaicesPositivas :: [Int] -> [Int] nRaicesPositivas xs = [n,n-2..0] where n = length (cambiosC xs) -- --------------------------------------------------------------------- -- Ejercicio 5. [2 puntos] Se considera la siguiente enumeración de los -- pares de números naturales -- (0,0), -- (0,1), (1,0), -- (0,2), (1,1), (2,0), -- (0,3), (1,2), (2,1), (3,0), -- (0,4), (1,3), (2,2), (3,1), (4,0), -- (0,5), (1,4), (2,3), (3,2), (4,1), (5,0), ... -- a. Definir la función -- siguiente :: (Int,Int) -> (Int,Int) -- tal que (siguiente (x,y)) es el siguiente del término (x,y) en la -- enumeración. Por ejemplo, -- siguiente (2,0) == (0,3) -- siguiente (0,3) == (1,2) -- siguiente (1,2) == (2,1) -- b. Definir la constante -- enumeracion :: [(Int,Int)] -- tal que enumeracion es la lista que representa la anterior -- enumeracion de los pares de números naturales. Por ejemplo, -- take 6 enumeracion == [(0,0),(0,1),(1,0),(0,2),(1,1),(2,0)] -- enumeracion !! 9 == (3,0) -- c. Definir la función -- posicion :: (Int,Int) -> Int -- tal que (posicion p) es la posición del par p en la -- enumeración. Por ejemplo, -- posicion (3,0) == 9 -- posicion (1,2) == 7 -- d. Definir la propiedad -- prop_posicion :: Int -> Bool -- tal que (prop_posicion n) se verifica si para los n primeros -- términos (x,y) de la enumeración se cumple que -- posicion (x,y) == (x+y)*(x+y+1) `div` 2 + x -- Comprobar si la propiedad se cumple para los 100 primeros -- elementos. -- --------------------------------------------------------------------- siguiente :: (Int,Int) -> (Int,Int) siguiente (x,0) = (0,x+1) siguiente (x,y+1) = (x+1,y) enumeracion :: [(Int,Int)] enumeracion = iterate siguiente (0,0) posicion :: (Int,Int) -> Int posicion (x,y) = length (takeWhile (/= (x,y)) enumeracion) prop_posicion :: Int -> Bool prop_posicion n = and [posicion (x,y) == (x+y)*(x+y+1) `div` 2 + x | (x,y) <- take n enumeracion] |