PRFO23 : TP4

Exercice 1 : Interface des ensembles

Reprendre le fichier set.mli du TP précédent.

Exercice 2 : Implémentation à l'aide d'arbres binaires de recherche

Dans un nouveau fichier set.ml, implémenter les ensembles à l'aide des arbres binaires de recherche. Pour ce TP, on ne cherchera pas à les équilibrer.

Exercice 3 : Utilisation, sous-ensembles qui valent une somme

Étant donné un ensemble S et un entier n, on cherche à afficher tous les sous-ensembles de S dont la somme des éléments vaut n. On travaillera dans un fichier subset_sums.ml.

1. (Cf. TP3.) Écrire une fonction de type int Set.set -> unit qui affiche un ensemble d'entiers sur la sortie standard, de la forme { x1 x2 ... xn }. On utilisera un fold.
2. Proposer une fonction qui prend un ensemble d'entiers en paramètre et qui retourne la somme de ses éléments.
3. Proposer une fonction qui prend un ensemble d'entiers et un entier en paramètres et qui affiche tous les sous-ensembles dont la somme vaut l'entier.
   On utilisera l'algorithme suivant :

   subset_sum(S, n):
     si sum(S) = n
       affiche(S)
     pour tout x dans S
       subset_sum(S \ { x }, n)
   

4. Pour tester, proposer une fonction qui prend un entier n en paramètre et qui retourne l'ensemble des entiers de 1 à n.
   On pourra alors tester d'afficher les sous-ensembles de { 1; ...; n } dont la somme vaut n pour certaines valeurs de n.
5. On constate qu'avec l'algorithme précédent, certains sous-ensembles sont alors affichés plusieurs fois. On va donc séparer l'ensemble en deux parties, celle des éléments déjà vus et celle des autres à traiter.
   Implémenter l'algorithme suivant :

   subset_sum(S, n):
     subset_sum_aux(∅, S, n)
   
   subset_sum_aux(V, A, n):
     soit S = V ∪ A
     si sum(S) = n
       affiche(S)
     pour tout x dans A
       subset_sum_aux(V, A \ { x }, n)
       V ← V ∪ { x }
       A ← A \ { x }
   

   (Bien entendu, on n'utilisera pas de trait impératif, mais on utilisera un fold.)