Soient deux entiers naturels a et b, dont on cherche le PGCD. Le cas où a ou b est nul ne nécessite aucun algorithme ; on l'exclut. Une suite d'entiers (an)n est définie par récurrencede pas 2, plus précisément par divisions euclidiennes successives ; la suite est initialisée par a0 = a, a1 = b, puis propagée par la règle de récurrence : tant que an+1 est non nul, an+2est défini comme le reste de la division euclidienne de an par an+1. On commence donc par calculer le reste de la division de a par b, qu'on note r ; puis on remplace a par b, puis b par r, et on réapplique le procédé depuis le début. On obtient ainsi une suite, qui vaut 0 à un certain rang ; le PGCD cherché est le terme précédent de la suite. Il est intéressant de noter que si a < b, la première itération de la boucle a pour effet de "permuter a et b". Plus précisément : dans ce cas, la division euclidienne de a par b s'écrit a = b.0 + a donc a2 = a, si bien que la suite produite par l'algorithme appliqué au couple (a, b) commence par a, suivie de la suite produite par l'algorithme appliqué au couple (b, a). Ainsi pgcd(a,b) (avec a> b) a0=a, a1=b an = q*an+1 + an+2 si r = 0 alors pgcd = an+1 sinon pgcd = pgcd (an+1, r)
Nous obtenons en Java
/**
* Le pgcd récursif Euclide
*/
package edu.isae.recusrive;
/**
* @author Pascal Fares
*
*/
public class EuclidPgcd {
public static int pgcd(int a, int b) {
if (a < b) return pgcd(b,a); /* préparer la division */
if (b ==0) return a; /* nous avons le pgcd d'après l'algo déuclide */
/* Calcul du du reste l'operareur modulo en java */
return pgcd(b,a%b);
}
/**
* La fonctiom main ici permet d'effectuer des test unitaires
* @param args les paramètres de la ligne de commande 2 nombres.
* Quelques exemples:
* pfares@pascal-Notebook:~/workspace/recursive/bin$ java edu.isae.recusrive.EuclidPgcd 25 5
* pgcd(25,5)=5
* pfares@pascal-Notebook:~/workspace/recursive/bin$ java edu.isae.recusrive.EuclidPgcd 1001 101
* pgcd(1001,101)=1
* pfares@pascal-Notebook:~/workspace/recursive/bin$ java edu.isae.recusrive.EuclidPgcd 1010 100
* pgcd(1010,100)=10
* pfares@pascal-Notebook:~/workspace/recursive/bin$ java edu.isae.recusrive.EuclidPgcd 1000 100
* pgcd(1000,100)=100
*/
public static void main(String[] args) {
if (args.length != 2) System.out.println("Utilisation : java EuclidPgcd a b");
int a=Integer.parseInt(args[0]);
int b=Integer.parseInt(args[1]);
int pgcd = pgcd(a,b);
System.out.printf("pgcd(%d,%d)=%d\n",a,b,pgcd);
}
}
|
Accueil > Les algorithmes récursifs >