Paradygmaty programowania/Ćwiczenia 14: Programowanie w logice w Prologu II: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 6 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 16: Linia 16:
 
Rozważmy program:
 
Rozważmy program:
  
   ''pocz(X, Y) :- p(X, Y).
+
   pocz(X, Y) :- p(X, Y).
 
   pocz(X, X) :- s(X).
 
   pocz(X, X) :- s(X).
 
   p(X, Y) :- sukces(1), q(X), sukces(2), r(Y).
 
   p(X, Y) :- sukces(1), q(X), sukces(2), r(Y).
Linia 25: Linia 25:
 
   r(d).
 
   r(d).
 
   s(e).
 
   s(e).
   sukces(_).''
+
   sukces(_).
  
 
Jaki będzie rezultat po wpisaniu celu pocz(X, Y)? Co się zmieni, gdy wywołanie sukces(1) zastąpimy odcięciem? Co, gdy zastąpimy sukces(2)?
 
Jaki będzie rezultat po wpisaniu celu pocz(X, Y)? Co się zmieni, gdy wywołanie sukces(1) zastąpimy odcięciem? Co, gdy zastąpimy sukces(2)?
Linia 32: Linia 32:
  
 
</div></div>
 
</div></div>
 +
 
===Zadanie 3===
 
===Zadanie 3===
 
Napisać program łączący listy. Czy można go użyć do wytworzenia wszystkich par list, które po złączeniu dają wskazaną listę? Sprawdź.
 
Napisać program łączący listy. Czy można go użyć do wytworzenia wszystkich par list, które po złączeniu dają wskazaną listę? Sprawdź.
Linia 37: Linia 38:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Jest to jeden z klasycznych programów dydaktycznych, wyglądających w Prologu bardzo efektownie; np.
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Jest to jeden z klasycznych programów dydaktycznych, wyglądających w Prologu bardzo efektownie; np.
  
   ''połącz([], X, X).
+
   połącz([], X, X).
   połącz([X | Y1], Z, [X | Y2]) :- połącz(Y1, Z, Y2).''
+
   połącz([X | Y1], Z, [X | Y2]) :- połącz(Y1, Z, Y2).
  
 
</div></div>
 
</div></div>
 +
 
===Zadanie 4===
 
===Zadanie 4===
 
Napisać program wyliczający ostatni element listy.
 
Napisać program wyliczający ostatni element listy.
Linia 46: Linia 48:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Prosta definicja rekurencyjna...
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Prosta definicja rekurencyjna...
  
   ''ostatni([X], X).
+
   ostatni([X], X).
   ostatni([_ | Og], X) :- ostatni(Og, X).''
+
   ostatni([_ | Og], X) :- ostatni(Og, X).
  
 
</div></div>
 
</div></div>
 +
 
===Zadanie 5*===
 
===Zadanie 5*===
 
Napisać program sprawdzający, czy jedna lista jest permutacją drugiej.
 
Napisać program sprawdzający, czy jedna lista jest permutacją drugiej.
Linia 55: Linia 58:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Jak zwykle, rekurencyjnie... Lista pusta jest permutacją listy pustej. Następnie, jeśli X jest permutacją listy Y, to po wstawieniu elementu Z (gdzieś) do X jest to permutacja listy [Z | Y]. A zatem:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Jak zwykle, rekurencyjnie... Lista pusta jest permutacją listy pustej. Następnie, jeśli X jest permutacją listy Y, to po wstawieniu elementu Z (gdzieś) do X jest to permutacja listy [Z | Y]. A zatem:
  
   ''perm([], []).
+
   perm([], []).
 
   perm([Z | Y], W) :- perm(Y, X), wstaw(Z, X, W).
 
   perm([Z | Y], W) :- perm(Y, X), wstaw(Z, X, W).
 +
 
 +
  wstaw(Z, X, W) :- połącz(X1, X2, X), połącz(X1, [Z | X2], W).
  
  wstaw(Z, X, W) :- połącz(X1, X2, X), połącz(X1, [Z | X2], W).''
+
</div></div>
  
</div></div>
 
 
===Zadanie 6===
 
===Zadanie 6===
 
Napisać (jak najprostszy) program sortujący listę liczb całkowitych.
 
Napisać (jak najprostszy) program sortujący listę liczb całkowitych.
Linia 66: Linia 70:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Ten, kto rozwiązał poprzednie zadanie, z tym nie powinien mieć kłopotów. Poniższe rozwiązanie, choć bardzo nieefektywne, jest w bardzo prologowym stylu...
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Ten, kto rozwiązał poprzednie zadanie, z tym nie powinien mieć kłopotów. Poniższe rozwiązanie, choć bardzo nieefektywne, jest w bardzo prologowym stylu...
  
   ''uporządkowana([]).
+
   uporządkowana([]).
 
   uporządkowana([_]).
 
   uporządkowana([_]).
 
   uporządkowana([X, Y | Z]) :- X =< Y, uporządkowana([Y | Z]).
 
   uporządkowana([X, Y | Z]) :- X =< Y, uporządkowana([Y | Z]).
 +
 
 +
  sortuj(X, Y) :- perm(X, Y), uporządkowana(Y).
  
  sortuj(X, Y) :- perm(X, Y), uporządkowana(Y).''
+
</div></div>
  
</div></div>
 
 
===Zadanie 7*===
 
===Zadanie 7*===
 
Napisać efektywny program sortujący listę liczb całkowitych „przez złączanie” (mergesort).
 
