Objectifs

• Écrire un algorithme en langage naturel puis le traduire en Python (et inversement).
• Utiliser variables, affectation, instructions conditionnelles, boucles bornées (for) et non bornées (while), fonctions.
• Créer une liste en extension, par ajouts successifs (append) ou en compréhension.
• Accéder à un élément par son indice, connaître la longueur d’une liste, parcourir une liste par ses indices ou par ses éléments.
• Programmer les algorithmes classiques sur les listes : somme, moyenne, maximum, comptage, recherche, termes d’une suite.

1. Algorithme, langage naturel et Python

On peut écrire un algorithme :

• en langage naturel (en français structuré), pour réfléchir et communiquer ;
• en Python, pour que l’ordinateur l’exécute.

Exemple résolu : une boucle « tant que »

Awa a 5 000 F CFA d’économies et en ajoute 1 500 chaque semaine. Écris un algorithme qui donne le nombre de semaines nécessaires pour atteindre au moins 20 000 F CFA. Cherche d’abord, puis déroule les étapes.

def semaines():
    s = 5000
    n = 0
    while s < 20000:
        s = s + 1500
        n = n + 1
    return n

2. Les listes en Python

2.1 Créer une liste

• En extension : on écrit tous les éléments. prix = [250, 1000, 500, 1500, 750]
• Par ajouts successifs : on part d’une liste vide et on ajoute avec append.

  L = []
  for k in range(4):
      L.append(3 * k)
  # L vaut [0, 3, 6, 9]

• En compréhension : on décrit la règle de construction. carres = [k**2 for k in range(5)] donne [0, 1, 4, 9, 16]. On peut ajouter une condition : [k for k in range(10) if k % 2 == 0] donne [0, 2, 4, 6, 8].

2.2 Indices et longueur

Si une liste contient \(n\) éléments, ses indices vont de \(0\) à \(n-1\). On lit l’élément d’indice \(i\) avec L[i], la longueur avec len(L), le dernier élément avec L[-1] ou L[len(L) - 1]. On modifie un élément par affectation : L[1] = 8.

2.3 Parcourir une liste

Deux façons de parcourir une liste :

# par les indices
for i in range(len(prix)):
    print(i, prix[i])

# directement par les éléments
for p in prix:
    print(p)

3. Les algorithmes classiques sur les listes

3.1 Somme et moyenne : l’accumulateur

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

Avec prix = [250, 1000, 500, 1500, 750] : la somme vaut \(250 + 1000 + 500 + 1500 + 750 = 4000\), donc la moyenne vaut \(\dfrac{4000}{5} = 800\) F CFA.

3.2 Le maximum : le record à battre

En langage naturel : m prend la valeur du premier élément ; pour chaque élément x de la liste, si x > m alors m prend la valeur x ; renvoyer m.

flowchart TD
A[m prend le premier élément] --> B{Reste-t-il un élément x}
B -->|oui| C{x plus grand que m}
C -->|oui| D[m prend la valeur x]
C -->|non| B
D --> B
B -->|non| E[Renvoyer m]

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

Exemple résolu : faire tourner l’algorithme à la main

Déroule maximum([250, 1000, 500, 1500, 750]) en suivant la valeur de m.

3.3 Compter et rechercher

Kofi a les notes notes = [12, 8, 15, 9, 10, 14]. Combien de notes sont supérieures ou égales à 10 ? Écris la fonction, puis donne le résultat.

def compter(L, seuil):
    c = 0
    for x in L:
        if x >= seuil:
            c = c + 1
    return c

Pour savoir si une valeur est présente, Python propose x in L (renvoie True ou False) ; l’algorithme correspondant parcourt la liste et renvoie True dès qu’il trouve l’élément.

3.4 Les termes d’une suite dans une liste

Soit la suite définie par \(u_0 = 1\) et \(u_{n+1} = 2u_n + 1\). Écris une fonction qui renvoie la liste des termes \(u_0\) à \(u_n\), puis donne la liste pour \(n = 4\).

def termes(n):
    u = 1
    L = [u]
    for k in range(n):
        u = 2 * u + 1
        L.append(u)
    return L

Erreurs fréquentes

• Confondre = (affectation) et == (test d’égalité).
• Oublier que les indices commencent à 0 et que range(n) s’arrête à \(n - 1\).
• Oublier les deux-points ou l’indentation après for, while, if, def.
• Placer l’initialisation d’un accumulateur dans la boucle, ou le return dans la boucle (la fonction s’arrête au premier tour).
• Écrire une boucle while dont la condition ne devient jamais fausse : le programme tourne sans fin.

Récapitulatif

• Un algorithme s’écrit en langage naturel puis se traduit en Python : affectation, condition, boucle for (nombre de tours connu), boucle while (on s’arrête quand une condition devient fausse), fonction avec return.
• Une liste se crée en extension, par ajouts successifs avec append, ou en compréhension.
• Indices de 0 à len(L) − 1 ; L[i] lit l’élément d’indice i ; L[-1] est le dernier.
• Algorithmes types : somme et moyenne (accumulateur), maximum (record), comptage (compteur), recherche, liste des termes d’une suite.