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 7 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 2: Linia 2:
 
Rozważmy następujący program:
 
Rozważmy następujący program:
  
   ''p(X, Y) :- q(X, Y).
+
   p(X, Y) :- q(X, Y).
 
   p(X, Y) :- q(X, Z), p(Z, Y).
 
   p(X, Y) :- q(X, Z), p(Z, Y).
 
   q(a, b).
 
   q(a, b).
   q(b, a).''
+
   q(b, a).
  
 
Jaki będzie rezultat po wpisaniu celu p(a, X)?
 
Jaki będzie rezultat po wpisaniu celu p(a, X)?
Linia 12: Linia 12:
  
 
</div></div>
 
</div></div>
 +
 
===Zadanie 2===
 
===Zadanie 2===
 
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 24: 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 31: 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 36: 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 45: 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 54: 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 65: 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 77: 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 92: 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 100: 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: