Chapitre 5 : Algorithmes sur les listes.

Introduction:

En algorithmique, les listes sont souvent parcourues pour extraire des informations utiles. Par exemple, on peut vouloir compter combien d’éléments répondent à un critère (combien d’animaux dans une liste d’objets variés), ou encore trouver le minimum et le maximum d’une série de valeurs. Ces algorithmes reposent toujours sur le même principe : parcourir la liste élément par élément en mettant à jour un compteur ou une valeur courante.

1. La boucle for:

En Python, la boucle for permet d’itérer sur un conteneur (liste, chaîne de caractères, dictionnaire, ensemble...). À chaque tour de boucle, la variable prend la valeur du prochain élément du conteneur, ce qui permet de traiter facilement chaque élément un par un.

fruits = ["pomme", "banane", "cerise"]

for fruit in fruits:
    print(fruit)

Ici, la variable fruit vaudra successivement "pomme", "banane", puis "cerise". C’est l’outil le plus pratique pour examiner chaque élément d’une collection.

2. Exercice :

A faire dans le cahier

On considère la boucle suivante :

liste = [9, 6, 4, 0]
for machin in liste:
    print(machin)

Quel est le conteneur parcouru par cette boucle ?
Quelles seront successivement les valeurs de la variable machin au cours de l’exécution ?

3. Exercice :

A faire dans le cahier

On considère la boucle suivante :

liste = [9, 6, 4, 0]
for machin in range(len(liste)):
    print(liste[machin])

Quel est le conteneur parcouru par cette boucle ?
Quelles seront successivement les valeurs de la variable machin ?
Quels seront les éléments effectivement affichés par le programme ?

4. Itération sur les éléments ou sur les indices:

En Python, il existe deux façons classiques de parcourir une liste :

for e in liste: : à chaque tour de boucle, la variable prend directement la valeur de l’élément de la liste. → On utilise cette forme lorsqu’on a besoin uniquement des éléments.
for i in range(len(liste)): : à chaque tour de boucle, la variable prend la valeur de l’indice (0, 1, 2, …). On accède alors à l’élément par liste[i]. → On utilise cette forme lorsqu’on a besoin de l’indice (sa position dans la liste).

Exemple :

fruits = ["pomme", "banane", "cerise"]

# Accès direct aux éléments
for e in fruits:
    print(e)

# Accès par les indices
for i in range(len(fruits)):
    print(i, fruits[i])

5. Exercice :

Créer une fonction affiche_liste qui prend une liste de nombres en paramètre et qui les affiche un par un.

nombres = [4, 7, 2, 9, 5, 12, 45, 78, 3, 15, 22, 37, 88, 101, 6, 19, 33, 41, 56, 72, 81, 90, 102, 111, 134, 145, 156, 167, 178, 189, 200, 215, 230, 245, 260, 275, 290, 305, 320, 335] def affiche_liste(liste): # parcourir la liste et afficher chaque élément ... affiche_liste(nombres) # exécute la fonction avec la liste nombres

Tests :

# Tests

Affichage :

Console:

>>>

6. Exercice :

Compléter la fonction somme ci-dessous qui prend une liste de nombres en paramètre et retourne la somme de ces nombres.

Si la liste est vide, elle renverra le string "Erreur, liste vide".

Exemples :

>>> somme([1,2,3,4,5,6])
21
>>> somme([5])
5
>>> somme([])
"Erreur, liste vide"

def somme(liste): if .......... return "Erreur, liste vide" sortie = ...... for element in ....... : sortie = sortie + .... return ......

Tests :

# Tests

Affichage :

Console:

>>>

7. Exercice :

Créer une fonction moyenne_liste qui prend une liste de nombres en paramètre et qui retourne leur moyenne. Si la liste est vide, la fonction devra renvoyer le string "Erreur, liste vide".

def moyenne_liste(liste): # calculer la moyenne des nombres de la liste ...

Tests :

# Tests

Affichage :

Console:

>>>

8. Exercice :

Compléter une fonction Python nommée incrementer_elements qui prend une liste de nombres en entrée et renvoie une nouvelle liste contenant chaque élément augmenté de 1.

def incrementer_elements(liste): nouvelle_liste = [] for .................. : ..................... return ...............

Tests :

# Tests

Affichage :

Console:

>>>

9. Exercice :

Un magasin enregistre le prix de ses articles. Écrire une fonction articles_pas_chers qui prend une liste de prix (nombres positifs) et retourne le nombre d’articles coûtant moins de 10 euros.

Exemple :

>>> articles_pas_chers([5, 12, 8, 20, 3, 15, 7])
4

prix_articles = [5, 12, 8, 20, 3, 15, 7, 9, 11, 14, 6, 2, 30, 4, 17, 19, 23, 5, 7, 8, 12, 6, 9, 10, 25, 3, 4, 18, 22, 13, 7, 5, 6, 8] def articles_pas_chers(prix_articles): compteur = 0 for prix in prix_articles: if ............... : ................. return ............... print(articles_pas_chers(prix_articles))

Tests :

# Tests

Affichage :

Console:

>>>

10. Exercice :

Un professeur a relevé les notes de ses élèves. Écrire une fonction admis qui prend en paramètre une liste de notes (valeurs entières entre 0 et 20) et retourne le nombre d’élèves ayant obtenu au moins 10.

Exemple :

>>> admis([12, 8, 14, 9, 10, 7, 18])
4

