Application

Fibonacci

On rapelle que la suite de Fibonacci est définie par

\[fibonacci(n) = \left\{ \begin{array}{l l} 0 & \quad \text{si $n = 0$,}\\ 1 & \quad \text{si $n = 1$,}\\ fibonacci(n - 2) + fibonacci(n - 1) & \quad \text{si $n > 1$}. \end{array} \right. \]

Question

Écrire et tester la fonction fibonacci(n) à l'aide de la programmation dynamique.

Comparer les temps d'exécution entre la version récursive et la version réalisée avec la programmation dynamique.

Indice

On utilisera une liste pour stocker toutes les valeurs de fibonacci(n).

Pyramide de nombres

On dispose d'une pyramide de nombres sous la forme suivante :

1
    1
2
   2 3
3
  4 5 6
4
...   ...

On peut réaliser un chemin dans la pyramide en partant du haut et en descendant toujours via un nombre plus bas à droite ou à gauche.

Par exemple, 1-2-4 est un chemin mais 1-3-4 n'en est pas un.

Chaque chemin a une valeur qui est égale à la somme des nombres qui composent ce chemin.

On cherche à trouver le chemin qui maximise cette valeur.

On souhaite réaliser une fonction Python pyramide(p) qui renvoie le chemin qui maximise la somme des nombres.

Question

1) Les pyramides sont représentées sous la forme p1 = [[1], [2, 3], [4, 5, 6]].

Rédiger une fonction generation_pyramide(n) qui génère et renvoie une pyramide de n étages avec des valeurs aléatoires.

Question

2) Rédiger une fonction récursive pyramide(p, i, j) qui prend une pyramide p, une hauteur i et une colonne j en paramètre et renvoie la valeur du meilleur chemin en partant du nombre aux coordonnées (i, j). Par exemple, pyramide(p1, 1, 0) = 7 (chemin 2-5).

Cette fonction devra tester tous les cas possibles sans utiliser de programmation dynamique.

Pensez aussi à tester votre programme avec une pyramide aléatoire.

Question

3) Afin de mettre en place un programme qui utilise la programmation dynamique, nous allons utiliser la mémoïsation en utilisant un dictionnaire qui sera donné en paramètre de la fonction pyramide_dyn(p, i, j, m={}). La clé du dictionnaire correspond au couple (i, j) et la valeur (si elle existe) à la valeur du meilleur chemin partant de (i, j).

Rédiger cette fonction et comparer avec la question 2.

Question

4) Proposer une amélioration qui renvoie également le détail du meilleur chemin.