Exercices#

Les types construits

Mode d’emploi

Niveau : ★ échauffement, ★★ classique (niveau bac), ★★★ défi ; les coups de pouce et les corrigés se déplient sous chaque exercice.
▶ À programmer et tester en Python. Le symbole >>> figure une saisie dans la console. Les exercices de lecture de trace sont à faire sans machine d’abord, puis à vérifier.
Réflexe fil rouge : dès qu’on partage ou copie des données mutables (tableau, dictionnaire), dessinez les noms, les objets et les flèches.
Le badge au-delà du programme signale un point hors programme (utile, non exigible).
Usage de l’IA, indiqué sur chaque exercice : aucune ; en appui (déboguer, reformuler, vérifier ; la réponse finale est écrite et comprise par vous) ; l’exercice s’appuie sur une réponse d’IA. Voir la charte d’usage de l’IA.

P-uplets (`tuple`)#

★ Exercice 1 — Lecture de trace #

• essentiel

Sans machine, donner la valeur de chaque expression. t = (5, 10, 15, 20, 25)

t[0] b) t[-1] c) t[1:3] d) len(t) e) 15 in t f) t[-2]

Coup de pouce

Les indices commencent à 0 ; un indice négatif compte à partir de la fin (-1 désigne le dernier élément). Dans une tranche t[a:b], l’indice b est exclu.

Corrigé

Remarque

Plusieurs écritures sont souvent possibles : on donne une version simple.

Les indices vont de 0 à 4 (ou de -5 à -1 en partant de la fin) ; la tranche t[1:3] prend les indices 1 et 2. a) 5 b) 25 c) (10, 15) d) 5 e) True f) 20.

▷ Erreur fréquente. inclure l’élément d’indice 3 dans t[1:3] : comme pour range, la borne de droite est exclue.

★ Exercice 2 — Vrai ou faux ? #

Justifier en une ligne (ou par un contre-exemple).

(7) est un p-uplet à un élément.
On peut écrire t[0] = 3 pour changer le premier élément d’un p-uplet.
Un p-uplet peut contenir des éléments de types différents.
() est un p-uplet vide valide.

Coup de pouce

Relire la sous-section « Création : c’est la virgule qui compte » du cours, puis tester chaque affirmation dans la console (par exemple type((7))).

Corrigé

1. Faux : (7) vaut l’entier 7 ; le singleton s’écrit (7,). 2. Faux : un p-uplet est immuable, l’affectation lève une TypeError. 3. Vrai : (1, "deux", 3.0) est valide. 4. Vrai : () est le p-uplet vide.

▷ Erreur fréquente. croire que les parenthèses font le p-uplet : c’est la virgule. (7) est un simple entier entre parenthèses.

★★ Exercice 3 — Une fonction, plusieurs résultats #

▶ Écrire une fonction somme_moyenne(t) qui renvoie le p-uplet (somme, moyenne) des éléments d’un tableau de nombres non vide. On récupérera le résultat par s, m = somme_moyenne([…]).

Coup de pouce

Deux étapes : un accumulateur pour la somme, puis la moyenne à partir de la somme et de len(t). Comment une fonction renvoie-t-elle deux valeurs à la fois ?

Corrigé

Un accumulateur donne la somme ; la moyenne s’en déduit. Pour renvoyer deux valeurs, on renvoie le p-uplet s, s / len(t), que l’appelant déballe avec s, m = ....

def somme_moyenne(t):
    s = 0
    for x in t:
        s = s + x
    return s, s / len(t)     # renvoie le p-uplet (somme, moyenne)

★★ Exercice 4 — Conversion de durée #

▶ Écrire convertir(n) qui, à partir d’un nombre de secondes n, renvoie le p-uplet (heures, minutes, secondes).

>>> convertir(3661)
(1, 1, 1)

Coup de pouce

Combien de secondes dans une heure ? dans une minute ? Penser au quotient entier // et au reste %.

Corrigé

Une heure fait \(3600\) secondes : le quotient n // 3600 donne les heures ; dans le reste n % 3600, le quotient par \(60\) donne les minutes, et le reste par \(60\) les secondes.

def convertir(n):
    heures = n // 3600
    minutes = (n % 3600) // 60
    secondes = n % 60
    return heures, minutes, secondes

★★ Exercice 5 — Permutation circulaire #

Soit a, b, c = 1, 2, 3. Écrire les instructions (avec une variable temporaire) qui font « tourner » les valeurs de sorte qu’ensuite a vaille 2, b vaille 3 et c vaille 1. Vérifier en console.

Coup de pouce

Quelle valeur serait perdue si l’on écrivait d’abord a = b ? C’est elle qu’il faut mettre de côté.

Corrigé

On sauvegarde a dans une variable temporaire, puis on décale les valeurs :

temp = a         # temp vaut 1 (l'ancien a)
a = b            # a vaut 2
b = c            # b vaut 3
c = temp         # c vaut 1

Tableaux (`list`) : accès, modification, parcours#

★ Exercice 6 — Lecture de trace #

• essentiel

Sans machine, donner l’état du tableau après chaque ligne.

t = [4, 8, 15, 16, 23]
t[0] = 42
t[-1] = 0
x = t[1:3]
n = len(t)

Que valent t, x et n à la fin ?

Coup de pouce

Écrire le contenu de t après chaque ligne. La tranche x est prise après les deux modifications, et t[1:3] s’arrête avant l’indice 3.

Corrigé

Après exécution : t = [42, 8, 15, 16, 0], x = [8, 15] (la tranche t[1:3], prise avant la fin), n = 5.

★ Exercice 7 — Fabriquer des tableaux #

