Adloun

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
—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.

100 % gratuit

Essaie le suivant avec le tuteur

Faire l'exercice suivant avec le tuteur

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.

Le cours du chapitre · Tous les exercices du chapitre

Exercice suivant avec le tuteur →