TP Python – Suites, Fibonacci et mémoïsation

BTS SIO SISR 2e année – Pour aller plus loin – S07

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Exercice A – Une suite récurrente

Écris u_rec(n) pour la suite \(u_0 = 3\), \(u_{n+1} = 2u_n - 1\), de façon récursive.

J'anticipe. Que vaut u_rec(4) ?

###

Lancer assert upy-undrec(0) == 3bksl-nlassert upy-undrec(1) == 5bksl-nlassert upy-undrec(4) == 33bksl-nlassert all(upy-undrec(k) == 2 py-strpy-str (k + 1) + 1 for k in range(0, 60))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def upy-undrec(n):bksl-nl """upy-und0 = 3, upy-und{n+1} = 2 upy-undn - 1, de facon recursive."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice B – Fibonacci naïf

Écris fib(n) (\(F_0 = 0\), \(F_1 = 1\)) avec deux appels récursifs.

J'anticipe. Combien d'appels pour fib(5) ?

###

Lancer assert fib(0) == 0bksl-nlassert fib(1) == 1bksl-nlassert fib(10) == 55bksl-nlassert fib(20) == 6765bksl-nlassert all(fib(k) == fib(k - 1) + fib(k - 2) for k in range(2, 18))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def fib(n):bksl-nl """Fibonacci, version recursive naive."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice C – Compter les appels

Écris appels_fib(n) qui renvoie le nombre d'appels que ferait fib(n) (sans calculer Fibonacci) : 1 si n < 2, sinon 1 + appels_fib(n-1) + appels_fib(n-2).

J'anticipe. Vérifie à la main appels_fib(5) avec le tableau du cours.

###

Lancer assert appelspy-undfib(0) == 1bksl-nlassert appelspy-undfib(5) == 15bksl-nlassert appelspy-undfib(10) == 177bksl-nlassert appelspy-undfib(20) == 21891bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def appelspy-undfib(n):bksl-nl """Nombre d'appels de fib(n) naive."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Pourquoi ce nombre croît-il si vite ? Par combien est-il à peu près multiplié à chaque rang ?

Exercice D – Fibonacci mémoïsé

Écris fib_memo(n, cache=None) avec un dictionnaire cache créé dans la fonction si besoin (pas de dictionnaire par défaut partagé).

###

Lancer assert fibpy-undmemo(0) == 0bksl-nlassert fibpy-undmemo(1) == 1bksl-nlassert fibpy-undmemo(30) == 832040bksl-nlassert fibpy-undmemo(90) == 2880067194370816120bksl-nlassert all(fibpy-undmemo(k) == fibpy-undmemo(k - 1) + fibpy-undmemo(k - 2) for k in range(2, 100))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def fibpy-undmemo(n, cache=None):bksl-nl """Fibonacci recursif avec memoisation (dictionnaire)."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Pourquoi cache=None et non cache={} ?

Exercice E – Fibonacci itératif

Écris fib_iter(n) avec une boucle et deux variables a, b.

J'anticipe. Écris la trace de a et b pour n = 6 (exercice 7).

###

Lancer assert fibpy-unditer(0) == 0bksl-nlassert fibpy-unditer(1) == 1bksl-nlassert fibpy-unditer(6) == 8bksl-nlassert fibpy-unditer(30) == 832040bksl-nlassert fibpy-unditer(90) == 2880067194370816120bksl-nlassert fibpy-unditer(2000) % 1000 == 125bksl-nlassert all(fibpy-unditer(k) == fibpy-unditer(k - 1) + fibpy-unditer(k - 2) for k in range(2, 300))bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def fibpy-unditer(n):bksl-nl """Fibonacci, version iterative."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Quel est l'invariant de ta boucle ?