-
Notifications
You must be signed in to change notification settings - Fork 0
/
relacion34.hs
259 lines (222 loc) · 11 KB
/
relacion34.hs
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
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
-- I1M 2015-16: Relación 34 (22 de abril de 2016)
-- División y factorización de polinomios mediante la regla de Ruffini.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================
-- ---------------------------------------------------------------------
-- Introducción --
-- ---------------------------------------------------------------------
-- El objetivo de esta relación de ejercicios es implementar la regla de
-- Ruffini y sus aplicaciones utilizando las implementaciones del TAD de
-- polinomio estudiadas en el tema 21 que se pueden descargar desde
-- http://www.cs.us.es/~jalonso/cursos/i1m-15/temas/tema-21.html
--
-- Para realizar los ejercicios hay que tener instalada la librería I1M
-- que contiene la implementación de TAD de los polinomios. Los pasos
-- para instalarla son los siguientes:
-- + Descargar el paquete I1M desde http://bit.ly/1pbnDqm
-- + Descomprimirlo (y se crea el directorio I1M-master.zip).
-- + Cambiar al directorio I1M-master.
-- + Ejecutar cabal install I1M.cabal
--
-- Otra forma es descargar, en el directorio de ejercicios, la
-- implementación del TAD de polinomios:
-- + PolRepTDA que está en http://bit.ly/1WJnS93
-- + PolRepDispersa que está en http://bit.ly/1WJnUO8
-- + PolRepDensa que está en http://bit.ly/1WJnV4E
-- + PolOperaciones que está en http://bit.ly/1WJnTd7
-- ---------------------------------------------------------------------
-- Importación de librerías --
-- ---------------------------------------------------------------------
import Test.QuickCheck
-- Hay que elegir una librería
import I1M.PolOperaciones
-- import PolOperaciones
-- ---------------------------------------------------------------------
-- Ejemplos --
-- ---------------------------------------------------------------------
-- Además de los ejemplos de polinomios (ejPol1, ejPol2 y ejPol3) que se
-- encuentran en PolOperaciones, usaremos el siguiente ejemplo.
ejPol11 :: Polinomio Int
ejPol11 = consPol 4 3 $ consPol 2 (-5) $ consPol 0 3 polCero
ejPol12 :: Polinomio Int
ejPol12 = consPol 5 1 $ consPol 2 5 $ consPol 1 4 polCero
ejPol14 :: Polinomio Int
ejPol14 = consPol 3 1
(consPol 2 2
(consPol 1 (-1)
(consPol 0 (-2) polCero)))
-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función
-- divisores :: Int -> [Int]
-- tal que (divisores n) es la lista de todos los divisores enteros de
-- n. Por ejemplo,
-- divisores 4 == [1,2,4,-1,-2,-4]
-- ---------------------------------------------------------------------
divisores :: Int -> [Int]
divisores 0 = [0]
divisores n = xs ++ map (*(-1)) xs
where xs = 1:[x | x <- [2..n], n `rem` x == 0]
-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
-- coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a
-- tal que (coeficiente k p) es el coeficiente del término de grado k en
-- p. Por ejemplo:
-- coeficiente 4 ejPol1 == 3
-- coeficiente 3 ejPol1 == 0
-- coeficiente 2 ejPol1 == -5
-- coeficiente 5 ejPol1 == 0
-- ---------------------------------------------------------------------
coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a
coeficiente k p | k > n = 0
| k < n = coeficiente k (restoPol p)
| otherwise = coefLider p
where n = grado p
-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
-- terminoIndep :: (Num a, Eq a) => Polinomio a -> a
-- tal que (terminoIndep p) es el término independiente del polinomio
-- p. Por ejemplo,
-- terminoIndep ejPol1 == 3
-- terminoIndep ejPol2 == 0
-- terminoIndep ejPol4 == -2
-- ---------------------------------------------------------------------
terminoIndep :: (Num a, Eq a) => Polinomio a -> a
terminoIndep = coeficiente 0
-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
-- coeficientes :: (Num a, Eq a) => Polinomio a -> [a]
-- tal que (coeficientes p) es la lista de coeficientes de p, ordenada
-- según el grado. Por ejemplo,
-- coeficientes ejPol1 == [3,0,-5,0,3]
-- coeficientes ejPol4 == [1,2,-1,-2]
-- coeficientes ejPol2 == [1,0,0,5,4,0]
-- ---------------------------------------------------------------------
coeficientes :: (Num a, Eq a) => Polinomio a -> [a]
coeficientes p = rastreaCoef [n,n-1..0] p
where n = grado p
rastreaCoef :: (Num a, Eq a) => [Int] -> Polinomio a -> [a]
rastreaCoef (n:ns) p | esPolCero p = []
| otherwise = coeficiente n p:
rastreaCoef ns p
rastreaCoef [] _ = []
-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir la función
-- creaPol :: (Num a, Eq a) => [a] -> Polinomio a
-- tal que (creaPol cs) es el polinomio cuya lista de coeficientes es
-- cs. Por ejemplo,
-- creaPol [1,0,0,5,4,0] == x^5 + 5*x^2 + 4*x
-- creaPol [1,2,0,3,0] == x^4 + 2*x^3 + 3*x
-- ---------------------------------------------------------------------
creaPol :: (Num a, Eq a) => [a] -> Polinomio a
creaPol [] = polCero
creaPol xs = construye (length xs - 1) xs
where construye :: (Num a, Eq a) => Int -> [a] -> Polinomio a
construye k (x:xs) = consPol k x (construye (k-1) xs)
construye _ _ = polCero
-- ---------------------------------------------------------------------
-- Ejercicio 6. Comprobar con QuickCheck que, dado un polinomio p, el
-- polinomio obtenido mediante creaPol a partir de la lista de
-- coeficientes de p coincide con p.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_coef:: Polinomio Int -> Bool
prop_coef p = p == creaPol (coeficientes p)
-- La comprobación es
-- ghci> quickCheck prop_coef
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir una función
-- pRuffini:: Int -> [Int] -> [Int]
-- tal que (pRuffini r cs) es la lista que resulta de aplicar un paso
-- del regla de Ruffini al número entero r y a la lista de coeficientes
-- cs. Por ejemplo,
-- pRuffini 2 [1,2,-1,-2] == [1,4,7,12]
-- pRuffini 1 [1,2,-1,-2] == [1,3,2,0]
-- ya que
-- | 1 2 -1 -2 | 1 x -1 -2
-- 2 | 2 8 14 n | 1 3 2
-- --+-------------- --+-------------
-- | 1 4 7 12 | r 3 2 0
-- ---------------------------------------------------------------------
pRuffini :: Int -> [Int] -> [Int]
pRuffini n (x:xs) = x: ruffini n xs x
where ruffini :: Int -> [Int] -> Int -> [Int]
ruffini n (x:xs) r = y : ruffini n xs y
where y = x + n * r
ruffini _ _ _ = []
-- ---------------------------------------------------------------------
-- Ejercicio 8. Definir la función
-- cocienteRuffini:: Int -> Polinomio Int -> Polinomio Int
-- tal que (cocienteRuffini r p) es el cociente de dividir el polinomio
-- p por el polinomio x-r. Por ejemplo:
-- cocienteRuffini 2 ejPol4 == x^2 + 4*x + 7
-- cocienteRuffini (-2) ejPol4 == x^2 + -1
-- cocienteRuffini 3 ejPol4 == x^2 + 5*x + 14
-- ---------------------------------------------------------------------
cocienteRuffini:: Int -> Polinomio Int -> Polinomio Int
cocienteRuffini r = creaPol . init . pRuffini r . coeficientes
-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir la función
-- restoRuffini:: Int -> Polinomio Int -> Int
-- tal que (restoRuffini r p) es el resto de dividir el polinomio p por
-- el polinomio x-r. Por ejemplo,
-- restoRuffini 2 ejPol4 == 12
-- restoRuffini (-2) ejPol4 == 0
-- restoRuffini 3 ejPol4 == 40
-- ---------------------------------------------------------------------
restoRuffini:: Int -> Polinomio Int -> Int
restoRuffini r = last . pRuffini r . coeficientes
-- ---------------------------------------------------------------------
-- Ejercicio 10. Comprobar con QuickCheck que, dado un polinomio p y un
-- número entero r, las funciones anteriores verifican la propiedad de
-- la división euclídea.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_diviEuclidea:: Int -> Polinomio Int -> Bool
prop_diviEuclidea r p =
p == ((cocienteRuffini r p) `multPol`(creaPol [1,-r]))
`sumaPol` (consPol 0 (restoRuffini r p) polCero)
-- La comprobación es
-- ghci> quickCheck prop_diviEuclidea
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 11. Definir la función
-- esRaizRuffini:: Int -> Polinomio Int -> Bool
-- tal que (esRaizRuffini r p) se verifica si r es una raiz de p, usando
-- para ello el regla de Ruffini. Por ejemplo,
-- esRaizRuffini 0 ejPol3 == True
-- esRaizRuffini 1 ejPol3 == False
-- ---------------------------------------------------------------------
esRaizRuffini :: Int -> Polinomio Int -> Bool
esRaizRuffini r p = restoRuffini r p == 0
-- ---------------------------------------------------------------------
-- Ejercicio 12. Definir la función
-- raicesRuffini :: Polinomio Int -> [Int]
-- tal que (raicesRuffini p) es la lista de las raices enteras de p,
-- calculadas usando el regla de Ruffini. Por ejemplo,
-- raicesRuffini ejPol1 == []
-- raicesRuffini ejPol2 == [0]
-- raicesRuffini ejPol3 == [0]
-- raicesRuffini ejPol4 == [-2,-1,1]
-- ---------------------------------------------------------------------
raicesRuffini :: Polinomio Int -> [Int]
raicesRuffini p = filter (flip esRaizRuffini p)
(divisores $ terminoIndep p)
-- ---------------------------------------------------------------------
-- Ejercicio 13. Definir la función
-- factorizacion :: Polinomio Int -> [Polinomio Int]
-- tal que (factorizacion p) es la lista de la descomposición del
-- polinomio p en factores obtenida mediante el regla de Ruffini. Por
-- ejemplo,
-- ghci> factorizacion (creaPol [1,0,0,0,-1])
-- [x^2 + 1,1*x + 1,1*x + -1]
-- ---------------------------------------------------------------------
factorizacion :: Polinomio Int -> [Polinomio Int]
factorizacion p | esPolCero p = [polCero]
| otherwise = descompon p (raicesRuffini p)
where descompon :: Polinomio Int -> [Int] -> [Polinomio Int]
descompon p [] = [p]
descompon p (a:as) = q : descompon r as
where q = consPol 1 1 $ consPol 0 (-a) polCero
r = cocienteRuffini a p