Fiche 6 : algorithmique et Python

Exécution à la main

On exécute le script à la main avec n = 3. La boucle for i in range(3) s'exécute $3$ fois ($i=0{,}1{,}2$).

• Avant la boucle : u = 2.

• $i=0$ : $u=3\times2-1=5$.

• $i=1$ : $u=3\times5-1=14$.

• $i=2$ : $u=3\times14-1=41$.

✅ La fonction renvoie $41$, c'est-à-dire $u_3$.

À chaque passage, la variable u contient le terme suivant de la suite, donc après $3$ passages elle contient $u_3$.

Le script

def terme(n):
    u = 3
    for i in range(n):
        u = 0.5*u + 2
    return u

La variable u est initialisée à $u_0=3$, puis la relation $u_{n+1}=0{,}5\,u_n+2$ est appliquée $n$ fois : la fonction renvoie bien $u_n$.

Exécution pour $n=3$

$u_0=3$

$u_1=0{,}5\times3+2=3{,}5$

$u_2=0{,}5\times3{,}5+2=3{,}75$

$u_3=0{,}5\times3{,}75+2=3{,}875$

✅ terme(3) renvoie $3{,}875$.

Question 1

Perdre $10\,\%$ de sa valeur revient à multiplier par $0{,}9$. La suite $(u_n)$ est donc géométrique de raison $0{,}9$ et de premier terme $u_0=5000$.

✅ Donc, pour tout $n\in\N$, $u_n=5000\times0{,}9^n$.

Question 2

On boucle tant que la valeur est encore supérieure ou égale à $2000$, et on compte les années :

def seuil():
    n = 0
    u = 5000
    while u >= 2000:
        u = 0.9*u
        n = n + 1
    return n

Terminaison : comme $-1<0{,}9<1$, $u_n=5000\times0{,}9^n$ tend vers $0$. Il existe donc un rang à partir duquel $u_n<2000$ : la condition u >= 2000 finit par être fausse et la boucle s'arrête.

Question 3

On cherche le plus petit entier $n$ tel que $5000\times0{,}9^n<2000$, soit $0{,}9^n<0{,}4$. La suite $(0{,}9^n)$ est strictement décroissante, et :

$0{,}9^8\approx0{,}4305\ge0{,}4$

$0{,}9^9\approx0{,}3874<0{,}4$

✅ La fonction renvoie $9$.

Piège évité : la suite décroît, donc la condition du while est u >= 2000 (on continue tant qu'on n'est pas passé sous le seuil).

Question 1

def somme(n):
    u = 1
    s = 1
    for i in range(n):
        u = u/2
        s = s + u
    return s

La variable u contient successivement $\dfrac12$, $\dfrac14$, $\dfrac18$…, et s cumule les termes : après $n$ passages, $s=1+\dfrac12+\dots+\dfrac1{2^n}=S_n$.

Exécution pour $n=3$ : s = 1, puis u = 0.5 et s = 1.5, puis u = 0.25 et s = 1.75, puis u = 0.125 et s = 1.875.

✅ somme(3) renvoie $1{,}875$.

Question 2

Comme $S_n=2-\dfrac1{2^n}$, on a $2-S_n=\dfrac1{2^n}$. On cherche le plus petit entier $n$ tel que $\dfrac1{2^n}<0{,}01$. Voici une fonction possible :

def seuil():
    n = 0
    while 1/2**n >= 0.01:
        n = n + 1
    return n

Terminaison : comme $-1<\dfrac12<1$, $\dfrac1{2^n}\to0$, donc $\dfrac1{2^n}$ finit par être inférieur à $0{,}01$ et la boucle s'arrête.

Valeur renvoyée : $\dfrac1{2^n}<0{,}01\iff2^n>100$. Comme $2^6=64<100$ et $2^7=128>100$, et que $2^n$ est croissante, le plus petit entier convenable est $n=7$.

✅ La fonction renvoie $7$.

Le script complété

def annee():
    n = 0
    u = 800
    while u >= 650:
        u = 0.9*u + 60
        n = n + 1
    return n

Justification des compléments : on part de n = 0 et u = u_0 = 800.

On continue tant que u >= 650, car on cherche le premier moment où u passe sous $650$.

À chaque passage, u devient 0.9*u + 60, c'est-à-dire le terme suivant, et n compte le rang.

Terminaison : $u_n=600+200\times0{,}9^n$ tend vers $600<650$, donc $u_n$ finit par être strictement inférieur à $650$.

Valeur renvoyée : $u_n=600+200\times0{,}9^n$ donne :

$u_{13}\approx650{,}8\ge650$

$u_{14}\approx645{,}8<650$

✅ La fonction renvoie $14$, ce qui correspond à l'année $2040$.

Question 1

u = 0
for n in range(1, 11):
    u = 1/(1 + u)
    print(n, u)

Au $n$-ième passage, u devient $u_n$, que l'on affiche avec son rang n.

Question 2

Valeurs approchées :

$u_1=1$, $u_2=0{,}5$, $u_3\approx0{,}6667$, $u_4=0{,}6$, $u_5=0{,}625$

$u_6\approx0{,}6154$, $u_7\approx0{,}6190$, $u_8\approx0{,}6176$, $u_9\approx0{,}6182$, $u_{10}\approx0{,}6180$

Les termes alternent au-dessus et en dessous d'une valeur voisine de $0{,}618$ en s'en rapprochant.

✅ On conjecture que $(u_n)$ converge vers $\dfrac{\sqrt5-1}2\approx0{,}618$.

Cette conjecture n'est pas une preuve : elle est cohérente avec la limite calculée dans la fiche 5 (à condition d'admettre la convergence).

Remarque : les termes alternent, ce qui confirme que la suite n'est pas monotone, comme on l'avait vu en fiche 5.

Question 1

La fonction seuil(1000) renvoie le plus petit entier $n$ tel que $u_n>1000$, c'est-à-dire $2^{n+1}-1>1000$, soit $2^{n+1}>1001$.

Comme $2^9=512<1001$ et $2^{10}=1024>1001$, et que $2^k$ est croissante en $k$, le plus petit entier convenable vérifie $n+1=10$, donc $n=9$.

Vérification : $u_8=511\le1000$ et $u_9=1023>1000$.

✅ La fonction renvoie $9$.

Question 2

On a $u_n=2^{n+1}-1=2\times2^n-1$. Comme $2>1$, $2^n\to+\infty$, donc, par produit et par somme, $u_n\to+\infty$.

Par définition de la limite, pour tout réel $A$, il existe un rang $n_0$ tel que $u_n>A$ dès que $n\ge n_0$. Donc la condition u <= A devient fausse après un nombre fini de passages :

✅ la boucle se termine, quel que soit $A$.

À retenir : « pourquoi l'algorithme se termine » se justifie toujours par une limite infinie (ou par une limite qui franchit le seuil). C'est un point que les correcteurs adorent.