Adloun

La suite de Fibonacci s'écrit en une ligne grâce à l'affectation…

Exercice de TD · niveau 3 (difficile) · NSI (première), chapitre 4 — Les types construits · P-uplets, déballage et affectation multiple

É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
---12
123
235
358
4813
51321
62134

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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.