Algorithmique et racine carrée en seconde, compléments publié le 03/03/2020 - mis à jour le 20/09/2023
Parcours sur les algorithmes d'approximation de racines carrées
Cet article fait suite à la première partie du parcours sur les racines carrées.
Algorithme de dichotomie pour les plus rapides
Lors de la séance de TP sur le balayage, quelques groupes avaient réussi les implémentations demandées avant la fin de l’heure.
Il leur a alors été demandé de construire un algorithme de détermination d’une racine carrée en utilisant le principe de la dichotomie, qu’ils devaient découvrir par eux-mêmes en faisant des recherches sur le web.
Les élèves engagés dans cette recherche ont globalement compris le principe de la dichotomie avec l’affectation des bornes qui diffère selon la position de la racine par rapport au milieu de l’intervalle et la longueur de l’intervalle qui est divisée par deux à chaque tour. En revanche, aucun groupe n’a pu établir un code fonctionnel de cet algorithme (voir exécution en ligne) :
- def racine_dicho(nombre,nb_decimales):
- """détermine par dichotomie un encadrement de la racine carrée d'un nombre d'amplitude 10**(-nb_decimales) en partant d'un encadrement à l'unité a et b"""
- x = 0 # on reprend l'algorithme de balayage pour trouver un encadrement à l'unité de la racine carrée
- while x**2 < nombre :
- x = x + 1
- debut = x - 1
- fin = x
- compteur = 0
- while abs(fin-debut) > 10**(-nb_decimales):
- milieu = (debut + fin) / 2
- if milieu**2 <= nombre :
- debut = milieu
- else :
- fin = milieu
- compteur = compteur + 1
- return round(debut, nb_decimales), round(fin, nb_decimales), compteur
- Vers l’algorithme de Héron
Cette archive contient tous les fichiers (fichiers tex, GeoGebra, scripts Python, illustrations,...) utilisés lors de la séquence.