Mathématice, intégration des Tice dans l'enseignement des mathématiques  

Algorithmes et PGCD
Moteur de recherche
Mis en ligne le 27 janvier 2007, par Benjamin Clerc

Utilisation du tableur en classe de 3ème à la découverte des algorithmes de la différence et d’Euclide.

En classe de troisième, après avoir revu les notions de diviseur, divisible, multiple et la division euclidienne, et après avoir rencontré des problèmes dont la solution est le PGCD de deux nombres, j’introduis la mise en place des algorithmes permettant le calcul du PGCD de deux nombres à l’aide d’une feuille de calcul vidéo projetée. Ainsi, je fais afficher la feuille suivante :

Après plusieurs exemples, je demande alors aux élèves "Quel procédé de calcul est répété dans les cellules vertes ?". Ils sont très nombreux à découvrir sans difficulté que les colonnes C et G sont obtenues en calculant la différence des nombres situés respectivement dans les colonnes A et B et dans les colonnes E et F. L’analyse des deux situations en ligne 6 leur permet également de voir que l’on prend le nombre le plus grand dans la colonne intitulée "a" et le plus petit dans la colonne intitulée "b". J’en profite alors pour leur montrer l’utilisation des formules MAX() et MIN() :

Les élèves voient également en ligne 8 qu’il faut toujours mettre le nombre le plus grand dans la colonne "a" et le plus petit dans la "b", d’où l’écriture de la deuxième ligne de l’algorithme (ligne 7 du tableur) :

C’est alors le moment de leur montrer que les formules suivantes étant itératives, il n’est pas nécessaire de les taper une à une puisqu’il est possible d’utiliser la poignée de recopie :

On remarque enfin que l’algorithme s’arrête lorsque l’on obtient une différence nulle, le PGCD étant alors le résultat de la dernière différence non nulle.
Utilisant alors le rappel des notions vues en début de séquence, nous démontrons que si un nombre divise deux nombres a et b alors il divise aussi leur différence a - b, d’où la légitimité de l’utilisation de cet algorithme.
Les élèves utilisent ce procédé pour calculer les PGCD de deux couples de nombres bien choisis. Je leur propose alors de calculer le PGCD de 412 et 225 :

Les élèves ne sont pas contents car c’est trop long, ils remarquent que l’on pouvait prévoir qu’il allait falloir enlever 11 fois 3 à 35 ! Je leur propose alors une nouvelle feuille de calcul dans laquelle un nouvel algorithme permettait de déterminer le PGCD de 412 et 225 beaucoup plus rapidement :

Je reprends alors les PGCD calculés précédemment avec ce nouvel algorithme. La recherche du procédé utilisé pour remplir la colonne C est un peu plus longue que pour le premier algorithme, mais ils sont plusieurs à découvrir qu’il s’agit du reste de la division euclidienne de a par b. Ils sont contents de retrouver le "11 fois 3 qui va dans 35" ... Reste à montrer la construction de l’algorithme dans la feuille de calcul :
On utilise la fonction QUOTIENT(numérateur ;dénominateur) qui renvoie le quotient entier d’une division, et avec la formule rappelée en début de séquence Dividende = Diviseur × Quotient + Reste, on en vient sans trop de mal à la formule à utiliser pour remplir la colonne "Reste" :

Tout au long du cours d’arithmétique, j’utilise ces feuilles de calcul en vidéo projection.

OpenDocument Spreadsheet - 13.5 ko
Pgcd_OOo
Le fichier utilisé dans ma classe.

Documents associés à l'article
  Pgcd_Excel   |   (Excel - 81.5 ko) La version Microsoft pour ceux qui n’auraient pas encore téléchargé OOo2.
Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197