NSI (première) · Chapitre 4 · Exercice de TD
La suite de Fibonacci s'écrit en une ligne grâce à l'affectation…
Les types construits · P-uplets, déballage et affectation multiple · niveau 3 (difficile)
Énoncé
La suite de Fibonacci s'écrit en une ligne grâce à l'affectation multiple : a, b = b, a + b. Dérouler à la main six tours en partant de . Écrire ensuite fibonacci(n), énoncer son invariant, puis montrer sur machine que remplacer l'affectation multiple par deux affectations successives donne un résultat faux.
Corrigé
La trace. Le membre de droite est évalué entièrement avant la moindre affectation : on calcule le couple avec les anciennes valeurs, puis on l'installe.
| tour | ||
|---|---|---|
| — | 1 | 2 |
| 1 | 2 | 3 |
| 2 | 3 | 5 |
| 3 | 5 | 8 |
| 4 | 8 | 13 |
| 5 | 13 | 21 |
| 6 | 21 | 34 |
def fibonacci(n):
"""n-ieme terme de Fibonacci, avec F(0) = 0 et F(1) = 1.
Precondition : n est un entier >= 0.
Invariant : avant le tour numero k, le couple (a, b) vaut (F(k), F(k+1)).
"""
assert n >= 0
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
L'invariant, et ce qu'il donne. Avant le tour , . Il est vrai au départ : . Un tour le préserve, puisqu'il remplace par . Après tours, : c'est la postcondition, obtenue sans autre raisonnement.
Vérification.
assert [fibonacci(k) for k in range(13)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
for n in range(2, 400):
assert fibonacci(n) == fibonacci(n - 1) + fibonacci(n - 2)
La version fausse. En deux affectations successives, la première écrase avant que la seconde ne s'en serve :
a, b = 0, 1
for _ in range(6):
a = b
b = a + b # a a DEJA change : on calcule b + b, donc 2*b
print(a, b) # 32 64 au lieu de 8 13
Après six tours, on obtient au lieu de : la boucle s'est mise à doubler , car a + b est devenu b + b.
La correction naïve demanderait une variable temporaire : tmp = a; a = b; b = tmp + b. L'affectation multiple s'en dispense, parce que le p-uplet est construit d'abord, avec les anciennes valeurs, puis déballé. C'est la raison profonde pour laquelle a, b = b, a échange sans temporaire.
100 % gratuit
Essaie le suivant avec le tuteur
- L'exercice suivant avec le tuteur, sans compte : il guide pas à pas, sans donner la réponse
- 16 autres exercices corrigés dans ce chapitre, et 20 à chercher avec le tuteur
- Le podcast et la vidéo du chapitre et la correction filmée du TD : 2 minutes sans compte
Sans compte : le cours, 2 minutes de podcast et de vidéo et un exercice avec le tuteur. Pour tout le reste : inscription gratuite en 30 secondes, sans carte bancaire.