Partie 1 — Compléments sur les listes

Rappels

Une liste est une collection ordonnée de valeurs, modifiable.

L = [3, 7, 2, 9, 5]
print(L[0])    # 3 (premier élément)
print(len(L))  # 5 (nombre d'éléments)
L.append(4)    # ajoute 4 à la fin

Extraction (slicing)

On peut extraire une sous-liste avec la notation L[début:fin] (fin exclue).

L = [10, 20, 30, 40, 50]
print(L[1:4])   # [20, 30, 40]
print(L[:3])    # [10, 20, 30]
print(L[2:])    # [30, 40, 50]

Listes de listes (tableaux 2D)

Une matrice peut être représentée par une liste de listes.

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

print(M[0][2])  # 3 (ligne 0, colonne 2)
print(M[1][1])  # 5 (ligne 1, colonne 1)

Parcourir une matrice :

for i in range(len(M)):
    for j in range(len(M[i])):
        print(M[i][j], end=" ")
    print()

Exemple — Somme de tous les éléments d’une matrice :

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

Partie 2 — Les dictionnaires

Un dictionnaire associe des clés à des valeurs.

eleve = {"nom": "Alice", "age": 17, "moyenne": 15.5}
print(eleve["nom"])       # Alice
print(eleve["moyenne"])   # 15.5

Ajouter et modifier

eleve["classe"] = "Tle"      # ajout d'une clé
eleve["moyenne"] = 16.0       # modification

Parcourir un dictionnaire

for cle, valeur in eleve.items():
    print(cle, ":", valeur)

On peut aussi parcourir uniquement les clés (eleve.keys()) ou les valeurs (eleve.values()).

Vérifier si une clé existe

if "nom" in eleve:
    print("La clé 'nom' existe")

Exemple — Compter les occurrences de chaque lettre dans un mot :

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

print(compter_lettres("mathematiques"))
# {'m': 2, 'a': 2, 't': 2, 'h': 1, 'e': 2, 'i': 1, 'q': 1, 'u': 1, 's': 1}

Partie 3 — Recherche dans une liste

Recherche séquentielle

On parcourt toute la liste pour trouver un élément.

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

Si x est dans la liste, la fonction renvoie son indice. Sinon, elle renvoie $-1$ .

L = [5, 12, 3, 8, 20]
print(recherche(L, 8))    # 3
print(recherche(L, 15))   # -1

Recherche du maximum

def maximum(L):
    m = L[0]
    for i in range(1, len(L)):
        if L[i] > m:
            m = L[i]
    return m

Recherche par dichotomie (liste triée)

Si la liste est triée, on peut chercher plus efficacement en divisant la liste en deux à chaque étape.

def dichotomie(L, x):
    g = 0
    d = len(L) - 1
    while g <= d:
        m = (g + d) // 2
        if L[m] == x:
            return m
        elif L[m] < x:
            g = m + 1
        else:
            d = m - 1
    return -1

Avec une liste de 1000 éléments, la recherche séquentielle peut nécessiter jusqu’à 1000 comparaisons, tandis que la dichotomie en nécessite au plus 10 (car $2^{10} = 1024$ ).

Exemple — L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], on cherche 23.

$g=0$ , $d=9$ , $m=4$ : L[4]=16 < 23 → $g=5$

$g=5$ , $d=9$ , $m=7$ : L[7]=56 > 23 → $d=6$

$g=5$ , $d=6$ , $m=5$ : L[5]=23 → trouvé à l’indice 5.

Partie 4 — Manipulation de chaînes de caractères

Opérations sur les chaînes

mot = "Bonjour"
print(len(mot))     # 7
print(mot[0])       # B
print(mot[3:6])     # jou

Les chaînes sont non modifiables : on ne peut pas écrire mot[0] = "b".

Parcourir une chaîne

for lettre in "Python":
    print(lettre)

Concaténation et conversion

prenom = "Alice"
age = 17
phrase = prenom + " a " + str(age) + " ans"
print(phrase)   # Alice a 17 ans

Exemple — Vérifier si un mot est un palindrome :

def est_palindrome(mot):
    mot = mot.lower()
    for i in range(len(mot) // 2):
        if mot[i] != mot[len(mot) - 1 - i]:
            return False
    return True

print(est_palindrome("kayak"))   # True
print(est_palindrome("python"))  # False

Partie 5 — Algorithmes avec boucles imbriquées

Moyenne d’une liste

def moyenne(L):
    s = 0
    for x in L:
        s = s + x
    return s / len(L)

Tri par sélection

Le tri par sélection cherche le minimum à chaque étape et le place au bon endroit.

def tri_selection(L):
    for i in range(len(L)):
        i_min = i
        for j in range(i + 1, len(L)):
            if L[j] < L[i_min]:
                i_min = j
        L[i], L[i_min] = L[i_min], L[i]
    return L

Déroulement sur [5, 3, 8, 1] :

Étape	Liste	Opération
1	`[1, 3, 8, 5]`	Échange de 5 et 1
2	`[1, 3, 8, 5]`	3 est déjà au bon endroit
3	`[1, 3, 5, 8]`	Échange de 8 et 5

Algorithmes en langage naturel

Les algorithmes peuvent être écrits en langage naturel (pseudo-code).

Fonction Recherche(L, x)
    Pour i allant de 0 à longueur(L) - 1
        Si L[i] = x alors
            Renvoyer i
        Fin Si
    Fin Pour
    Renvoyer -1
Fin Fonction

Traduction en Python :

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

Exemple d’application

Énoncé — On dispose d’un dictionnaire contenant les notes d’élèves. Écrire un programme qui :

Calcule la moyenne de chaque élève.

Détermine l’élève ayant la meilleure moyenne.
notes = {
    "Alice": [15, 12, 18, 14],
    "Bob": [10, 8, 13, 11],
    "Clara": [17, 16, 19, 15]
}

def moyenne(L):
    s = 0
    for x in L:
        s = s + x
    return s / len(L)

def meilleur_eleve(notes):
    meilleur = ""
    moy_max = 0
    for nom, liste_notes in notes.items():
        m = moyenne(liste_notes)
        print(nom, ":", m)
        if m > moy_max:
            moy_max = m
            meilleur = nom
    return meilleur

print("Meilleur élève :", meilleur_eleve(notes))
Alice : $(15 + 12 + 18 + 14) / 4 = 14{,}75$

Bob : $(10 + 8 + 13 + 11) / 4 = 10{,}5$

Clara : $(17 + 16 + 19 + 15) / 4 = 16{,}75$

Le meilleur élève est Clara avec une moyenne de $16{,}75$ .