UW/Programowanie w logice/Laboratorium
Archive
Spis treści |
[edytuj] Grafy
e(1,2). e(2,3). e(3,1). e(3,4). % 1- 2- 3- ... [[2,3], [3], []]. % connected(X, Y) - wtw gdy istnieje sciezka z X do Y connected(X, X). connected(X, Y) :- e(X, Z), connected(Z, Y). %e(G, X, Z) :- e(G, X, Z, 1). %e([H|T], X, Z, X) :- member(Z, H). %e([H|T], X, Z, L) :- M is L+1, e(T, X, Z, M). neigh(G, X, Z) :- neigh(G, X, Z, 1). neigh([H|T], X, H, X). neigh([H|T], X, Z, L) :- M is L+1, e(T, X, Z, M). connected(G, X, X). % connected(G, X, Y) :- e(G, X, Z), connected(G, Z, Y). connected(G, X, Y) :- neigh(G, X, N),!, member(Z, N), connected(G, Z, Y). % path(X, Y, L) - L jest sciezka z X do Y % euler(G) - G jest grafem eulera % euler(G, C) - SC = E delete(X, [X|Rest], Rest) :- !. delete(X, [Y|Rest], [Y|Rest2]) :- delete(X, Rest, Rest2). euler([], [CH], CH). euler(G, [C1|[C2|CT]], CH) :- member(e(C1, C2), G), delete(e(C1, C2), G, G1), euler(G1, [C2|CT], CH). euler(G, [CH|CT]) :- euler(G, [CH|CT], CH). dfs([], L, L, R, []). dfs(G, L, L2, R, G3) :- member(e(R, C2), G), \+ member(C2, L), delete(e(R, C2), G, G1), dfs(G1, [C2|L], L1, C2, G2), dfs(G2, L1, L2, R, G3). dfs(G, L, L, R, G1) :- member(e(R, C2), G), member(C2, L), delete(e(R, C2), G, G1). dfs(G, L, L, R, G) :- \+ member(e(R, C2), G). dfs([e(X,Y)|T], L) :- dfs([e(X,Y)|T], [X], L, X, _).
[edytuj] Listy otwarte
% listy otwarte % [1,2,3,4|X] % var(X) - wtw gdy X jest zmienna wstaw(H, E) :- var(H), H = [E|_]. wstaw([H|T],E) :- \+var(H), wstaw(T, E). zamknij(H, []) :- var(H). zamknij([H|T],[H|LW]) :- \+var(H), zamknij(T, LW). zamknij(T) :- var(T), T=[]. zamknij([H|T]) :- \+var(H), zamknij(T). otworz([], _). otworz([H|T],[H|LW]) :- \+var(H), otworz(T, LW).
[edytuj] Komputerówka 1 (Startek, 2008)
spr(M) - dla ustalonych M. Odnosi sukces gdy M jest macierzą permutacji.
Macierz permutacji:
| 1 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
W każdej kolumnie i w każdym wierszu jest dokładnie jedna jedynka. Macierz jest macierzą kwadratową.
% Wolno korzystać z Integer(X) (ale nie jest to konieczne do poprawnego rozwiązania). % spr(M) - dla ustalonych M, gdy M jest macierza permutacji % zera(L, Z) - % L - dowolna lista % Z - lista dlugosci L, skladajaca sie z samych 0 zera([], []). zera([_|L1], [0|L2]) :- zera(L1, L2). % jedynki(J) - % J - lista samych "1" dowolnej dlugosci jedynki([]). jedynki([1|L]) :- jedynki(L). % scal(L1, L2, L3) - % odnosi sukces wtw gdy L1 i L2 nie maja wartosci 1 na tych samych miejscach % oraz gdy L3 ma wartosc 1 na danym miejscu wtw gdy L1 lub L2 ma wartosc 1 na % danym miejscu. (~logiczny or list) % Ponadto lista L1 musi miec dokladnie jedna wartosc 1 % scal2(L1, L2, L3) - % to samo co scal, ale lista L1 sklada sie z wartosci 0 scal2([], [], []). scal2([0|L1], [1|L2], [1|L3]) :- scal2(L1, L2, L3). scal2([0|L1], [0|L2], [0|L3]) :- scal2(L1, L2, L3). scal([1|L1], [0|L2], [1|L3]) :- scal2(L1, L2, L3). scal([0|L1], [1|L2], [1|L3]) :- scal(L1, L2, L3). scal([0|L1], [0|L2], [0|L3]) :- scal(L1, L2, L3). % spr(M) - % odnosi sukces gdy M jest macierza permutacji spr([H|M]) :- zera(H, Z), spr([H|M], Z). % spr(M, L) - % odnosi sukces gdy macierz [L|M] jest zawiera dokladnie jedna "1" w kazdej % kolumnie. spr([], W) :- jedynki(W). spr([H|M], L) :- scal(H, L, W), spr(M, W).
[edytuj] Komputerówka 1 (M.Miłkowska, 2007)
Zdefiniuj predykat podziel(Lista, Podlisty), który dla podanej ustalonej listy złożonej z dowolnych elementów odniesie sukces wtw, gdy Podlisty jest listą niepustych podlist listy Lista spelniającą następujace warunki:
- Podlisty=[P1, ..., Pk],
P1 * P2 * ... * Pk = Lista (* - konkatenacja list) - pierwszy element każdej podlisty Pi jest równy ostatniemu elementowi tej podlisty.
Podziałem listy pustej jest lista pusta.
Przykładowe zapytanie i wszystkie odpowiedzi:
?- podziel([1,a,1,2,a,2], P). P = [[1,a,1],[2,a,2]] P = [[1,a,1],[2],[a],[2]] P = [[1],[a,1,2,a],[2]] P = [[1],[a],[1],[2,a,2]] P = [[1],[a],[1],[2],[a],[2]]
podziel([], []). podziel([X|L], [[X|R]|P]) :- podziel(L, X, X, R, P). % podziel(Lista, PierwszyElemPodlisty, PoprzedniElemPodlisty, % ResztaTworzonejPodlisty, ResztaListyPodlist) podziel([], A, A, [], [] ). % koniec, pierwszy = ostatni podziel([X|L], A, A, [], [[X|R]|P]) :- % koniec podlisty podziel(L, X, X, R, P). podziel([X|L], A, _, [X|R], P) :- % kontynuacja podlisty podziel(L, A, X, R, P).
[edytuj] Komputerówka 1 (A.Zaroda, 2005)
Edycje napisu bedziemy reprezentowali jako liste termow, ktore oznaczaja nacisniecie klawisza:
- znak(C)
- znak C
Powoduje wprowadzenie znaku C do napisu na miejscu wskazywaneprzez kursor.
- left
- strzalka w lewo
Powoduje przesuniecie kursora o jedna pozycje w lewo. Nacisniecie strzalki w lewo w chwili, gdy kursor jest na poczatku napisu, jest bledem.
- right
- strzalka w prawo
Jak wyzej, ale kursor przesuwamy w prawo. Nacisniecie strzalki w prawo w chwili, gdy kursor jest na koncu napisu, jest bledem.
- backspace
- klawisz backspace
Powoduje usuniecie znaku znajdujacego sie bezposrednio przed kursorem. Jesli znajdujemy sie na poczatku napisu, nacisniecie backspace jest bledem.
Zdefiniuj predykat edytor/2 tak, by zapytanie edytor(E,S) odnioslo sukces, gdy napis S jest wynikiem edycji E. Predykat powinien dzialac dla zapytan, w ktorych pierwszy argument jest ustalony. Zapytanie edytor(E,S) powinno poniesc porazke, gdy E nie jest poprawnym zapisem edycji.
Pozycja kursora w chwili zakonczenia edycji nie ma wplywu na jej wynik.
Przyklady sukcesow:
?-edytor([],[]). ?-edytor([znak(a),znak(b),left,znak(c)],[a,c,b]). ?-edytor([znak(a),left,znak(b),right,znak(c)],[b,a,c]). ?-edytor([znak(a),znak(b),left,backspace,znak(c)],[c,b]). ?-edytor([znak(a),left,znak(b),left,znak(c)],[c,b,a]).
Przyklady porazek:
?-edytor([znak(a),znak(b)],[a]). ?-edytor([znak(a)],[b]). ?-edytor([znak(a),left,left],_). ?-edytor([znak(a),backspace,right],_). ?-edytor([backspace,znak(a)],_).
- Uwaga 1
- Rozwiazanie powinno zawierac komentarze deklaratywnie opisujace znaczenie predykatow pomocniczych.
- Uwaga 2
- Efektywnosc rozwiazania bedzie miala istotny wplyw na jego ocene.
/*znaczenie predykatu edytor/2 takie, jak w tresci zadania*/ edytor(E,S):-reverse(E,F),edytor(F,X,Y),reverse(X,Z),append(Z,Y,S). /* edytor(C,L,R) zachodzi, jesli po wykonaniu polecen z listy rev(C) dostajemy rev(L)+R, gdzie kursor jest na pierwszym znaku R */ edytor([],[],[]). edytor([znak(X) | T], [X | Y], Z):-edytor(T, Y, Z). edytor([right | T], [H | Y], Z):-edytor(T,Y,[H|Z]). edytor([left | T], Y, [H|Z]):-edytor(T,[H|Y],Z). edytor([backspace | T], Y, Z):-edytor(T,[_ | Y],Z).
[edytuj] Komputerówka 3
kom(L, D) - L lista, D drzewo. Drzewo otwarte D takie, że D odczytane warstwa po warstwie da listę L. Jezeli rozmiar L nie pozwala na skonstruowanie pełnego drzewa, to skonstruowane drzewo powinno być uzupełniane od lewej.
kom2(L, D) - to samo co kom, ale wynikowe drzewo D ma być zwykłym drzewem.
% kom(L, D) - L lista, D drzewo. Drzewo otwarte D takie, że D odczytane warstwa po warstwie da listę L. % jezeli rozmiar L nie pozwala na skonstruowanie pełnego drzewa, to skonstruowane drzewo powinno być uzupełniane od lewej. % kom2(L, D) - to samo co kom, ale wynikowe drzewo D ma być zwykłym drzewem. :- op(500, xfx, [--]). pusta(X--X). put(E, L--[E|Y], L--Y). get(H, [H|T]--X, T--X). kon(L, D) :- kon1(L,[D|T]--T, _). kon1([H|T], L2, L) :- get(E, L2, L3), E=node(X1,H,X2), put(X1, L3, L4), put(X2, L4, L5), kon1(T, L5, L). kon1([], L,L). kon2(L, D) :- kon1(L,D--D, L2), zamknij(L2). zamknij(L--L) :- var(L), !. zamknij(L) :- get(nil, L, L1), zamknij(L1). % kon1(L, L2, L3) :- L to lista z zadania, L2 to lista roznicowa lisci tworzonego drzewa(zmienne), L3 to akumulator. % zamknij(L) - odnosi sukces gdy lista roznicowa L jest listą nil'i.
