Patrons d'algorithmes classiques

2. Somme et moyenne

La somme est le patron d'accumulateur le plus simple : on part de 0 et on ajoute. La moyenne s'en déduit en divisant par le nombre d'éléments.

def moyenne(liste):
    total = 0
    for x in liste:
        total = total + x
    return total / len(liste)

print(moyenne([4, 7, 2, 9, 3]))   # 5.0

3. Maximum et minimum

Trouver le plus grand élément d'une liste est un patron d'accumulateur… mais avec un piège d'initialisation redoutable. La règle d'or : on initialise l'accumulateur au premier élément de la liste, jamais à une valeur arbitraire.

def maximum(liste):
    m = liste[0]         # on part du PREMIER element
    for x in liste:
        if x > m:
            m = x        # on garde le plus grand vu jusqu ici
    return m

print(maximum([4, 7, 2, 9, 3]))   # 9

Traçons l'exécution sur [4, 7, 2, 9, 3], tour par tour :

4. Compter

Compter, c'est un accumulateur entier : on part de 0 et on ajoute 1 chaque fois qu'un élément vérifie une condition. Deux usages fréquents : compter les occurrences d'une valeur, ou compter les éléments qui satisfont un test.

def compte_occurrences(liste, valeur):
    compteur = 0
    for x in liste:
        if x == valeur:          # est-ce l element cherche ?
            compteur = compteur + 1
    return compteur

print(compte_occurrences([3, 1, 3, 7, 3], 3))   # 3

5. Rechercher un élément (recherche séquentielle)

Chercher si une valeur figure dans une liste, c'est la recherche séquentielle : on parcourt du début à la fin. Nouveauté par rapport aux patrons précédents : dès qu'on trouve, on peut arrêter tout de suite avec un return à l'intérieur de la boucle.

def contient(liste, valeur):
    for x in liste:
        if x == valeur:
            return True          # trouve : on sort immediatement
    return False                 # boucle finie sans trouver : absent

print(contient([4, 7, 2, 9, 3], 9))   # True
print(contient([4, 7, 2, 9, 3], 5))   # False

def indice_de(liste, valeur):
    for i in range(len(liste)):
        if liste[i] == valeur:
            return i             # premiere position trouvee
    return -1                    # absent

print(indice_de([4, 7, 2, 9, 3], 9))   # 3
print(indice_de([4, 7, 2, 9, 3], 5))   # -1

6. Combiner les patrons

Les vrais exercices mélangent souvent plusieurs patrons. Exemple canonique : trouver non pas le maximum, mais l'indice du maximum. On fusionne le patron « maximum » et le patron « parcours par indice ».

def indice_du_max(liste):
    i_max = 0                    # on suppose que le max est en position 0
    for i in range(len(liste)):
        if liste[i] > liste[i_max]:
            i_max = i            # on garde la position du plus grand
    return i_max

print(indice_du_max([4, 7, 2, 9, 3]))   # 3   (car liste[3] == 9)

7. Exercices d'application

À faire de tête, en s'appuyant sur les patrons, avant d'ouvrir le corrigé.

def nb_au_dessus_moyenne(liste):
    moyenne = sum(liste) / len(liste)
    compteur = 0
    for x in liste:
        if x > moyenne:
            compteur = compteur + 1
    return compteur

8. Erreurs classiques (les pièges qui coûtent des points)

Ces cinq erreurs reviennent chez presque tous les débutants sur les patrons de parcours. Les repérer à l'avance, c'est éviter de perdre bêtement des points en TP comme en concours.

9. Pour aller plus loin

Ces patrons sont les briques de base des algorithmes plus ambitieux que tu rencontreras juste après. Tous réinvestissent le parcours de liste, la comparaison et l'accumulateur que tu viens de revoir :

• Recherche par dichotomie — sur une liste triée, on coupe l'intervalle en deux à chaque étape : bien plus rapide que la recherche séquentielle de la section 5.
• Tris par insertion et par sélection — le tri par sélection cherche à répétition le minimum du reste de la liste : c'est le patron « minimum » utilisé en boucle.
• Complexité temporelle — pour comparer ces algorithmes, on compte le nombre d'opérations : parcourir une liste de taille n, c'est de l'ordre de n comparaisons.