1. naloga

Binarna drevesa so podana v obliki b(L, E, R), kjer sta L in R levo oziroma desno poddrevo, E pa element v vozlišču. Prazno drevo predstavlja simbol nil. Drevo z enim samim elementom je tako b(nil, E, nil). Napišite predikat memberBT(X, BT), ki z vračanjem vrne vse elemente X binarnega drevesa BT!

Rešitev

memberBT(X, b(L, X, R)).
memberBT(X, b(L, _, R)):-memberBT(X,L).
memberBT(X, b(L, _, R)):-memberBT(X,R).

2. naloga

Kako bi prologu zastavili naslednja vprašanja? Ne pišite programov!

• a) Imate podano družinsko drevo (z relacijami parent ter male/female). Ali obstaja nekdo, ki v drevesu nima podanega nobenega otroka, ima pa vsaj enega starša?
• b) Za isto družinsko drevo kot pri (a): koliko ljudi ima več kot dve hčerki?
• c) Z vračanjem naštej sve elemente podanega seznama L, ki niso sestavljenega tipa!
• d) Je v seznamu L kakšen element vkleščen med dva a-ja (en a nekje pred njim, drugi za njim)?
• e) Koliko različnih črk je v seznamu L, katerega elementi so lahko ali črke ali cifre?

Rešitev

• a)

  parent(_,Y), not(parent(Y,_))

• b)

  setof( X, A^B^(parent(X,A), parent(X,B), not(A=B), female(A), female(B)), L ), length(L, N).

• c)

  member(X, L), (atomic(X); var(X)).

• d)

  conc(_, [a,X,a|_], L)

% lahko je NEKJE pred njim, dvoumno je napisano .. tole je še ena varianta, upošteva tudi L = [a,v,s,g,a,b].
conc(First, [X,a|Tail], L), member(a, First).

• e)

  setof( X, (member(X, L), \+integer(X)), S), length(S, N).

3. naloga

Kaj odgovori prolog na naslednja vprašanja? Podajte vse odgovore v pravilnem vrstnem redu!

• a)

  ?- length([3,a,Z,_X,_,a*b], N).

• b)

  ?- delete(X, [a,b,b,c], [a,c]).

• c)

  ?- member(X, [1,4,5]), member(Y, [2,4]), X > Y.

• d)

  ?- _L = [i,z,p,i,t], delete(X, _L, _L1), \+ member(X, _L1).

• e)

  ?- setof(X, member(X, [i,z,p,i,t]), L).

Rešitev

• a)

N = 6 ;
 
No

• b)

Error

• c)

X = 4,
Y = 2 ;
 
X = 5,
Y = 2 ;
 
X = 5,
Y = 4 ;
 
No

• d)

_L = [i, z, p, i, t],
X = z,
_L1 = [i, p, i, t] ;
 
_L = [i, z, p, i, t],
X = p,
_L1 = [i, z, i, t] ;
 
_L = [i, z, p, i, t],
X = t,
_L1 = [i, z, p, i] ;
 
No

• e)

L = [i, p, t, z] ;
 
No

4. naloga

Napišite preprost program ali celo vprašanje prologu, ki za podani seznam kateri vsebuje samo cifre ali črke, preveri, če njegova vsebina lahko predstavlja število v šestnajstiškem sistemu.

Rešitev

\+(member(X, L), atom(X), \+member(X, [a,b,c,d,e,f])).

Rešitev, ki preverja tudi številke

member(X, L, ((integer(X), X =< 9, X >= 0); (atom(X), member(X, [a,b,c,d,e,f]))).

Rešitev

_L=['X','A',2,3,4],_SEST=[1,2,3,4,5,6,7,9,0,'A','B','C','D','E','F'], bagof(X,(member(X,_SEST), member(X,_L)),_D), length(_D,_F),length(_L,_H),_H=_F.

-meni gornje dve ne vrneta pravilnega rezultata. _L seznam ki ga preverjamo, rezultat je true ali "no" če ne vsebuje. Stvar deluje.

5. naloga

Kaj je namen spodnjega programa? Kakšna je njegova časovna kompleksnost?

npalin(L, P):-
  length(L, N),
  npalin(L, N, P), !.
 
npalin(L, N, P):-
  findpal(L, N, P).
 
npalin(L, N, P):-
  N1 is N - 1,
  npalin(L, N1, P).
 
findpal(L, N, P):-
  conc(_, R, L),
  conc(P, _, R),
  length(P, N),
  palindrome(P).
 
palindrome(L):-
  reverse(L, L).

Rešitev

Program poišče najdaljši palindrom v podanem seznamu.

Časovna kompleksnost: