Algorithmique et racine carrée en seconde publié le 03/03/2020  - mis à jour le 19/03/2020

Algorithmes de balayage

Balayage à pas constant à partir de 0

La suite s’est déroulée sur machine, avec l’emploi du langage Python. L’algorithme ayant été défini auparavant, son implémentation n’a pas posé problème, mise à part la difficulté habituelle liée à la gestion de l’indentation (voir exécution en ligne) :

Le résultat renvoyé par la machine

a quelque peu dérouté les élèves et ce fut l’occasion de revenir une nouvelle fois sur la gestion des nombres (affichage, stockage en mémoire...) par une machine. Pour satisfaire l’attente des élèves, la fonction round, qui permet d’afficher un arrondi avec une certaine précision, a été introduite.

Généralisation et traduction par une fonction

Après avoir fait "jouer" les élèves avec le programme en leur demandant de modifier le pas, puis la valeur du nombre dont on veut la racine carrée, la manipulation s’est poursuivie par la recherche d’une fonction racine_balayage(nombre, nb_decimales) permettant de déterminer la racine carrée d’un nombre réel positif quelconque, à une précision choisie par l’utilisateur, ces deux éléments variables étant passés en paramètres de la fonction.

Le travail réalisé depuis plusieurs séances sur les fonctions a permis de construire rapidement l’enveloppe de la fonction :

• l’en-tête avec le mot-clé def : def racine_balayage(nombre, nb_decimales) ;
• l’instruction de renvoi du résultat avec le mot-clé return : return round(x-pas, nb_decimales), round (x, nb_decimales)

Entre ces deux lignes, on insère le bloc d’instructions venant du script précédent en l’adaptant à la généralité recherchée. Le code suivant a été obtenu par une majorité d’élèves de manière plus ou moins autonome (voir exécution en ligne) :

Appels de la fonction racine_balayage et limites

Les appels successifs de cette fonction pour divers nombres et diverses précisions a mis en évidence une lenteur de la réponse à partir d’une précision de 7 décimales. Le questionnement soumis aux élèves a fait émerger le problème dû au fait que l’algorithme repartait toujours de 0 donc balayait toujours l’intervalle $\left[0\,;\,\sqrt{\text{nombre}}\,\right]$, ce qui demandait un nombre de tours de boucle de plus en plus important quand la précision augmentait : pour un nombre donné, la distance à parcourir entre 0 et sa racine carrée reste la même mais comme le pas est plus petit, il y a plus de répétitions.

Afin de mettre en évidence ce phénomène, il leur a été proposé d’insérer un compteur dans la fonction racine_balayage : ce compteur, initialisé à 0, s’incrémente à chaque tour de boucle et compte ainsi le nombre de tours de boucle nécessaire pour obtenir l’encadrement souhaité (voir exécution en ligne) :

Les appels successifs avec la nouvelle fonction racine_balayage_bis mettent en évidence une propriété qui aurait pu être obtenue par un petit raisonnement : le nombre de tours nécessaire est de l’ordre de $\dfrac{\sqrt{\text{nombre}}}{10^{-\text{nb_decimales}}}$ et on dépasse le million de tours de boucle dès qu’on veut la racine carrée d’un nombre supérieur à 1 avec une précision de 6 décimales.

 Vers l’algorithme de balayage optimisé