PGCD ou l'algorithme d'euclide ."L'heure des affrontements viendra .." par Jean Claude GAUDIN ....?

 

-Ý- RUBRIQUE: THÉORIE DES NOMBRES DIVISEURS ET MULTIPLES
§         PGCD	§         PPCM		§         Premiers entre eux
§         Algorithme d'Euclide	§		§         Pgcd/Ppcm/Racine
Sommaire de cette page >>> RAPPEL >>> ORGANIGRAMME >>> PROGRAMME		Pages voisines §         Algorithmes §         Diviseurs: calculs et facteurs premiers §         Théorie des nombres

---

ALGORITHME D'EUCLIDE pour le calcul du  Plus Grand Commun Diviseur Exemple de présentation d'un algorithme

  

-Ý- RAPPEL

Notions de base sur le PGCD et présentation classique de l'algorithme d'Euclide:

Voir  PGCD - Euclide

Rappel du principe

La division de A	par B	donne un reste C
8 136	492	264
492	264	228
264	228	36
228	36	12
36	12	0

On a bien

8 136	= 12	x 678
492	= 12	x 41

On note la simplicité

§        À chaque ligne suivante: o       A prend la valeur de B o       B celle de C §        Et, on recommence la division o       avec ces nouvelles valeurs de B et C §        On s'arrêt lorsque o       C est nul §        Le PGCD est égal au B final

-Ý-  ORGANIGRAMME

Organigramme - Anglais: flow chart §        La symbologie utilisée ici est la plus courante o       Les rectangles correspondent à des ordres à éxecuter o       On parcourt les instructions dans le sens des flèches §        Les aiguillages sont symbolisés par un losange o       On emprunte la flèche qui correspond au résultat du test

Autre exemple

La division de A	par B	donne un reste C
123 456 789	467 769	433 542
467 769	433 542	34 227
433 542	34 227	22 818
34 227	22 818	11 409
22 818	11 409	0

On a bien

123 456 789	= 11 409	x 10 821
467 769	= 11 409	x 41

-Ý- PROGRAMME

Programme qui fonctionne selon l'organigramme ci-dessus
A := 8136: B := 492: C := 1: while C<>0 do C := A mod(B): lprint(A,B,C): A := B: B := C: od:	§ Le calcul du reste de la division est remplacé o par son équivalent o le calcul du modulo: C = A modulo B § On imprime le résultat à chaque itération (boucle de programmation) pour obtenir le résultat présenté comme en début de page § Notez que: o L'instruction while se poursuit tant que C est différent de 0 o Il est donc important de lancer le programme avec une valeur de C différente de 0 o Ici, on a choisit de forcer C à 1
Langage type Mapple	Voir Convention de notations