TAD de los polinomios: Regla de Ruffini con representación densa
Usando el tipo abstracto de los polinomios definir la función
|
1 |
ruffiniDensa :: Int -> [Int] -> [Int] |
tal que ruffiniDensa r cs es la lista de los coeficientes del cociente junto con el rsto que resulta de aplicar la regla de Ruffini para dividir el polinomio cuya representación densa es cs entre x-r. Por ejemplo,
|
1 2 |
ruffiniDensa 2 [1,2,-1,-2] == [1,4,7,12] ruffiniDensa 1 [1,2,-1,-2] == [1,3,2,0] |
ya que
|
1 2 3 4 |
| 1 2 -1 -2 | 1 2 -1 -2 2 | 2 8 14 1 | 1 3 2 --+-------------- --+------------- | 1 4 7 12 | 1 3 2 0 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
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 |
import Test.QuickCheck -- 1ª solución -- =========== ruffiniDensa :: Int -> [Int] -> [Int] ruffiniDensa _ [] = [] ruffiniDensa r p@(c:cs) = c : [x+r*y | (x,y) <- zip cs (ruffiniDensa r p)] -- 2ª solución -- =========== ruffiniDensa2 :: Int -> [Int] -> [Int] ruffiniDensa2 r = scanl1 (\s x -> s * r + x) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_ruffiniDensa :: Int -> [Int] -> Bool prop_ruffiniDensa r cs = ruffiniDensa r cs == ruffiniDensa2 r cs -- La comprobación es -- λ> quickCheck prop_ruffiniDensa -- +++ OK, passed 100 tests. |
|
1 2 3 4 5 6 7 |
def ruffiniDensa(r: int, p: list[int]) -> list[int]: if not p: return [] res = [p[0]] for x in p[1:]: res.append(x + r * res[-1]) return res |