TNSI : TD Classe Polynôme⚓︎

On se donne la classe Poly suivante (à compléter) :

class Poly:
  def __init__(self, ...etc...):
    # ... à compléter ...

Compléter le constructeur __init__(self, p=[0]) de sorte que:
- il reçoive en entrée un argument p sous forme d'une liste Python. Nous modéliserons les polynômes donnés en entrée pour instancier un objet de la classe Poly, par une logique inspirée des exemples suivants :
  - [5] \(=5x^0=5\times 1 = 5\) (rappel: dans ce cas, le degré du polynôme vaut \(0\))
  - [3,5] \(=3x^1+5x^0=3x+5\) (rappel: dans ce cas, le degré du polynôme vaut \(1\))
  - [2,3,5] \(=2x^2+3x^1+5x^0=2x^2+3x+5\) (rappel: dans ce cas, le degré du polynôme vaut \(2\))
  - [4,2,3,5] \(=4x^3+2x^2+3x^1+5x^0=4x^3+2x^2+3x+5\) (rappel: dans ce cas, le degré du polynôme vaut \(3\))
  - etc..
Créer un attribut public d'instance, coeffs qui contient la liste des coefficients [a_n,..,a_2,a_1,a_0] modélisant le polynôme
Créer une méthode magique __repr__() qui représente le polynôme de l'instance courante self dans un Terminal, sous la forme a_n x^n + ...+ a_2 x^2 + a_1 x + a_0 où a_n, .. , a_2, a_1, a_0 désignent les coefficients du polynôme.
On pourra améliorer l'affichage dans Terminal en affichant, par exemple : 7x^2-3x+5 plutôt que 7x^2+-3x+5
Créer une méthode degre() qui renvoie le degré de l'instance courante self
Créer une méthode coeff(n:int)->float telle que:
- elle reçoit en entrée un entier n
- elle renvoie en sortie :
  - le coefficient a_n correspondant au monôme x^n, lorsque ce monôme existe dans le polynôme, ou bien,
  - \(0\) lorsque ce monôme n'existe pas dans le polynôme
Créer une méthode publique oppose() qui renvoie le polynôme opposé du polynôme de l'instance courante self. Le polynôme opposé est le polynôme dont chaque coefficient a été transformé en son opposé (l'opposé d'un coefficent \(a_n\) est \(-a_n\))
Créer une méthode magique __eq__() qui teste l'égalité de deux polynômes : rappelons que deux polynômes sont égaux si et seulement si:
- leur degré est le même
- tous leurs coefficents sont égaux deux à deux (pour les monômes correspondants) Cette méthode renvoie donc un booléen:
- True lorsque les deux polynômes sont égaux
- False sinon : lorsque les deux polynômes NE sont PAS égaux
Remarque Les deux syntaxes des méthodes magiques doivent donc fonctionner pour cette méthode précise, lorsque polynômeGauche et polynômeDroite sont deux instances de la classe Poly :
- ou bien polynômeGauche.__eq__(polynômeDroite)
- ou bien polynômeGauche == polynômeDroite
Créer une méthode magique __add__() qui ajoute deux polynômes. Cette méthode magique renvoie donc un object de classe Poly

Remarque Les deux syntaxes des méthodes magiques doivent donc fonctionner pour cette méthode précise, lorsque polynômeGauche et polynômeDroite sont deux instances de la classe Poly :
- ou bien polynômeGauche.__add__(polynômeDroite)
- ou bien polynômeGauche + polynômeDroite
Créer une méthode magique __sub__() qui soustrait deux polynômes. Cette méthode magique renvoie donc un object de classe Poly.

Remarque Les deux syntaxes des méthodes magiques doivent donc fonctionner pour cette méthode précise, lorsque polynômeGauche et polynômeDroite sont deux instances de la classe Poly :
- ou bien polynômeGauche.__sub__(polynômeDroite)
- ou bien polynômeGauche - polynômeDroite
Créer une méthode magique __mul__() qui multiplie deux polynômes. Cette méthode magique renvoie donc un object de classe Poly.

Remarque Les deux syntaxes des méthodes magiques doivent donc fonctionner pour cette méthode précise, lorsque polynômeGauche et polynômeDroite sont deux instances de la classe Poly :
- ou bien polynômeGauche.__mul__(polynômeDroite)
- ou bien polynômeGauche * polynômeDroite
Créer une méthode magique récursive __pow__(n:int) qui calcule le polynôme à la puissance un nombre entier (positif) n. Cette méthode magique renvoie donc un object de classe Poly.
On dispose de la propriété suivante pour des polynômes :
Vers la division euclidienne polynômiale, un début...

