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

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.

Animation illustrant la recherche d'une racine carrée par dichotomie

Choisissez un nombre dont vous voulez la racine carrée, réglez l’amplitude de l’encadrement final et appuyez sur la touche "étape suivante" jusqu’à atteindre la précision souhaitée.

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) :

Bloc de code informatique : voir l'article sur le site.
  
  1. def racine_dicho(nombre,nb_decimales):
  2.     """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"""
  3.     x = 0 # on reprend l'algorithme de balayage pour trouver un encadrement à l'unité de la racine carrée
  4.     while x**2 < nombre :
  5.         x = x + 1
  6.     debut = x - 1
  7.     fin = x
  8.     compteur = 0
  9.     while abs(fin-debut) > 10**(-nb_decimales):
  10.         milieu = (debut + fin) / 2
  11.         if milieu**2 <= nombre :
  12.             debut = milieu
  13.         else :
  14.             fin = milieu
  15.         compteur = compteur + 1
  16.     return round(debut, nb_decimales), round(fin, nb_decimales), compteur

- Vers l’algorithme de Héron

Document joint

Cette archive contient tous les fichiers (fichiers tex, GeoGebra, scripts Python, illustrations,...) utilisés lors de la séquence.