Entrez deux entiers relatifs dans les deux premiers champs du formulaire, puis cliquez
sur le bouton Calculer:
Pour commencer, nous avons besoin d'un formulaire: deux zones de texte (a et b) pour entrer le paramètres, une troisième pour afficher le résultat, et un bouton pour lancer le calcul.
<form>
|
calcul(form) :
C'est la fonction principale du programme.Tout d'abord, elle appelle la fonction
check(form), qui vérifie que la saisie est correcte, c'est-à-dire que les cases a et b contiennent bien des nombres entiers. Dans le cas contraire, le script s'arrête en affichant un message d'alerte.Si la fonction
check(form)ne décèle pas d'erreur, le script continue.Tout d'abord, on teste si l'un au moins des entiers a et b est nul (c'est la condition
eval(a*b)==0). Si c'est le cas, le script retourne la plus grande des valeurs absolues de a et b (car PGCD(a,0)=|a| pour tout entier a).
Sinon, on utilise l'algorithme d'Euclide proprement dit.L'algorithme utilise le lemme suivant:
Lemme :
Si a, b, q et r sont des entiers relatifs tels que a=bq+r, alors PGCD(a,b)=PGCD(b,r).On effectue donc la division euclidienne de a par b. On obtient ainsi un quotient q et un reste r. Il nous faut une variable r pour cette division; la valeur de q n'a pas d'importance pour l'algorithme.
Si r est nul, alors PGCD(a,b)=PGCD(b,0)=|b|. Sinon, on effectue une nouvelle division euclidienne de b par r; comme on a |r|<|b|, on obtiendra un reste nul en au plus |b| étapes. Le dernier reste non nul (notons-le rn) vérifie PGCD(a,b)=PGCD(rn,0)=|rn|; la fonction doit donc retourner sa valeur absolue.
function calcul(form) {
var r;
if (check(form)) { //verifie la saisie
var a=form.a.value; //passage des parametres
var b=form.b.value;
if (eval(a*b)==0) { //cas particulier: PGCD(a,0)=|a|
form.resultat.value=max(abs(eval(a)),abs(eval(b)));
}
else {
for (;abs(eval(b))>0;) { //l'algo lui-meme
r=eval(a) % eval(b)
a=b; //PGCD(a,b)=PGCD(b,r)
b=r; //on continue jusqu'a r=0
} //PGCD(a,b) est le dernier r non nul
}
form.resultat.value=abs(a); //renvoie le resultat
}
else {
alert("Attention! vous devez entrer des entiers!");
}
}
- Le fonctions max(a,b) et abs(a) :
Pas grand chose à en dire;max(a,b)retourne le plus grand des deux paramètres etabs(a)retourne la valeur absolue de a.
function max(a,b) { //explicite...
if (a>=b) { return(a) }
else { return(b) }
}
function abs(a) { //valeur absolue
return max(a,-a);
}
- Le fonctions de vérification de saisie :
La fonctionLe source complet du scriptisDigit(c)vérifie que son argument, un caractère, est bien un chiffre.La fonction
isInteger(s)vérifie que la chaîne de caractères passée en argument est bien un entier: le premier caractère peut être un chiffre ou un signe + ou -; les autres, s'ils existent, doivent être des chiffres.La fonction
check(form)vérifie que les champs de saisie a et b contiennent bien des entiers.
function isDigit(c) { //verifie que c contient un chiffre
var test=""+c;
if (test=="0"||test=="1"||test=="2"||test=="3"||test=="4"||test=="5"||test=="6"||
test=="7"||test=="8"||test=="9") {
return true;
}
return false;
}
function isInteger(s) { //verifie que s contient un entier
var test=""+s;
for (var k=1;k<test.length;k++) { //verifie que tous les caracteres sauf le premier
//sont des chiffres
var c=test.substring(k,k+1);
if (isDigit(c)==false) {
return false;
}
}
return (isDigit(test.substring(0,1))||test.substring(0,1)=="+"||test.substring(0,1)=="-");
//le premier caractere peut etre + ou -
//ou un chiffre
}
function check(form) { //verification de la saisie
return (isInteger(form.a.value)&&isInteger(form.b.value));
}