Algorithmique Listes
1ERE-SPE • MATHS — Learna
Suivez votre progression
Connectez-vous pour enregistrer votre progression et vos tentatives de quiz.
Cours — Algorithmique : Les listes
Stocker des données • parcourir • rechercher • compter • filtrer • calculer • trier.
1) Objectifs et plan de travail
Compétences attendues (1ère Spé)
- Comprendre ce qu’est une liste et savoir créer une liste simple en Python.
- Accéder à un élément, connaître la notion d’indice, comprendre que le premier indice est \(0\).
- Parcourir une liste de deux façons : sur les valeurs ou sur les indices.
- Modifier une liste, ajouter des éléments, construire progressivement une nouvelle liste.
- Écrire des algorithmes pour calculer une somme, une moyenne, un maximum ou un minimum.
- Rechercher une valeur, compter des occurrences, filtrer des éléments selon une condition.
- Comprendre les premiers ordres de complexité : accès direct, parcours complet, recherche simple.
Pièges fréquents
- Confondre indice et valeur.
- Penser que le premier élément a l’indice \(1\) alors qu’il a l’indice \(0\).
- Utiliser \(L[0]\) sans se demander si la liste peut être vide.
- Oublier d’initialiser une variable : somme, compteur, maximum, booléen…
- Choisir une mauvaise boucle : valeurs au lieu d’indices, ou inversement.
- Écrire un algorithme correct en idée, mais imprécis dans les mises à jour.
Réflexe “copie propre” : je repère d’abord ce qu’on me demande
(somme ? max ? recherche ? filtrage ?), puis j’écris :
initialisation → boucle → condition éventuelle → mise à jour → conclusion.
2) Définition d’une liste
Définition
Une liste est une suite ordonnée de valeurs.
En Python, on l’écrit entre crochets.
L = [5, 8, 3, 10]
Vocabulaire
- Chaque valeur de la liste est un élément.
- La position d’un élément est son indice.
- Le nombre d’éléments est la taille de la liste.
Exemple 1 — Lire la structure d’une liste
Si \(L=[12,4,9,7]\), alors :
- \(L[0]=12\)
- \(L[1]=4\)
- \(L[2]=9\)
- \(L[3]=7\)
Attention : une liste garde l’ordre des éléments.
\([2,5,7]\) et \([7,5,2]\) ne sont pas la même liste.
3) Accéder aux éléments
Accès par indice
L = [10, 4, 9, 7]
print(L[0]) # 10
print(L[2]) # 9
Dernier élément et taille
L[-1] # dernier élément
len(L) # taille de la liste
En Python, L[-1] désigne le dernier élément.
Exemple 2 — Lire des éléments précis
Si \(L=[3,8,11,6,14]\), alors :
- \(L[0]=3\)
- \(L[3]=6\)
- \(L[-1]=14\)
- \(len(L)=5\)
Erreur classique : si la liste a 5 éléments, les indices sont
\(0,1,2,3,4\). Demander \(L[5]\) provoque une erreur.
4) Parcourir une liste
Méthode 1 — parcours direct
L = [5, 8, 3, 10]
for x in L:
print(x)
La variable x prend successivement les valeurs
\(5\), \(8\), \(3\), \(10\).
Méthode 2 — parcours par indices
L = [5, 8, 3, 10]
for i in range(len(L)):
print(i, L[i])
Ici, la variable i prend les indices
\(0\), \(1\), \(2\), \(3\).
À retenir :
- for x in L : parfait si on travaille sur les valeurs.
- for i in range(len(L)) : utile si on a besoin des positions.
Exemple 3 — Quand choisir l’une ou l’autre méthode ?
- Pour calculer une somme : le parcours direct suffit.
- Pour trouver la position d’un élément : il faut généralement parcourir les indices.
5) Modifier une liste
Remplacer une valeur
L = [4, 7, 12]
L[1] = 20
# L vaut maintenant [4, 20, 12]
Ajouter une valeur
L = [4, 7, 12]
L.append(9)
# L vaut maintenant [4, 7, 12, 9]
Supprimer un élément
L = [4, 7, 12, 9]
L.pop()
# enlève le dernier élément
Exemple 4 — Construire progressivement une liste
On part souvent d’une liste vide :
M = []
M.append(5)
M.append(8)
M.append(13)
On obtient alors \(M=[5,8,13]\).
Une liste est dite mutable :
son contenu peut être modifié après sa création.
6) Calculs classiques sur une liste
Somme
L = [5, 8, 3, 10]
s = 0
for x in L:
s = s + x
À la fin, \(s=26\).
Moyenne
L = [5, 8, 3, 10]
s = 0
for x in L:
s = s + x
moy = s / len(L)
Ici, \(\text{moy}=\dfrac{26}{4}=6{,}5\).
Maximum
L = [5, 8, 3, 10]
maxi = L[0]
for x in L:
if x > maxi:
maxi = x
Minimum
L = [5, 8, 3, 10]
mini = L[0]
for x in L:
if x < mini:
mini = x
Exemple 5 — Pourquoi initialise-t-on avec le premier élément ?
Pour trouver un maximum ou un minimum, on veut partir d’une valeur qui appartient
réellement à la liste. Utiliser \(L[0]\) donne une base sûre de comparaison.
Exemple 6 — Somme des carrés
On peut adapter l’idée selon la question posée :
L = [1, 2, 3, 4]
s = 0
for x in L:
s = s + x**2
Ici, on calcule \(1^2+2^2+3^2+4^2=30\).
7) Rechercher une valeur
Recherche booléenne
L = [5, 8, 3, 10]
x = 8
trouve = False
for y in L:
if y == x:
trouve = True
À la fin, trouve vaut True si la valeur est présente.
Version Python rapide
x in L
Cette écriture est pratique, mais au lycée il faut souvent savoir
reconstituer l’algorithme.
Trouver la position d’une valeur
L = [5, 8, 3, 10]
x = 3
indice = -1
for i in range(len(L)):
if L[i] == x:
indice = i
Si \(x\) est trouvé, indice contient sa position.
Sinon, on garde \(-1\).
Exemple 7 — Recherche d’une occurrence
Dans \(L=[7,4,9,4,12]\), la valeur \(4\) est présente.
Si on parcourt les indices, on peut rencontrer plusieurs positions.
À savoir : dans une recherche simple, on peut être obligé de lire
toute la liste.
8) Compter et filtrer
Compter des éléments
L = [4, 12, 7, 15, 18]
c = 0
for x in L:
if x > 10:
c = c + 1
Ici, on compte les valeurs strictement supérieures à \(10\).
Compter des occurrences
L = [3, 5, 3, 7, 3, 8]
x = 3
c = 0
for y in L:
if y == x:
c = c + 1
Filtrer les nombres pairs
L = [5, 8, 3, 10, 7, 12]
pairs = []
for x in L:
if x % 2 == 0:
pairs.append(x)
On obtient \([8,10,12]\).
Filtrer les valeurs positives
L = [-2, 5, -1, 7, 0, 9]
positifs = []
for x in L:
if x > 0:
positifs.append(x)
Filtrer, c’est construire une nouvelle liste contenant seulement
les éléments qui vérifient une condition.
Exemple 8 — Construire la liste des carrés
L = [2, 4, 5]
carres = []
for x in L:
carres.append(x**2)
On obtient la liste \([4,16,25]\).
9) Sous-listes et tri
Sous-listes
L = [2, 4, 6, 8, 10, 12]
L[1:4] # [4, 6, 8]
L[:3] # [2, 4, 6]
L[3:] # [8, 10, 12]
Dans L[a:b], l’indice \(a\) est inclus
et l’indice \(b\) est exclu.
Tri
L = [8, 3, 10, 5]
M = sorted(L) # copie triée
L.sort() # tri sur place
Après tri croissant, on obtient \([3,5,8,10]\).
Exemple 9 — Extraire une partie utile d’une liste
Les sous-listes sont utiles quand on veut travailler seulement sur
une partie des données.
10) Premiers éléments de complexité
| Opération | Coût | Idée |
|---|---|---|
| Accès à \(L[i]\) | \(O(1)\) | Très rapide : accès direct |
| Parcours complet | \(O(n)\) | On lit les \(n\) éléments |
| Recherche simple | \(O(n)\) | On peut devoir tester toute la liste |
| Maximum / minimum | \(O(n)\) | Il faut parcourir la liste |
À retenir :
- Lire un élément précis est très rapide.
- Chercher une valeur ou calculer un maximum demande en général un parcours complet.
Exemple 10 — Pourquoi la recherche simple est-elle en \(O(n)\) ?
Si la valeur cherchée est absente, on doit lire tous les éléments.
Si elle est à la fin, on lit presque toute la liste.
11) Mini-formulaire (à connaître)
Commandes utiles
L = [3, 8, 5]
len(L) # taille
L[0] # premier élément
L[-1] # dernier élément
L.append(7) # ajoute 7
L.pop() # enlève le dernier
Autres outils
x in L # teste la présence
sorted(L) # renvoie une copie triée
L.sort() # trie la liste sur place
L[1:4] # sous-liste
Schéma type d’un algorithme sur liste
# 1. initialisation
# 2. boucle sur la liste
# 3. test éventuel
# 4. mise à jour
# 5. résultat final
12) Checklist “copie parfaite”
- Je sais définir une liste, lire sa taille et accéder à ses éléments.
- Je sais parcourir une liste avec for x in L et avec for i in range(len(L)).
- Je sais calculer somme, moyenne, maximum et minimum.
- Je sais rechercher une valeur et retrouver sa position.
- Je sais compter des éléments et construire une nouvelle liste par filtrage.
- Je comprends l’idée des sous-listes, du tri et de la complexité \(O(1)\) / \(O(n)\).
- Je relis toujours mon algorithme avec un petit exemple test.
Dernier rappel : en algorithmique, on n’évalue pas seulement le résultat final,
mais aussi la clarté, la logique et la rigueur de la méthode.