2-01. Parcours de tableau

• Choisir la boucle adaptée selon que l’on a besoin de l’indice ou de la valeur seule.
• Ne pas confondre la case (valeur) et son adresse (indice).

Nous avons vu au chapitre 3-02 qu’une boucle for permet de visiter tous les éléments d’un tableau. Deux approches sont possibles :

            notes = [12, 15, 8, 19]

            # 1. Parcours par VALEURS (direct)
            for n in notes:
                print(n)

            # 2. Parcours par INDICES (accès positionnel)
            for i in range(len(notes)):
                print(f"Index {i} : {notes[i]}")
        

• Calculer la somme et la moyenne des valeurs d’une liste numérique.
• Compter le nombre d’occurrences respectant un critère précis.
• Identifier et traiter le cas limite d’une liste vide.

Somme et moyenne

Le principe consiste à utiliser un accumulateur (une variable initialisée à zéro avant la boucle) auquel on ajoute successivement chaque élément du tableau lors de la visite.

        def somme(tab):
            total = 0
            for val in tab:
                total += val
            return total

        def moyenne(tab):
            if len(tab) == 0:
                return None   # Évite la division par zéro si la liste est vide !
            return somme(tab) / len(tab)
    

Comptage conditionnel

On peut combiner l’accumulation avec un test if pour ne comptabiliser que les éléments vérifiant une condition donnée.

        def compter_reçus(notes):
            """Compte le nombre de notes supérieures ou égales à 10."""
            compteur = 0
            for note in notes:
                if note >= 10:
                    compteur += 1
            return compteur
    

                def occurrence(cible, tab):
                    nb = 0
                    for element in tab:
                        if element == cible:
                            nb += 1
                    return nb
            

                def moyenne_ponderee(notes, coefficients):
					somme_notes = 0
					total_coef = 0
					for i in range(len(notes)):
						if type(notes[i]) == int:
							somme_notes += notes[i] * coefficients[i]
							total_coef += coefficients[i]
					if total_coef == 0:
						return None
					return somme_notes / total_coef
            

• Tester la présence d'une valeur dans un tableau.
• Trouver l’indice d'une occurrence.
• Maîtriser le principe de sortie anticipée d’une fonction avec return.

Recherche de présence (booléen)

Pour savoir si un élément figure dans un tableau, on examine les cases l’une après l’autre. Dès qu’on le trouve, il est inutile de continuer : on interrompt immédiatement la fonction avec un return True.

        def existe(cible, tab):
            for element in tab:
                if element == cible:
                    return True   # Trouvé ! On quitte la fonction immédiatement.
            return False          # On a tout examiné sans succès.
    

            # ❌ CODE ERRONÉ :
            def existe(cible, tab):
                for element in tab:
                    if element == cible:
                        return True
                    else:
                        return False  # la boucle s'arrête dès le premier élément !
        

Recherche de l’indice d’une valeur

Si l'on veut savoir où se trouve l'élément, on utilise le parcours par indices. On renvoie l’indice dès la première rencontre, ou None (ou -1) si l’élément n’existe pas.

        def trouver_indice(cible, tab):
            for i in range(len(tab)):
                if tab[i] == cible:
                    return i
            return None
    

                def tous_positifs(tab):
                    for val in tab:
                        if val <= 0:
                            return False
                    return True
            

                # Méthode avec parcours à rebours :
                def dernier_indice(cible, tab):
                    for i in range(len(tab) - 1, -1, -1):
                        if tab[i] == cible:
                            return i
                    return None
            

• Déterminer la valeur maximale ou minimale d'un tableau.
• Déterminer l'indice de l'extremum.
• Comprendre l'impératif de l'initialisation sur le premier élément.

Le principe de recherche d’un maximum

Pour trouver la plus grande valeur d’un tableau :

1. On considère provisoirement que le maximum est le tout premier élément (tab[0]).
2. On parcourt les éléments suivants : dès qu’on rencontre une valeur plus grande que notre champion provisoire, elle devient le nouveau champion.
3. Une fois le tableau terminé, notre variable contient le maximum absolu.

        def valeur_max(tab):
            if len(tab) == 0:
                return None

            maxi = tab[0]  # Initialisation sur le premier élément
            for i in range(1, len(tab)):
                if tab[i] > maxi:
                    maxi = tab[i]
            return maxi
    

Rechercher l’indice de l’extremum

Dans de nombreuses situations (trouver le vainqueur d’une course, le jour de la température la plus basse), on cherche non pas la valeur mais sa position dans le tableau.

        def indice_min(tab):
            if len(tab) == 0:
                return None

            i_min = 0  # L'indice du plus petit élément provisoire
            for i in range(1, len(tab)):
                if tab[i] < tab[i_min]:
                    i_min = i
            return i_min
    

                def etendue(tab):
                    mini = tab[0]
                    maxi = tab[0]
                    for val in tab:
                        if val < mini:
                            mini = val
                        if val > maxi:
                            maxi = val
                    return maxi - mini
            

• Identifier le nombre d'opérations élémentaires d'un algorithme.
• Comprendre la notion de complexité linéaire $*\mathcal{O}(n)*$.
• Distinguer le cas le plus favorable du pire des cas.

Combien d'opérations exécute un ordinateur ?

Le temps d’exécution réel d'un programme dépend de nombreux facteurs extérieurs (puissance du processeur, langage employé, applications en arrière-plan). Pour comparer l'efficacité de deux algorithmes, l'informatique mesure le nombre d'opérations élémentaires (comparaisons, additions, affectations) en fonction du nombre d'éléments $*n*$ contenus dans le tableau.

La complexité linéaire $*\mathcal{O}(n)*$

Dans nos fonctions somme(tab) ou valeur_max(tab), la boucle traite chaque case exactement une fois. Si le tableau contient $*n*$ éléments, la boucle réalise environ $*n*$ itérations.

Pire cas et meilleur cas

Pour certains algorithmes, le nombre d'opérations dépend non seulement de la taille du tableau, mais aussi de l'ordre de ses valeurs :

• Algorithmes d'extremum et de moyenne : ils doivent impérativement lire toutes les cases. Le coût est toujours linéaire, quel que soit le contenu du tableau.
• Recherche séquentielle avec sortie anticipée :
  • Meilleur cas : la cible est située dans la toute première case (index 0). La fonction s’arrête en 1 seule étape (coût constant $*\mathcal{O}(1)*$).
  • Pire cas : la cible est tout à la fin du tableau ou n'y figure pas du tout. La boucle doit visiter les $*n*$ éléments (coût linéaire $*\mathcal{O}(n)*$).