Napisać efektywny program sortujący listę liczb całkowitych „przez złączanie” (mergesort).
Linia 78: Linia 83:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Tworzymy najpierw funktory do dzielenia i do złączania list. Sortowanie jest wówczas proste.
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Tworzymy najpierw funktory do dzielenia i do złączania list. Sortowanie jest wówczas proste.
  
   ''podziel([], [], []).
+
   podziel([], [], []).
 
   podziel([X], [], [X]).
 
   podziel([X], [], [X]).
 
   podziel([X, Y | Z], [X | V], [Y | W]) :- podziel(Z, V, W).
 
   podziel([X, Y | Z], [X | V], [Y | W]) :- podziel(Z, V, W).
 
+
 
 
   złącz(X, [], X).
 
   złącz(X, [], X).
 
   złącz([], Y, Y).
 
   złącz([], Y, Y).
 
   złącz([X | A], [Y | B], [X | C]) :- X <  Y, złącz(A, [Y | B], C).
 
   złącz([X | A], [Y | B], [X | C]) :- X <  Y, złącz(A, [Y | B], C).
 
   złącz([X | A], [Y | B], [Y | C]) :- X >= Y, złącz([X | A], B, C).
 
   złącz([X | A], [Y | B], [Y | C]) :- X >= Y, złącz([X | A], B, C).
 
+
 
 
   sortujz([], []).
 
   sortujz([], []).
 
   sortujz([X], [X]).
 
   sortujz([X], [X]).
Linia 93: Linia 98:
 
     sortujz(D1, S1),
 
     sortujz(D1, S1),
 
     sortujz(D2, S2),
 
     sortujz(D2, S2),
     złącz(S1, S2, Y).''
+
     złącz(S1, S2, Y).
  
 
</div></div>
 
</div></div>
 +
 
===Zadanie 8===
 
===Zadanie 8===
 
Dlaczego w rozwiązaniu poprzedniego zadania pierwszy parametr ostatniej klauzuli sortujz jest zapisany jako [X1, X2 | Xo]? Co by się stało, gdyby zamienić go (wraz z pierwszym parametrem podziel) po prostu na X? Jak zaradzić tej niedogodności?
 
Dlaczego w rozwiązaniu poprzedniego zadania pierwszy parametr ostatniej klauzuli sortujz jest zapisany jako [X1, X2 | Xo]? Co by się stało, gdyby zamienić go (wraz z pierwszym parametrem podziel) po prostu na X? Jak zaradzić tej niedogodności?
Linia 101: Linia 107:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Chodzi o jednoznaczność wyboru klauzuli do rezolucji. Jeśli napiszemy po prostu X, to dla list pustych i jednoelementowych będziemy mieli dwie pasujące klauzule; to z kolei spowoduje „pętlenie się” interpretera. Można temu zaradzić, umieszczając odcięcie w dwóch pierwszych klauzulach sortujz:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Chodzi o jednoznaczność wyboru klauzuli do rezolucji. Jeśli napiszemy po prostu X, to dla list pustych i jednoelementowych będziemy mieli dwie pasujące klauzule; to z kolei spowoduje „pętlenie się” interpretera. Można temu zaradzić, umieszczając odcięcie w dwóch pierwszych klauzulach sortujz:
  
   ''sortujz([], []) :- !.
+
   sortujz([], []) :- !.
   sortujz([X], [X]) :- !.''
+
   sortujz([X], [X]) :- !.
  
 
</div></div>
 
</div></div>

Aktualna wersja na dzień 20:37, 25 wrz 2006

Zadanie 1

Rozważmy następujący program:

 p(X, Y) :- q(X, Y).
 p(X, Y) :- q(X, Z), p(Z, Y).
 q(a, b).
 q(b, a).

Jaki będzie rezultat po wpisaniu celu p(a, X)?

Wskazówka:

Zadanie 2

Rozważmy program:

 pocz(X, Y) :- p(X, Y).
 pocz(X, X) :- s(X).
 p(X, Y) :- sukces(1), q(X), sukces(2), r(Y).
 p(X, Y) :- s(X), r(Y).
 q(a).
 q(b).
 r(c).
 r(d).
 s(e).
 sukces(_).

Jaki będzie rezultat po wpisaniu celu pocz(X, Y)? Co się zmieni, gdy wywołanie sukces(1) zastąpimy odcięciem? Co, gdy zastąpimy sukces(2)?

Wskazówka:

Zadanie 3

Napisać program łączący listy. Czy można go użyć do wytworzenia wszystkich par list, które po złączeniu dają wskazaną listę? Sprawdź.

Wskazówka:

Zadanie 4

Napisać program wyliczający ostatni element listy.

Wskazówka:

Zadanie 5*

Napisać program sprawdzający, czy jedna lista jest permutacją drugiej.

Wskazówka:

Zadanie 6

Napisać (jak najprostszy) program sortujący listę liczb całkowitych.

Wskazówka:

Zadanie 7*

Napisać efektywny program sortujący listę liczb całkowitych „przez złączanie” (mergesort).

Wskazówka:

Zadanie 8

Dlaczego w rozwiązaniu poprzedniego zadania pierwszy parametr ostatniej klauzuli sortujz jest zapisany jako [X1, X2 | Xo]? Co by się stało, gdyby zamienić go (wraz z pierwszym parametrem podziel) po prostu na X? Jak zaradzić tej niedogodności?

Wskazówka: