Je vous en prie, si quelqun sait faire cet exercice, qu'il me le fasse j'en ai vraiment besoin, je vous remercie d'avance !!!
Cet exercice propose de definir en scheme le type abstrait de donnees “ensemble”. Un ensemble est une collection de
donnees ayant diff´erentes caracteristiques comme celle de ne pas contenir deux fois le meme ´element. Il existe plusieurs
problemes `a resoudre. Un premier probleme est celui de la representation, la premiere solution propos´ee ici est de
representer un ensemble `a l’aide d’une liste contenant tous ses elements. Un second probleme est de savoir ce que l’on peut
ranger dans un ensemble. Nos ensembles pourront contenir n’importe quelle sorte d’´elements representables en scheme.
Un troisieme probleme consiste `a definir l’´egalite entre elements ; dans notre solution l’´egalite sera l’´egalite semantique
definie par la fonction equal ? de scheme.
Exemples :
> (define s1 (faire-ens ’(1 2 2 3 #\a 5 "abc")))
> (define s2 (faire-ens ’(1 2 #\a 4)))
> (define s3 (ajout "abc" s2))
> (vide? s1)
= #f
> (appartient? 2 s1)
= #t
> (union s1 s2)
= (3 5 "abc" 1 2 #\a 4)
; l’ordre des ´element peut ^etre different
> (retrait #\a s3)
= ("abc" 1 2 4)
1. Definissez la fonction (faire-ens l)
qui rend une liste sans repetitions representant l’ensemble contenant tous les elements donnes dans l. La liste l peut etre vide.
2. Definissez les fonctions booleennes (vide ? e) et (appartient ? el e).
3. Definissez les fonctions (ajout el e) et (retrait el e) permettant d’ajouter et de retirer un element d’un
ensemble.
4. Definissez la fonction (union e1 e2)
5. Donnez une version recursive terminale (sans parametre supplementaire) de union.
6. Envisageons de ne plus repr´esenter un ensemble par une liste mais par un autre type de collection comme vecteur
ou tableau. Expliquez, sans les reecrire, quelles sont les fonctions, parmi les precedentes, que vous devez modifier
pour realiser ce changement. Justifiez Donnez un exemple de nouvelle definition d’une de ces fonctions.
Partager