Cours et exercices corrigés de première : Algorithmique et programmation en Python : listes, suites, seuils et simulations

1. Les listes en Python

Une liste est une suite ordonnée de valeurs, écrite entre crochets : L = [5, 8, 13].

• Les indices commencent à $0$ : L[0] vaut $5$, L[2] vaut $13$ ; L[-1] désigne le dernier élément.
• len(L) est le nombre d'éléments ; les indices vont donc de $0$ à len(L) - 1.
• L.append(x) ajoute x à la fin ; L[i] = x remplace l'élément d'indice i.
• Supprimer : L.pop() retire (et renvoie) le dernier élément ; del L[i] supprime l'élément d'indice i ; L.remove(x) supprime la première occurrence de la valeur x. Avec L = [5, 8, 13] : après L.remove(8), L vaut [5, 13] ; après del L[0], L vaut [13].
• sum(L), max(L), min(L) donnent la somme, le maximum, le minimum.

L = []
for k in range(5):
    L.append(k ** 2)
print(L)        # affiche [0, 1, 4, 9, 16]
print(len(L))   # affiche 5

2. Listes en compréhension et parcours

On peut construire une liste en une ligne, en compréhension :

carres = [k ** 2 for k in range(5)]                # [0, 1, 4, 9, 16]
pairs = [k for k in range(1, 20) if k % 2 == 0]   # entiers pairs de 2 à 18

Deux façons de parcourir une liste :

for x in L:              # par élément
    print(x)
for i in range(len(L)):  # par indice
    print(i, L[i])

Le parcours par indice est utile quand on a besoin de la position (par exemple pour comparer L[i] et L[i + 1]).

3. Calculer les termes d'une suite

• Suite explicite $u_n = f(n)$ : on programme une fonction.

def u(n):
    return 3 * n ** 2 - 1

• Suite récurrente $u_0 = 2$, $u_{n+1} = 3u_n - 1$ : on répète l'affectation $n$ fois ; après $n$ tours, la variable contient $u_n$.

def terme(n):
    u = 2
    for k in range(n):
        u = 3 * u - 1
    return u

def premiers_termes(n):
    L = [2]
    for k in range(n):
        L.append(3 * L[k] - 1)
    return L          # [u0, u1, ..., un]

terme(3) vaut $41$ et premiers_termes(3) vaut [2, 5, 14, 41].

4. Sommes de termes

Pour calculer $S_n = u_0 + u_1 + \dots + u_n$, on utilise un accumulateur s initialisé à $0$ :

def somme(n):
    s = 0
    u = 1
    for k in range(n + 1):
        s = s + u        # on ajoute u_k
        u = 2 * u        # on calcule u_(k+1)
    return s

Ici $u_k = 2^k$ et somme(n) vaut $1 + 2 + \dots + 2^n = 2^{n+1} - 1$. Attention à l'ordre des deux instructions de la boucle et au nombre de termes : de $u_0$ à $u_n$, il y a $n + 1$ termes.

5. Algorithme de seuil

Pour une suite croissante qui tend vers $+\infty$, on cherche le plus petit rang $n$ tel que $u_n \ge A$. On répète le calcul tant que le seuil n'est pas atteint :

def seuil(A):
    n = 0
    u = 500
    while u < A:
        u = 1.04 * u
        n = n + 1
    return n

À la sortie de la boucle, u vaut $u_n$ et c'est le premier terme supérieur ou égal à $A$. Pour une suite décroissante, la condition devient while u > A:. (Voir aussi le chapitre 1A5.)

6. Simulation et fréquences

Le module random permet de simuler le hasard :

• random() renvoie un flottant aléatoire de $[0 ; 1[$ ; la condition random() < p est vraie avec la probabilité $p$ ;
• randint(a, b) renvoie un entier aléatoire entre $a$ et $b$ inclus.

from random import randint

def frequence_sept(N):
    c = 0
    for i in range(N):
        if randint(1, 6) + randint(1, 6) == 7:
            c = c + 1
    return c / N

Pour $N$ grand, la fréquence obtenue est proche de la probabilité $\frac{6}{36} = \frac{1}{6}$, et la moyenne de valeurs simulées est proche de l'espérance (loi des grands nombres, voir 1S2).

7. Exemples classiques : factorielle, Fibonacci, Syracuse

def factorielle(n):
    p = 1
    for k in range(1, n + 1):
        p = p * k
    return p

def fibonacci(n):        # n premiers termes (n >= 2) : 1, 1, 2, 3, 5...
    L = [1, 1]
    while len(L) < n:
        L.append(L[-1] + L[-2])
    return L

def syracuse(a):         # termes à partir de a, jusqu'à atteindre 1
    L = [a]
    while a != 1:
        if a % 2 == 0:
            a = a // 2
        else:
            a = 3 * a + 1
        L.append(a)
    return L

• factorielle(5) vaut $5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$.
• fibonacci(8) vaut [1, 1, 2, 3, 5, 8, 13, 21] : chaque terme est la somme des deux précédents.
• syracuse(7) contient $17$ termes (de $7$ à $1$) et atteint au maximum $52$. Personne ne sait démontrer que la suite atteint $1$ quel que soit l'entier de départ : c'est la conjecture de Syracuse.

8. Fréquences d'apparition des lettres d'un texte

def frequences(texte):
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    lettres = [c for c in texte.lower() if c in alphabet]
    return [(l, lettres.count(l) / len(lettres)) for l in alphabet]

La fonction renvoie une liste de couples (lettre, fréquence). Sur un long texte en français, le « e » est nettement la lettre la plus fréquente ; la répartition est différente en anglais. Ces fréquences servent par exemple à décrypter un message codé par décalage des lettres.

9. Programmation modulaire

On découpe un problème en fonctions simples, que l'on combine. Par exemple, pour calculer $u_0 + u_1 + \dots + u_n$ avec $u_k = 2^k$, on sépare le calcul d'un terme et celui de la somme :

def u(k):
    return 2 ** k

def somme(n):
    s = 0
    for k in range(n + 1):
        s = s + u(k)
    return s

somme(10) vaut $2^{11} - 1 = 2\,047$. Pour une autre suite, il suffit de modifier la fonction u : la fonction somme reste inchangée.