▶ Sans les écrire à la main, produire :

le tableau des entiers de 0 à 9 ;
le tableau [10, 20, 30, 40, 50] ;
un tableau de 8 cases valant toutes 0.

Coup de pouce

Pour a) et b), une compréhension sur un range bien choisi (avec un pas pour b). Pour c), penser à la répétition *, déjà vue avec les chaînes.

Corrigé

Compréhension sur un range (de 10 à 50 inclus, avec un pas de 10, d’où la borne 51), et répétition * pour le tableau de zéros.

a = [i for i in range(10)]            # [0, 1, ..., 9]
b = [i for i in range(10, 51, 10)]    # [10, 20, 30, 40, 50]
c = [0] * 8                           # huit zeros

★★ Exercice 8 — Parcours : les grands classiques #

• essentiel

▶ Écrire, sans utiliser les fonctions sum, max, min, les fonctions suivantes (tableau de nombres non vide) :

somme(t) : la somme des éléments ;
maximum(t) : le plus grand élément ;
moyenne(t) : la moyenne ;
nb_positifs(t) : le nombre d’éléments strictement positifs.

Coup de pouce

Somme et comptage : un accumulateur initialisé avant la boucle. Maximum : avec quelle valeur initialiser le « meilleur jusqu’ici », sachant que le tableau est non vide ?

Coup de pouce 2 (début de solution)

def maximum(t):
m = t[0]
for x in t:
puis comparer x à m.

Corrigé

Somme et comptage : accumulateur initialisé à 0 avant la boucle. Maximum : on part d’un élément qui existe, t[0], et on le remplace dès qu’on trouve plus grand. La moyenne réutilise somme.

def somme(t):
    s = 0
    for x in t:
        s = s + x
    return s

def maximum(t):
    m = t[0]
    for x in t:
        if x > m:
            m = x
    return m

def moyenne(t):
    return somme(t) / len(t)

def nb_positifs(t):
    c = 0
    for x in t:
        if x > 0:
            c = c + 1
    return c

▷ Erreur fréquente. initialiser le maximum à 0 : pour [-5, -2, -9], la fonction renverrait 0, qui n’est même pas dans le tableau.

★★ Exercice 9 — Modifier sur place #

▶ Écrire des fonctions qui modifient le tableau reçu (sans en renvoyer un nouveau) :

ajouter_un(t) : ajoute 1 à chaque élément ;
plafonner(t, m) : remplace par m tout élément supérieur à m.

Coup de pouce

Pour modifier une case, il faut connaître sa position : parcourir par indice (for i in range(len(t))) plutôt que par élément.

Corrigé

On parcourt par indice (indispensable pour modifier).

def ajouter_un(t):
    for i in range(len(t)):
        t[i] = t[i] + 1

def plafonner(t, m):
    for i in range(len(t)):
        if t[i] > m:
            t[i] = m

▷ Erreur fréquente. écrire for x in t: puis x = x + 1 : on modifie la variable x, pas la case du tableau, qui reste inchangé.

★★ Exercice 10 — Chercher et compter #

▶ Écrire sans utiliser les méthodes count/index :

occurrences(t, x) : le nombre de fois où x apparaît dans t ;
est_present(t, x) : True si x est dans t, sinon False ;
premier_indice(t, x) : l’indice de la première occurrence de x, ou -1 s’il est absent.

Coup de pouce

Pour premier_indice, parcourir par indice et sortir avec return dès qu’on trouve x. Que renvoyer si la boucle se termine sans avoir rien trouvé ?

Corrigé

Compteur pour occurrences ; pour les deux recherches, on sort par return dès que x est trouvé, et l’on ne conclut à l’absence qu’après la boucle.

def occurrences(t, x):
    c = 0
    for v in t:
        if v == x:
            c = c + 1
    return c

def est_present(t, x):
    for v in t:
        if v == x:
            return True
    return False

def premier_indice(t, x):
    for i in range(len(t)):
        if t[i] == x:
            return i
    return -1

▷ Erreur fréquente. ajouter else: return False dans la boucle de est_present : la fonction conclut dès le premier élément examiné.

★★ Exercice 11 — Renverser sans `reverse` #

▶ Écrire renverser(t) qui renvoie un nouveau tableau contenant les éléments de t en ordre inverse, sans utiliser la méthode reverse ni la tranche [::-1].

Coup de pouce

Partir d’un tableau vide et le remplir avec append : dans quel ordre faut-il parcourir les indices de t ?

Corrigé

On construit un nouveau tableau en parcourant t de la fin vers le début.

def renverser(t):
    r = []
    for i in range(len(t) - 1, -1, -1):
        r.append(t[i])
    return r

Autre méthode : une fois la compréhension vue, le même parcours des indices à l’envers s’écrit en une ligne : return [t[i] for i in range(len(t) - 1, -1, -1)].

★ Exercice 12 — Ajouter et retirer au-delà du programme #

▶ Partant de t = [3, 1, 4, 1, 5], donner une instruction pour chaque étape (dans l’ordre), et le contenu de t après chacune :

ajouter 9 à la fin (méthode append) ;
ajouter 0 en tête, par concaténation ;
retirer (et récupérer) le dernier élément ;
retirer (et récupérer) l’élément d’indice 2 ;
ne garder que les trois premiers éléments, à l’aide d’une tranche.

Coup de pouce

Les méthodes append et pop sont présentées dans la sous-section « Méthodes des tableaux » du cours. Recalculer les indices après chaque étape : le tableau change à chaque ligne.

Corrigé

Avec t = [3, 1, 4, 1, 5] :