notes = [12, 8, 14, 9, 10, 7, 18, 4, 19, 3, 11, 15, 6, 13, 10, 2, 20, 7, 5, 17, 16, 8, 12, 14, 9, 11, 19, 6, 10, 13, 18, 7, 4, 15] def admis(liste_notes): compteur = 0 for note in liste_notes: if ............... : ................. return ............... print(admis(notes))

Tests :

# Tests

Affichage :

Console:

>>>

11. Exercice :

Créer une fonction caracteres qui prend une chaîne de caractères texte en paramètre et qui renvoie une liste contenant tous les caractères de cette chaîne.

def caracteres(texte): # transformer le string en liste de caractères ...

Tests :

# Tests

Affichage :

Console:

>>>

12. Exercice :

Créer une fonction caracteres_uniques qui prend une chaîne de caractères texte en paramètre et qui renvoie une liste contenant les caractères de cette chaîne, chaque caractère n’apparaissant qu’une seule fois.

def caracteres_uniques(texte): resultat = [] for caractere in texte: if .............: resultat.append(.............) return .............

Tests :

# Tests

Affichage :

Console:

>>>

13. Exercice :

Créer une fonction sans_espace qui prend une chaîne de caractères texte en paramètre et qui renvoie une liste contenant les caractères de cette chaîne, mais sans inclure les espaces.

Exemple :

>>> sans_espace("a b c")
['a', 'b', 'c']

def sans_espace(texte): resultat = [] for caractere in texte: if caractere != ...: resultat.append(...) return ...

Tests :

# Tests

Affichage :

Console:

>>>

14. Exercice :

Compléter la fonction trouve_les_mots qui prend une chaîne de caractères texte et qui renvoie une liste contenant les mots (séparés par des espaces).

Exemple :

>>> trouve_les_mots("bonjour le monde")
['bonjour', 'le', 'monde']

def trouve_les_mots(texte): liste = [] mot_a_completer = "" for carac in texte: if carac == " ": # si le caractère est un espace if mot_a_completer != "": # si mot_a_completer est non vide ..................... ..................... # réinitialisation de mot_a_completer else: # le caractère doit être ajouté au mot_a_completer ........................... if ..................: # cas où texte ne finit pas par un espace ..................... return liste

Tests :

# Tests

Affichage :

Console:

>>>

15. Les listes par compréhension

En Python, il existe une manière rapide et élégante de créer des listes : la compréhension de liste.

Elle permet de générer une nouvelle liste à partir d’une autre, en appliquant une règle et éventuellement une condition.

nouvelle_liste = [règle for variable in liste_existante if condition]

Par exemple, pour obtenir les carrés des nombres pairs entre 0 et 9 :

nombres = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
carres_pairs = [n**2 for n in nombres if n % 2 == 0]
print(carres_pairs)   # Résultat : [0, 4, 16, 36, 64]

16. Exercice :

Compléter l’expression ci-dessous pour créer une liste doubles contenant les doubles des nombres de 1 à 10 en utilisant une liste par compréhension.

Exemple attendu :

[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

doubles = [ .... for i in .... ]

Tests :

# Tests

Affichage :

Console:

>>>

17. Exercice :

Un magasin vend 10 articles dont les prix sont les entiers de 1 à 10 euros. Compléter le code ci-dessous pour créer une liste prix_reduits qui contient les prix après une réduction de 20 % (multiplier chaque prix par 0.8), en utilisant une liste par compréhension.

Exemple attendu (arrondi à 1 décimale) :

[0.8, 1.6, 2.4, 3.2, 4.0, 4.8, 5.6, 6.4, 7.2, 8.0]

prix = [1,2,3,4,5,6,7,8,9,10] prix_reduits = [ .... for i in .... ]

Tests :

# Tests

Affichage :

Console:

>>>

18. Recherche du minimum dans une liste :

La recherche du minimum dans une liste consiste à identifier l'élément ayant la plus petite valeur.

Retenir dans les grande lignes que :

On initialise en partant du principe que le candidat pour être le minimum est temporairement le premier élément.
Pour chaque autre élément :
- Si on trouve un élément inférieur à celui actuel, on change de candidat pour être le minimum.

19. Exercice :

Compléter la fonction minimum_liste qui prend une liste de nombres (au moins un élément) et qui retourne le plus petit élément.

def minimum_liste(liste): mini = ......... # à l'initialisation, le plus petit est le premier élément for element in ........ : if ......... : mini = ...... return mini

Tests :

# Tests

Affichage :

Console:

>>>

20. Exercice :

Écrire la fonction maximum_liste qui prend une liste de nombres (au moins un élément) et qui retourne le plus grand élément.

def maximum_liste(liste): ................. # à l'initialisation, le plus grand est le premier élément for ......................... : if .................. : .................. return .......................

Tests :

# Tests

Affichage :

Console:

>>>

21. Exercice :

A faire dans le cahier

Voici une fonction mauvais_maximum_liste qui prétend calculer le maximum d’une liste de nombres. Elle initialise le maximum à 0.

Commence par exécuter la fonction avec la liste donnée et observe le résultat : cela a l’air correct. Puis modifie la liste afin de montrer que cette fonction est en réalité fausse.

Quand tu as trouvé, explique dans ton cahier le problème.

liste = [4, -2, 7, -5, 3] def mauvais_maximum_liste(liste): maxi = 0 # Mauvaise initialisation for element in liste: if element > maxi: maxi = element return maxi print(mauvais_maximum_liste(liste))

Tests :

Affichage :

Console:

>>>