Le PGCD et l'algorithme d'Euclide
Voici un algorithme inventé il y a plus de 2 300 ans par le mathématicien grec Euclide, et que les ordinateurs utilisent encore tous les jours.
Le problème
Le PGCD de deux nombres est leur plus grand commun diviseur : le plus grand nombre qui les divise tous les deux. Pour 12 et 18, les diviseurs communs sont 1, 2, 3 et 6 : le PGCD est 6.
Il sert par exemple à simplifier une fraction : 12/18 = 2/3, en divisant le haut et le bas par 6.
La méthode naïve
On essaie tous les candidats, du plus grand au plus petit :
grand est un nombre vaut 84
petit est un nombre vaut 36
resultat est un nombre vaut 1
pour d de petit à 1 pas -1
si grand mod d = 0 et petit mod d = 0 alors
resultat vaut d
arrête
fin si
fin pour
affiche 'PGCD : ' + resultat // 12
Ça fonctionne, mais pour de très grands nombres, il faudrait des millions d'essais.
L'idée d'Euclide
Euclide a remarqué ceci : le PGCD de deux nombres est aussi le PGCD du plus petit et du reste de leur division. On remplace donc le problème par un problème plus petit, et on recommence jusqu'à ce que le reste soit nul.
Avec 84 et 36 :
- 84 = 2 × 36 + 12 : on continue avec 36 et 12 ;
- 36 = 3 × 12 + 0 : le reste est nul, on s'arrête.
Le PGCD est le dernier diviseur utilisé : 12. Deux étapes seulement !
fonction plusGrandDiviseur(nombre1, nombre2)
grand est un nombre vaut nombre1
petit est un nombre vaut nombre2
reste est un nombre
tant que petit <> 0
reste vaut grand mod petit
grand vaut petit
petit vaut reste
fin tant que
retourne grand
fin fonction
affiche plusGrandDiviseur(84, 36) // 12
affiche plusGrandDiviseur(1071, 462) // 21
À chaque tour, les trois variables se décalent : l'ancien petit devient le nouveau grand, et le reste devient le nouveau petit.
Question : Avec 20 et 8, quel est le reste de la première division dans l'algorithme d'Euclide ? — 4. 20 = 2 × 8 + 4 : le reste est 4. On continue avec 8 et 4, puis 8 = 2 × 4 + 0 : le PGCD est 4.
Simplifier une fraction
fonction plusGrandDiviseur(nombre1, nombre2)
grand est un nombre vaut nombre1
petit est un nombre vaut nombre2
reste est un nombre
tant que petit <> 0
reste vaut grand mod petit
grand vaut petit
petit vaut reste
fin tant que
retourne grand
fin fonction
haut est un nombre
bas est un nombre
demande 'Numérateur ? ' dans haut
demande 'Dénominateur ? ' dans bas
diviseur est un nombre vaut plusGrandDiviseur(haut, bas)
affiche haut + '/' + bas + ' = ' + (haut / diviseur) + '/' + (bas / diviseur)
Pour 84 et 36, le programme affiche 84/36 = 7/3.
CoddyRun possède déjà une fonction pgcd(a, b). C'est pour cela que la nôtre s'appelle plusGrandDiviseur : deux fonctions ne peuvent pas porter le même nom.
Pourquoi c'est un grand algorithme
- Il est court : une boucle de trois lignes.
- Il est rapide : même pour des nombres de plusieurs dizaines de chiffres, quelques dizaines d'étapes suffisent.
- Il se termine toujours : le reste diminue à chaque tour, il finit forcément par valoir 0.
En résumé
- Le PGCD est le plus grand diviseur commun à deux nombres.
- Algorithme d'Euclide : remplacer (grand, petit) par (petit, reste), jusqu'à un reste nul.
- Diviser le haut et le bas d'une fraction par leur PGCD la simplifie au maximum.
- Une bonne idée mathématique vaut mieux que des millions d'essais.
