Programmation impérative : TP 9

Fonction de Fibonacci

1re partie : Dictionnaires (interface)

Un dictionnaire (aussi appelé tableau associatif ou table d'association, en anglais map) est une structure de données abstraite qui permet de modéliser des fonctions (au sens mathématique) partielles discrètes : on associe à certains éléments d'un ensemble K (les clefs) des valeurs d'un ensemble V.

Il est possible

Pour cette première partie, on se contentera d'écrire l'interface d'un module pour les dictionnaires. On utilisera les entiers int aussi bien pour l'ensemble des clefs que pour l'ensemble des valeurs.

Dans un fichier map.h :
(Attention dans cette partie on se contente d'écrire l'interface donc on n'écrira pas l'implémentation des fonctions !)

  1. Déclarer un type abstrait map pour les dictionnaires.
  2. Déclarer une fonction map_empty qui retourne un dictionnaire vide.
  3. Déclarer une procédure map_add qui prend en paramètre une clef, une valeur et un dictionnaire et qui ajoute par effet une association entre cette clef et cette valeur dans le dictionnaire.
  4. Déclarer une fonction map_find qui prend en paramètre une clef et un dictionnaire et qui retourne la valeur associée à cette clef dans le dictionnaire.

    Pour simplifier, on supposera que cette fonction retournera -1 dans le cas où l'association n'est pas trouvée. Une version plus propre consisterait à mettre EDOM dans la variable globale errno pour indiquer l'erreur. Cf. man errno.

  5. Déclarer une procédure map_delete qui prend en paramètre une clef et un dictionnaire et qui supprime par effet toutes les associations avec cette clef.

Les deux parties suivantes sont indépendantes et peuvent être traitées dans l'ordre voulu. Une bonne idée est de se partager le travail avec un camarade puis de mettre en commun vos modules. Vous inverserez ensuite les rôles.

2e partie : Fonctions récursives et mémoïsation

On cherche à calculer la suite de Fibonacci à l'aide de l'algorithme récursif suivant: 

Fib(n) :
  si n = 0, retourne 0
  si n = 1, retourne 1
  sinon, retourne Fib(n-1) + Fib(n-2)
  1. Dans un fichier fib.c, implémenter naïvement cet algorithme.
  2. Écrire une fonction main pour la tester. Compiler et tester.

En implémentant ceci naïvement, on va être amené à calculer plusieurs fois la même valeur : en appelant Fib(4) on va appeler Fib(3) et Fib(2), mais l'appel à Fib(3) va lui même appeler récursivement Fib(2). Pour éviter cela, on va utiliser la mémoïsation : une fois une valeur calculée, on va la stocker pour ne pas avoir à la recalculer à l'appel suivant. On va utiliser un dictionnaire pour stocker l'association entre un entier et la valeur de la suite de Fibonacci pour cet entier. On aura donc l'algorithme suivant : 

Fib_memo(n, d) :
  si n est associé à m dans d, retourne m
  sinon
    si n = 0, r := 0
    si n = 1, r := 1
    sinon, r := Fib_memo(n-1, d) + Fib_memo(n-2, d)
    ajoute l'association de n à r dans d
    retourne r
  1. Implémenter cet algorithme en utilisant les fonctions déclarées dans l'interface des dictionnaires.
  2. Si ce n'est pas déjà fait, écrire un Makefile dans lequel seront indiquées les dépendances permettant de compiler fib.o.

3e partie : Implémentation des dictionnaires à l'aide de listes d'associations

Une des possibilités pour implémenter des dictionnaires est d'utiliser des listes chaînées dont les maillons contiendront non pas juste une valeur et l'adresse du maillon suivant, mais une clef, la valeur associée, et l'adresse du maillon suivant.

Pour rechercher la valeur associée à une clef, il faudra donc parcourir la liste jusqu'à trouver un maillon avec cette clef.

  1. Dans un fichier map.c, implémenter les dictionnaires à l'aide de listes d'associations.
  2. Si ce n'est pas déjà fait, écrire un Makefile dans lequel seront indiquées les dépendances permettant de compiler map.o.

4e partie : Exécutable final

  1. Modifier la fonction main pour tester également Fib_memo
  2. Modifier le Makefile pour produire un exécutable fibonacci. Tester.
  3. Modifier les fonctions Fib et Fib_memo pour qu'elles comptent le nombre d'appels récursifs. Tester.