t.append(9)      # a) [3, 1, 4, 1, 5, 9]
t = [0] + t      # b) [0, 3, 1, 4, 1, 5, 9] (nouveau tableau)
x = t.pop()      # c) x vaut 9 ; t -> [0, 3, 1, 4, 1, 5]
y = t.pop(2)     # d) y vaut 1 ; t -> [0, 3, 4, 1, 5]
t = t[:3]        # e) [0, 3, 4]

Construction par compréhension#

★ Exercice 13 — Lecture de trace #

Sans machine, donner le tableau produit.

[n + 1 for n in range(5)]
[2 ** k for k in range(5)]
[c for c in "python" if c in "aeiouy"]
[n for n in range(30) if n % 5 == 0]

Coup de pouce

Lire la compréhension comme une boucle : pour chaque valeur de la variable, si la condition est vraie, on ajoute l’expression au tableau. Écrire d’abord la liste des valeurs prises par la variable.

Corrigé

On écrit les valeurs de la variable, on garde celles qui vérifient la condition, on calcule l’expression. a) [1, 2, 3, 4, 5] b) [1, 2, 4, 8, 16] c) [’y’, ’o’] d) [0, 5, 10, 15, 20, 25].

★★ Exercice 14 — Écrire des compréhensions #

• essentiel

Donner en une ligne (compréhension) le tableau :

des cubes de 0 à 6 ;
des multiples de 3 strictement inférieurs à 40 ;
des longueurs des mots de ["chat", "python", "nsi"] (on pourra utiliser len) ;
des entiers de 1 à 50 qui sont des carrés parfaits.

Coup de pouce

Forme générale : [expression for variable in ... if condition]. Pour la 4, plutôt que de tester chaque entier, peut-on fabriquer directement les carrés ? Jusqu’où faire varier la variable ?

Corrigé

[k ** 3 for k in range(7)]                 # 1. cubes de 0 a 6
[n for n in range(40) if n % 3 == 0]       # 2. multiples de 3 < 40
[len(mot) for mot in ["chat", "python", "nsi"]]   # 3. longueurs
[k * k for k in range(1, 8)]               # 4. carres parfaits de 1 a 50

Pour 4, on fabrique directement les carrés plutôt que de tester chaque entier : \(7 \times 7 = 49 \leqslant 50\) mais \(8 \times 8 = 64 > 50\), donc k va de 1 à 7. Si l’on ne veut pas chercher la borne, on filtre : [k * k for k in range(1, 51) if k * k <= 50].

★★ Exercice 15 — De la boucle à la compréhension #

Réécrire chacun de ces codes en une compréhension.

# (a)                              # (b)
r = []                             r = []
for x in [5, -2, 7, -8, 3]:        for mot in ["le", "chat", "dort"]:
    if x > 0:                          r.append(mot[0])
        r.append(x)

Coup de pouce

Repérer dans chaque boucle trois morceaux : ce qui est ajouté (dans append), la ligne for, et la condition éventuelle. Dans quel ordre les placer entre crochets ?

Corrigé

Ce qui est ajouté par append vient en tête, puis la ligne for, puis la condition éventuelle.

r = [x for x in [5, -2, 7, -8, 3] if x > 0]   # (a) -> [5, 7, 3]
r = [mot[0] for mot in ["le", "chat", "dort"]]   # (b) -> ['l', 'c', 'd']

★★ Exercice 16 — Nettoyer une phrase #

▶ À l’aide d’une compréhension, écrire voyelles(phrase) qui renvoie le tableau des voyelles de phrase (minuscules ou majuscules), dans l’ordre. Puis en déduire nb_voyelles(phrase).

>>> voyelles("Bonjour NSI")
['o', 'o', 'u', 'I']

Coup de pouce

Le filtre porte sur chaque caractère : est-il dans "aeiouyAEIOUY" ? Pour nb_voyelles, réutiliser voyelles.

Corrigé

Compréhension avec filtre : on garde chaque caractère c qui est dans la chaîne des voyelles ; nb_voyelles n’est que la longueur de ce tableau.

def voyelles(phrase):
    return [c for c in phrase if c in "aeiouyAEIOUY"]

def nb_voyelles(phrase):
    return len(voyelles(phrase))

Autre méthode : la même idée avec une boucle et append (c’est exactement ce que la compréhension condense).

def voyelles(phrase):
    resultat = []
    for c in phrase:
        if c in "aeiouyAEIOUY":
            resultat.append(c)
    return resultat

Matrices (tableaux de tableaux)#

★ Exercice 17 — Se repérer dans une matrice #

On pose M = [[1, 2, 3], [4, 5, 6], [7, 8, 9]].

Que valent M[0], M[2][1], M[1][0] ?
Que valent len(M) et len(M[0]) ? Que représentent-ils ?
Écrire l’instruction qui met la case centrale à 0.

Coup de pouce

M[i] est la ligne d’indice i (elle-même un tableau) ; M[i][j] est la case d’indice j de cette ligne. Lignes et colonnes sont numérotées à partir de 0.

Corrigé

On choisit d’abord la ligne (premier indice), puis la case dans la ligne (second indice). a) M[0] = [1, 2, 3], M[2][1] = 8, M[1][0] = 4. b) len(M) = 3 (nombre de lignes), len(M[0]) = 3 (nombre de colonnes). c) M[1][1] = 0.

★★ Exercice 18 — Parcourir une matrice #

• essentiel

▶ Pour une matrice M de nombres (n lignes, p colonnes), écrire :

somme_matrice(M) : la somme de toutes les cases ;
maximum_matrice(M) : la plus grande case ;
somme_ligne(M, i) : la somme de la ligne d’indice i.

