% Programowanie w logice - laboratorium poniedzialki 12:15-13:45, % Prowadzacy: Artur Zaroda r. a. 2001-2002, lab.6/s.1030 % % Karol Bienkowski % % % Lab 1, 18 lutego 2002 %%%%%%%%%%%%%%%%%%%%%%%%%%%% % lista( [] ). lista( [_|X] ) :- lista( X ). % przyklad zapytania: lista([1,2]). ostatni( [X], X ). ostatni( [_ | Y], X) :- ostatni(Y, X). drugi( [_, Y | _], Y ). po_jednym( [], [] ). po_jednym( [X | Y], [[X] | Z] ) :- po_jednym(Y, Z). % np. po_jednym([1, 2, 3], X). dlugosc_s( [], 0). dlugosc_s( [_ | Y], s(X) ) :- dlugosc_s(Y, X). dlugosc( [], 0 ). dlugosc( [_ | Y], X) :- dlugosc(Y, Z), X is Z + 1. % znajdz(L,K,X) gdy X jest K-tym na L, indeksuje od 1 znajdz( [X | _], 1, X ). znajdz( [_ | Y], L, X ) :- znajdz( Y, K, X), L is K + 1. % zmien (przypisanie w tablicy), np. zmien([10,20,30], 2, 0, M) -> M = [10, 0, 30] zmien( [_ | L], 1, Y, [Y | L] ). zmien( [X | L], N, Y, [X | R] ) :- zmien( L, M, Y, R ), N is M + 1. % l1_9 - podslowo (dziala dla drugiego ustalonego, a pierwszego niekoniecznie) prefix( [], _ ). prefix( [X | Y], [X | Z] ) :- prefix( Y, Z ). suffix( X, X ). suffix( X, [_ | Y] ) :- suffix( X, Y ). podslowo( X, Y ) :- suffix( Z, Y ), prefix( X, Z ). % kolejnosc! (bo glupi prefix) % l1_10 - podciag (dziala dla drugiego ustalonego a pierwszego niekoniecznie) podciag( [], [] ). podciag( X, [_ | Y] ) :- podciag( X, Y ). podciag( [A | X], [A | Y] ) :- podciag( X, Y ). % % Lab 2, 25 lutego 2002 %%%%%%%%%%%%%%%%%%%%%%%%%%%% % Przepisalem od Miska % % Wypisuje napis, np. pisznapis("ala") pisznapis( [] ). pisznapis( [X|L] ) :- put(X), pisznapis(L). % wypisuje napis od konca piszodwrnapis( [] ). piszodwrnapis( [X|L] ) :- piszodwrnapis(L), put(X). % listaliczb( N, L ) - L jest lista liczb od 0 do N % trzeci argument to akumulator listaliczb_( 0, L, L ). listaliczb_( N, L, L1 ) :- M is N - 1, listaliczb_(M, L, [M|L1]). listaliczb( N, L ) :- listaliczb_(N, L, [N]). % nowa wersja z listami roznicowymi listal__( 0, X-X ). %listal__( N, L2 ) :- M is N - 1, listal__(M, L1), wstawrk(N, L1, L2). listal__( N, A-B ) :- M is N - 1, listal__(M, A-[N|B]). listal_r( N, L ) :- listal__(N, L-[]). % funkcje do roznicowych pustar( L-L ). zamknijr( L-[], L ). wstawrp( X, A-B, [X|A]-B ). wstawrk( X, A-[X|B], A-B ). scalr( A-B, B-C, A-C ). usunrp( X, [X|A]-B, A-B ). %testuj( X ) :- pustar(A), wstawrp(3, A, B), wstawrp(2, B, C), wstawrk(5, C, D), zamknijr(D, X). % odwroc( X, Y ) - X to odwrocone Y %append( [], L, L ). %append( [X|L], L1, [X|L2] ) :- append(L, L1, L2). odwroc( [], [] ). odwroc( [X|L], L1 ) :- odwroc(L, L2), scal(L2, [X], L1). % dlugosc listy z akumulatorem dlugosc_pom( [], N, N ). dlugosc_pom( [_|L], A, N ) :- B is A + 1, dlugosc_pom(L, B, N). dlugosc_ak( L, N ) :- dlugosc_pom(L, 0, N). %% tlumaczenie tego na jezyk funk: %% dlugosc_pom([], N) = N %% dlugosc_pom([_,L), A) = dlugosc_pom(L, A+1) %% dlugosc_ak(L,N) = dlugosc_pom(L, 0) % fast odwroc % fodwroc_pom przezuca elementy z pierwszego na ostatni przy okazji odwracajac kolejnosc % drugi argument _pom to akumulator % fodwroc_pom(X, Y, Z) oznacza, ze rev(X) + Y = Z fodwroc_pom([], L, L). fodwroc_pom([X|L], L2, L1) :- fodwroc_pom(L, [X|L2], L1). fodwroc(L1, L2) :- fodwroc_pom(L1, [], L2). % wersja z listami roznicowymi (tak naprawde to to samo co fodwroc) fodwroc__([], W-W). fodwroc__([X|L], A-B) :- fodwroc__(L, A-[X|B]). fodwroc_r(L, W) :- fodwroc__(L, W-[]). % dodatkowy parametr na ktorym jest liczona liczba porownan (AZ) uzgodnij(L, L). insert(X, [Y|L], L1, N) :- X > Y, insert(X, L, L2, M), N is (M + 1), uzgodnij(L1, [Y | L2]), !. insert(X, L, [X|L], 0). insortlicz([], [], 0). insortlicz([X], [X], 0). insortlicz([X|L], L2, N) :- insortlicz(L, L1, K), insert(X, L1, L2, M), N is (K+M). insort(L1, L2) :- insortlicz(L1, L2, _Z). %selsort([], []). %selsort(L1, L2) :- selmax(L1, LY, Y), selsort(LY, LZ), uzgodnij(L2, LZ). % dokonczyc selsort (mozna) % % Lab 3, 4 marca 2002 %%%%%%%%%%%%%%%%%%%%%%%%%%%% % % quicksort % - partition(lista, element, l1, l2) - l1 (<=x) i l2 (>x) to rozrzucone listy % - quicksort(lista, posort) % zrobic laczenie list (w quicksortcie) bez appenda, tylko z akumulatorem % (cos w stylu fodwroc) % TECHNIKA Z AKUMULATOREM, akumulator przechowuje dotad obliczony wynik % na razie nie dziala jak sa powtarzajace sie elementy na listach scal([], R, R). scal([X | L], R, [X | S]) :- scal(L, R, S). partition([], _X, [], []). partition([Y | L], X, [Y | L1], L2) :- Y < X, partition(L, X, L1, L2). partition([Y | L], X, [Y | L1], L2) :- Y = X, partition(L, X, L1, L2). partition([Y | L], X, L1, [Y | L2]) :- Y > X, partition(L, X, L1, L2). quicksort([], []). quicksort([X | L], S) :- partition(L, X, L1, L2), quicksort(L1, S1), quicksort(L2, S2), scal(S1, [X | S2], S). % partition z akumulatorem % partition_pom(L, E, A1, L1, A2, L2) : Ax - akumulatory, Lx - docelowe, L - cala l, E - elt roz. % partiotion_pom odwraca listy partition_pom([], _E, A1, A1, A2, A2). partition_pom([X|L], E, A1, L1, A2, L2) :- X < E, partition_pom(L, E, [X|A1], L1, A2, L2). partition_pom([X|L], E, A1, L1, A2, L2) :- X = E, partition_pom(L, E, [X|A1], L1, A2, L2). partition_pom([X|L], E, A1, L1, A2, L2) :- X > E, partition_pom(L, E, A1, L1, [X|A2], L2). partition_ak(L, E, L1, L2) :- partition_pom(L, E, [], L1, [], L2). % quicksort z akumulatorem (nie uzywa part z akum, ale moze go uzyc) % w akumulatorze trzymam dotad posortowany kawalek quicksort_pom([], A, A). quicksort_pom([X|L], A, S) :- partition(L, X, L1, L2), quicksort_pom(L2, A, S2), quicksort_pom(L1, [X|S2], S). quicksort_ak(L, S) :- quicksort_pom(L, [], S). % TERMY: % node(wartosc, lewePoddrzewo, prawePoddrzewo) - wezel drzewa % nil - lisc % node(1, node(2, nil, nil), node(3, nil, nil)) % drzewo, sukces kiedy parametr jest drzewem drzewo(nil). drzewo(node(_, LP, PP)) :- drzewo(LP), drzewo(PP). % infiksowo(d, l) jezeli l to infiksowa lista wszystkich wartosci drzewa % trzeba by to zrobic z akumulatorem infiksowo(nil, []). infiksowo(node(W, LP, PP), LI) :- infiksowo(LP, LLI), infiksowo(PP, PLI), scal(LLI, [W | PLI], LI). % wysokosc drzewa max(A, B, B) :- A < B. max(A, A, A). max(A, B, B) :- A > B. wysokosc(nil, 0). wysokosc(node(_, LP, PP), N) :- wysokosc(LP, A), wysokosc(PP, B), max(A, B, M), N is M + 1. % wstaw_bst(d1, x, d2) wstawiam x do drzewa d1, otrzymuje d2 % jezeli jest juz w drzewie to nie wstawiam wstaw_bst(nil, X, node(X, nil, nil)). wstaw_bst(node(W, L, P), X, node(W, L1, P)) :- X < W, wstaw_bst(L, X, L1). wstaw_bst(node(W, L, P), X, node(W, L, P1)) :- X > W, wstaw_bst(P, X, P1). wstaw_bst(node(W, L, P), W, node(W, L, P)). % czy dane drzewo jest bst (nie dopuszcza duplikatow, wartosci > -100 i < 100 maks_drz(nil, -100). maks_drz(node(W, LP, PP), W) :- maks_drz(LP, LM), maks_drz(PP, PM), W > PM, W > LM. maks_drz(node(W, LP, PP), PM) :- maks_drz(LP, LM), maks_drz(PP, PM), PM > LM, PM > W. maks_drz(node(W, LP, PP), LM) :- maks_drz(LP, LM), maks_drz(PP, PM), LM > PM, LM > W. min_drz(nil, 100). min_drz(node(W, LP, PP), W) :- min_drz(LP, LM), min_drz(PP, PM), W < PM, W < LM. min_drz(node(W, LP, PP), PM) :- min_drz(LP, LM), min_drz(PP, PM), PM < LM, PM < W. min_drz(node(W, LP, PP), LM) :- min_drz(LP, LM), min_drz(PP, PM), LM < PM, LM < W. bst(nil). bst(node(W, LP, PP)) :- bst(LP), bst(PP), max_drz(LP, LM), min_drz(PP, PM), LM < W, PM > W. % tak dla zabawy %append_pom( %append_pom( %append_ak(L, P, W) :- append_pom( % % Lab 4, 11 marca 2002 %%%%%%%%%%%%%%%%%%%%%%%%%%%% % % pomocna rzecz: `ledit | sicstus` % potem [z]. % potem testuj(X, 7). % UWAGA: na poprzednim labie node byl (Wart, LewePoddrz, Prawe...) a teraz (Lp, W, Pp) % bst_sort(L1, L2) - l2 to posortowana l1 przy pomocy sortowania bst wstaw_pom([], D, D). wstaw_pom([X|L], A, D) :- wstaw_bst(A, X, B), wstaw_pom(L, B, D). wstaw_wszystkie(L, D) :- wstaw_pom(L, nil, D). bst_sort(L, S) :- wstaw_wszystkie(L, BST), infiksowo(BST, S). %testuj(X) :- bst_sort([1,3,2], X). % uzycie: przyklad_bst(X). przyklad_bst(node(node(node(nil,2,nil),3,node(nil,5,nil)),7,node(nil,8,nil))). % 7 % 3/ \8 % 2/ \5 przyklad_bst2(node(node(node(node(nil,1,nil),2,nil),3,node(nil,5,nil)),7,node(nil,8,node(nil,9,nil)))). % 7 % 3/ \8 % 2/ \5 \9 % 1/ % usun_bst(D1, X, D2) - sukces gdy D2 to D1 bez X-a (gdy nie ma Xa to porazka) % dziala, gdy w drzewie rozne elementy usun_max(node(nil, X, nil), nil, X). usun_max(node(L, X, P), node(L1, X, P), Y) :- usun_max(L, L1, Y). usun_bst(node(nil, X, nil), X, nil). usun_bst(node(L, S, P), X, node(L1, S, P)) :- X < S, usun_bst(L, X, L1). usun_bst(node(L, S, P), X, node(L, S, P1)) :- X > S, usun_bst(P, X, P1). usun_bst(node(nil, X, P), X, P). usun_bst(node(L, X, nil), X, L). % obejdzie sie bez tego usun_bst(node(L, X, P), X, node(L1, LMAX, P)) :- usun_max(L, L1, LMAX). % L niepuste %testuj(X, Y) :- przyklad_bst(D), usun_bst(D, Y, X). % czy przypadkiem usun i wstaw nie moglyby byc jednym predykatem? % przeciez to operacje odwrotne. % trudno sie to robi % wstaw_bst(X, E, Y) - bylo, ze Y zmienne (czy sie da ze X nieustalone, albo E nieustalone?) % liscie(Drzewo, Ak) (z akumulatorem np., tzn. chodze od L do P % i dolaczam sobie na koncu swojej listy) % odciecie jest WAZNE! % uzgodnij(Lp, node(_,_,_) i dla Pp wyeliminuje odciecie (uzgodnij(X,X).) liscie_pom(nil, Ak, Ak). liscie_pom(node(nil, X, nil), Ak, [X|Ak]) :- !. liscie_pom(node(Lp, _, Pp), Ak, Wyn) :- liscie_pom(Pp, Ak, WynP), liscie_pom(Lp, WynP, Wyn). liscie(Drzewo, ListaLisci) :- liscie_pom(Drzewo, [], ListaLisci). %testuj(X) :- przyklad_bst(D), liscie(D, X). % nie wyszlo mi bfs... dfs_pom([nil], A, A). dfs_pom([nil|Wie], A, B) :- dfs_pom(Wie, A, B). dfs_pom([node(L, S, P)], A, Wyn) :- dfs_pom([L,P], [S|A], Wyn). dfs_pom([node(L, S, P)|Wie], A, Wyn) :- dfs_pom([L,P|Wie], [S|A], Wyn). dfs(D, L) :- dfs_pom([D], [], Lrev), odwroc(L, Lrev). %testuj(X) :- przyklad_bst2(D), bfs(D, X). % bfs(Drzewo, ListaWezlow), prawie jak liscie - wszystkie wezly w porzadku BFS % bfs to to z ko % to jest dfs (do poprawienia)! % najlatwiej naprawic wrzucajac appendy w dwoch miejscach % POMYSL: liste do zrobienia trzymam na pierwszym parametrze i na drugim % (tak, ze dobrze jest pierwsza skonkatenowana z odwrocona druga) bfs_pom([], [], Ak, Ak). bfs_pom([], R, Ak, Wyn) :- odwroc(R, RR), bfs_pom(RR, [], Ak, Wyn). bfs_pom([nil], R, Ak, Wyn) :- bfs_pom([], R, Ak, Wyn). bfs_pom([nil|W], R, Ak, Wyn) :- bfs_pom(W, R, Ak, Wyn). bfs_pom([node(L, S, P)], R, Ak, Wyn) :- bfs_pom([], [P,L|R], [S|Ak], Wyn). bfs_pom([node(L, S, P)|W], R, Ak, Wyn) :- bfs_pom(W, [P,L|R], [S|Ak], Wyn). bfs(D, L) :- bfs_pom([D], [], [], LL), odwroc(LL, L). %testuj(X) :- przyklad_bst2(D), bfs(D, X). % Hint AZ: implementacja listy a.X. Dodadanie na liste to ukonkretnienie X. % reprezentacja kolejki: para (calosc, zmienna - koniec listy) % Pytanie: czy to to samo co moje czy nie? Chyba nie. % % Lab 5, 18 marca 2002 %%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Grafy - graf to lista krawedzi (np. krawedz(x,y) -> k(x,y)) przyklad_grafu([k(a,b), k(b,a), k(a,c), k(c,a), k(b,c), k(c,b)]). % dobry_graf (kazdy wierzcholek jest parzystego stopnia), jest niezorientowany % tzn. jezeli jest k(x,y) to jest i k(y,x) % negacja: \+ % odciecia sa tu wazne usun_zX([], _, []). % usuwa te pary w ktorych jest X na pierwszej pozycji usun_zX([k(X,_)|R], X, S) :- usun_zX(R, X, S), !. usun_zX([k(Y,D)|R], X, [k(Y,D)|S]) :- usun_zX(R, X, S). parzyscie([], _). parzyscie([k(X,_)|R], X) :- nieparzyscie(R, X), !. parzyscie([k(_,_)|R], X) :- parzyscie(R, X). nieparzyscie([k(X,_)], X). nieparzyscie([k(X,_)|R], X) :- parzyscie(R, X), !. nieparzyscie([k(_,_)|R], X) :- parzyscie(R, X). dobry([]). dobry([k(X,_)|R]) :- nieparzyscie(R, X), usun_zX(R, X, Y), dobry(Y). %testuj :- przyklad_grafu(X), dobry(X). % Graf moze byc reprezentowany jako zbior predykatow (reprezentacja klauzulowa) % np. k(a,b). k(b,c). k(b,d). k(c,e). k(e,a). % droga(x,y,l) mozna przejsc od x do y za pomoca l droga(X, X, []). droga(X, Y, [k(X,Z)|L]) :- k(X, Z), droga(Z, Y, L). % droga niepetlaca sie (sie mi jednak petli :[) nalezy(X,[X]). nalezy(X,[_|Y]) :- nalezy(X,Y). drogacykl_pom(X, X, _, []). drogacykl_pom(X, Y, Byly, [k(X, Z)|L]) :- k(X, Z), drogacykl_pom(Z, Y, [k(X, Z)|Byly], L), \+ nalezy(k(X, Z), Byly). drogacykl(X,Y,L) :- drogacykl_pom(X, Y, [], L). % % Lab 6, 25 marca 2002 %%%%%%%%%%%%%%%%%%%%%%%%%%%% % % ciag liczb od 1 do 9, tak ze miedzy dwoma n stoi n-liczb, np. % 1 4 1 3 1 4 2 3 .... % lista ma byc dlugosci 3 * 9 = 27 % Schemat: generator-test % moze byc generator wszystkich i test odsiewa, i plynnie % mozna przejsc do testowania w generatorze % C - dlugosc listy na ktorej mam badac % UWAGA na odciecie. Jezeli nie_da_sie zdefiniuje, to sie nie % uzgodni i odciecie nie zadziala, wiec sie zapetli juz_nie_ma(_, _, -1) :- nicoooo. juz_nie_ma(_, [], 0). juz_nie_ma(N, [_|X], C) :- C > 0, D is C - 1, juz_nie_ma(N, X, D). sprawdz_1(N, 0, [N|X], C) :- !, D is C - 1, juz_nie_ma(N, X, D). sprawdz_1(N, K, [_|X], C) :- D is C - 1, L is K - 1, sprawdz_1(N, L, X, D). sprawdz_2(N, 0, [N|X], C) :- !, D is C - 1, sprawdz_1(N, N, X, D). sprawdz_2(N, K, [_|X], C) :- D is C - 1, L is K - 1, sprawdz_2(N, L, X, D). sprawdz(N, [N|X], C) :- D is C - 1, sprawdz_2(N, N, X, D). sprawdz(N, [_|X], C) :- D is C - 1, sprawdz(N, X, D). sprawdz_do(0, _). sprawdz_do(N, X) :- sprawdz(N, X, 27), M is N - 1, sprawdz_do(M, X). ciag27(X) :- sprawdz_do(9, X). % inna metoda: % generujemy 27 elementowa liste zmiennych % piszemy predykat, ze ok % (u mnie dwa w jednym) % lamiglowka - znajdz cyfre dla litery (najlepiej miec zmienne S, P, E, ...) % SPEED % + LIMIT % ------- % FIFTY