[ Pobierz całość w formacie PDF ]
.1: Wzorce określające łączność operatorów w Prologu.Lacznosc = yfx ;NoJak widać operator+występuje zarówno w wersji prefixowej jak i infixowej.Terazspróbujmy wyświetlić informacje o wszystkich wbudowanych operatorach?- current_op(Priorytet, Lacznosc, Operator).Priorytet = 1150,Lacznosc = fx,Operator = (volatile) ;Priorytet = 400,Lacznosc = yfx,Operator = 1 obliczamy najpierw liczby Fibonacciego dlaN - 1 oraz N - 2 i używając tych rezultatów pośrednich obliczamy ostatecznie wartośćdla N.8.3.2 Z dołu do góryMetoda obliczeniowa  z dołu do góry (ang.bottom up computation) rozpoczyna odznanych faktów a następnie rozszerza je w oparciu o posiadane reguły i fakty tak długoaż nie zostanie rozwiązany problem wyjściowy.W ogólności metoda ta jest mniej efektywna w porównaniu z metodą  z góry na dółco spowodowane jest generowaniem dużej ilości faktów nie mających nic wspólnego zposzukiwanym rozwiązaniem.Z tego powodu w Prologu używana jest metoda z  góryna dół choć możliwe jest  symulowanie metody  z dołu do góry przy wykorzystaniudodatkowych zmiennych  właśnie poznanych akumulatorów.Działanie takie ma o tylesens, że często funkcje wykorzystujące akumulator (czyli działające  z dołu do góry )okazują się wydajniejsze od funkcji  z góry na dół.fibBU(N,X) :- fibBU(0,0,1,N,X).fibBU(N,X,_,N,X)fibBU(N1,X1,X2,N,X) :- N1Y.Zostanie ukonkretniona zmiennaList1=[1,2]." Ponieważ Prolog zawsze szuka odpowiedzi posuwając się jak najbardziej w głąb,aż do znalezienia pierwszego rozwiązania rozpatrywanego problemu, więc w tymprzypadku oznacza to, że nie zostanie wypróbowana druga z reguł określającychswap.Dodatkowo symbol odcięcia gwarantuje ustalenie zmiennejList1aż dokońca rozwiązywania zadanego sortowania.Teraz program musi poradzić sobie zzapytaniem?- bSort([1,2],Sorted).( ), co oznacza, że znów  uruchomi funkcjęswap." Dokładniej, po ukonkretnieniu zmiennychXiZmamy?- swap([1,2|[]],[2,1|[]]) :- 1>2.zatem brana jest pod uwagę druga regułaswap([1|[2]],[1|Rest1]) :- swap([2],Rest1).Zgodnie z dyskusją sortowania listy jednoelementowej, udzielona zostanie odpo-wiedz
No, zatem zastosowana zostanie druga reguła dotyczącabSortdla listy[1,2]w punkcie ( ).Oznacza to, że otrzymamySorted=[1,2], co jest jednocześnie szu-kanym wynikiem.Programowanie w logice.Prolog �2007 2009 by P.Fulmański (ostatnia modyfikacja: 18 maja 2009)86 ROZDZIAA
9.SORTOWANIE9.3 Sortowanie przez wstawianieSortowanie przez wstawianie przypomina postępowanie osoby układającej książki napółce.Wybieramy jedną książkę i szukamy (począwszy od miejsca w którym ta książkasię znajduje aż do pierwszej książki od lewej) takiego miejsca aby tak książka była wyższalub równa od innej książki i jednocześnie mniejsza od kolejnej.Jeśli znajdziemy takiemiejsce to wstawiamy w nie wybraną książkę i bierzemy kolejną, która za nią występo-wała.Jeśli takiego miejsca nie znajdziemy to pozostawiamy ją na dotychczasowej pozycjii bieżemy książkę następną.Niech {ai}i=1,.,n będzie sortowanym ciągiem.1.Niech j = 2.2.Porównywać element aj, po kolei, ze wszystkimi elementami ai, i = j - 1,., 1 domomentu, gdy zostanie znaleziony taki element ai, dla którego zachodzić będzienierówność ai d" aj.Wówczas element aj należy usunąć z jego dotychczasowejpozycji, wstawić pomiędzy elementy ai oraz ai+1 i przejść do kroku następnego.3.Zwiększyć j o jeden.4.Jeśli j > n to przejdz
do 6.5.Powrót do 2.6.Koniec.Implementacja algorytmu w Prologu wygląda następująco.iSort([],[]).iSort([X|Tail],Sorted) :- iSort(Tail,SortedTail), insert(X,SortedTail,Sorted).insert(X,[Y|Sorted],[Y|Sorted1]) :- X>Y, !, insert(X,Sorted,Sorted1).insert(X,Sorted,[X|Sorted]).Zacznijmy analizę od sortowania listy jednoelementowej:?- iSort([1],Sorted)." Pierwsza w kodzie programu odpowiednia dla tego przypadku reguła, toiSort([1|[]],Sorted) :- iSort([],SortedTail),insert(1,SortedTail,Sorted)." Prolog próbuje zatem odpowiedzieć na pytanie?- iSort([],SortedTail).co udaje się dzięki pierwszej regule w programie.Otrzymujemy w ten sposóbpodstawienieSortedTail=[]." Kolejne zapytanie, jakie napotyka program, to term?- insert(1,[],Sorted).Programowanie w logice.Prolog �2007 2009 by P.Fulmański (ostatnia modyfikacja: 18 maja 2009)9.4.SORTOWANIE PRZEZ A

CZENIE 87Z uwagi na argumenty, jakie już się znajdują wewnątrz tej funkcji, pierwsza reguładlainsertnie jest spełniona, druga zwraca zaś zmiennąSorted=[1|[]].Jejukonkretnienie powoduje spełnenie pierwszej reguły dlaiSorti jednocześnie jestona wypisywanym na ekran wynikiem.Sortowanie listy dwuelementowej, czyli pytamy?- iSort([1,2],Sorted)." Znów, pierwsza reguła, którą Prolog może dopasować do zapytania, toiSort([1|[2]],Sorted) :- iSort([2],SortedTail),insert(1,SortedTail,Sorted)." Pierwsze napotkane w tej regule zapytanieiSort([2],SortedTail).już rozpa-trywaliśmy.ZmiennaSortedTailzostaje skonkretyzowana listą[2].Prolog kon-tynuuje regułę, stąd pojawia się pytanie?- insert(1,[2],Sorted).które prowadzi do skorzystania z regułyinsert(1,[2|[]],[2|Sorted1]) :- 1>2,!,insert(1,[],Sorted1).która oczywiście nie jest w tym przypadku spełniona [ Pobierz całość w formacie PDF ]