Algorithmique : les listes

La notion nouvelle de Première en programmation : la liste, qui permet de stocker et traiter d'un coup les termes d'une suite, les valeurs d'une série statistique ou les résultats d'une simulation.

  • Générer une liste (extension, ajouts, compréhension)
  • Manipuler les éléments et leurs indices
  • Parcourir une liste
  • Programmer les algorithmes de l'année

Tous les programmes s'exécutent ici même (Python chargé dans la page à la première exécution). Mode « pas à pas » disponible pour suivre l'évolution des variables.

Cours

1. Créer une liste

Une liste est une suite ordonnée d'éléments, notée entre crochets : L = [3, 1, 4, 1, 5]. La liste vide est [].

  • En extension : on écrit tous les éléments, [2, 4, 6, 8].
  • Par ajouts successifs : on part de [] et on utilise L.append(x) dans une boucle.
  • En compréhension : [n**2 for n in range(10)], éventuellement avec une condition : [n for n in range(50) if n % 7 == 0].
# en extension
L1 = [1, 4, 9, 16, 25]

# par ajouts successifs
L2 = []
for n in range(1, 6):
    L2.append(n ** 2)

# en compréhension
L3 = [n ** 2 for n in range(1, 6)]

print(L1, L2, L3)
print(L1 == L2 == L3)
print([n for n in range(1, 60) if n % 7 == 0])

2. Éléments et indices

InstructionEffet
len(L)nombre d'éléments
L[0], L[i]premier élément, élément d'indice i (les indices commencent à 0)
L[-1]dernier élément
L[i] = xmodifie l'élément d'indice i
L.append(x)ajoute x à la fin
L[a:b]sous-liste des indices a à b - 1
sum(L), max(L), min(L)somme, maximum, minimum
sorted(L)copie triée

Une liste de $n$ éléments a des indices de $0$ à $n - 1$ : L[len(L)] provoque une erreur IndexError.

3. Parcourir une liste

Par les éléments : for x in L: (quand seule la valeur compte). Par les indices : for i in range(len(L)): (quand on a besoin de la position, ou de comparer deux éléments voisins).

notes = [12, 15.5, 8, 17, 11, 14]

def moyenne(L):
    s = 0
    for x in L:
        s = s + x
    return s / len(L)

def position_max(L):
    im = 0
    for i in range(len(L)):
        if L[i] > L[im]:
            im = i
    return im

def est_croissante(L):
    for i in range(len(L) - 1):
        if L[i + 1] < L[i]:
            return False
    return True

print(moyenne(notes), position_max(notes), est_croissante(notes), est_croissante(sorted(notes)))

4. Les algorithmes de l'année

def termes(u0, q, n):
    # liste des n premiers termes d'une suite géométrique
    L = [u0]
    for i in range(n - 1):
        L.append(L[-1] * q)
    return L

def seuil(u0, q, M):
    # premier rang n tel que u_n > M
    u, n = u0, 0
    while u <= M:
        u, n = u * q, n + 1
    return n

print(termes(3, 2, 10))
print(sum(termes(1, 0.5, 30)))   # proche de 2
print(seuil(1000, 1.05, 2000))

from random import randint

def echantillon(n):
    # liste de n lancers de dé
    return [randint(1, 6) for i in range(n)]

def frequence(L, v):
    return L.count(v) / len(L)

E = echantillon(1000)
print("Fréquence des 6 :", frequence(E, 6))
print("Moyenne :", sum(E) / len(E))

# N moyennes d'échantillons de taille 100
moyennes = [sum(echantillon(100)) / 100 for k in range(500)]
print("Min et max des moyennes :", min(moyennes), max(moyennes))

Méthodes à connaître

  1. Liste vide puis ajouts : L = [] et L.append(x) dans une boucle.
  2. En compréhension : [f(k) for k in range(n)], avec éventuellement une condition if.
  3. Longueur : len(L) ; éléments : L[0] à L[len(L) - 1].

Exemple. Carrés des nombres pairs inférieurs à 20 : [k**2 for k in range(20) if k % 2 == 0].

  1. Par les valeurs : for x in L: (somme, maximum, comptage).
  2. Par les indices : for i in range(len(L)): (quand la position compte).
  3. Initialise l'accumulateur (somme à 0, maximum au premier élément) avant la boucle.

Mini-jeux

Exercices

# Écris ton programme ici

Que contient L après ces instructions ? L = [5, 2, 7] ; L.append(L[0] + L[-1]) ; L[1] = 10.

[5, 10, 7, 12].

Écrire en compréhension la liste des cubes des entiers de 1 à 10, puis la liste des entiers de 1 à 100 dont le reste dans la division par 7 vaut 3.

[n**3 for n in range(1, 11)] ; [n for n in range(1, 101) if n % 7 == 3].

Écrire une fonction fibo(n) renvoyant la liste des $n$ premiers termes de la suite de Fibonacci ($1, 1, 2, 3, 5\dots$). Calculer les quotients de deux termes consécutifs : vers quoi semblent-ils tendre ?

def fibo(n):
    L = [1, 1]
    while len(L) < n:
        L.append(L[-1] + L[-2])
    return L[:n]

F = fibo(30)
print([F[i + 1] / F[i] for i in range(29)])

Les quotients tendent vers le nombre d'or $\frac{1 + \sqrt5}{2} \approx 1{,}618$.

Écrire une fonction ecart_type(L) qui calcule l'écart type d'une série de valeurs (formule du cours de statistique).

def ecart_type(L):
    m = sum(L) / len(L)
    v = sum([(x - m)**2 for x in L]) / len(L)
    return v ** 0.5

Écrire une fonction premiers(n) qui renvoie la liste des nombres premiers inférieurs ou égaux à $n$ en utilisant une liste de booléens est_premier que l'on « raye » au fur et à mesure.

def premiers(n):
    est_premier = [True] * (n + 1)
    est_premier[0] = est_premier[1] = False
    for i in range(2, n + 1):
        if est_premier[i]:
            for k in range(2 * i, n + 1, i):
                est_premier[k] = False
    return [i for i in range(n + 1) if est_premier[i]]