Paradygmaty programowania/Ćwiczenia 14: Programowanie w logice w Prologu II: Różnice pomiędzy wersjami
m (→Zadanie 5*) |
m (→Zadanie 6) |
||
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([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). | ||
− | + | </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)?
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)?
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ź.
Zadanie 4
Napisać program wyliczający ostatni element listy.
Zadanie 5*
Napisać program sprawdzający, czy jedna lista jest permutacją drugiej.
Zadanie 6
Napisać (jak najprostszy) program sortujący listę liczb całkowitych.
Zadanie 7*
Napisać efektywny program sortujący listę liczb całkowitych „przez złączanie” (mergesort).
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?