L'algorithme de seuil

À partir de quel rang une suite franchit-elle une valeur donnée ? Quand on ne sait pas résoudre l'inéquation, un algorithme trouve la réponse.

10.1 Un problème de seuil

On lâche une balle d'une hauteur de $200$ cm. À chaque rebond, elle remonte aux trois quarts de la hauteur précédente. On note $h_n$ la hauteur après $n$ rebonds : $h_0 = 200 \quad \text{et} \quad h_{n+1} = 0{,}75\,h_n.$ On trouve $h_1 = 150$, $h_2 = 112{,}5$ et $h_3 \approx 84{,}4$. Les hauteurs diminuent et semblent tendre vers $0$. On cherche le premier rebond après lequel la balle remonte à moins de $10$ cm, c'est-à-dire le premier rang $n$ tel que $h_n < 10$.

10.2 L'algorithme

n ← 0
h ← 200
Tant que h ⩾ 10
    h ← 0,75 × h
    n ← n + 1
Fin Tant que

Attention à la condition. On veut $h < 10$. La boucle tourne tant que ce n'est pas le cas : la condition de la boucle est le contraire de ce qu'on cherche. À la sortie de la boucle, $n$ est le rang cherché.

10.3 En Python

def seuil(s):
    n = 0
    h = 200
    while h >= s:
        h = 0.75 * h
        n = n + 1
    return n

>>> seuil(10)
11

Vérification. $h_{10} = 200 \times 0{,}75^{10} \approx 11{,}3 \geq 10$ et $h_{11} = 200 \times 0{,}75^{11} \approx 8{,}4 < 10$. C'est donc au onzième rebond que la balle remonte à moins de $10$ cm.

10.4 Une boucle sans fin

Reprenons l'aquarium, dont le volume semble tendre vers $50$ litres. On cherche quand il dépasse $45$ litres.

def seuil_eau(s):
    n = 0
    u = 20
    while u <= s:
        u = 0.9 * u + 5
        n = n + 1
    return n

>>> seuil_eau(45)
18

Il faut $18$ semaines. Mais avec seuil_eau(60), le volume n'atteint jamais $60$ litres : la condition reste toujours vraie, et le programme ne s'arrête pas. Avant de lancer un algorithme de seuil, on vérifie donc que le seuil sera franchi.

10.5 La méthode

1. Traduire : écrire le premier terme et la relation.
2. Observer : le seuil sera-t-il franchi ?
3. Écrire la boucle, avec la condition contraire de ce qu'on cherche.
4. Contrôler le résultat avec les deux termes qui encadrent le rang trouvé.