TAD de los polinomios - Regla de Ruffini con representación densa
Utilizando el tipo abstracto de datos de los polinomios definir la función
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,
ruffiniDensa 2 [1,2,-1,-2] == [1,4,7,12] ruffiniDensa 1 [1,2,-1,-2] == [1,3,2,0]
ya que
| 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.
Soluciones en Haskell
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.
Soluciones en Python
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