Horner

Avís

Per a resoldre aquest exercici no es poden fer servir iteracions (ni for ni while ), només funcions recursives.

La classe polinomi.Polinomi (idèntica a la d’aquest exercici) està especificada així:

class polinomi.Polinomi

Representa un polinomi que inicialment serà el polinomi nul amb tots els coeficients iguals a zero.

Mètode:

grau()

Retorna el grau del polinomi

Operacions:

Operació	Resultat
p[g]	retorna el valor que té el coeficient de grau g del polinomi p
p[g] = val	assigna el valor val al coeficient de grau g del polinomi p
p == v	retorna True si els polinomis p i v són iguals i False altrament

Disposeu d’una implementació de la classe polinomi.Polinomi al fitxer polinomi.py.

En el mòdul horner.py dissenyeu la funció recursiva següent:

horner.horner(p, x)

Retorna el valor del polinomi Polinomi p corresponent al valor x.

Per exemple:

>>> from polinomi import Polinomi 
>>> from horner import horner
>>> p = Polinomi()
>>> p[9]=2
>>> horner(p,2)
1024.0
>>> horner(p,1)
2.0
>>> q = Polinomi()
>>> q[3]=1; q[1]=1; q[0]= 1
>>> horner(q,1)
3.0
>>> horner(q,2)
11.0
>>> horner(q,3)
31.0

L’avaluació del polinomi s’implementarà seguint el mètode de Horner. Donat un polinomi \(p(x)\) de grau \(n\):

\[p(x) = \sum_{i=0}^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n\]

Es pot avaluar generant una seqüència de valors \(v_nv_{n-1}\ldots v_1v_0\) de la següent forma:

\[\begin{split}\begin{align} v_n & = a_n \\ v_{n-1} & = a_{n-1} + v_n x \\ \quad\quad\quad & ~~~ \vdots \\ v_1 & = a_1 + v_2 x \\ v_0 & = a_0 + v_1 x. \end{align}\end{split}\]

Essent finalment \(v_0 = p(x)\) el valor del polinomi en \(x\).

Nota

Disposeu de jocs de prova al fitxer test-horner.txt.

Solució

Disposeu d’una solució al fitxer horner.py.