// Ce programme ne fonctionne qu'avec des entiers naturels
// demande les données à l'utilisateur et convertit les chaînes de caractères en entiers
var a = parseInt(prompt("Entrer un entier naturel a",0))
var b = parseInt(prompt("Entrer un entier naturel b",0))
// On sauvegarde les valeurs de a et b.
a0 = a;
b0 = b;
// Initialisations. On laisse invariant p*a0 + q*b0 = a et r*a0 + s*b0 = b.
p = 1; q = 0;
r = 0; s = 1;
// La boucle principale:
while (b != 0) {
c = a % b;
quotient = Math.floor(a/b); //Javascript n'a pas d'opération de division entière.
a = b;
b = c;
nouveau_r = p - quotient * r; nouveau_s = q - quotient * s;
p = r; q = s;
r = nouveau_r; s = nouveau_s;
}
// Affiche le résultat.
alert("pgcd(" + a0 + "," + b0 + ")=" + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a)
Bonjour
, j'ai un petit problème avec cette algorithme qui permet de trouver
les deux coefficients de Bezout , est ce que quelqu'un pourrait me dire
comment on trouve les deux coefficient avec ces deux lignes :
nouveau_r = p - quotient * r;
nouveau_s = q - quotient * s;
Algo trouvé sur Wikipédia : (
http://fr.wikipedia.org/wiki/Algorithme . C3%A9tendu)
je ne comprend pas trop comment en fesant :
nouveau_r = p - quotient * r;
nouveau_s = q - quotient * s;
On à les coeficient intermédiaire de bezout .
Voila un screen que j'ai fais :
La valeur a affiche 1 * 120 + 0 * 23
Resultat de l'operation entre 120 et 23
Le reste 5
Le quotient 5
nouvelle valeur de a , l'ancien diviseur 23
nouvelle valeur de b , le nouveau reste 5
Valeur de nouveau_r u 1 - quotient 5 * r 0 =1 ->>>>>> je comprends pas pq ca marche ?
Valeur de nouveau_s v 0 - quotient 5 * s 1 =-5
nouvelle valeur de u 0
nouvelle valeur de v 1
nouvelle valeur de r 1
nouvelle valeur de s -5
-----------------------------
La valeur a affiche 0 * 120 + 1 * 23
Resultat de l'operation entre 23 et 5
Le reste 3
Le quotient 4
nouvelle valeur de a , l'ancien diviseur 5
nouvelle valeur de b , le nouveau reste 3
Valeur de nouveau_r u 0 - quotient 4 * r 1 =-4
Valeur de nouveau_s v 1 - quotient 4 * s -5 =21
nouvelle valeur de u 1
nouvelle valeur de v -5
nouvelle valeur de r -4
nouvelle valeur de s 21
-----------------------------
La valeur a affiche 1 * 120 + -5 * 23
Resultat de l'operation entre 5 et 3
Le reste 2
Le quotient 1
nouvelle valeur de a , l'ancien diviseur 3
nouvelle valeur de b , le nouveau reste 2
Valeur de nouveau_r u 1 - quotient 1 * r -4 =5
Valeur de nouveau_s v -5 - quotient 1 * s 21 =-26
nouvelle valeur de u -4
nouvelle valeur de v 21
nouvelle valeur de r 5
nouvelle valeur de s -26
Je me suis servi d'un exemple comme celui de wikipedia avec 120 et 23 .