Algorithmes de seuil et de dichotomie : exercices de Terminale

La suite est géométrique de raison 2 et de premier terme 1, donc $u_n = 2^n$.

La boucle tourne tant que $u \leq 1000$ et s'arrête dès que $u > 1000$ : la fonction renvoie le plus petit rang $n$ tel que $2^n > 1000$.

On calcule : $2^9 = 512$, qui est inférieur à 1000, puis $2^{10} = 1024$, qui est supérieur à 1000.

La fonction renvoie donc $n = 10$.

On initialise n = 0 et C = 1000.

La condition de continuation est C < 2000 : on veut s'arrêter quand C >= 2000.

Dans la boucle, on écrit C = 1.05 * C puis n = n + 1.

On vérifie avec la forme explicite : $1{,}05^{14} \approx 1{,}980$, donc 1 980 euros environ, encore sous 2 000 ; $1{,}05^{15} \approx 2{,}079$, donc environ 2 079 euros, au-dessus.

Le capital atteint au moins 2 000 euros au bout de $n = 15$ années.

Au départ : $n = 0$, $u = 3$. On a $3 \leq 100$, la boucle commence.

Tour 1 : $u = 2 \times 3 - 1 = 5$, $n = 1$.

Tour 2 : $u = 9$, $n = 2$. Tour 3 : $u = 17$, $n = 3$. Tour 4 : $u = 33$, $n = 4$. Tour 5 : $u = 65$, $n = 5$.

Tour 6 : $u = 2 \times 65 - 1 = 129$, $n = 6$. Comme $129 > 100$, la condition du while est fausse et la boucle s'arrête.

À la fin, $n = 6$ et $u = 129$. On peut le confirmer : $u_n = 2^{n+1} + 1$, et $u_6 = 2^7 + 1 = 129$.

Fonction : on initialise n = 0 et u = 5, on boucle tant que u <= S, on remplace u par 3 * u + 2, on augmente n, puis on renvoie n.

def seuil(S):
    n = 0
    u = 5
    while u <= S:
        u = 3 * u + 2
        n = n + 1
    return n

On pose $v_n = u_n + 1$. Alors $v_{n+1} = u_{n+1} + 1 = 3u_n + 3 = 3(u_n + 1) = 3v_n$. La suite $(v_n)$ est géométrique de raison 3 et de premier terme $v_0 = 6$.

On en déduit $v_n = 6 \times 3^n$, donc $u_n = 6 \times 3^n - 1$.

On cherche $6 \times 3^n - 1 > 1000$, soit $3^n > \dfrac{1001}{6} \approx 166{,}8$.

Or $3^4 = 81$ ne convient pas et $3^5 = 243$ convient : seuil(1000) renvoie $5$. Contrôle : $u_5 = 6 \times 243 - 1 = 1457 > 1000$ et $u_4 = 6 \times 81 - 1 = 485 \leq 1000$.

Une baisse de 20 % multiplie par $1 - 0{,}2 = 0{,}8$, donc $q_{n+1} = 0{,}8\,q_n$ et $q_n = 100 \times 0{,}8^n$.

On veut $100 \times 0{,}8^n < 10$, c'est-à-dire $0{,}8^n < 0{,}1$.

On teste : $0{,}8^{10} \approx 0{,}1074$, qui est encore supérieur à $0{,}1$ ; $0{,}8^{11} \approx 0{,}0859$, qui est inférieur à $0{,}1$.

La quantité passe donc sous 10 grammes au bout de $n = 11$ heures.

Dans le programme, on écrit while q >= 10: avec q = 0.8 * q. Le sens de l'inégalité s'inverse par rapport à un seuil vers le haut, parce que la suite est décroissante.

$f(1) = -1 < 0$ et $f(2) = 2 > 0$. La fonction $f$ est continue et strictement croissante sur $[1\,;\,2]$ : elle s'annule une seule fois sur cet intervalle.

Étape 1 : $m = 1{,}5$ et $f(1{,}5) = 2{,}25 - 2 = 0{,}25 > 0$. Le signe change entre $a=1$ et $m$, donc on garde $[1\,;\,1{,}5]$.

Étape 2 : $m = 1{,}25$ et $f(1{,}25) = 1{,}5625 - 2 = -0{,}4375 < 0$. Le signe change entre $m$ et $b = 1{,}5$, donc on garde $[1{,}25\,;\,1{,}5]$.

Étape 3 : $m = 1{,}375$ et $f(1{,}375) = 1{,}890625 - 2 \approx -0{,}109 < 0$. On garde $[1{,}375\,;\,1{,}5]$.

Après trois étapes, la borne gauche vaut $a = 1{,}375$ et l'amplitude est $0{,}125 = \dfrac{1}{2^3}$.

Chaque étape coupe l'intervalle en deux et garde une moitié, donc la longueur après $k$ étapes est $\dfrac{1}{2^k}$.

On veut $\dfrac{1}{2^k} < 0{,}01$, soit $2^k > 100$.

On teste : $2^6 = 64$ est trop petit, $2^7 = 128$ convient.

Il faut donc au minimum $k = 7$ étapes. Contrôle : $\dfrac{1}{64} \approx 0{,}0156$ n'est pas assez petit, et $\dfrac{1}{128} \approx 0{,}0078$ l'est.

Boucle : while b - a >= 0.01: on calcule m = (a + b) / 2, on met à jour a ou b selon le signe, et on fait k = k + 1 à chaque tour.

Tour 1 : a = 0, b = 9, m = 9 // 2 = 4. On lit L[4] = 16, qui est inférieur à 23 : on pose a = 5.

Tour 2 : a = 5, b = 9, m = 14 // 2 = 7. On lit L[7] = 56, qui est supérieur à 23 : on pose b = 6.

Tour 3 : a = 5, b = 6, m = 11 // 2 = 5. On lit L[5] = 23 : la valeur est trouvée.

L'algorithme renvoie l'indice 5, après seulement 3 comparaisons.

Dans le pire cas pour dix éléments, la zone de recherche reste coupée en deux à chaque tour, donc le nombre de comparaisons reste très petit devant la taille de la liste. Un balayage séquentiel de la liste aurait demandé 6 lectures pour atteindre la valeur 23.

On calcule $f(0) = -1 < 0$ et $f(1) = 1 > 0$. La fonction est croissante et change de signe sur $[0\,;\,1]$ : il faut garder à chaque tour la moitié aux bornes de laquelle $f$ prend des signes contraires.

Si $f(m) > 0$, alors $m$ est déjà à droite de la solution, car $f$ est croissante et positive à partir de la solution. Il faut garder $[a\,;\,m]$ et poser b = m. Le programme fait l'inverse et pose a = m.

Conséquence : le programme garde la moitié qui ne contient pas la solution. Par exemple, au premier tour $m = 0{,}5$ et $f(0{,}5) = -0{,}375 < 0$, donc le programme pose b = 0.5 alors que la solution est à droite de $0{,}5$. L'intervalle final ne contient pas la solution.

Version corrigée : inverser les deux affectations.

while b - a > 0.001:
    m = (a + b) / 2
    if f(m) > 0:
        b = m
    else:
        a = m

Après correction, l'invariant est : $f(a) \leq 0 \leq f(b)$ à chaque tour. Le programme s'arrête quand l'amplitude descend sous $0{,}001$, soit après 10 étapes puisque $\dfrac{1}{2^{10}} \approx 0{,}00098$.