Algorithmique — Listes | Fiches de révision — 1ère Spé Maths | Learna

Fiche ultra-synthèse — Algorithmique : Listes (1ère Spé)

Accès • parcours • calculs • recherche • filtrage • sous-listes • tri • complexité. Objectif : écrire des algorithmes propres, efficaces et sans erreur.

Essentiel Méthodes Pièges Mini-tests Checklist

Essentiel (à savoir par cœur)

1 Définition d’une liste

Une liste est une suite ordonnée de valeurs. En Python, on l’écrit avec des crochets.

L = [4, 7, 12, 5]

Les éléments sont repérés par des indices : \(L[0]=4\), \(L[1]=7\), \(L[2]=12\), \(L[3]=5\).

Piège : le premier indice est 0, pas 1.

2 Accès et taille

Commande	Rôle
L[i]	accéder à l’élément d’indice \(i\)
L[-1]	dernier élément
len(L)	taille de la liste

Exemple : si \(L=[10,4,9,7]\), alors \(len(L)=4\) et \(L[-1]=7\).

Si la liste a 4 éléments, les indices autorisés sont \(0,1,2,3\).

3 Parcourir une liste

Deux écritures essentielles :

Parcours direct : on lit les valeurs.
Parcours par indices : on lit les positions.

for x in L: print(x)

for i in range(len(L)): print(i, L[i])

4 Modifier une liste

Une liste est modifiable : on peut remplacer, ajouter ou supprimer.

L = [4, 7, 12] L[1] = 20 # devient [4, 20, 12] L.append(9) # devient [4, 20, 12, 9] L.pop() # enlève le dernier élément

On utilise souvent append pour construire progressivement une nouvelle liste.

5 Calculs classiques

Objectif	Idée
Somme	initialiser à 0 puis additionner
Moyenne	sommer puis diviser par \(len(L)\)
Maximum	comparer tous les éléments
Minimum	même méthode que le maximum

Pour un max ou un min, on initialise en général avec le premier élément.

6 Recherche et présence

Chercher une valeur consiste à tester si elle apparaît dans la liste.

x = 8 trouve = False for y in L: if y == x: trouve = True

Écriture Python rapide : x in L.

Au lycée, on demande souvent de savoir réécrire l’algorithme complet, pas seulement d’utiliser in.

7 Filtrer une liste

Filtrer, c’est construire une nouvelle liste contenant seulement les éléments qui vérifient une condition.

pairs = [] for x in L: if x % 2 == 0: pairs.append(x)

Ici, on garde uniquement les éléments pairs.

8 Complexité (premiers repères)

En 1ère Spé, on retient surtout l’idée : accès direct = rapide ; parcours complet = plus coûteux.

Opération	Coût
Accéder à \(L[i]\)	\(O(1)\)
Parcourir toute la liste	\(O(n)\)
Rechercher une valeur	\(O(n)\)
Calculer un maximum	\(O(n)\)

Méthodes (procédures rapides 20/20)

A Calculer une somme et une moyenne

Créer une variable somme \(s\) initialisée à 0.
Parcourir la liste.
Ajouter chaque valeur à \(s\).
Diviser par la taille si on veut la moyenne.

L = [5, 8, 3, 10] s = 0 for x in L: s = s + x moy = s / len(L)

B Trouver le maximum

Initialiser avec le premier élément.
Parcourir la liste.
Comparer chaque élément au maximum courant.
Remplacer si on trouve plus grand.

L = [5, 8, 3, 10] maxi = L[0] for x in L: if x > maxi: maxi = x

C Compter des éléments vérifiant une condition

Initialiser un compteur à 0.
Parcourir la liste.
Tester la condition.
Ajouter 1 si la condition est vraie.

L = [4, 12, 7, 15, 18] c = 0 for x in L: if x > 10: c = c + 1

D Construire une nouvelle liste

On utilise souvent : nouvelle_liste = [] puis append.

L = [2, 4, 5] carres = [] for x in L: carres.append(x**2)

On obtient ici la liste des carrés : \([4,16,25]\).

E Trouver la position d’une valeur

Initialiser une variable d’indice, par exemple à \(-1\).
Parcourir les indices de la liste.
Comparer \(L[i]\) à la valeur cherchée.
Mettre à jour l’indice si trouvé.

L = [5, 8, 3, 10] x = 3 indice = -1 for i in range(len(L)): if L[i] == x: indice = i

F Sous-listes et tri

Les sous-listes permettent d’extraire une partie de la liste. Le tri permet de classer les valeurs.

L = [2, 4, 6, 8, 10, 12] L[1:4] # [4, 6, 8] L[:3] # [2, 4, 6] L[3:] # [8, 10, 12] M = sorted(L) L.sort()

Pièges classiques (à éviter)

1 Indices

Le premier élément a l’indice 0.
Une liste de taille 5 a les indices \(0\) à \(4\).

2 Valeur / indice

Ne pas confondre la valeur d’un élément et sa position dans la liste.

3 Initialisation

Un compteur commence souvent à \(0\).
Un maximum commence souvent à L[0].

4 Boucle mal choisie

Si tu as besoin de l’indice, utilise for i in range(len(L)).

5 Liste vide

On ne peut pas faire L[0] si la liste est vide.

6 Mauvaise condition

Vérifier soigneusement : \(>\), \(\ge\), \(<\), \(\le\), \(==\).

Réflexe : relire l’algorithme avec une petite liste test, par exemple \([2,5,1]\), pour vérifier chaque étape.

Mini-tests (30 secondes chacun) — corrigés

Q1 Taille

Si \(L=[4,8,2,9]\), combien vaut \(len(L)\) ?

Corrigé : \(len(L)=4\).

Q2 Accès

Si \(L=[4,8,2,9]\), combien vaut \(L[2]\) ?

Corrigé : \(L[2]=2\).

Q3 Dernier

Si \(L=[4,8,2,9]\), combien vaut \(L[-1]\) ?

Corrigé : \(L[-1]=9\).

Q4 Somme

Quelle est la somme des éléments de \([1,2,3,4]\) ?

Corrigé : \(1+2+3+4=10\).

Q5 Maximum

Quel est le maximum de \([7,3,12,5]\) ?

Corrigé : le maximum est \(12\).

Q6 Recherche

La valeur \(8\) est-elle dans \([4,8,2,9]\) ?

Corrigé : oui, donc 8 in L vaut True.

Q7 Comptage

Dans \([4,12,7,15,18]\), combien de valeurs sont \(>10\) ?

Corrigé : \(12,15,18\), donc il y en a \(3\).

Q8 Filtrage

Quels sont les nombres pairs de \([5,8,3,10,7,12]\) ?

Corrigé : \([8,10,12]\).

Q9 Complexité

Le parcours complet d’une liste de taille \(n\) est de quel ordre ?

Corrigé : \(O(n)\).

Checklist (avant contrôle)

Je sais faire

Créer une liste et lire ses éléments.
Utiliser les indices correctement.
Calculer la taille avec len.
Parcourir une liste selon deux méthodes.
Calculer somme, moyenne, maximum, minimum.
Tester la présence d’une valeur.
Compter les éléments vérifiant une condition.
Construire une nouvelle liste par filtrage.
Utiliser des sous-listes et un tri simple.

Réflexes 20/20

1) Je choisis tout de suite si je travaille sur les valeurs ou sur les indices.
2) J’initialise proprement : somme, compteur, booléen, max, min.
3) Je teste mon algorithme sur une petite liste avant de conclure.

À bannir : oublier que les indices commencent à 0, confondre valeur et position, utiliser L[0] sans vérifier le contexte, écrire une condition approximative.