Bases & algorithmique · 6 mondes · 18 étapes
Algorithmique
Apprendre à penser un problème, en Python, dans le navigateur.
Progression
0 %
0/18 étapes terminées
Fondamental · 8 min de lecture
Penser un algorithme
Ce qu'il faut faire avant d'écrire la première ligne
1Définition
Un algorithme est une suite finie d'étapes non ambiguës qui transforme une entrée en sortie. Le langage de programmation n'est qu'un moyen de le dicter à une machine : la difficulté est dans la méthode, pas dans la syntaxe.
2Principes fondamentaux
01
Nommer l'entrée et la sortie
Deux phrases avant tout le reste : de quoi je dispose, et qu'est-ce que je dois produire. La moitié des blocages vient d'un énoncé mal relu.
02
Une étape doit être exécutable
Si une étape demande une décision humaine (« choisis le meilleur »), ce n'est pas une étape : il faut la décomposer.
03
Dérouler à la main
Un tableau avec une colonne par variable et une ligne par tour. C'est l'outil le plus rentable de tout l'apprentissage.
04
Chercher le cas limite tout de suite
Liste vide, un seul élément, valeurs égales, valeur absente. Un algorithme juste à 99 % est un algorithme faux.
3Exemples pratiques
Le motif de l'accumulateur
1poids = [12, 7, 23]2total = 0 # préparer AVANT la boucle3 4for p in poids:5 total = total + p6 7print(total) # 42Préparer, cumuler, lire. Somme, compte, moyenne, maximum : tous ces calculs sont le même squelette avec une opération différente.
Le motif du maximum
1temperatures = [18, 25, 21, 30, 27]2maximum = temperatures[0] # et non 0 !3 4for t in temperatures:5 if t > maximum:6 maximum = t7 8print(maximum) # 30Partir de la première valeur, jamais de zéro : avec des températures négatives, un départ à 0 donnerait un résultat faux sans lever d'erreur.
4Erreurs courantes
Initialiser l'accumulateur dans la boucle
À éviter
for p in poids: total = 0 total = total + pÀ faire
total = 0for p in poids: total = total + pPourquoi : Remis à zéro à chaque tour, le total finit par valoir le dernier élément. L'erreur ne provoque aucun message : elle donne juste un chiffre faux.
Afficher dans la boucle au lieu d'après
À éviter
for t in temperatures: if t > maximum: maximum = t print(maximum)À faire
for t in temperatures: if t > maximum: maximum = tprint(maximum)Pourquoi : Le résultat n'existe qu'une fois la boucle terminée. Afficher dedans montre des résultats partiels, ce qui est utile pour déboguer et faux pour un rendu.
Oublier la liste vide
À éviter
maximum = valeurs[0]À faire
if not valeurs: print("Aucune valeur")else: maximum = valeurs[0]Pourquoi : IndexError sur une liste vide. C'est le cas limite le plus fréquent, et le plus facile à traiter.
5Subtilités à connaître
- ◆
>et>=ne donnent pas le même résultat quand deux valeurs sont à égalité :>garde la première rencontrée,>=la dernière. - ◆Un algorithme correct mais non déterministe (qui dépend de l'ordre des dictionnaires, du hasard) est très difficile à tester : préfère le déterminisme.
- ◆La finitude fait partie de la définition : une méthode qui ne s'arrête pas ne résout rien, même si chaque étape est juste.
6Vérifie ta compréhension
Question 1/3
Score 0
Où initialiser un accumulateur ?
Envie d'essayer ? Ouvre le Labo et recopie les exemples pour les modifier.