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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 70: 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).

Wersja z 20:36, 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: