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 4 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 48: 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 57: 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 68: 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 80: 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 95: 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 103: 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: