algorithme d'Euclide

NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 29/10/2010 Orientation générale DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique
	THÉORIE DES NOMBRES
Débutants Général	DIVISEURS ET MULTIPLES			Glossaire Général
INDEX Th des Nbs	PGCD	PPCM	Premiers entre eux
	Algorithme d'Euclide		PGCD / PPCM / Racine
	Sommaire de cette page >>> Rappel >>> Organigramme >>> Programme >>> Exemple

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

On a bien

8 136 = 12 x 678

492 = 12 x 41

On note la simplicité

À chaque ligne suivante:

A prend la valeur de B,

B celle de R.

Et, on recommence la division avec ces nouvelles valeurs de B et R.

On s'arrête lorsque R est nul.

Le PGCD est égal au B final.

Illustration

ORGANIGRAMME

Organigramme - Anglais: flow chart

La symbologie utilisée ici est la plus courante.

Les rectangles correspondent à des ordres à exécuter.

On parcourt les instructions dans le sens des flèches.

Les aiguillages sont symbolisés par un losange.

On emprunte la flèche qui correspond au résultat du test.

PROGRAMME *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é par son équivalent : le calcul du modulo: C = A modulo B. On imprime le résultat à chaque itération pour obtenir le résultat présenté comme en début de page. Notez que: L'instruction while se poursuit tant que C est différent de 0. Il est donc important de lancer le programme avec une valeur de C différente de 0. Ici, on a choisit de forcer C à 1.
Langage type Mapple	Voir Convention de notations

Autre exemple

On a bien

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

Voir