Division euclidienne algorithme
Bonjour,
J'avoue ne pas réussir à comprendre cette algorithme. Il n'y a aucune explication dans mon livre, seulement un exemple de division euclidienne entre 2 polynômes.
Par ailleurs, à votre avis, est-ce facile de le programmer sur Python ? J'aimerais essayer dès lors que j'aurais compris l'algorithme.
J'avoue ne pas réussir à comprendre cette algorithme. Il n'y a aucune explication dans mon livre, seulement un exemple de division euclidienne entre 2 polynômes.
Par ailleurs, à votre avis, est-ce facile de le programmer sur Python ? J'aimerais essayer dès lors que j'aurais compris l'algorithme.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Quand tu auras vu comment ça marche, tu pourras démontrer :
- que l'algorithme se termine en un nombre fini d'étapes (nombre vérifiant une certaine relation fonction des degrés des polynômes $A$ et $B$) ;
- qu'il donne la réponse attendue.
Pour cela, il est utile de trouver un « invariant de boucle » : une propriété intéressante qui est vraie à chaque étape au début de la boucle. Montrer que ladite propriété est vraie à chaque étape revient à faire une petite récurrence.X^5 = X^3*(X^2 + 1) + R(X)
R(X) = la différence = -X^3
Ensuite
-X^3 = -X(X^2 + 1) + R(X)
R(X) = X
Tu vois que :
R(X) = le dernier terme = X
Q(X) = somme des quotients = X^3 - X
On peut vérifier : (X^3 - X)(X^2 + 1) + X = X^5
A toi de jouer, en python c'est pas compliqué
Si $\deg(n) < deg (p)$ il suffit de prendre $Q=0$ et $R=A$ on a bien $A=B \times 0 + A$ avec $\deg A < \deg B$
Sinon j'ai réussi à comprendre le programme en posant la division euclidienne.
J'ai pas envie de rentrer dans la théorie des algorithmes, ce qui m'intéresse c'est son application à Python.
Je n'arrive pas avec mon programme Python, le $X^{n-p}$ me gêne je ne sais pas comment faire. Mon début de programme :
Ensuite j'ai plus qu'à les appeler pour faire la somme et le produit.
Python m'envoie un message d'erreur pour la commande en disant que r n'est pas défini alors que je l'ai défini en posant r=a
Tu n'as pas respecté l'indentation à partir de la ligne n=len(r) - 1.
Cordialement,
Rescassol
Enfin noobey a raison si tu écris q=somme(q,(a[n]/b[p])*q[n-p]) tu fais la somme du polynôme q avec le nombre (a[n]/b[p])*q[n-p] ce qui ne vas pas fonctionner.
4*[0]. donne [0,0,0,0]. Que crois tu que peut faire (a[n]/b[p])*q surtout si (a[n]/b[p]) n'est pas entier ?
Il faut te renseigner sur les array de numpy, ou faire des boucles indigestes.
Cordialement,
Rescassol
Commençons par Q.
Q = Q + constante*X^(n-p)
Il faut donc
1) que tu définisses le polynome X^(n-p)
2) que tu le multiplies avec ta constante. Pour rappel une constante est un polynome de degré....
3) que tu additionnes avec Q
Ensuite tu fais la meme pour R
Et tu oublies pas dactualiser n à chaque étape
Je pense que ce programme est un peu trop dur par rapport à mes connaissances de Python. Il y a trop de choses que je ne maitrise pas comme multiplier un réel par une liste etc...
C'est dommage que je perde des heures qui m'auraient permis d'avancer dans le programme de sup.
Mais j'ai quand même appris des petites choses.
est correcte.
OK. Au cas où si tu reviens à Python il y a cette version en ligne qui te permet d'exécuter rapidement des scripts https://repl.it/languages/python3 (enfin si tu ne connaissais pas déjà...)
J'ai utilisé cette version mais j'ai toujours des erreurs c'est lassant.
@Brian
Oui j'essaie d'utiliser print souvent mais ici je me suis perdu avec $\dfrac{a_n}{b_p} X^{n-p} B$ que je n'ai pas réussi à programmer. Je n'ai rien trouvé sur google pour multiplier une liste par un réel non entier.
Cordialement,
Rescassol
Exemple:
Cordialement,
Rescassol
Edit : grillé par noobey.
Oui vous avez raison mais je vais m'acheter un bouquin de Python pour justement poser moins de questions.
Dans vos minis programmes je ne comprends pas la différence entre aP et P.
@Brian
Ah une commande qui a l'air facile à manipuler. J'avais cherché des trucs sur Numpy mais j'ai pas compris grand chose.
Votre commande marche très bien Ça m'affiche le bon résultat.
C'est exactement le même programme que celui de Brian, sauf qu'il faut définir en amont P et a .....