2. Potència d’un polinomi

Avís

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

2.1. Funció eleva_pol (2 punts)

En aquest exercici treballarem amb la classe Polinomi, que representa un polinomi amb una sola variable. Reviseu la seva especificació i fixeu-vos que disposa de les operacions str(), suma i producte, entre d’altres. La trobareu implementada al fitxer polinomis.py.

Volem elevar un polinomi a un nombre natural n, és a dir, volem calcular \([p(x)]^n, \, n \in \mathbb{N}\). Utilitzarem el mètode d’elevació ràpida, consistent en utilitzar la següent definició recursiva:

\[\begin{split}&\quad [p(x)]^0=1,\\[4pt] &\quad \text{per }n\ge 1, \quad [p(x)]^{n}= \begin{cases} r(x) \cdot r(x), & \text{amb} \;\; r(x) = [p(x)]^{n/2} & \text{si } n \text{ és parell}, \\[6pt] p(x) \cdot r(x) \cdot r(x), & \text{amb} \;\; r(x) = [p(x)]^{(n-1)/2} & \text{si }n\text{ és senar}. \end{cases}\end{split}\]

Es demana que, utilitzant aquesta definició, implementeu la funció que eleva un polinomi p a una potència n. Deseu-la al mòdul power (fitxer power.py).

power.eleva_pol(p, n)
Paràmetres:

  • p (Polinomi) – base (polinomi que es vol elevar)

  • n (int) – exponent (enter no negatiu)

Retorna:

\([p(x)]^n\) (p elevat a n)

Tipus de retorn:

Polinomi

Per exemple,


>>> from polinomis import Polinomi
>>> from power import eleva_pol

>>> p = Polinomi()
>>> q = eleva_pol(p, 0)
>>> print("[p(x)]^0 =", q)
[p(x)]^0 = 1
>>> isinstance(q, Polinomi)  # Comprovació que la funció retorna un Polinomi
True

>>> p = Polinomi()
>>> p[1], p[0] = 3, 1
>>> q = eleva_pol(p, 2)
>>> print("p(x) =", p, "; [p(x)]^2 =", q)
p(x) = 3x+1 ; [p(x)]^2 = 9x^2+6x+1

>>> p = Polinomi()
>>> p[3], p[2], p[1] = 1, -1, -2
>>> q = eleva_pol(p, 5)
>>> print("p(x) =", p, "; [p(x)]^5 =", q)
p(x) = x^3-x^2-2x ; [p(x)]^5 = x^15-5x^14+30x^12-15x^11-81x^10+30x^9+120x^8-80x^6-32x^5

Disposeu de més jocs de prova en el fitxer tests-eleva.txt.