Étape 1
Pour comprendre le fonctionnement global de l'algorithme, analysons le rôle de chaque fonction de manière modulaire :
Étape 2
La fonction moyenne(liste) calcule la moyenne arithmétique des éléments d'une liste de nombres.
Étape 3
La fonction sous_liste(liste, debut, taille) extrait une liste secondaire contenant taille éléments consécutifs de liste à partir de l'indice debut.
Étape 4
La fonction compte_valides(liste, taille, seuil) parcourt toutes les sous-listes de longueur taille et compte combien d'entre elles ont une moyenne strictement supérieure au paramètre seuil.
Étape 5
Appliquons ce traitement à la liste $L = [10, 15, 8, 14, 11, 16, 9, 13, 12]$ avec une fenêtre de longueur $\text{taille} = 3$. La boucle parcourt $i$ de $0$ à $9 - 3 + 1 - 1 = 6$ :
Étape 6
Pour $i = 0$, la sous-liste est $[10, 15, 8]$ et sa moyenne est $\frac{10 + 15 + 8}{3} = \frac{33}{3} = 11$.
Étape 7
Pour $i = 1$, la sous-liste est $[15, 8, 14]$ et sa moyenne est $\frac{15 + 8 + 14}{3} = \frac{37}{3} \approx 12{,}33$.
Étape 8
Pour $i = 2$, la sous-liste est $[8, 14, 11]$ et sa moyenne est $\frac{8 + 14 + 11}{3} = \frac{33}{3} = 11$.
Étape 9
Pour $i = 3$, la sous-liste est $[14, 11, 16]$ et sa moyenne est $\frac{14 + 11 + 16}{3} = \frac{41}{3} \approx 13{,}67$.
Étape 10
Pour $i = 4$, la sous-liste est $[11, 16, 9]$ et sa moyenne est $\frac{11 + 16 + 9}{3} = \frac{36}{3} = 12$.
Étape 11
Pour $i = 5$, la sous-liste est $[16, 9, 13]$ et sa moyenne est $\frac{16 + 9 + 13}{3} = \frac{38}{3} \approx 12{,}67$.
Étape 12
Pour $i = 6$, la sous-liste est $[9, 13, 12]$ et sa moyenne est $\frac{9 + 13 + 12}{3} = \frac{34}{3} \approx 11{,}33$.
Étape 13
La moyenne maximale obtenue sur l'ensemble de ces sous-listes est $\frac{41}{3} \approx 13{,}67$.
Étape 14
La fonction compte_valides renvoie $0$ si et seulement si la condition moyenne(bloc) > S n'est vérifiée pour aucun bloc, ce qui signifie que pour tout bloc, $\text{moyenne}(bloc) \le S$.
Étape 15
Par conséquent, $S$ doit vérifier l'inégalité $S \ge \frac{41}{3} \approx 13{,}67$.
Étape 16
Comme $S$ est un nombre entier, la plus petite valeur entière qui satisfait $S \ge 13{,}67$ est $S = 14$.
Méthode clé
Décomposer l'analyse d'un algorithme modulaire en étudiant d'abord le rôle des fonctions secondaires (calcul de moyenne, extraction de sous-liste) pour comprendre l'action de la fonction principale.
Piège à éviter
Confondre l'inégalité stricte `>` avec une inégalité large, ou oublier de convertir le résultat décimal vers l'entier supérieur immédiatement strict.
