il Dizionario Informatico -ESERCIZI PROLOG-

Esercizi di Prolog


Dare un programma in Prolog che definisca la relazione tra due 
liste di avere l'una lunghezza doppia dell'altra.

definizione del predicato lunghezza
definiamo le due clausole: la condizione di uscita (un fatto) stabilisce
che la lista vuota ha lunghezza 0. Il caso ricorsivo (una regola) dice che
la lunghezza puo' essere calcolata sommando 1 alla coda della lista:

lunghezza([],0).
lunghezza([A|B],N):- lunghezza(B,N1), N is N1+1.

definiamo il predicato listadoppia 
listadoppia(X,Y):- lunghezza(X,A), lunghezza(Y,B), A is 2*B.

Seconda soluzione (piu' elegante):
listadoppia2([],[]).
listadoppia2([X1,X2|Y], [A|B]):- listadoppia2(Y,B).
 
Attenzione, i seguenti esercizi potrebbero non essere corretti
(verranno controllati ed evenualmente corretti fra pochi giorni):


Dare un programma in Prolog che definisca, tra un elemento e una lista, la relazione 
"ultimo elemento della lista".
ultimo(X,[X]).                                     % l'elemento X e' il primo e l'ultimo elemento della lista contenete solo X
ultimo(X,[_|Y]):- ultimo(X,Y).          % ricorsivamente riapplico il predicato ultimo alla coda della lista

Dare un programma in Prolog che definisca la seguente relazione tra due liste:
"le due liste non hanno elementi in comune".
									% le due liste sono differenti se:
differenti([A|_],[X|_]):- A\=X.                       % il primo elemnto della lista e' diverso dal primo elemento della seconda lista
differenti([A|_],[_|Y]):- differenti(A,Y).       % oppure se confronto ricorsivamente il primo elemento della lista con la coda della seconda lista,
						   %con lo stesso procedimento della clausola precedente
differenti([_|B],[_|Y]):- differenti(B,Y).

Soluzione2 (Marco Lizza):
non_in_lista(X, []).
non_in_lista(X, [A|B]) :- X\=A, non_in_lista(X, B).
differenti([A|B], L) :- non_in_lista(A, L), differenti(B, L). 

Dare un programma in Prolog che definisca la seguente relazione tra un albero 
binario
ed una lista: "la lista contiene la frontiera dell'albero binario".

frontiera (VOID, []).
frontiera (btree(X,VOID,VOID), [X]).
frontiera (btree(X,A,B), L) :- frontiera (A,L1), frontiera (B,L2), append(L1,L2,L).

Dare un programma in Prolog che definisca la relazione tra due alberi binari
di avere la stessa struttura.
stessaStrutt(VOID,VOID).
stessaStrutt((A,A1,A2),(B,B1,B2)) :- stessaStrutt(A1,B1), stessaStrutt(A2,B2).

Dare un programma in Prolog che definisca la relazione "nodiInterni" tra un
albero binario e un naturale, tale che il numero naturale indichi il numero di nodi
interni dell'albero

nodiInterni(VOID,0).
nodiInterni((X,VOID,VOID),0).
nodiInterni((A,A1,A2),N) :- nodiInterni(A1,N1), nodiInterni(A2,N2), N = N1+N2+1.
Termini mancanti/suggerimenti ?