Algorithmique et programmation : la notion de liste
Un algorithme est une suite d'instructions qui conduit à un résultat. En première, tu consolides variables, conditions, boucles et fonctions, et tu rencontres une seule notion nouvelle : la liste. Une liste range plusieurs valeurs sous un même nom : les termes d'une suite, une série statistique, un tableau de valeurs. À la fin, tu sauras générer une liste, modifier ses éléments grâce à leurs indices, la parcourir et écrire de petites fonctions qui la traitent. Tu peux écrire un algorithme en langage naturel (avec « ← » pour l'affectation) ou en Python ; ce cours privilégie Python.
Variables, types et affectation
Une variable est un nom qui désigne une valeur gardée en mémoire. L'affectation range une valeur dans une variable : on écrit en langage naturel, a = 5 en Python. L'ordinateur calcule d'abord le membre de droite, puis le range dans la variable de gauche. Ce n'est pas une égalité mathématique : a = a + 1 augmente de .
Chaque valeur a un type : entier (int, 3), flottant (float, 3.0), chaîne de caractères (str, "3"), booléen (bool, True ou False) ou liste (list). Le type change l'effet des opérations : 3 + 4 donne 7, mais "3" + "4" donne "34". En Python, 7 / 2 vaut 3.5, 7 // 2 vaut 3 (quotient entier) et 7 % 2 vaut 1 (reste de la division).
Exemple
Suis les variables ligne par ligne.
a ← 5
b ← a * 2
a ← b - 3
Ligne 1 : . Ligne 2 : . Ligne 3 : , et reste égal à . À la fin, et .
Conditions et boucles
Une instruction conditionnelle (if, else) exécute un bloc seulement si la condition est vraie. Les tests s'écrivent == (égal), != (différent), <, <=, et se combinent avec and, or, not. Une boucle for répète un bloc un nombre connu de fois ; une boucle while le répète tant qu'une condition reste vraie. Le bloc répété est décalé vers la droite : c'est l'indentation, qui fait partie de la syntaxe.
range(n) fournit les entiers ; range(a, b) fournit . La borne est exclue.
Exemple
Calculer la somme des carrés des entiers de à .
s = 0
for i in range(1, 5):
s = s + i * i
Suivi : donne ; donne ; donne ; donne . La boucle s'arrête avant : à la fin, .
Générer une liste
Une liste est une suite ordonnée d'éléments, notée entre crochets, ses éléments étant séparés par des virgules. L'ordre compte et les répétitions sont permises : et sont deux listes différentes, alors que et désignent le même ensemble. Trois façons de générer une liste :
- En extension : on écrit tous les éléments, par exemple
L = [2, 5, 8, 11, 14]; la liste vide s'écrit[]. - Par ajouts successifs : on part de la liste vide et on ajoute les éléments un à un avec
append. - En compréhension : on décrit les éléments par une règle, comme on décrit un ensemble par une propriété ;
[3 * n + 2 for n in range(5)]correspond à . Une conditioniffiltre les éléments.
Exemple
Les trois écritures suivantes génèrent la même liste.
L = [2, 5, 8, 11, 14]
L = []
for n in range(5):
L.append(3 * n + 2)
L = [3 * n + 2 for n in range(5)]
Pour les deux dernières, on pose les calculs : donne ; donne ; donne ; donne ; donne . Ce sont les cinq premiers termes de la suite .
Sur la figure, l'abscisse est l'indice et l'ordonnée la valeur L[i]. Le point d'abscisse a pour ordonnée : L[3] vaut , c'est le quatrième élément, car on compte à partir de .
Avec une condition. [n * n for n in range(1, 8) if n % 2 == 1] correspond à . Le test n % 2 == 1 est vrai pour , donc la liste obtenue est . La condition est une proposition vraie ou fausse pour chaque : c'est la logique du chapitre précédent.
Indices et manipulation
Chaque élément d'une liste a un indice, c'est-à-dire sa position, et le premier indice est . Pour L = [2, 5, 8, 11, 14] : L[0] vaut , L[1] vaut , L[4] vaut . len(L) donne le nombre d'éléments, ici ; le dernier indice est donc len(L) - 1, soit . Demander L[5] provoque une erreur (« index out of range »).
L[i] = vremplace l'élément d'indice par ;L.append(v)ajoute à la fin ;L.insert(i, v)insère à l'indice et décale les suivants ;L.pop(i)supprime l'élément d'indice et le renvoie ;L.remove(v)supprime la première occurrence de la valeur .
En langage naturel : « ajouter à », « supprimer de l'élément d'indice ».
Exemple
On part de L = [2, 5, 8, 11, 14] et on note la liste après chaque instruction.
L.append(17) # [2, 5, 8, 11, 14, 17]
L[1] = 6 # [2, 6, 8, 11, 14, 17]
L.pop(0) # [6, 8, 11, 14, 17]
L.remove(11) # [6, 8, 14, 17]
L.insert(1, 7) # [6, 7, 8, 14, 17]
À la fin, len(L) vaut et L[2] vaut .
Parcourir une liste
Deux façons de parcourir une liste L :
- par indice :
for i in range(len(L)), puis on litL[i], utile quand la position compte ; - par élément :
for x in L, la variable prend successivement chaque valeur de la liste, dans l'ordre ; c'est plus simple quand la position est inutile.
Exemple
Somme des éléments de L = [6, 7, 8, 14, 17].
total = 0
for x in L:
total = total + x
Suivi : donne ; donne ; donne ; donne ; donne . La somme vaut .
Exemple
Liste des éléments pairs de L.
pairs = []
for x in L:
if x % 2 == 0:
pairs.append(x)
Le test est vrai pour , et (restes nuls) et faux pour et : pairs vaut . Parcourir et filtrer revient à écrire en compréhension [x for x in L if x % 2 == 0].
Fonctions et programmation modulaire
Une fonction se définit avec def, reçoit des paramètres et renvoie son résultat avec return. La programmation modulaire découpe une tâche complexe en tâches simples : chaque tâche devient une fonction, que les autres peuvent appeler.
Exemple
Moyenne des cinq premiers termes de la suite .
def suite(n):
return [3 * k + 2 for k in range(n)]
def somme(L):
total = 0
for x in L:
total = total + x
return total
def moyenne(L):
return somme(L) / len(L)
On évalue moyenne(suite(5)). D'abord suite(5) renvoie . Ensuite la somme vaut et len vaut . Enfin : Python affiche 8.0, car / renvoie un flottant.
Les pièges
- Compter à partir de 1.
L[1]est le deuxième élément ; le dernier indice estlen(L) - 1, jamaislen(L). - Oublier que
rangeexclut la borne. Pour parcourir les entiers de à , écrisrange(1, n + 1). - Écrire
L = L.append(x).appendmodifieLet ne renvoie rien :Lvaut alorsNone. - Confondre
popetremove.L.pop(3)supprime l'élément d'indice ;L.remove(3)supprime la valeur . - Supprimer pendant le parcours. Ne retire pas d'éléments de
Lpendant quefor x in Lla parcourt : des éléments sont sautés. Construis plutôt une nouvelle liste. - Placer
returndans la boucle. La fonction s'arrête dès le premier tour ; metsreturnhors de la boucle, comme danssomme. - Confondre
=et==.=affecte une valeur,==teste une égalité.
Ce qu'il faut retenir
- Une liste est ordonnée, notée entre crochets, et peut contenir des répétitions.
- On la génère en extension, par ajouts successifs (
append) ou en compréhension ([f(n) for n in ... if ...]). - Le premier indice est ; le dernier est
len(L) - 1. L[i] = v,append,insert,pop(i)etremove(v)modifient la liste ;popsupprime par indice,removepar valeur.range(a, b)va de à .- On parcourt une liste par indice (
for i in range(len(L))) ou par élément (for x in L). - Une condition
ifdans une compréhension filtre les éléments, comme une propriété dans un ensemble. - Une fonction qui traite une liste la reçoit en paramètre et renvoie son résultat avec
return. - L'affectation se note « ← » en langage naturel et
=en Python.
À l'épreuve
Les listes apparaissent dans des exercices sur les suites, la statistique ou les probabilités. Les formulations habituelles : « que contient la liste L après exécution de ce script ? », « quelle valeur renvoie la fonction pour tel argument ? », « écris la ligne manquante du script », « que calcule cette fonction ? ». Le correcteur attend un suivi des variables posé étape par étape (variable de boucle, accumulateur, contenu de la liste), pas seulement le résultat final. Il attend aussi une lecture exacte des indices et des bornes de range, une indentation correcte, et, pour « que calcule cette fonction ? », une phrase qui dit ce qu'elle calcule en général, pas seulement sur un exemple.