-- I1M 2009-10: G1_Rel_6.hs -- 5ª relación de ejercicios (11 de Noviembre) -- Departamento de Ciencias de la Computación e I.A. -- Universidad de Sevilla -- ===================================================================== -- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck import Data.List (sort) -- ---------------------------------------------------------------------------- -- Ejercicio 1 (Máximo común divisor) -- ---------------------------------------------------------------------------- -- Dados dos números naturales, a y b, es posible calcular su máximo -- común divisor mediante el Algoritmo de Euclides. Este algoritmo se -- puede resumir en la siguiente fórmula: -- mcd(a,b) = a, si b = 0 -- = mcd (b, a módulo b), si b > 0 -- ---------------------------------------------------------------------------- -- Ejercicio 1.1. Definir la función mcd. -- ---------------------------------------------------------------------------- -- La definición es mcd :: Integer -> Integer -> Integer mcd = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 1.2. Definir y comprobar la propiedad prop_mcd según la cual el -- máximo común divisor de dos números a y b (ambos mayores que 0) es siempre -- mayor o igual que 1 y además es menor o igual que el menor de los números a -- y b. -- ---------------------------------------------------------------------------- -- La propiedad es prop_mcd a b = undefined -- y su comprobación es -- ---------------------------------------------------------------------------- -- Ejercicio 1.3. Teniendo en cuenta que buscamos el máximo común divisor de a -- y b, sería razonable pensar que el máximo común divisor siempre sería igual -- o menor que la mitad del máximo de a y b. Definir esta propiedad y -- comprobarla. -- ---------------------------------------------------------------------------- -- La propiedad es prop_mcd_div a b = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 2 (Suma de cuadrados) -- ---------------------------------------------------------------------------- -- Ejercicio 2.1. Definir por recursión la función sumaCuadrados tal que -- (sumaCuadrados n) es la suma de los cuadrados de los números de 1 a n. Por -- ejemplo, -- sumaCuadrados 4 => 30 -- ---------------------------------------------------------------------------- -- La definición es sumaCuadrados :: Integer -> Integer sumaCuadrados = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 2.2. Comprobar con QuickCheck si sumaCuadrados n es igual a -- n(n+1)(2n+1)/6. -- ---------------------------------------------------------------------------- -- La propiedad es prop_SumaCuadrados n = undefined -- y la comprobación es -- ---------------------------------------------------------------------------- -- Ejercicio 3. (Medidas de centralización) -- ---------------------------------------------------------------------------- -- Ejercicio 1.1. Definir la función -- media :: [Double] -> Double -- que calcule la media aritmética de una lista numérica. Por ejemplo, -- media [1,2,3] ==> 2.0 -- media [1,-2,3.5,4] ==> 1.625 -- Nota: La expresión (fromIntegral x) es el número real correspondiente -- al número entero x. -- ---------------------------------------------------------------------------- media :: [Double] -> Double media xs = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 3.2. Definir la función -- mediana :: [Double] -> Double -- que calcule la mediana de una lista numérica; esto es, el valor que deja el -- mismo número de datos menores y mayores que él (si la lista contiene un -- número par de elementos, la mediana será la media aritmética de los dos -- valores centrales). Por ejemplo, -- mediana [3,2,5,1,4] ==> 3.0 -- mediana [-1,7,8,1] ==> 4.0 -- Notas: -- 1. (sort xs) es el resultado de ordenar la lista xs. -- 2. (xs !! n) es el n-ésimo elemento de xs. -- ---------------------------------------------------------------------------- mediana :: [Double] -> Double mediana xs = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 3.3. La función -- divideMedia :: [Double] -> [[Double]] -- dada una lista numérica, xs, calcula la lista [ys,zs], donde ys contiene los -- elementos de xs estrictamente menores que la media, mientras que zs contiene -- los elementos de xs estrictamente mayores que la media. Por ejemplo, -- divideMedia [6,7,2,8,6,3,4] ==> [[2.0,3.0,4.0],[6.0,7.0,8.0,6.0]] -- divideMedia [1,2,3] ==> [[1.0],[3.0]] -- Definir la función divideMedia por comprensión. -- ---------------------------------------------------------------------------- divideMedia :: [Double] -> [[Double]] divideMedia xs = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 3.4. Dada una lista, xs, sus valores externos son aquellos valores -- menores que media xs-(máximo xs-mínimo xs)/2) o mayores que -- media xs+(máximo xs-mínimo xs)/2). -- -- Definir, por comprensión, la función -- valoresExternos:: [Double] -> [Double] -- que calcula los valores externos de una lista numérica. Por ejemplo, -- valoresExternos [1,2,5,5,5,5,5,5] ==> [1.0,2.0] -- valoresExternos [5,5,5,5,5,5,8,9] ==> [8.0,9.0] -- valoresExternos [1,2,5,5,5,5,5,5,8,9] ==> [] -- ---------------------------------------------------------------------------- valoresExternos :: [Double] -> [Double] valoresExternos xs = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 3.5. Comprobar con QuickCheck si se verifica alguna de las -- siguientes propiedades: -- * La media de una lista no vacía es mayor o igual que la mediana. -- * La media de una lista no vacía es menor o igual que la mediana. -- * La media de una lista no vacía es menor o igual que (minimo + maximo)/2 -- ---------------------------------------------------------------------------- -- Las propiedades son: prop1, prop2, prop3 :: [Double] -> Property prop1 xs = undefined prop2 xs = undefined prop3 xs = undefined -- La comprobación con QuickCheck es -- ---------------------------------------------------------------------------- -- Ejercicio 4 (Extracciones e inserciones) -- ---------------------------------------------------------------------------- -- Ejercicio 4.1. Definir la función extrae tal que (extrae xs n) es la lista -- resultado de eliminar el elemento n-ésimo de la lista xs. Si n es negativo -- o mayor que la longitud de la lista el resultado debe ser la misma -- lista. Por ejemplo, -- extrae [1,2,3,4,5] 2 ==> [1,2,4,5] -- extrae [1,2,3,4,5] 4 ==> [1,2,3,4] -- extrae [1,2,3,4,5] (-1) ==> [1,2,3,4,5] -- extrae [1,2,3,4,5] 7 ==> [1,2,3,4,5] -- Nota: (drop n xs) es la lista obtenida eliminando los n primeros -- elementos de xs. -- ---------------------------------------------------------------------------- extrae :: [a] -> Int -> [a] extrae xs n = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 4.2. Definir la función inserta tal que (inserta xs e n) debe -- introducir el elemento n en la posición n de la lista xs. Si (n<=0) el -- elemento se insertará al principio de la lista, y si n es igual o mayor que -- la longitud de la lista, el elemento e se colocará al final de la lista. Por -- ejemplo, -- inserta [1,3,5] 7 1 ==> [1,7,3,5] -- inserta [1,3,5] 7 3 ==> [1,3,5,7] -- inserta [1,3,5] 7 (-1) ==> [7,1,3,5] -- inserta [1,3,5] 7 9 ==> [1,3,5,7] -- ---------------------------------------------------------------------------- inserta :: [a] -> a -> Int -> [a] inserta xs e n = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 4.3. Comprobar con QuickCheck que si se inserta el elemento -- n-ésimo de una lista xs en el resultado de extraer el elemento n-ésimo de xs -- se obtiene la lista xs. -- ---------------------------------------------------------------------------- -- La propiedad es prop_InsertaExtrae :: [Int] -> Int -> Property prop_InsertaExtrae xs n = undefined -- La comprobación es -- ---------------------------------------------------------------------------- -- Ejercicio 5. (Reconocimiento de permutaciones) -- ---------------------------------------------------------------------------- -- Una permutación de una lista es otra lista con los mismos elementos, -- pero posiblemente en distinto orden. Por ejemplo, [1,2,1] es una -- permutación de [2,1,1] pero no de [1,2,2]. En este ejercicio vamos a -- estudiar las permutaciones. -- ---------------------------------------------------------------------------- -- Ejercicio 5.1. Definir la función -- borra :: Eq a => a -> [a] -> [a] -- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de x en la -- lista xs. Por ejemplo, -- borra 1 [1,2,1] ==> [2,1] -- borra 3 [1,2,1] ==> [1,2,1] -- ---------------------------------------------------------------------------- borra :: Eq a => a -> [a] -> [a] borra x [] = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 5.2. Definir la función esPermutacion tal que -- (esPermutacion xs ys) se verifique si xs es una permutación de -- ys. Por ejemplo, -- esPermutacion [1,2,1] [2,1,1] ==> True -- esPermutacion [1,2,1] [1,2,2] ==> False -- ---------------------------------------------------------------------------- -- La definición es esPermutacion :: Eq a => [a] -> [a] -> Bool esPermutacion = undefined -- ---------------------------------------------------------------------------- -- Ejercicio 5.3. Comprobar con QuickCheck que si una lista es una permutación -- de otra, las dos tienen el mismo número de elementos. -- ---------------------------------------------------------------------------- -- La propiedad es prop_PemutacionConservaLongitud :: [Int] -> [Int] -> Property prop_PemutacionConservaLongitud xs ys = undefined -- y la comprobación es -- ---------------------------------------------------------------------------- -- Ejercicio 5.4. Comprobar con QuickCheck que la inversa de una lista es una -- permutación de la lista. -- ---------------------------------------------------------------------------- -- La propiedad es prop_InversaEsPermutacion :: [Int] -> Bool prop_InversaEsPermutacion xs = undefined -- y la comprobación es