Soit \(A\) et \(B\) deux polynômes, avec \(B\neq 0\), alors il existe un unique couple \((Q_1,R_1)\) de deux polynômes \(Q_1\) et \(R_1\) tels que :
- \(Q_1\) est un monôme de la forme \(aX^n\), avec \(\deg(Q_1)=\deg(A)-\deg(B)\)
- \(A=Q_1\times B + R_1\), \(\,\) donc \(R_1 = A-Q_1\times B\)
- \(\deg(R_1) < \deg(A)\)
Exp

Soit \(A=X^5-X^4-X^3+3X^2-2X\) et \(B= X^2-X+1\), alors on peut toujours choisir \(Q_1\) comme un monôme simple, puis calculer \(R_1\) :
- On choisit \(Q_1=X^3\) (car \(X^2\times X^3=X^5\)),
- On calcule :
  \(\begin{align*} R_1 &= A-Q_1\times B\\ &= \underbrace{X^5-X^4-X^3+3X^2-2X}_{A} - \underbrace{X^3}_{Q_1}\underbrace{(X^2-X+1)}_{B} \\ &= -2X^3+3X^2-2X \\ \end{align*}\)
  Ce que l'on peut écrire :
\({\displaystyle \left.{\begin{matrix}A&=&X^{5}&-X^{4}&-X^{3}&+3X^{2}&-2X\\-Q_{1}.B&=&-X^{5}&+X^{4}&-X^{3}&&\\R_{1}&=&&&-2X^{3}&+3X^{2}&-2X\\\end{matrix}}\right|{\begin{matrix}X^{2}&-X&+1&=&B\\X^{3}&&&=&Q_{1}\\\\\end{matrix}}}\)
Créer une méthode divmodmono(B:Poly)->tuple(Q1,P1) telle que:
- Elle reçoit en entrée l'instance courante self d'un Polynôme \(A\) et un Polynôme \(B\), et
- elle renvoie en sortie le tuple des deux instances \((Q_1, R_1)\), de classe Poly, telles que décrites précécemment
Division Euclidienne Polynômiale
Info

Rappel : La division euclidienne entre deux entiers \(a\) et \(b\), avec \(b\neq 0\), est une opération arithmétique algorithmique permettant de déterminer de manière unique deux nombres entiers \(q\) (le quotient) et \(r\) (le reste), tels que:
- \(a=bq+r\)
- \(0\leq r \lt b\)
Par extension et généralisation, La Division Euclidienne Polynômiale d'un Polynôme \(A\) par un Polynôme \(B\), avec \(B\neq 0\), quelquefois appelée plus simplement Division Polynômiale de \(A\) par \(B\), est une opération arithmétique algorithmique généralisant la division euclienne dans le cas des polynômes. La division polynômiale de \(A\) par \(B\) détermine de manière unique un couple de deux polynômes \((Q,R)\) tel que :
- \(A=BQ+R\)
- \(0\leq \deg(R)<\deg(B)\)
Plus précisément, on dispose du :
Division Euclidienne Polynômiale

Soit \(A\) et \(B\) deux polynômes, avec \(B\neq 0\), alors il existe un unique couple de polynômes \((Q,R)\) appelés quotient (\(Q\)) et Reste (\(R\)) de la division euclidienne polynômiale de \(A\) par \(B\), tels que :
- \(Q\) est un polynôme avec \(\deg(Q)=\deg(A)-\deg(B)\)
- \(A=Q\times B + R\), \(\,\) donc \(R = A-Q\times B\)
- \(0\leq \deg(R) < \deg(B)\)
Exp

Il s'agit de poursuivre le calcul initié dans l'exemple 1 de la question précédente (car \(\deg(R_1)\geq \deg(B)\)), mais en repartant de là où on s'était arrêté dans la division polynômiale, càd en repartant de :
- \(A_1=R_1=-2X^3+3X^2-2X\) et
- \(B=X^2-X+1\) (ça, ça ne change pas)
- enfin, on répète récursivement ces divisions jusqu'à ce que \(\deg(R)<\deg(B)\) : auquel cas, la division euclidienne polynômiale s'arrête.
Dans notre cas :
- On choisit \(Q_2=-2X\) (car \(-2X\times X^2=-2X^3\)),
- On calcule :
  \(\begin{align*} R_2 &= A_1-Q_2\times B\\ &= R_1-Q_2\times B\\ &= \underbrace{-2X^3+3X^2-2X}_{A_1 (=R_1)} - \underbrace{-2X}_{Q_2}\underbrace{(X^2-X+1)}_{B} \\ &= X^2 \\ \end{align*}\)
  Ce que l'on peut écrire :
