Algorithme du balayage

Lycée

Klérigo propose une activité pour encadrer les valeurs décimales de diverses racines carrées, par la méthode du balayage.

Au fur et à mesure que tu obtiens des valeurs de plus en plus précises, un algorithme type Python se met en place.

Le script Python

a = 0
b = 1
while b**2 < 2 :
__a = a+1
__b = b+1
b = a + 0.1
while b**2 < 2 :
__a = a+0.1
__b = b+0.1
b = a + 0.01
while b**2 < 2 :
__a = a+0.01
__b = b+0.01
b = a + 0.001
while b**2 < 2 :
__a = a+0.001
__b = b+0.001
print(“La racine de 2 est comprise”)
print(“entre”, a, “et”, b)

Le résultat

La racine de 2 est comprise
entre 1.414 et 1.415

Pour tout savoir sur la notation b**2 et les mots-clefs while et print, consulte l’article Programmer en Python au lycée .

La méthode du balayage, c’est quoi ?

Cette méthode est très utilisée au lycée pour déterminer la valeur approchée des solutions d’une équation que l’on ne sait pas résoudre autrement.

Au collège tu as déjà rencontré de telles équations. L’une d’entre elles est \(x^2=2\).

Si tu as bien appris ton cours, tu sais que cette équation a deux solutions. La première est notée \(\sqrt2\), la seconde est l’opposée de la première, on la note donc \(-\sqrt2\).

Tout ça c’est bien gentil, mais quelle est la valeur de \(\sqrt2\) ? Et bien personne ne le sait. La calculatrice en donne une valeur — 1,41421 — mais ce n’est qu’une valeur approchée, pas la valeur exacte. Et comment la calculatrice a-t-elle trouvé cette valeur ?

La méthode du balayage consiste à balayer des intervalles de plus en plus petits.

Tu sais que \(\sqrt2\) est positif, donc le premier intervalle de recherche est \([0\;;\;+\infty[\).

Premier niveau

Dans l’équation \(x^2=2\) tu vas tester des valeurs possibles de \(x\) de plus en plus grandes ;
inutile de tester 0, mais bon, après tout, pourquoi pas ?
\(0^2=0<2\) donc 0 est trop petit, mais tu le savais déjà ;
remplace \(x\) par 1 : \(1^2=1<2\) donc 1 est trop petit ;
remplace \(x\) par 2 : \(2^2=4>2\) donc 2 est trop grand ;
conclusion : \(\sqrt2\) est compris entre 1 et 2 ;
conclusion de la conclusion : le nouvel intervalle de recherche est \([1\;;\;2]\).

Et en Python ?

Les variables a et b représentent les bornes de l’intervalle ;
a = 0 puisque la recherche s’effectue sur l’intervalle \([0\;;\;+\infty[\) ;
tu dois choisir la longueur des intervalles successifs que tu vas balayer ; par défaut choisis un pas de 1 ;
donc b = a + 1 ; autrement dit b = 1 ;
et maintenant les instructions à effectuer en boucle : on augmente les variables a et b de la valeur du pas : a = a + 1 et b = b + 1
on boucle jusqu’à quand ? tu cherches un intervalle [a ; b] pour lequel a est trop petit et b est trop grand ;
la boucle va tourner tant que b est trop petit, c’est-à-dire tant que b au carré est plus petit que 2.

a = 0
b = 1
while b**2 < 2 :
__a = a+1
__b = b+1

Deuxième niveau

Le script est sorti de l’algorithme avec a = 1 et b = 2 ;
tu vas réduire le pas de la recherche pour améliorer la précision ; diviser le pas par 10 est un bon compromis, le nouveau pas sera 1 ÷ 10 = 0,1 ;
le premier intervalle à explorer sera donc \([1\;;\;1,1]\) ;
donc a ne change pas, mais b prend la valeur a + 0,1 ;
il ne reste plus qu’à réécrire la boucle, en prenant en compte le nouveau pas.

Donc en Python

b = a + 0.1
while b**2 < 2 :
__a = a + 0.1
__b = b + 0.1

Et ainsi de suite…

L’activité Klérigo

Le script s’affiche niveau par niveau.
Les boutons + et – permettent d’avancer ou reculer dans la boucle.
Le bouton “valider” permet de passer au niveau suivant.
Les valeurs des variables s’affichent en vert, à droite du script.
La condition de la boucle apparait en vert ou en noir, selon qu’elle est en cours ou terminée.

Envie de tester l’activité ? Clique sur une des deux images ci-dessus !

En bonus

Une version interactive et raccourcie du script :

encore = “1”
while encore == “1” :
__n = int(input(“n = “))
__a = 0
__pas = 1
__for i in range(4) :
____b = a + pas
____while b**2 < n :
______a = a + pas
______b = b + pas
____pas = pas / 10
__print(“La racine de”, n, “est comprise”)
__print(“entre”, a, “et”, b)
__encore = input(“Encore ? (1 = oui) : “)

L’instruction “for i in range(4) :” permet de ne pas copier 4 fois la même boucle, comme c’était le cas dans le script original.
Amuse-toi à étudier les autres différences entre les deux scripts.
Tu trouveras une multitude d’explications sur Python dans l’article Programmer en Python au lycée.