Bonjour!
Je cherche à écrire un algorithme permettant de calculer le reste et le quotient de la division euclidienne de deux polynômes.
Voilà ce que j'ai fait, mais j'aimerai savoir si c'est correct:
Initialisation des variables: Valeurs d'entrée: A et B (on cherche à faire la DE de A par B), Q=0
Tant que degA<=degB,
M<--(domA/domB)*X^(degA)
A<--A-B*M
Q<--Q+M
Sorties: Q et A avec Q le quotient et A le reste
Il faut par ailleurs que je prouve la terminaison de l'algorithme cad qu'à partir d'un certain rang, degA>degB. Pour cela, je pensais justifier en disant que degA est une suite d'entiers strictement décroissante, alors que degB est constant. Donc forcément, degA>degB à partir d'un certain rang. Mais je ne suis pas très convaincu car degA peut très bien décroitre sans pour autant devenir inférieur à degB non?
Merci d'avance pour votre réponse!
Bonjour !
Tu démontres simplement que la suite (deg A) est strictement décroissante. Pour une suite d'entiers la propriété (deg(A)<(deg B) sera atteinte en un nombre fini d'itérations.
Merci pour cette réponse rapide!Mon algorithme est donc correct?
Pour montrer que degA décroissante je propose ce raisonnement:
Il s'agit de montrer que deg(Ak+1)-deg(Ak)<=0
deg(Ak+1)=deg(Ak-B*Mk)
dc deg(Ak+1)<=max(deg(Ak);deg(BMk)
1er cas: max(deg(Ak);deg(BMk)=deg(Ak)
alors deg(Ak+1)-Ak<=0
2nd cas: max(deg(Ak);deg(BMk)=deg(BMk)
deg(Ak+1)-deg(Ak)<=deg(BMk)-deg(Ak) mais là je n'arrive pas à montrer que c'est inférieur à 0 ... Faut-il écrire deg(BMk)=degB+deg(Mk)? Mais je trouve que cela ne mène à rien ...
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :