Le carnet de calculs
Un ami te demande combien font 7 fois 8. Tu calcules : 56. Dix minutes plus tard, il te le redemande. Tu ne refais pas le calcul. Tu le sais déjà.
Un programme ne fait pas toujours ça. Parfois il refait le même calcul des milliers de fois, et devient très lent.
La solution : écrire les réponses dans un carnet, et regarder le carnet avant de calculer.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Suite de Fibonacci | Une suite de nombres : chaque nombre est la somme des deux précédents. On commence par 0 et 1. | 0, 1, 1, 2, 3, 5, 8 |
| Sous-problème | Un petit calcul dont on a besoin pour faire le grand. | fib(3) pour calculer fib(4) |
| Mémoire | Un dictionnaire où l'on range les réponses déjà calculées. La clé est le n, la valeur est la réponse. | {3: 2, 4: 3} |
| Mémoïsation | Ranger chaque réponse dans la mémoire, et la relire au lieu de la recalculer. | if n in memoire |
| Tableau de résultats | Une liste qu'on remplit des petits calculs vers le grand, sans récursivité. | [0, 1, 1, 2, 3] |
| Appel | Chaque fois qu'on utilise une fonction. | fib(4) est un appel |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : la suite de Fibonacci
À toi de jouer
À toi : la suite de Fibonacci
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
La suite avec une fonction récursive
fib(0) vaut 0 et fib(1) vaut 1. Pour tout autre n, fib(n) est fib(n - 1) plus fib(n - 2).
C'est facile à écrire avec une fonction qui s'appelle elle-même. Mais regarde combien d'appels elle fait.
À toi : compter les appels
appels = 0
def fib(n):
global appels
appels = appels + 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
for n in [5, 10, 20]:
appels = 0
resultat = fib(n)
print("fib(", n, ") =", resultat, "avec", appels, "appels")
# Essaie n = 25. Combien d'appels ? Et n = 30 : attends-tu longtemps ?
À toi : lire le dessin
À toi de jouer
À toi : lire le dessin
4 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.