Algorithme Python — Compétences

Ce que le Bac demande

On ne te demande pas d’être développeur. Quatre gestes reviennent sans cesse :

Lire

Que calcule cette fonction ? Quelle valeur renvoie-t-elle pour $n=4$ ?

Compléter

Remplir une ligne : souvent la mise à jour $u = \ldots$ ou le test du while.

Corriger

Spotter un range trop court, un test à l’envers, une variable non mise à jour.

Écrire

Un petit programme : terme d’une suite, seuil, ou dichotomie.

Vidéo — Lire un algorithme

Vidéo à venir

Comment dérouler un script à la main, ligne par ligne.

Le vocabulaire utile

Instruction	Rôle
`u = 2`	Affectation : $u$ prend la valeur $2$.
`for i in range(n):`	$i$ vaut $0, 1, \ldots, n-1$ : la boucle tourne $n$ fois.
`while u < A:`	On répète tant que la condition est vraie. Pense à un seuil.
`return u`	La fonction s’arrête et renvoie $u$.

range(n) s’arrête avant $n$. C’est le piège n°1.

Exemple 1 — Terme d’une suite

$u_0 = 2$ et $u_{n+1} = 0{,}5\, u_n + 1$. On veut $u_n$.

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

Déroulé pour $n=3$

départ $u=2$
$i=0$ : $u = 0{,}5\times 2 + 1 = 2$
$i=1$ : $u = 0{,}5\times 2 + 1 = 2$
$i=2$ : $u = 2$ encore — ici la suite est constante égale à $2$.

La boucle tourne $n$ fois : après $n$ mises à jour, on a $u_n$. Si tu écris range(n+1), tu calcules $u_{n+1}$.

Exemple 2 — Seuil

$u_0=1$, $u_{n+1}=1{,}2\,u_n$. Plus petit $n$ tel que $u_n \geq 10$.

def seuil():
n = 0
u = 1
while u < 10:
    n = n + 1
    u = 1.2 * u
return n

Pourquoi ça marche

On avance $n$ et $u$ ensemble. On s’arrête dès que $u$ a dépassé le seuil : $n$ est alors le rang cherché.

Piège

Inverser l’ordre (u = ... avant n = n+1 sans faire gaffe) décale le rang. Toujours se demander : « $n$ et $u$ parlent-ils du même terme ? »

Vidéo — Seuil et dichotomie

Vidéo à venir

Les deux algorithmes les plus classiques du Bac, rédigés et testés.

Exemple 3 — Dichotomie

$f$ continue, $f(a)$ et $f(b)$ de signes contraires. On encadre une racine à $\varepsilon$ près.

def dicho(f, a, b, e):
while b - a > e:
    m = (a + b) / 2
    if f(a) * f(m) <= 0:
        b = m
    else:
        a = m
return (a + b) / 2

L’idée : on coupe $[a;b]$ en deux. Le zéro est dans la moitié où $f$ change de signe. Le test $f(a)\times f(m) \leq 0$ veut dire « $f(a)$ et $f(m)$ sont de signes opposés (ou nuls) ».

Check-list avant de rendre

1.

range(n) = $n$ tours, indices $0$ à $n-1$.

2.

Indentation : tout ce qui est dans la boucle est reculé d’un cran.

3.

Dérouler à la main pour $n=2$ ou $n=3$ : tu vois tout de suite si ça dépasse.

4.

Le return est hors de la boucle, sauf si tu veux t’arrêter au premier coup.