-- I1M 2009-10: Relación 21 (8 de abril de 2010) -- Departamento de Ciencias de la Computación e I.A. -- Universidad de Sevilla -- ===================================================================== -- --------------------------------------------------------------------- -- Importación de librerías -- -- --------------------------------------------------------------------- import Test.QuickCheck import Data.List -- --------------------------------------------------------------------- -- Ejercicio 1.1. Definir la función -- divisoresEn :: Integer -> [Integer] -> Bool -- tal que (divisoresEn x ys) se verifica si x puede expresarse como un -- producto de potencias de elementos de ys. Por ejemplo, -- divisoresEn 12 [2,3,5] == True -- divisoresEn 14 [2,3,5] == False -- --------------------------------------------------------------------- divisoresEn :: Integer -> [Integer] -> Bool divisoresEn = undefined -- --------------------------------------------------------------------- -- Ejercicio 1.2. Los números de Hamming forman una sucesión -- estrictamente creciente de números que cumplen las siguientes -- condiciones: -- 1. El número 1 está en la sucesión. -- 2. Si x está en la sucesión, entonces 2x, 3x y 5x también están. -- 3. Ningún otro número está en la sucesión. -- Definir, usando divisoresEn, la constante -- hamming :: [Integer] -- tal que hamming es la sucesión de Hamming. Por ejemplo, -- take 12 hamming == [1,2,3,4,5,6,8,9,10,12,15,16] -- --------------------------------------------------------------------- hamming :: [Integer] hamming = undefined -- --------------------------------------------------------------------- -- Ejercicio 1.3. Definir la función -- cantidadHammingMenores :: Integer -> Int -- tal que (cantidadHammingMenores x) es la cantidad de números de -- Hamming menores que x. Por ejemplo, -- cantidadHammingMenores 6 == 5 -- cantidadHammingMenores 7 == 6 -- cantidadHammingMenores 8 == 6 -- --------------------------------------------------------------------- cantidadHammingMenores :: Integer -> Int cantidadHammingMenores x = undefined -- --------------------------------------------------------------------- -- Ejercicio 1.4. Definir la función -- siguienteHamming :: Integer -> Integer -- tal que (siguienteHamming x) es el menor número de la sucesión de -- Hamming mayor que x. Por ejemplo, -- siguienteHamming 6 == 8 -- siguienteHamming 21 == 24 -- --------------------------------------------------------------------- siguienteHamming :: Integer -> Integer siguienteHamming x = undefined -- --------------------------------------------------------------------- -- Ejercicio 1.5. Definir la función -- huecoHamming :: Integer -> [(Integer,Integer)] -- tal que (huecoHamming n) es la lista de pares de números consecutivos -- en la sucesión de Hamming cuya distancia es mayor o igual que n. Por -- ejemplo, -- take 4 (huecoHamming 2) == [(12,15),(20,24),(27,30),(32,36)] -- take 3 (huecoHamming 2) == [(12,15),(20,24),(27,30)] -- take 2 (huecoHamming 3) == [(20,24),(32,36)] -- head (huecoHamming 10) == (108,120) -- head (huecoHamming 1000) == (34992,36000) -- --------------------------------------------------------------------- huecoHamming :: Integer -> [(Integer,Integer)] huecoHamming n = undefined -- --------------------------------------------------------------------- -- Ejercicio 1.6. Comprobar con QuickCheck que para todo n, existen -- pares de números consecutivos en la sucesión de Hamming cuya -- distancia es mayor o igual que n. -- --------------------------------------------------------------------- -- La propiedad es prop_Hamming :: Integer -> Bool prop_Hamming n = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 2.1. Definir la función -- iniciales :: [a] -> [[a]] -- tal que (iniciales xs) es la lista de los segmentos iniciales de la -- lista xs. Por ejemplo, -- iniciales [2,3,4] == [[],[2],[2,3],[2,3,4]] -- iniciales [1,2,3,4] == [[],[1],[1,2],[1,2,3],[1,2,3,4]] -- --------------------------------------------------------------------- iniciales :: [a] -> [[a]] iniciales = undefined -- --------------------------------------------------------------------- -- Ejercicio 2.2. Comprobar con QuickCheck que el número de los -- segmentos iniciales es el número de los elementos de la lista más -- uno. -- --------------------------------------------------------------------- -- La propiedad es prop_iniciales :: [Int] -> Bool prop_iniciales xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 3.1. Definir la función -- finales :: [a] -> [[a]] -- tal que (finales xs) es la lista de los segmentos finales de la lista -- xs. Por ejemplo, -- finales [2,3,4] == [[2,3,4],[3,4],[4],[]] -- finales [1,2,3,4] == [[1,2,3,4],[2,3,4],[3,4],[4],[]] -- --------------------------------------------------------------------- finales :: [a] -> [[a]] finales = undefined -- --------------------------------------------------------------------- -- Ejercicio 3.2. Comprobar con QuickCheck que el número de los -- segmentos finales es el número de los elementos de la lista más uno. -- --------------------------------------------------------------------- -- La propiedad es prop_finales :: [Int] -> Bool prop_finales xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 4.1. Definir la función -- segmentos :: [a] -> [[a]] -- tal que (segmentos xs) es la lista de los segmentos de la lista -- xs. Por ejemplo, -- Main> segmentos [2,3,4] -- [[],[4],[3],[3,4],[2],[2,3],[2,3,4]] -- Main> segmentos [1,2,3,4] -- [[],[4],[3],[3,4],[2],[2,3],[2,3,4],[1],[1,2],[1,2,3],[1,2,3,4]] -- --------------------------------------------------------------------- segmentos :: [a] -> [[a]] segmentos = undefined -- --------------------------------------------------------------------- -- Ejercicio 4.2. Comprobar con QuickCheck que todos los segmentos -- iniciales de xs son segmentos de xs. -- --------------------------------------------------------------------- -- La propiedad es prop_iniciales_segmentos :: [Int] -> Bool prop_iniciales_segmentos xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 4.3. Comprobar con QuickCheck que si para todo lista xs se -- verifica que (segmentos xs) tiene algún elemento que no pertenece a -- (iniciales xs) ni a (finales xs). -- -- En el caso de no verificarse, determinar una condición suficiente -- para que se verifique. -- --------------------------------------------------------------------- -- La propiedad general es prop_segmentos :: [Int] -> Bool prop_segmentos xs = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 5.1. Definir la función -- subconjuntos :: [a] -> [[a]] -- tal que (subconjuntos xs) es la lista de las subconjuntos de la lista -- xs. Por ejemplo, -- Main> subconjuntos [2,3,4] -- [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]] -- Main> subconjuntos [1,2,3,4] -- [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1], -- [2,3,4], [2,3], [2,4], [2], [3,4], [3], [4], []] -- --------------------------------------------------------------------- subconjuntos :: [a] -> [[a]] subconjuntos = undefined -- --------------------------------------------------------------------- -- Ejercicio 6.1. Definir, por recursión, la función -- subconjunto :: Eq a => [a] -> [a] -> Bool -- tal que (subconjunto xs ys) se verifica si xs es un subconjunto de -- ys. Por ejemplo, -- subconjunto [1,3,2,3] [1,2,3] == True -- subconjunto [1,3,4,3] [1,2,3] == False -- --------------------------------------------------------------------- subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto = undefined -- --------------------------------------------------------------------- -- Ejercicio 6.2. Definir, mediante all, la función -- subconjunto' :: Eq a => [a] -> [a] -> Bool -- tal que (subconjunto' xs ys) se verifica si xs es un subconjunto de -- ys. Por ejemplo, -- subconjunto' [1,3,2,3] [1,2,3] == True -- subconjunto' [1,3,4,3] [1,2,3] == False -- --------------------------------------------------------------------- subconjunto' :: Eq a => [a] -> [a] -> Bool subconjunto' xs ys = undefined -- --------------------------------------------------------------------- -- Ejercicio 6.3. Comprobar con QuickCheck que las funciones subconjunto -- y subconjunto' son equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_equivalencia :: [Int] -> [Int] -> Bool prop_equivalencia xs ys = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- igualConjunto :: Eq a => [a] -> [a] -> Bool -- tal que (igualConjunto xs ys) se verifica si las listas xs e ys, -- vistas como conjuntos, son iguales. Por ejemplo, -- igualConjunto [1..10] [10,9..1] == True -- igualConjunto [1..10] [11,10..1] == False -- --------------------------------------------------------------------- igualConjunto :: Eq a => [a] -> [a] -> Bool igualConjunto xs ys = undefined -- --------------------------------------------------------------------- -- Ejercicio 8. Definir la función -- permutaciones :: Eq a => [a] -> [[a]] -- tal que (permutaciones xs) es la lista de las permutaciones de la -- lista xs. Por ejemplo, -- Main> permutaciones [2,3] -- [[2,3],[3,2]] -- Main> permutaciones [1,2,3] -- [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] -- --------------------------------------------------------------------- permutaciones :: Eq a => [a] -> [[a]] permutaciones = undefined -- --------------------------------------------------------------------- -- Ejercicio 9. Definir la función -- combinaciones :: Int -> [a] -> [[a]] -- tal que (combinaciones n xs) es la lista de las combinaciones n-arias -- de la lista xs. Por ejemplo, -- combinaciones 2 [1,2,3,4] == [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] -- --------------------------------------------------------------------- combinaciones :: Int -> [a] -> [[a]] combinaciones n xs = undefined -- --------------------------------------------------------------------- -- Ejercicio 10. El triángulo de Pascal es un triángulo de números -- 1 -- 1 1 -- 1 2 1 -- 1 3 3 1 -- 1 4 6 4 1 -- 1 5 10 10 5 1 -- ............... -- construido de la siguiente forma -- * la primera fila está formada por el número 1; -- * las filas siguientes se construyen sumando los números adyacentes -- de la fila superior y añadiendo un 1 al principio y al final de la -- fila. -- --------------------------------------------------------------------- -- Ejercicio 10.1. Definir la función -- pascal :: Integer -> [Integer] -- tal que (pascal n) es lan-ésima fila del triángulo de Pascal. Por -- ejemplo, -- pascal 6 ==> [1,5,10,10,5,1] -- ---------------------------------------------------------------------------- pascal :: Integer -> [Integer] pascal = undefined -- --------------------------------------------------------------------- -- Ejercicio 10.2. Comprobar con QuickCheck, que la fila n-ésima del -- triángulo de Pascal tiene n elementos. -- --------------------------------------------------------------------- -- La propiedad es prop_Pascal :: Integer -> Property prop_Pascal n = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 10.3. Comprobar con QuickCheck, que la suma de los -- elementos de la fila n-ésima del triángulo de Pascal es igual a -- 2^(n-1). -- --------------------------------------------------------------------- -- la propiedad es prop_sumaPascal :: Integer -> Property prop_sumaPascal n = undefined -- La comprobación es -- --------------------------------------------------------------------- -- Ejercicio 10.4. Comprobar con QuickCheck, que el m-ésimo elemento de -- la fila (n+1)-ésima del triángulo de Pascal es el número combinatorio -- (n sobre m) = n! / (k!(n-k)!). -- --------------------------------------------------------------------- -- La propiedad es prop_Combinaciones :: Integer -> Property prop_Combinaciones n = undefined -- La comprobación es