Voici quelques exemples classiques d’algorithmes qui nécessitent un parcours simple d’une collection (une seule boucle for). Leur complexité est linéaire.
Dans l’ensemble de cette fiche, les exemples utilisent des listes de personnes. Une personne est modélisée par un tuple (nom, age).
I. Algorithmes de cumul
1) Exemple de moyenne
Voici une fonction qui renvoie la moyenne d’âge, arrondie à l’entier inférieur, d’une liste de personnes.
2) Exemple de comptage
Voici une fonction qui compte le nombre de personnes d’une liste qui ont strictement moins de 15 ans.
3) Autres exemples d’algorithme de la même famille
• Calculer la somme des nombres positifs d’une liste de nombres.
• Compter le nombre de voyelles dans une chaîne de caractères.
II. Recherche d’un extremum (maximum ou minimum)
Voici une fonction qui renvoie le nom de la personne la plus âgée d’une liste.
Autres problèmes de la même famille :
- trouver le nombre le plus proche de zéro dans une liste de nombres ;
- trouver l’indice du mot qui contient le plus de « a » dans une liste de mots.
III. Algorithmes de vérification
On parcourt la liste en faisant une recherche/vérification à chaque étape. On s’arrête dès qu’on trouve ce que l’on cherche ou un contre-exemple dans le cas d’une vérification.
Voici une fonction qui renvoie l’indice de la première personne qui a au moins 15 ans dans une liste (et None si aucune personne ne correspond au critère).
À noter
Ici, nous utilisons return en milieu de boucle pour quitter la fonction. C’est tolérable dans le cas d’une fonction très simple, comme c’est le cas ici, mais souvent à éviter dans des fonctions plus complexes.
Autres problèmes de la même famille :
- vérifier qu’une personne dont le nom est passé en paramètre est bien membre d’une liste de personnes ;
- vérifier qu’une liste de personnes est rangée en ordre décroissant d’âges ;
- chercher le premier mot de plus de 5 lettres dans une liste de mots.