Coup de pouce

Deux boucles imbriquées : l’une sur les lignes, l’autre sur les cases de la ligne. Pour le maximum, initialiser avec une case qui existe. Pour somme_ligne, une seule boucle suffit.

Coup de pouce 2 (début de solution)

def somme_matrice(M):
s = 0
for ligne in M:
for x in ligne:

Corrigé

Deux boucles imbriquées (les lignes, puis les cases de chaque ligne) avec un accumulateur ou un « meilleur jusqu’ici » initialisé avec une case existante, M[0][0] ; une seule boucle pour une ligne donnée.

def somme_matrice(M):
    s = 0
    for ligne in M:
        for x in ligne:
            s = s + x
    return s

def maximum_matrice(M):
    m = M[0][0]
    for ligne in M:
        for x in ligne:
            if x > m:
                m = x
    return m

def somme_ligne(M, i):
    s = 0
    for x in M[i]:
        s = s + x
    return s

Autre méthode pour somme_matrice, par indices : for i in range(len(M)): puis for j in range(len(M[i])): et s = s + M[i][j]. Elle est indispensable dès qu’on a besoin de la position de la case.

★★ Exercice 19 — Créer une grille — et le piège #

Lecture de trace (sans machine). On exécute :
```
g = [[0] * 3] * 2
g[0][0] = 1
```
Donner la valeur de g. Est-ce le résultat attendu ? Expliquer avec un schéma du fil rouge (noms, objets, flèches).
▶ Écrire grille_zeros(n, p) qui renvoie correctement une matrice de n lignes et p colonnes remplie de 0, en utilisant une compréhension. Vérifier que modifier une case n’en modifie qu’une.

Coup de pouce

Question 1 : * 2 recopie-t-il la ligne, ou seulement la flèche vers la ligne ? Question 2 : chaque ligne doit être un objet neuf ; quelle construction réévalue [0] * p pour chaque ligne ?

Corrigé

1. g vaut [[1, 0, 0], [1, 0, 0]] : pas le résultat attendu ! Avec *, les deux « lignes » sont le même objet (deux flèches vers un seul tableau) ; modifier g[0][0] modifie donc aussi g[1].

2. Avec une compréhension, chaque tour crée une ligne neuve :

def grille_zeros(n, p):
    return [[0 for j in range(p)] for i in range(n)]

g = grille_zeros(2, 3)
g[0][0] = 1        # g vaut [[1, 0, 0], [0, 0, 0]] : une seule case changee

Autre méthode : return [[0] * p for i in range(n)]. Chaque tour réévalue [0] * p, donc crée une ligne neuve.

★★★ Exercice 20 — Transposée #

≈ 15 min

▶ Écrire transposee(M) qui renvoie la transposée d’une matrice n\(\times\)p (les lignes deviennent les colonnes), sans modifier M.

>>> transposee([[1, 2, 3], [4, 5, 6]])
[[1, 4], [2, 5], [3, 6]]

Coup de pouce

Si M a n lignes et p colonnes, combien de lignes et de colonnes a sa transposée ? Comparer la case (i, j) de la transposée avec une case de M.

Coup de pouce 2 (début de solution)

n = len(M)
p = len(M[0])
puis construire p lignes de n cases chacune, par compréhension ou avec deux boucles.

Corrigé

La transposée a p lignes et n colonnes : la case (j, i) du résultat est M[i][j].

def transposee(M):
    n = len(M)
    p = len(M[0])
    return [[M[i][j] for i in range(n)] for j in range(p)]

Autre méthode : avec deux boucles, on construit la transposée ligne par ligne ; sa ligne j est la colonne j de M.

def transposee(M):
    resultat = []
    for j in range(len(M[0])):
        ligne = []                  # la colonne j de M
        for i in range(len(M)):
            ligne.append(M[i][j])
        resultat.append(ligne)
    return resultat

★★★ Exercice 21 — Traitement d’image #

≈ 20 min

Une image en niveaux de gris est une matrice d’entiers de 0 à 255.

▶ negatif(image) : modifie l’image en remplaçant chaque pixel p par 255 - p.
▶ symetrie_horizontale(image) : renvoie une nouvelle image, miroir gauche-droite (chaque ligne est renversée).

Coup de pouce

1 : on modifie sur place, donc on parcourt par indices (ligne i, colonne j). 2 : chaque ligne se renverse comme dans l’exercice « Renverser sans reverse » ; on construit l’image résultat ligne par ligne.

Coup de pouce 2 (début de solution)

def negatif(image):
for i in range(len(image)):
for j in range(len(image[i])):

Corrigé

def negatif(image):                     # modifie sur place
    for i in range(len(image)):
        for j in range(len(image[0])):
            image[i][j] = 255 - image[i][j]

def symetrie_horizontale(image):        # renvoie une NOUVELLE image
    nouvelle = []
    for ligne in image:
        p = len(ligne)
        nouvelle.append([ligne[p - 1 - j] for j in range(p)])
    return nouvelle

Dictionnaires (`dict`)#

★ Exercice 22 — Lecture de trace #

• essentiel

On part de d = {"a": 1, "b": 2}. Donner l’état de d (ou la valeur) après chaque ligne, dans l’ordre.

d["c"] = 3
d["a"] = 10
del d["b"]
x = "c" in d
y = 3 in d
z = len(d)

Coup de pouce

Affecter une clé absente l’ajoute ; affecter une clé présente remplace sa valeur. Le mot-clé in teste-t-il les clés ou les valeurs ?

Corrigé

Dans l’ordre : d = {"a": 1, "b": 2, "c": 3}, puis {"a": 10, "b": 2, "c": 3}, puis {"a": 10, "c": 3}. Ensuite x = True ("c" est une clé), y = False (in teste les clés, pas les valeurs), z = 2.

▷ Erreur fréquente. croire que 3 in d cherche parmi les valeurs : in ne regarde que les clés.

★★ Exercice 23 — Parcourir un dictionnaire #

On dispose de notes = {"Alice": 14, "Bob": 9, "Chloe": 17}.

▶ Écrire moyenne(notes) qui renvoie la moyenne des valeurs.
▶ Écrire admis(notes, seuil) qui renvoie le tableau des prénoms dont la note est \(\geqslant\) seuil.
▶ Écrire meilleur(notes) qui renvoie le prénom ayant la meilleure note.

Coup de pouce

for prenom in notes: parcourt les clés ; la note est notes[prenom]. Pour meilleur, il faut retenir le prénom du meilleur jusqu’ici, pas seulement sa note.

Corrigé

def moyenne(notes):
    total = 0
    for note in notes.values():
        total = total + note
    return total / len(notes)

def admis(notes, seuil):
    return [prenom for prenom in notes if notes[prenom] >= seuil]

def meilleur(notes):
    champion = None
    meilleure_note = -1             # toute note est superieure a -1
    for prenom in notes:
        if notes[prenom] > meilleure_note:
            meilleure_note = notes[prenom]
            champion = prenom
    return champion

Pour meilleur, c’est une recherche de maximum où l’on retient aussi le prénom du champion. On part ici d’une note fictive -1 (une sentinelle), valable seulement parce que toutes les notes sont positives ; le chapitre Algorithmique : le parcours séquentiel préférera partir d’un élément existant, ce qui marche dans tous les cas.

★ Exercice 24 — Compter des votes : code à trous #

Le tableau votes contient le prénom choisi par chaque votant. Recopier et compléter les pointillés pour que la fonction renvoie un dictionnaire associant à chaque prénom son nombre de voix.

def compter_votes(votes):
    resultat = ......
    for prenom in ......:
        if prenom ...... resultat:
            resultat[prenom] = ......
        else:
            resultat[prenom] = ......
    return resultat

>>> compter_votes(["Ada", "Léo", "Ada"])
{'Ada': 2, 'Léo': 1}

Coup de pouce

Le résultat part vide. Pour chaque prénom : s’il est déjà une clé, on augmente son compte ; sinon, on le crée. Avec quelle valeur ?

Corrigé

def compter_votes(votes):
    resultat = {}
    for prenom in votes:
        if prenom in resultat:
            resultat[prenom] = resultat[prenom] + 1
        else:
            resultat[prenom] = 1
    return resultat

C’est le schéma du compteur par dictionnaire du cours : une clé absente est créée avec la valeur 1, une clé présente voit sa valeur augmenter de 1.

★★ Exercice 25 — Comptage d’occurrences #

• essentiel

▶ Écrire compter_lettres(mot) qui renvoie un dictionnaire associant à chaque lettre de mot son nombre d’occurrences.

>>> compter_lettres("banane")
{'b': 1, 'a': 2, 'n': 2, 'e': 1}

Coup de pouce

Même schéma que l’exercice précédent : qu’est-ce qui joue ici le rôle de clé ? Que faire quand on rencontre une lettre pour la première fois ?

Corrigé

Même schéma que « Compter des votes » : chaque lettre est une clé ; à la première rencontre, on la crée avec la valeur 1, ensuite on augmente sa valeur.

def compter_lettres(mot):
    compteur = {}
    for lettre in mot:
        if lettre in compteur:
            compteur[lettre] = compteur[lettre] + 1
        else:
            compteur[lettre] = 1
    return compteur

▷ Erreur fréquente. écrire seulement compteur[lettre] = compteur[lettre] + 1, sans tester la présence de la clé : à la première lettre, la clé n’existe pas encore et Python lève une KeyError.

★★ Exercice 26 — Inverser un dictionnaire #

▶ Écrire inverser(d) qui échange clés et valeurs (on suppose les valeurs uniques).

>>> inverser({"a": 1, "b": 2})
{1: 'a', 2: 'b'}

Question : pourquoi cela ne marcherait-il pas si deux clés partageaient la même valeur ?

Coup de pouce

Remplir un dictionnaire neuf en parcourant les clés de d : que devient la clé, que devient la valeur ? Pour la question : que se passe-t-il quand on affecte deux fois la même clé ?

Corrigé

On remplit un dictionnaire neuf en parcourant les couples (clé, valeur) de d : chaque valeur devient une clé, associée à l’ancienne clé.

def inverser(d):
    resultat = {}
    for cle, valeur in d.items():
        resultat[valeur] = cle
    return resultat

Si deux clés partageaient la même valeur, cette valeur deviendrait une clé unique dans le résultat : la seconde écraserait la première, et une information serait perdue.

★★★ Exercice 27 — Un mini-annuaire à clés composées #

≈ 15 min

On enregistre les notes d’une classe dans un dictionnaire dont la clé est le p-uplet (élève, matière).

releve = {("Ada", "NSI"): 18, ("Ada", "Maths"): 15, ("Léo", "NSI"): 12}

Donner l’instruction qui lit la note d’Ada en Maths.
▶ Écrire moyenne_eleve(releve, eleve) qui renvoie la moyenne d’un élève sur toutes ses matières.
Pourquoi la clé est-elle un p-uplet et non un tableau ? (une phrase, fil rouge)

Coup de pouce

Question 2 : parcourir les clés (nom, matiere) du relevé et ne garder que celles de l’élève cherché ; il faut une somme et un compteur. Question 3 : relire la règle du cours sur les clés de dictionnaire.

Coup de pouce 2 (début de solution)

total = 0
n = 0
for (nom, matiere) in releve:
if nom == eleve:

Corrigé

1. releve[("Ada", "Maths")] vaut 15.

2.

def moyenne_eleve(releve, eleve):
    total = 0
    n = 0
    for (nom, matiere) in releve:      # chaque cle est un couple
        if nom == eleve:
            total = total + releve[(nom, matiere)]
            n = n + 1
    return total / n

3. La clé doit être immuable : un p-uplet ne peut pas changer après coup, un tableau si — ce qui empêcherait de retrouver la valeur.

Le fil rouge à l’épreuve : références, alias, copie#

★★ Exercice 28 — Alias ou copie ? (lecture de trace) #

• essentiel

Sans machine, prédire l’affichage. Pour chaque cas, dire s’il y a un ou deux objets en mémoire.

# (a)                     # (b)
a = [1, 2, 3]             a = [1, 2, 3]
b = a                     b = [x for x in a]
b.append(4)               b.append(4)
print(a, b)               print(a, b)

Coup de pouce

Dessiner, pour chaque cas, les noms et les flèches après la 2^e ligne : la compréhension [x for x in a] fabrique-t-elle un nouvel objet ?

Corrigé

(a) affiche [1, 2, 3, 4] [1, 2, 3, 4] : b = a crée un alias, un seul objet pour deux noms. (b) affiche [1, 2, 3] [1, 2, 3, 4] : la compréhension [x for x in a] crée un nouvel objet, deux objets indépendants.

★★ Exercice 29 — Effet de bord d’une fonction #

Sans machine, prédire l’affichage et l’expliquer.

def ajoute_zero(t):
    t.append(0)

notes = [12, 15]
ajoute_zero(notes)
print(notes)

Question : comment récrire ajoute_zero pour qu’elle ne modifie pas le tableau reçu mais en renvoie un nouveau ?

Coup de pouce

Pendant l’appel, le paramètre t et la variable notes sont-ils deux objets, ou deux étiquettes sur le même objet ? Pour la question, commencer par fabriquer une copie.

Corrigé

Affiche [12, 15, 0]. Le paramètre t et la variable notes pointent vers le même tableau : la méthode append le modifie, donc le changement est visible à l’extérieur (effet de bord). Pour ne pas modifier l’original, on travaille sur une copie :

def ajoute_zero(t):
    nouveau = [x for x in t]   # copie independante
    nouveau.append(0)
    return nouveau

★★★ Exercice 30 — Le piège en dictionnaire #

≈ 10 min

Sans machine, prédire l’affichage.

modele = {"vie": 100, "sac": []}
joueur1 = modele
joueur2 = {cle: modele[cle] for cle in modele}
joueur1["vie"] = 50
joueur2["sac"].append("clef")
print(modele["vie"], modele["sac"])

au-delà du programme

Coup de pouce

La compréhension copie le premier niveau seulement : la valeur associée à "sac" est-elle recopiée, ou seulement la flèche vers ce tableau ?

Coup de pouce 2 (début de solution)

Dessiner trois noms modele, joueur1, joueur2 : joueur1 pointe vers le même dictionnaire que modele ; joueur2 pointe vers un nouveau dictionnaire. Suivre ensuite chaque flèche lors des deux modifications.

Corrigé

Affiche 50 [’clef’].

joueur1 = modele est un alias : joueur1["vie"] = 50 change bien modele["vie"].
La compréhension crée bien un nouveau dictionnaire joueur2, mais elle ne copie que le premier niveau : la valeur associée à "sac" (le tableau) reste partagée : joueur2["sac"].append("clef") modifie donc aussi modele["sac"]. Il faudrait une copie profonde, qui recopie aussi le tableau : joueur2["sac"] = [x for x in modele["sac"]].

Synthèse : petits problèmes#

★★ Exercice 31 — Carnet de notes #

Un carnet associe à chaque élève le tableau de ses notes :

carnet = {"Alice": [12, 15, 9], "Bob": [8, 14]}

▶ ajouter_note(carnet, eleve, note) : ajoute une note à un élève (créer l’élève s’il est absent).
▶ moyenne_eleve(carnet, eleve) : la moyenne d’un élève.
▶ moyennes(carnet) : un dictionnaire prénom \(\to\) moyenne.

Coup de pouce

Question 1 : tester eleve in carnet avant d’ajouter. Question 3 : réutiliser moyenne_eleve pour chaque clé du carnet.

Coup de pouce 2 (début de solution)

def ajouter_note(carnet, eleve, note):
if eleve not in carnet:
carnet[eleve] = []

Corrigé

Pour ajouter, on crée l’élève absent avec un tableau d’une note, sinon on ajoute la note à son tableau ; la moyenne est un accumulateur sur ce tableau ; moyennes réutilise moyenne_eleve pour chaque clé.

def ajouter_note(carnet, eleve, note):
    if eleve in carnet:
        carnet[eleve].append(note)
    else:
        carnet[eleve] = [note]

def moyenne_eleve(carnet, eleve):
    notes = carnet[eleve]
    total = 0
    for note in notes:
        total = total + note
    return total / len(notes)

def moyennes(carnet):
    resultat = {}
    for eleve in carnet:
        resultat[eleve] = moyenne_eleve(carnet, eleve)
    return resultat

★★★ Exercice 32 — Panier d’une boutique #

≈ 20 min

Un panier est un dictionnaire produit\(\to\)quantité, et prix un dictionnaire produit\(\to\)prix unitaire.

panier = {"pomme": 3, "pain": 2}
prix   = {"pomme": 0.5, "pain": 1.2, "lait": 0.9}

▶ total(panier, prix) : le montant total du panier.
▶ ajouter(panier, produit, q) : ajoute q unités (cumule si le produit y est déjà).
▶ article_le_plus_cher(panier, prix) : le nom du produit du panier dont le sous-total est le plus élevé.

Coup de pouce

Sous-total d’un produit = quantité \(\times\) prix unitaire. Question 3 : c’est une recherche de maximum, mais on retient le nom du produit en plus de son sous-total.

Coup de pouce 2 (début de solution)

def total(panier, prix):
s = 0
for produit in panier:

Corrigé

def total(panier, prix):
    s = 0
    for produit, q in panier.items():
        s = s + q * prix[produit]
    return s

def ajouter(panier, produit, q):
    if produit in panier:
        panier[produit] = panier[produit] + q
    else:
        panier[produit] = q

def article_le_plus_cher(panier, prix):
    champion = None
    meilleur_sous_total = -1
    for produit, q in panier.items():
        sous_total = q * prix[produit]
        if sous_total > meilleur_sous_total:
            meilleur_sous_total = sous_total
            champion = produit
    return champion

Comme pour meilleur (exercice « Parcourir un dictionnaire »), le sous-total fictif -1 est une sentinelle, valable parce que les sous-totaux sont positifs.

★★★ Exercice 33 — Vers le bac — le jeu du démineur (grille) #

≈ 20 min

▶ On représente un champ de mines par une matrice de 0 et de 1 (1 = mine). Écrire compter_voisines(champ, i, j) qui renvoie le nombre de mines dans les (au plus 8) cases voisines de la case (i, j). Attention aux bords : ne pas sortir de la grille.

>>> champ = [[0, 1, 0], [1, 0, 0], [0, 0, 1]]
>>> compter_voisines(champ, 1, 1)
3

Coup de pouce

Une voisine de (i, j) s’écrit (i + di, j + dj) avec di et dj pris dans -1, 0, 1. Quel couple (di, dj) faut-il écarter ? Quand une case (a, b) est-elle dans la grille ?

Coup de pouce 2 (début de solution)

for di in [-1, 0, 1]:
for dj in [-1, 0, 1]:
a, b = i + di, j + dj

Corrigé

On balaie les 9 cases (a, b) du carré \(3 \times 3\) centré sur (i, j) ; on ne compte une case que si elle est dans la grille et que ce n’est pas la case (i, j) elle-même.

def compter_voisines(champ, i, j):
    n = len(champ)
    p = len(champ[0])
    total = 0
    for di in [-1, 0, 1]:
        for dj in [-1, 0, 1]:
            a = i + di
            b = j + dj
            dans_grille = a >= 0 and a < n and b >= 0 and b < p
            if dans_grille and not (di == 0 and dj == 0):
                total = total + champ[a][b]
    return total

★★ Exercice 34 — Une copie selon un assistant d’IA #

Un élève demande à un assistant d’IA : « Écris une fonction Python qui renvoie un nouveau tableau contenant le double de chaque note, sans modifier le tableau d’origine. » Voici la réponse obtenue.

def doubler(t):
    copie = t                 # copie du tableau d'origine
    for i in range(len(copie)):
        copie[i] = copie[i] * 2
    return copie

« On commence par copier le tableau dans copie, puis on double chaque case de la copie et on la renvoie : le tableau t passé en argument n’est pas touché. »

On exécute ensuite :

notes = [12, 15, 9]
doubles = doubler(notes)
print(doubles, notes)

La réponse est-elle correcte ? Prédire l’affichage (avec le dessin noms / flèches / objets), puis ▶ vérifier.
Localiser et corriger l’erreur.
Quelle vérification simple, faite avant de faire confiance à la réponse, aurait suffi à détecter l’erreur ?

Coup de pouce

Dessiner les noms t et copie juste après la première ligne de la fonction : combien d’objets tableau y a-t-il ?

Corrigé

1. Non. L’affichage est [24, 30, 18] [24, 30, 18] : le tableau d’origine notes a été modifié, contrairement à ce qui était demandé. Dessin : notes, puis t et copie pendant l’appel, puis doubles au retour ; ces quatre noms pointent tous vers un seul tableau.

2. L’erreur est la ligne copie = t : elle ne copie rien, elle crée un alias (deux noms qui pointent vers le même tableau, fil rouge du cours). Modifier copie[i], c’est modifier t. Il faut construire un nouvel objet, copie = [x for x in t] (ou t[:]) :

def doubler(t):
    copie = [x for x in t]    # NOUVEL objet, independant de t
    for i in range(len(copie)):
        copie[i] = copie[i] * 2
    return copie

notes = [12, 15, 9]
doubles = doubler(notes)
print(doubles, notes)         # [24, 30, 18] [12, 15, 9]

3. Afficher le tableau d’origine après l’appel : c’est exactement ce que la demande promettait (« sans modifier ») et donc la première chose à tester. Un commentaire qui dit « copie » ne prouve pas qu’il y a copie.

Entraînement#

Exercices courts pour s’entraîner aux gestes de base, chacun avec plusieurs données. Ils font tous partie du parcours essentiel.

★ Exercice 35 — Indices et tranches #

• essentiel

Sans machine, donner t[0], t[-1], t[1:3], t[len(t) - 2] et len(t) pour chacune des valeurs suivantes de t, puis ▶ vérifier dans la console : a) [7, 3, 9, 1, 5] ; b) ("lun", "mar", "mer", "jeu") ; c) "Monaco".

