I1M2011: Operaciones con el TAD de los polinomios en Haskell (2)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos continuado estudiando la implementación en Haskell de operaciones con los polinomios utilizando las implementaciones del TAD de los polinomios estudiadas en las clases anteriores.
En los ejercicios se usan las siguientes libretrías:
- PolRepTDA: Implementación de los polinomios mediante tipos de datos algebraicos.
- PolRepDispersa: Implementación de los polinomios mediante listas dispersas.
- PolRepDensa: Implementación de los polinomios mediante listas densas.
- PolOperaciones: Operaciones con el TAD de los polinomios.
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 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 |
-- --------------------------------------------------------------------- -- Importación de librerías -- -- --------------------------------------------------------------------- import PolOperaciones import Test.QuickCheck import Data.Ratio -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- creaPolDispersa :: Num a => [a] -> Polinomio a -- tal que (creaPolDispersa xs) es el polinomio cuya representación -- dispersa es xs. Por ejemplo, -- creaPolDispersa [7,0,0,4,0,3] == 7*x^5 + 4*x^2 + 3 -- --------------------------------------------------------------------- creaPolDispersa :: Num a => [a] -> Polinomio a creaPolDispersa [] = polCero creaPolDispersa (x:xs) = consPol (length xs) x (creaPolDispersa xs) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- creaPolDensa :: Num a => [(Int,a)] -> Polinomio a -- tal que (creaPolDensa xs) es el polinomio cuya representación -- densa es xs. Por ejemplo, -- creaPolDensa [(5,7),(4,2),(3,0)] == 7*x^5 + 2*x^4 -- --------------------------------------------------------------------- creaPolDensa :: Num a => [(Int,a)] -> Polinomio a creaPolDensa [] = polCero creaPolDensa ((n,a):ps) = consPol n a (creaPolDensa ps) -- --------------------------------------------------------------------- -- Nota. En el resto de la sucesión se usará en los ejemplos los -- los polinomios que se definen a continuación. -- --------------------------------------------------------------------- pol1, pol2, pol3 :: Num a => Polinomio a pol1 = creaPolDensa [(5,1),(2,5),(1,4)] pol2 = creaPolDispersa [2,3] pol3 = creaPolDensa [(7,2),(4,5),(2,5)] pol4, pol5, pol6 :: Polinomio Rational pol4 = creaPolDensa [(4,3),(2,5),(0,3)] pol5 = creaPolDensa [(2,6),(1,2)] pol6 = creaPolDensa [(2,8),(1,14),(0,3)] -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- densa :: Num a => Polinomio a -> [(Int,a)] -- tal que (densa p) es la representación densa del polinomio p. Por -- ejemplo, -- pol1 == x^5 + 5*x^2 + 4*x -- densa pol1 == [(5,1),(2,5),(1,4)] -- --------------------------------------------------------------------- densa :: Num a => Polinomio a -> [(Int,a)] densa p | esPolCero p = [] | otherwise = (grado p, coefLider p) : densa (restoPol p) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- densaAdispersa :: Num a => [(Int,a)] -> [a] -- tal que (densaAdispersa ps) es la representación dispersa del -- polinomio cuya representación densa es ps. Por ejemplo, -- densaAdispersa [(5,1),(2,5),(1,4)] == [1,0,0,5,4,0] -- --------------------------------------------------------------------- densaAdispersa :: Num a => [(Int,a)] -> [a] densaAdispersa [] = [] densaAdispersa [(n,a)] = a : replicate n 0 densaAdispersa ((n,a):(m,b):ps) = a : (replicate (n-m-1) 0) ++ densaAdispersa ((m,b):ps) -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- dispersa :: Num a => Polinomio a -> [a] -- tal que (dispersa p) es la representación dispersa del polinomio -- p. Por ejemplo, -- pol1 == x^5 + 5*x^2 + 4*x -- dispersa pol1 == [1,0,0,5,4,0] -- --------------------------------------------------------------------- dispersa :: Num a => Polinomio a -> [a] dispersa = densaAdispersa . densa -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- coeficiente :: Num a => Int -> Polinomio a -> a -- tal que (coeficiente k p) es el coeficiente del término de grado k -- del polinomio p. Por ejemplo, -- pol1 == x^5 + 5*x^2 + 4*x -- coeficiente 2 pol1 == 5 -- coeficiente 3 pol1 == 0 -- --------------------------------------------------------------------- coeficiente :: Num a => Int -> Polinomio a -> a coeficiente k p | k == n = coefLider p | k > grado (restoPol p) = 0 | otherwise = coeficiente k (restoPol p) where n = grado p -- Otra definición equivalente es coeficiente' :: Num a => Int -> Polinomio a -> a coeficiente' k p = busca k (densa p) where busca k ps = head ([a | (n,a) <- ps, n == k] ++ [0]) -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- coeficientes :: Num a => Polinomio a -> [a] -- tal que (coeficientes p) es la lista de los coeficientes del -- polinomio p. Por ejemplo, -- pol1 == x^5 + 5*x^2 + 4*x -- coeficientes pol1 == [1,0,0,5,4,0] -- --------------------------------------------------------------------- coeficientes :: Num a => Polinomio a -> [a] coeficientes p = [coeficiente k p | k <-[n,n-1..0]] where n = grado p -- Una definición equivalente es coeficientes' :: Num a => Polinomio a -> [a] coeficientes' = dispersa -- --------------------------------------------------------------------- -- Ejercicio 8. Definir la función -- potencia :: Num a => Polinomio a -> Int -> Polinomio a -- tal que (potencia p n) es la potencia n-ésima del polinomio p. Por -- ejemplo, -- pol2 == 2*x + 3 -- potencia pol2 2 == 4*x^2 + 12*x + 9 -- potencia pol2 3 == 8*x^3 + 36*x^2 + 54*x + 27 -- --------------------------------------------------------------------- potencia :: Num a => Polinomio a -> Int -> Polinomio a potencia p 0 = polUnidad potencia p n = multPol p (potencia p (n-1)) -- --------------------------------------------------------------------- -- Ejercicio 9. Mejorar la definición de potencia definiendo la función -- potenciaM :: Num a => Polinomio a -> Int -> Polinomio a -- tal que (potenciaM p n) es la potencia n-ésima del polinomio p, -- utilizando las siguientes propiedades: -- * Si n es par, entonces x^n = (x^2)^(n/2) -- * Si n es impar, entonces x^n = x * (x^2)^((n-1)/2) -- Por ejemplo, -- pol2 == 2*x + 3 -- potenciaM pol2 2 == 4*x^2 + 12*x + 9 -- potenciaM pol2 3 == 8*x^3 + 36*x^2 + 54*x + 27 -- --------------------------------------------------------------------- potenciaM :: Num a => Polinomio a -> Int -> Polinomio a potenciaM p 0 = polUnidad potenciaM p n | even n = potenciaM (multPol p p) (n `div` 2) | otherwise = multPol p (potenciaM (multPol p p) ((n-1) `div` 2)) |