Documents autorisés: Supports (et notes) de cours de TD

Expliquer ... — 6 points Construire l’arbre de recherche pour les requêtes member(X,[a,b,c,d], member(e,[a,b,c,d] et

reverse([a,b,c,d],L).
member(X,[X|_]):-!.
member(X,[_|L]):-
    member(X,L).
reverse(L1,L2):- reverse(L1,[],L2).
reverse([],L,L).
reverse([T|Q],L_aux,L):-
    reverse(Q,[T|L_aux],L).

Adapter ... — 6 points Modifier le programme simplify sum(Sum,Simplified), vu en TD et décrit dans l’ annexe 1, pour qu’il puisse traiter une somme algébrique. Exemples :

| ?-  simplify_sum(3+5+b-6-c,S).
S = 2+b-c
true
| ?-  simplify_sum(3-5+b-6+c,S).
S = -8+b+c
| ?- simplify_sum(11-5-6+x,S).
S = x
true

Définir ... — 8 points Les fameuses huit reines — 4 points Ecrire un prédicat reines(L) qui calcule les différentes positions que peuvent prendre huits reines sur un échiquier sans être en prise (rappel : deux reines sont en prise si elles sont sur la même ligne, la même colonne ou la même diagonale

| ?-   reines(L).
L = [1,5,8,6,3,7,2,4]
...

Le fameux ’self’ — 4 points Ecrire un prédicat self(X) qui unifie X à la définition même de ce prédicat (au renomage de variables pres). Pas d’exemple ... car il contiendrait le résultat !!

*Annexe 1

% Arithmetic expression simplifier - The Craft of Prolog/ R.A. O'Keefe
simplify_sum(Sum,Simplified) :-
    simplify_sum(Sum,TopOfTree,HoleAtBottom,0,N),
    simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N).
simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N):-
    N \== 0,
    HoleAtBottom=N,
    Simplified=TopOfTree,
    !.
simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N):-
    N == 0,
    var(TopOfTree),
    Simplified=0,
    !.
simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N):-

    N == 0,
    nonvar(TopOfTree),
    TopOfTree=Simplified+HoleAtBottom.
simplify_sum(A+B,Hole0,Hole,N0,N):-!,
    simplify_sum(B,Hole0,Hole1,N0,N1),
    simplify_sum(A,Hole1,Hole,N1,N).
simplify_sum(C,Hole,Hole,N0,N):- number(C), !,
    N is N0 + C.
simplify_sum(X,Hole+X,Hole,N,N).

/* Exemples
| ?- simplify_sum(3+5,S).
  S = 8
| ?- simplify_sum(3+5+b+6+c,S).
  S = 14+b+c
| ?- simplify_sum((3+5)+b+6+c,14+b+c).
  true
| ?- simplify_sum(3+5+b+6+c,S).
S = 14+b+c

*/