\({\displaystyle \left.{\begin{matrix}A&=&X^{5}&-X^{4}&-X^{3}&+3X^{2}&-2X&+0\\-Q_{1}.B&=&-X^{5}&+X^{4}&-X^{3}&&&\\R_{1}&=&&&-2X^{3}&+3X^{2}&-2X&\\-Q_{2}.B&=&&&+2X^{3}&-2X^{2}&+2X&\\R_{2}&=&&&&+X^{2}&&\\\end{matrix}}\right|{\begin{matrix}X^{2}&-X&+1&=&B\\X^{3}&-2X&&=&Q_{1}+Q_{2}\\\\\\\\\end{matrix}}}\)

On poursuit encore le calcul (car \(\deg(R_2)\geq \deg(B)\)), encore une fois là on s'est arrêté à l'étape précédente, càd avec \(A_2=R_2=X^2\) et (toujours) \(B=X^2-X+1\) (ça, ça ne change pas) :
- On choisit \(Q_3=+1\) (car \((+1)\times X^2=X^2\)),
- On calcule :
  \(\begin{align*} R_3 &= A_2-Q_3\times B\\ &= R_2-Q_3\times B\\ &= \underbrace{X^2}_{A_2 (=R_2)} - \underbrace{(+1)}_{Q_3}\underbrace{(X^2-X+1)}_{B} \\ &= X-1 \\ \end{align*}\)
  Ce que l'on peut écrire :
\({\displaystyle \left.{\begin{matrix}A=&X^{5}&-X^{4}&-X^{3}&+3X^{2}&-2X&+0\\&-X^{5}&+X^{4}&-X^{3}&&&\\&&&-2X^{3}&+3X^{2}&-2X&\\&&&+2X^{3}&-2X^{2}&+2X&\\&&&&+X^{2}&&\\&&&&-X^{2}&+X&-1\\R=&&&&&+X&-1\\\end{matrix}}\right|{\begin{matrix}X^{2}&-X&+1&=&B\\X^{3}&-2X&+1&=&Q\\\\\\\\\\\\\end{matrix}}}\)

La Division Euclidienne Polynômiale est donc terminée :

\(\underbrace{X^5-X^4-X^3+3X^2-2X}_{A}= \underbrace{(X^3-2X+1)}_{Q} \underbrace{(X^2-X+1)}_{B} +\underbrace{(X-1)}_{R}\)
Créer une méthode magique __divmod__(B:Poly)->tuple(Q:Poly, R:Poly) (récursive si possible) telle que:
- Elle reçoit en entrée l'instance courante self du Polynôme \(A\) et un Polynôme \(B\)
- Elle renvoie en sortie un tuple constitué du quotient \(Q\) (=un polynôme) et du reste \(R\) (=un polynôme) de la division euclidienne polynômiale de \(A\) par \(B\).
Cette méthode magique renvoie donc un tuple de deux objects de classe Poly.

Remarque Les deux syntaxes des méthodes magiques doivent donc fonctionner pour cette méthode précise, lorsque polynômeGauche et polynômeDroite sont deux instances de la classe Poly :
- ou bien polynômeGauche.__divmod__(polynômeDroite)
- ou bien divmod(polynômeGauche, polynômeDroite)
On pourra se référer aux pages suivantes
- Wikipedia Division Polynômiale
- jybaudot, Division Euclidienne de Polynômes
En déduire une méthode magique __floordiv__() qui renvoie (uniquement) le quotient (=un polynôme) de la division euclidienne entre deux polynômes. Cette méthode magique renvoie donc un object de classe Poly.

Remarque Les deux syntaxes des méthodes magiques doivent donc fonctionner pour cette méthode précise, lorsque polynômeGauche et polynômeDroite sont deux instances de la classe Poly :
- ou bien polynômeGauche.__floordiv__(polynômeDroite)
- ou bien polynômeGauche // polynômeDroite
En déduire une méthode magique __mod__() qui renvoie (uniquement) le reste (=un polynôme) de la division euclidienne entre deux polynômes. Cette méthode magique renvoie donc un object de classe Poly.

Remarque Les deux syntaxes des méthodes magiques doivent donc fonctionner pour cette méthode précise, lorsque polynômeGauche et polynômeDroite sont deux instances de la classe Poly :
- ou bien polynômeGauche.__mod__(polynômeDroite)
- ou bien polynômeGauche % polynômeDroite