Discussion :

[aocaoc]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 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)

Salut ,
Je voudrais savoir si quelqu'un comprend cette algo trouvé sur wikipedia (http://fr.wikipedia.org/wiki/Algorit...de_%C3%A9tendu), à quoi servent les valeurs sauvegardées :
// On sauvegarde les valeurs de a et b.
a0 = a;
b0 = b;
je vois pas trop à quoi correspondent les éléments , donc si vous saviez m'expliquez un petit coup
merci

[PRomu@ld]

L'algorithme cherche à calculer le PGCD étendu de a et b, comme l'algorithme travaille directement sur a et b si à la fin de l'algorithme tu veux retrouver a et b, il faut donc les sauvegarder.

Ca n'est pas très logique en fait, le mieux aurait été de lire a et b et de travailler sur a0 et b0.

[aocaoc]

Oui d'accord mais je comprends pas trop comment il fais cela , si quelqu'un comprend se serait possible d'avoir quelque commentaires?
Merci

[fremen167]

Oui d'accord mais je comprends pas trop comment il fais cela , si quelqu'un comprend se serait possible d'avoir quelque commentaires?
Merci

C'est l'algo classique de calcul d'un PGCD par divisions euclidiennes successives : si n est diviseur de p et q, alors n est aussi diviseur de q et p mod q.

En effet, si p = a * q + b, et si p et q sont divisibles par n, tu vois bien que b doit l'être aussi.

[Edit : Droggo, on s'est un peu "téléscopé" ]

[aocaoc]

Oui ok je suis bien d'accord mais 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 .