Click here to load reader
Upload
vuminh
View
212
Download
0
Embed Size (px)
Citation preview
Prolog TP 1 – NFP120
Pierre Courtieu
Ecrire le programme prolog dans un fichier (par exemple tpprolog.pl), puislancer prolog avec le commande : prolog -s tpprolog.pl.Testez ensuite vosprogramme en tapant des requetes (terminees par un “.” puis <entree>. Il est recom-mande de taper les requetes dans le meme fichier que le programme, en les mettant dansdes commentaires (%), puis de les copier dans prolog. Pour demander un autre solutiona la requete courante, tapez “;”. Pour sortir de la requete courante, tapez <entree>.
1 Rappels sur les listes– [a,b,c] represente la liste [a,b,c].– [a|[b,c]] represente la liste [a,b,c].– [a,b|[c]] represente la liste [a,b,c].– [a|X] represente une liste quelconque commencant par a et dont la queue est la
variable X (X est donc la liste des autres elements).– etc.
2 Predicats simplesEcrivez les predicats suivants :
Ex. 1 — prem(X, Y) : Y est la tete de la liste X.
Ex. 2 — rest(X, Y) : Y est la queue de la liste X.
Ex. 3 — der(X, Y) : Y est le dernier element de la liste X.
Ex. 4 — nieme(N, X, Y) : Y est le N-ieme element de la liste X.
Ex. 5 — elem(Y, X) : Y est un element de la liste X.
Ex. 6 — concat(X, Y, Z) : Z est la concatenation de X et Y.
Ex. 7 — long(X, N) : N est longueur de la liste X.
Ex. 8 — Ecrire paire et impaire qui permettent de tester la parite de la longueurd’une liste.
1
3 Reversibilite des predicatsEx. 9 —
1.Ecrire le predicat extraire(X, Y, E) : Y est la liste X dont on a extrait l’elementE.
2.Essayer les buts :
extraire([3], [], 3).extraire(L, [1,2,3,2,1], 2).extraire([1,2,3,4,5], [1,2,4,5], X).extraire([1,2,3,4,5], L, X).extraire([1,2,4,5], L, 3).
3.Commentez.
Ex. 10 — Utiliser concat pour ecrire sous_liste :sous_liste(ListeIncluse,ListeContenant):-...
Ex. 11 — Ecrire palindrome qui permet de tester si une liste est un palindrome. Onpourra penser a utiliser un accumulateur, c’est-a-dire une liste dans laquelle on stockeles elements lus au moment de l’appel recursif.
4 ArbresOn veut maintenant representer les arbres sous forme de listes contenant les valeurs
des nœuds et les sous-arbres (les listes n’etant pas typees en prolog, ceci est parfaite-ment possible).
Par exemple la liste ci-dessous :
[4,[2,[],[]],[4,[],[]],[7,[5,[],[]],
[9,[],[]]]]
correspond a l’arbre :
4
2 4 7
5 9
Ex. 12 — Ecrire un predicat qui verifie qu’une liste est un arbre binaire.
Ex. 13 — Ecrire un predicat qui verifie qu’un arbre binaire est un arbre de recherche.C’est-a-dire que pour tout nœud de valeur x, tous les nœuds du fils gauche contiennentdes valeurs inferieures (ou egales) a x, et tous les nœuds du file droit contiennent desvaleurs (strictement) superieurs a x. On utilisera les operateurs de comparaison sur lesentier : <, >, <=, >=. . .
2