Coup de pouce

Écrire les indices sous chaque élément : 0, 1, 2… puis, en partant de la fin, -1, -2… Une tranche d’un tableau est un tableau, celle d’un p-uplet un p-uplet, celle d’une chaîne une chaîne.

Corrigé

Dans l’ordre t[0], t[-1], t[1:3], t[len(t) - 2], len(t) : a) 7, 5, [3, 9], 1, 5 ; b) ’lun’, ’jeu’, (’mar’, ’mer’), ’mer’, 4 ; c) ’M’, ’o’, ’on’, ’c’, 6. t[len(t) - 2] est l’avant-dernier élément, comme t[-2].

★ Exercice 36 — Dictionnaires : prédire l’état #

• essentiel

Sans machine, donner l’état du dictionnaire après chaque ligne, puis la valeur des dernières expressions. ▶ Vérifier ensuite.

a)

stock = {"pomme": 4, "poire": 0}
stock["kiwi"] = 7
stock["pomme"] = stock["pomme"] + 2
del stock["poire"]
len(stock)
7 in stock

b)

ages = {"Ada": 16, "Léo": 15}
ages["Zoé"] = 17
ages["Ada"] = 17
"Léo" in ages
15 in ages
len(ages)

Coup de pouce

Une affectation d[cle] = valeur crée la clé si elle est absente et remplace sa valeur sinon. in et len portent sur les clés.

Corrigé

États successifs, puis valeurs des expressions :

a)

{'pomme': 4, 'poire': 0, 'kiwi': 7}
{'pomme': 6, 'poire': 0, 'kiwi': 7}
{'pomme': 6, 'kiwi': 7}
2
False

b)

{'Ada': 16, 'Léo': 15, 'Zoé': 17}
{'Ada': 17, 'Léo': 15, 'Zoé': 17}
True
False
3

7 in stock et 15 in ages valent False : ce sont des valeurs, pas des clés. Dans b), la clé "Ada" existait déjà : sa valeur est remplacée, aucune clé n’est ajoutée.

★ Exercice 37 — Compréhensions : prédire le tableau #

• essentiel

Sans machine, donner le tableau construit par chaque compréhension, puis ▶ vérifier.

[3 * k for k in range(4)]
[len(m) for m in ["a", "bb", "ccc"]]
[x for x in [4, -1, 0, 7] if x > 0]
[c + c for c in "nsi"]
[k for k in range(10) if k % 2 == 1]

Coup de pouce

Écrire d’abord les valeurs successives de la variable, puis barrer celles qui ne vérifient pas la condition, et enfin calculer l’expression pour chacune des valeurs restantes.

Corrigé

a) [0, 3, 6, 9] b) [1, 2, 3] c) [4, 7] (0 n’est pas strictement positif) d) [’nn’, ’ss’, ’ii’] e) [1, 3, 5, 7, 9].

Exercices#

P-uplets (tuple)#

★ Exercice 1 — Lecture de trace #

★ Exercice 2 — Vrai ou faux ? #

★★ Exercice 3 — Une fonction, plusieurs résultats #

★★ Exercice 4 — Conversion de durée #

★★ Exercice 5 — Permutation circulaire #

Tableaux (list) : accès, modification, parcours#

★ Exercice 6 — Lecture de trace #

★ Exercice 7 — Fabriquer des tableaux #

★★ Exercice 8 — Parcours : les grands classiques #

★★ Exercice 9 — Modifier sur place #

★★ Exercice 10 — Chercher et compter #

★★ Exercice 11 — Renverser sans reverse #

★ Exercice 12 — Ajouter et retirer au-delà du programme #

Construction par compréhension#

★ Exercice 13 — Lecture de trace #

★★ Exercice 14 — Écrire des compréhensions #

★★ Exercice 15 — De la boucle à la compréhension #

★★ Exercice 16 — Nettoyer une phrase #

Matrices (tableaux de tableaux)#

★ Exercice 17 — Se repérer dans une matrice #

★★ Exercice 18 — Parcourir une matrice #

★★ Exercice 19 — Créer une grille — et le piège #

★★★ Exercice 20 — Transposée #

★★★ Exercice 21 — Traitement d’image #

Dictionnaires (dict)#

★ Exercice 22 — Lecture de trace #

★★ Exercice 23 — Parcourir un dictionnaire #

★ Exercice 24 — Compter des votes : code à trous #

★★ Exercice 25 — Comptage d’occurrences #

★★ Exercice 26 — Inverser un dictionnaire #

★★★ Exercice 27 — Un mini-annuaire à clés composées #

Le fil rouge à l’épreuve : références, alias, copie#

★★ Exercice 28 — Alias ou copie ? (lecture de trace) #

★★ Exercice 29 — Effet de bord d’une fonction #

★★★ Exercice 30 — Le piège en dictionnaire #

Synthèse : petits problèmes#

★★ Exercice 31 — Carnet de notes #

★★★ Exercice 32 — Panier d’une boutique #

★★★ Exercice 33 — Vers le bac — le jeu du démineur (grille) #

★★ Exercice 34 — Une copie selon un assistant d’IA #

Entraînement#

★ Exercice 35 — Indices et tranches #

★ Exercice 36 — Dictionnaires : prédire l’état #

★ Exercice 37 — Compréhensions : prédire le tableau #

P-uplets (`tuple`)#

Tableaux (`list`) : accès, modification, parcours#

★★ Exercice 11 — Renverser sans `reverse` #

Dictionnaires (`dict`)#