I1M2012: Problemas 8 y 9 y ejercicios sobre cadenas
En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los problemas 8 (números bonitos y números feos) y 9 (ceros finales del factorial).
En la segunda parte hemos comentado las soluciones de los ejercicios 4 y 6 de la 12ª relación de funciones sobre cadenas.
Los ejercicios, y sus soluciones, se muestran a continuació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 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Data.Char import Data.List import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 4.1. Definir, por comprensión, la función -- buscaCrucigrama :: Char -> Int -> Int -> [String] -> [String] -- tal que (buscaCrucigrama l pos lon ps) es la lista de las palabras de -- la lista de palabras ps que tienen longitud lon y poseen la letra l en -- la posición pos (comenzando en 0). Por ejemplo, -- ghci> buscaCrucigrama 'c' 1 7 ["ocaso", "casa", "ocupado"] -- ["ocupado"] -- --------------------------------------------------------------------- buscaCrucigrama :: Char -> Int -> Int -> [String] -> [String] buscaCrucigrama l pos lon ps = [p | p <- ps, length p == lon, 0 <= pos, pos < length p, p !! pos == l] -- --------------------------------------------------------------------- -- Ejercicio 4.2. Definir, por recursión, la función -- buscaCrucigramaR :: Char -> Int -> Int -> [String] -> [String] -- tal que (buscaCrucigramaR l pos lon ps) es la lista de las palabras -- de la lista de palabras ps que tienn longitud lon y posen la letra l -- en la posición pos (comenzando en 0). Por ejemplo, -- ghci> buscaCrucigramaR 'c' 1 7 ["ocaso", "acabado", "ocupado"] -- ["acabado","ocupado"] -- --------------------------------------------------------------------- buscaCrucigramaR :: Char -> Int -> Int -> [String] -> [String] buscaCrucigramaR letra pos lon [] = [] buscaCrucigramaR letra pos lon (p:ps) | length p == lon && 0 <= pos && pos < length p && p !! pos == letra = p : buscaCrucigramaR letra pos lon ps | otherwise = buscaCrucigramaR letra pos lon ps -- --------------------------------------------------------------------- -- Ejercicio 4.3. Comprobar con QuickCheck que ambas definiciones son -- equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_buscaCrucigrama :: Char -> Int -> Int -> [String] -> Bool prop_buscaCrucigrama letra pos lon ps = buscaCrucigrama letra pos lon ps == buscaCrucigramaR letra pos lon ps -- La comprobación es -- ghci> quickCheck prop_buscaCrucigrama -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 6.1. Definir, por recursión, la función -- contieneR :: String -> String -> Bool -- tal que (contieneR xs ys) se verifica si ys es una subcadena de -- xs. Por ejemplo, -- contieneR "escasamente" "casa" == True -- contieneR "escasamente" "cante" == False -- contieneR "" "" == True -- Nota: Se puede usar la predefinida (isPrefixOf ys xs) que se verifica -- si ys es un prefijo de xs. -- --------------------------------------------------------------------- contieneR :: String -> String -> Bool contieneR _ [] = True contieneR [] ys = False contieneR xs ys = isPrefixOf ys xs || contieneR (tail xs) ys -- --------------------------------------------------------------------- -- Ejercicio 6.2. Definir, por comprensión, la función -- contiene :: String -> String -> Bool -- tal que (contiene xs ys) se verifica si ys es una subcadena de -- xs. Por ejemplo, -- contiene "escasamente" "casa" == True -- contiene "escasamente" "cante" == False -- contiene "casado y casada" "casa" == True -- contiene "" "" == True -- Nota: Se puede usar la predefinida (isPrefixOf ys xs) que se verifica -- si ys es un prefijo de xs. -- --------------------------------------------------------------------- contiene :: String -> String -> Bool contiene xs ys = or [isPrefixOf ys zs | zs <- sufijos xs] -- (sufijos xs) es la lista de sufijos de xs. Por ejemplo, -- sufijos "abc" == ["abc","bc","c",""] sufijos :: String -> [String] sufijos xs = [drop i xs | i <- [0..length xs]] -- Notas: -- 1. La función sufijos es equivalente a la predefinida tails. -- 2. contiene se puede definir usando la predefinida isInfixOf contiene2 :: String -> String -> Bool contiene2 xs ys = isInfixOf ys xs -- --------------------------------------------------------------------- -- Ejercicio 6.3. Comprobar con QuickCheck que ambas definiciones son -- equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_contiene :: String -> String -> Bool prop_contiene xs ys = contieneR xs ys == contiene xs ys -- La comprobación es -- ghci> quickCheck prop_contiene -- +++ OK, passed 100 tests. |