Home > Algorithmes > Pseudo-code et calcul du PGCD

Pseudo-code et calcul du PGCD

Dans cet article, qui fait partie d’une série sur les algorithmes usuels en PHP, nous verrons comment rédiger du pseudo-code pour modéliser nos fonctions PHP. L’algorithme présenté n’est pas là en raison de sa surpuissance ou de son utilité (pas flagrante dans la vie courante… ou du moins pas dans la mienne), mais simplement parce qu’il est facile à comprendre. Merci :)

Le “Plus Grand Commun Diviseur” est le nombre entier maximal qui divise deux autres entiers (deux, ou plus!). Par exemple, le PGCD de 30 et 12 est 6: il n’y a aucun nombre entier (integer) supérieur à 6 qui puisse diviser à la fois 12 et 30. Pour calculer le PGCD, théoriquement, on décompose chaque entier en produit de nombres premiers. Ca donne, pour 30 : 2×3x5 et pour 12 : 2×2x3. Quand on prend les facteurs en commun dans les deux expressions, on a bien 3×2 = 6.

Mais décomposer un nombre en produits de nombres premiers n’est pas à proprement parler simple en termes de calculs. Surtout pour un ordinateur, où les divisions coûtent toujours plus cher au niveau du processeur, et à plus forte raison quand, comme ici, il faudra en faire en grand nombre. Assez difficile donc d’en tirer un algorithme facile à réutiliser et à comprendre.

Calcul du PGCD par l’Algorithme d’Euclide

Sauf avec l’Algorithme d’Euclide, qui part du principe que :

si un nombre entier divise deux autres nombres entiers, alors il divise leur différence (et leur somme). Il divisera donc les différences successives du plus petit ôté du plus grand.

Source: Wikipedia, PGCD (Mathématiques élémentaires)

Il devient alors très simple de trouver le PGCD de deux entiers, sans effectuer la moindre division. On soustrait le plus grand entier au plus petit, jusqu’à obtenir le plus petit reste non nul. Reprenons l’exemple de 30 et 12 :

30 – 12 = 18
18 – 12 = 6

Et voila !

Le code de l’Algorithme d’Euclide de calcul du PGCD

Pour pouvoir écrire le code de notre fonction à partir de l’énoncé de l’Algorithme, il faut qu’on traduise les étapes de la résolution du problème en “pseudo-code”. Le pseudo-code est une simple syntaxe qui utilise des mots classiques et ressemble fort à du code, mais sans référence à un langage de programmation en particulier. C’est une étape intermédiaire entre le langage naturel et les langages de programmation. Son but est de modéliser le cheminement “de pensée” de l’Algorithme.
Ici, on dirait :

Soient $a et $b deux entiers. (On devra les passer comme paramètres de notre fonction)
Tant que (reste de la soustraction des deux entiers) > entier le plus petit et 0, on continue.

On passe ensuite au vrai code PHP, qui traduit simplement ce pseudo-code :

  1. function pgcd($a,$b) {
  2.     $reste = $b;
  3.     while($reste > $a && $reste > 0) {
  4.         $reste -= $a;
  5.     }
  6.     return $reste;
  7. }
  8. echo pgcd(12,30);

Remarques sur le code : Le code présenté n’est pas du tout optimal. Il faudrait, notamment, vérifier que l’entier le plus petit est bien le premier paramètre de la fonction. Bref, c’est un exemple.

Comme on le voit, l’Algorithme d’Euclide permet de trouver très simplement le PGCD de deux entiers (ou plus en modifiant un peu la fonction) sans effectuer de division, avec une seule boucle.

Et en passant par l’étape du pseudo-code, on sait déjà clairement où on va avant même d’écrire la première ligne de code. Ici, cela semble trivial, voire même superflu, mais ma vie a déjà été sauvée par quelques lignes de pseudo-code laissées en commentaires dans une fonction particulièrement ardue. Essayez, vous verrez !

Ce post vous a été utile ? Re-Twittez le ! ReTwittez ce post

Algorithmes , ,

  1. No comments yet.
  1. No trackbacks yet.