Listes, seuils et suites en Python

Listes et boucle for

Une liste Python est une suite ordonnée de valeurs écrite entre crochets : L = [3, 5, 8]. Le premier élément a l'indice 0 : L[0] vaut 3. La fonction len(L) donne le nombre d'éléments.

Pour construire une liste, on part d'une liste vide et on ajoute des éléments avec append dans une boucle for. L'instruction range(1, 6) parcourt les entiers de 1 à 5 : la borne de droite est exclue.

L = []

for k in range(1, 6):

    L.append(2 * k)

print(L)

Ce script affiche [2, 4, 6, 8, 10]. En Python, la puissance s'écrit ** : k**2 désigne $k^2$.

L = []

for k in range(1, 6):

    L.append(k**2)

print(L)

Fonctions et suites par récurrence

Une fonction Python regroupe des instructions et renvoie un résultat avec return. Pour une suite définie par récurrence, on garde en mémoire le terme courant dans une variable et on le met à jour à chaque tour de boucle. Le symbole d'affectation « ← » des algorithmes s'écrit = en Python.

Pour $u_0 = 5$ et $u_{n+1} = 0{,}9\,u_n + 2$ :

def terme(n):

    u = 5

    for k in range(n):

        u = 0.9 * u + 2

    return u

La boucle s'exécute $n$ fois : on passe de $u_0$ à $u_n$. Attention, Python utilise le point décimal (0.9) dans le code, alors que les mathématiques s'écrivent avec la virgule.

Le même principe donne la factorielle : $n! = 1 \times 2 \times \dots \times n$.

def fact(n):

    p = 1

    for k in range(1, n + 1):

        p = p * k

    return p

Ici p est un produit que l'on multiplie peu à peu : on l'initialise à 1 (élément neutre de la multiplication), alors qu'une somme s'initialise à 0.

def f(n):

    p = 1

    for k in range(1, n + 1):

        p = p * k

    return p

Seuils avec while

Quand on ne connaît pas à l'avance le nombre de tours, on utilise une boucle while : elle se répète tant que la condition est vraie. C'est la structure d'un algorithme de seuil.

Reprenons notre livret : 2 000 € à 3 % par an. Chaque année, le capital est multiplié par $1{,}03$ : c'est une suite géométrique $C_n = 2000 \times 1{,}03^n$. On cherche le plus petit $n$ tel que $C_n > 2500$.

def seuil():

    c = 2000

    n = 0

    while c <= 2500:

        c = c * 1.03

        n = n + 1

    return n

La boucle continue tant que le seuil n'est pas dépassé ; elle s'arrête dès que c > 2500, et n est alors le rang cherché.

Retour au début : pour dépasser 3 000 € il faut calculer $2000 \times 1{,}03^n > 3000$, c'est-à-dire $1{,}03^n > 1{,}5$. Comme $1{,}03^{13} \approx 1{,}469$ et $1{,}03^{14} \approx 1{,}513$, la réponse est 14 ans.

Algorithmes classiques : Syracuse, statistiques

Syracuse. On part d'un entier $a$. Si le terme est pair, on le divise par 2 ; sinon on le multiplie par 3 et on ajoute 1. Pour tester la parité, on utilise % (reste de la division euclidienne) : n % 2 == 0 signifie « $n$ est pair ». L'opérateur // donne le quotient entier : 7 // 2 vaut 3.

def syracuse(a):

    L = [a]

    while L[-1] != 1:

        if L[-1] % 2 == 0:

            L.append(L[-1] // 2)

        else:

            L.append(3 * L[-1] + 1)

    return L

L[-1] désigne le dernier élément de la liste. Dans une condition, on teste l'égalité avec == (et non =, qui sert à affecter).

Statistiques. Pour une liste L de $N$ valeurs à effectifs égaux, la moyenne est $m = \frac{1}{N}\sum x_i$, la variance $V = \frac{1}{N}\sum (x_i - m)^2$ et l'écart type $\sigma = \sqrt V$.

from math import sqrt

def stats(L):

    N = len(L)

    m = sum(L) / N

    V = sum((x - m)**2 for x in L) / N

    return m, V, sqrt(V)

On peut aussi parcourir directement une liste : for x in L: donne successivement chaque élément.

Fibonacci, Newton et Euler

Fibonacci

La suite $F_0 = 0$, $F_1 = 1$, $F_{n+2} = F_{n+1} + F_n$ a besoin de deux termes précédents. On les garde dans deux variables, ou on lit les deux derniers éléments de la liste :

def fibo(n):

    F = [0, 1]

    for k in range(2, n + 1):

        F.append(F[-1] + F[-2])

    return F[:n + 1]

Le découpage F[:n + 1] garde les éléments d'indices 0 à $n$ (utile si $n = 0$).

Méthode de Newton

Pour approcher une solution de $f(x) = 0$, on remplace la courbe par sa tangente en $x_n$. La tangente d'équation $y = f(x_n) + f'(x_n)(x - x_n)$ coupe l'axe des abscisses en $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$. Pour $f(x) = x^2 - 2$, on a $f'(x) = 2x$, d'où $x_{n+1} = \frac12\left(x_n + \frac{2}{x_n}\right)$ : on approche $\sqrt 2$.

def newton(eps):

    x = 2

    while abs(x**2 - 2) >= eps:

        x = (x + 2 / x) / 2

    return x

Méthode d'Euler

Pour approcher la solution de $y' = y$ avec $y(0) = 1$, on avance par petits pas $h$ en suivant la tangente : $y_{k+1} = y_k + h\,y_k = (1+h)\,y_k$. C'est une suite géométrique de raison $1+h$, donc $y_k = (1+h)^k$, qui approche $\mathrm e^{x_k}$.

def euler(h, n):

    y = 1

    L = [y]

    for k in range(n):

        y = y + h * y

        L.append(y)

    return L

L'essentiel

• Une liste se construit avec L = [] puis L.append(...) dans une boucle ; range(a, b) va de a à b - 1.

• Pour une suite récurrente, on initialise le terme courant avant la boucle for et on le met à jour à chaque tour ; une somme s'initialise à 0, un produit à 1.

• Un seuil se programme avec while : on boucle tant que le seuil n'est pas atteint, avec un compteur n.

• % donne le reste, // le quotient entier, L[-1] le dernier élément.

• Syracuse, Fibonacci, Newton et Euler suivent tous le même schéma : état initial, règle de mise à jour, condition d'arrêt.

• Toujours vérifier un programme en le faisant tourner à la main sur de petites valeurs.