PGCD et Algorithme d'Euclide

Rouen

Objectifs

- Découvrir l'algorithme d'Euclide.
- Programmer l'algorithme d'Euclide à l'aide d'un tableur en utilisant la propriété suivante :

Si r est le reste de la division euclidienne de a par b alors PGCD(a ; b) = PGCD(b ; r).

Description de l'activité

L'activité débute par une présentation de l'algorithme d'Euclide :

Pour calculer le PGCD de deux entiers naturels non nuls a et b (a > b) avec l'algorithme d'Euclide, on utilise la séquence ordonnée d'opérations schématisées ci-contre et décrites ci-dessous : (1) Diviser a par b ; obtenir le reste r. (2) Si r = 0, alors l'algorithme se termine : PGCD(a ; b) = b. (3) Si r ¹ 0, remplacer a par b, b par r et recommencer à partir de (1).

L'activité propose ensuite de programmer cet algorithme à l'aide d'un tableur.
Des aides pour établir la feuille de calcul sous Works ou Excel sont proposées aux élèves.

Cette activité peut servir à valider la compétence 3 du Brevet informatique et internet scolaire
- niveau 2 : organiser des traitements numériques à l'aide d'un tableur
car l'élève doit être capable de créer une feuille de calcul simple qui réponde
à un problème donné en utilisant à bon escient les formules, et d'en vérifier la validité.

Fiche professeur : algeucl.doc