Kontrolltöö loogilises programmeerimises 23.10.98, I

1. 1. Sugulassuhted on defineeritud lausetega:

poeg(okeanos, uranos).
poeg(koios, uranos).
poeg(kronos, uranos).
tytar(demeter, kronos).
poeg(atlas, iapetos).
poeg(iapetos, gaia).

jne

(semantika: poeg(Poeg, Vanem), tytar(Tytar, Vanem). )

Defineerida selle põhjal minimaalse arvu lausetega predikaat meessoost(Isik) ja predikaat järglane(Jarglane, Isik).

Lahendus: meessoost on kõik pojad; need, kelle kohta pojaksolemise fakti ei ole esitatud , tuleb defineerida "jõuga":

meessoost(Isik):-

poeg(Isik,_).
meessoost(uranos).

Järglased on kõik lapsed ja laste järglased:

laps(Laps,Vanem):-

poeg(Laps, Vanem).
laps(Laps,Vanem):-
tytar(Laps, Vanem).
jarglane(Jarglane, Eellane):-
laps(Jarglane, Eellane).
jarglane(Jarglane, Eellane):-
laps(Laps1, Eellane),
jarglane(Jarglane, Laps1).

2. Defineeri predikaat : tagurpidi(Nimistu, Tagurpidi) , mis muudab nimistu elementide järjekorra (hea lahendus peaks olema lõpprekursiivne ja töötama mõlemas suunas, s.t. ka siis, kui antud on nimistu Tagurpidi.

Elementaarne lahendus (ei ole lõpprekursiivne):

tagurpidi([],[]).

tagurpidi([Pea|Keha], Tagurpidi):-
tagurpidi(Keha, Algus),
append(Algus, [Pea], Tagurpidi).

Predikaat append(Nimistu1, Nimistu2, Nimistu1+Nimistu2) ühendab kaks nimistut üheks nimistuks ja on defineeritud moodulis util.pro

Parem (lõpprekursiivne) lahendus:

tagurpidi(Nimistu, Tagurpidi):-

poora1(Nimistu, [], Tagurpidi).
poora1([], Tagurpidi, Tagurpidi).
poora1([Pea|Keha], Pooratud, Tulemus):-
poora1(Keha, [Pea|Pooratud], Tulemus).

Abipredikaadi poora1 liidab samm sammult esimese argumendi (nimistu veel pöörata olev osa) elemendi teise argumendi (juba pööratud osa) esimeseks elemendiks; kui esimene argument on tühi (kogu nimistu on pööratud), saadakse kolmanda argumendi abil tulemus.

3. Kaart on esitatud kahe linna vahelist kaugust esitavate lausetega:

tee(paide, tapa, 49).
tee(jogeva, mustvee, 40).
tee(tapa, rakvere, 28).
tee(rakvere, jogeva, 72).
tee(tallinn, rakvere,97).
tee(rakvere, kohtla_järve,73).
tee(kohtla_järve, narva,50).
tee(tallinn, paide, 97).
tee(tallinn,rakvere,96).
tee(paide, poltsamaa, 39).
tee(poltsamaa, tartu, 60).
tee(poltsamaa, jogeva, 27).
tee(jogeva, mustvee, 40).
tee(kohtla_järve, mustvee, 76).

jne

Koosta programm kahe antud linna vahel sellise tee (esitada linnad ja kogu tee pikkus) leidmiseks, millel läbitakse minimaalne arv vahelinnu.

 

Kontrolltöö loogilises programmeerimises 23.10.98, II

1. 1. Sugulassuhted on defineeritud lausetega:

poeg(okeanos, uranos).
poeg(koios, uranos).
poeg(kronos, uranos).
tytar(demeter, kronos).
poeg(atlas, iapetos).
poeg(iapetos, gaia).

jne

(semantika: poeg(Poeg, Vanem), tytar(Tytar, Vanem) . )

Koosta programm antud isiku kõigi sugulaste nimistu leidmiseks, s.t predikaat sugulased(Isik, Sugulased) , kus Sugulased on nimistu kõigist Isiku sugulastest. Sugulasteks loetakse kaks isikut siis ja ainult siis, kui neil leidub mingi yhine esivanem.

Lahendus. Järglased on kõik lapsed ja laste järglased, aga lapsed on kõik pojad ja tytred; järglasi teades on lihtne määrata isiku sugulased:

laps(Laps,Isik):-

poeg(Laps, Isik).
laps(Laps, Isik):-
tytar(Laps, Isik).
jarglane(Jarglane, Isik):-
laps(Jarglane, Isik).
jarglane(Jarglane, Isik):-
laps(Laps1, Isik),
jarglane(Jarglane, Laps1).
sugulane(Isik, Sugulane):-
jarglane(Isik, Eellane),
jarglane(Sugulane, Eellane).
sugulased(Isik, Sugulased):-
findall(Sugulane, sugulane(Isik, Sugulane),Sugulased).

2. Koosta programm nimistu elementide esinemise kordsuse leidmiseks, näiteks päringu

? kordseid([a,2b,a,4,2b, 2b], Kordseid).

sisestamisel vastaks programm

Kordseid = [[a,2],[2b,3],[4,1]]

Lahendus. Defineerime algul abipredikaadi, mis leiab elemendi nimistus esinemise kordsuse:

kordsus(X,[],0):-!.
kordsus(X,[X],1):-

!.
kordsus(X,[Y],0):-
not(X=Y),
!.
kordsus(X,[X|Z],N):-
kordsus(X,Z,N1),
N is N1+1.
kordsus(X,[Y|Z],N):-
not(X=Y),
kordsus(X,Z,N).

Kordsuste nimistu leidmiseks leiame esimese elemendi kordsuse ja kasutame sama predikaati taas; et hiljem taas ei tuleks sama elementi hakata uurime, eemaldame ta järelejäänud nimistust (NB! Amzi-Prologi util.pro. util.plm-moodulites defineeritud remove(Elem, Nimistu, Nimistu1) on vigane!) :

kordseid([],[]).
kordseid([X],[[X,1]]):-

!.
kordseid([X|Y],[[X,N]|Z]):-
kordsus(X,[X|Y],N),
eemalda(X,[X|Y],Z1),
kordseid(Z1,Z).
eemalda(X,[X],[]):-
!.
eemalda(X,[X|Y],Z):-
eemalda(X,Y,Z),
!.
eemalda(X,[Y|Z],[Y|Z1]):-
eemalda(X,Z,Z1).

3. Koosta programm, mis liidab mod 2 järgi ( Å ) liikmeti kaks suvalise pikkusega bitijada, näiteks

? liida([0,1,1,0],[1,0], Tulemus).

sisestamisel saadakse

Tulemus = [0,1,0,0] .

Kuna liitma tuleb hakata viimastest bittidest ettepoole ja nimistute pikkus võib olla erinev, võib selle ylesande lahendamiseks (näiteks) pöörata algul mõlemad nimistud tagurpidi (vt ülalesitatud predikaati tagurpidi), liita nimistud ja pöörata tulemus taas tagurpidi (teha ise).