Programozási paradigmák, nagyzárthelyi, 2000. március 27. 17.15--18.45
Munkaidő: 90 perc, összpontszám: 60
Prolog, ,,A'' csoport (30 pont)
A Prolog eljárás megírását kérő feladatokban a jegyzetben szereplő összes
Prolog eljárás (akár beépített, akár a jegyzetben definiált) szabadon
használható. Ha segédeljárást definiál, feltétlenül adjon meg hozzá
fejkommentet; enélkül a megoldás nem értékelhető, vagy csak csökkentett
pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra;
használjon jobbrekurziót, kerülje a felesleges hívásokat (pl. az append
eljárás felesleges használatát)!
1. Írja fel az alábbi kifejezések alapstruktúra-alakját (azaz szintaktikus
édesítőszerek nélküli formáját) vagy rajzolja fel a hozzájuk tartozó
fastruktúrákat! Állapítsa meg, hogy a két kifejezés egyesíthető-e, és ha
igen, milyen behelyettesítéssel! (3 pont)
.(A*B+C, [1*C]) [X+2,X]
Megoldás:
.(+(*(A,B),C), .(*(1,C), [])) .(+(X,2),.(X,[]))
Egyesítés: A = 1, B = C = 2, X = 1*2
2. Egy célsorozat keresési fája egy olyan irányított gráf, amelynek
csúcsaiban célsorozatok vannak és két csúcs között akkor megy él, ha a
kiinduló csúcs célsorozatából egyetlen (Prolog) redukciós lépéssel
eljuthatunk a cél csúcs célsorozatába. Az élek a redukció során
alkalmazott klóz sorszámával vannak címkézve. A fa gyökerében a teljes
kiindulási célsorozat van, az üres célsorozatot egy négyzettel jelöljük.
Rajzolja fel az alábbi célsorozat keresési fáját! A fa nem üres
célsorozatot tartalmazó leveleinél jelezze a visszalépést! (A select
és a write szavakat rövidítheti (s ill. w).) (7 pont)
| ?- select(1, A, [2,3]), write(A).
A select/3 eljárás definíciója:
(1) select(E, [E|L], L).
(2) select(E, [X|T], [X|L]) :-
select(E, T, L).
Megoldás:
3. Írjon olyan Prolog eljárást, amely előállítja egy lista első N elemének
elhagyásával keletkező listát! (7 pont)
% dob(N, L, M): M az L lista első N elemének elhagyásával áll elő.
% N és L adott, bemenő paraméter, M kimenő paraméter.
| ?- dob(2, [1,2,3], L). L = [3] ? ; no
| ?- dob(-1, [1,2,3], L). no
| ?- dob(8, [1,2,3], L). no
Megoldás:
dob(0, L0, L) :- !, L = L0.
dob(N, [_|T], M) :-
N > 0,
N1 is N-1,
dob(N1, T, M).
4. Írjon olyan Prolog eljárást, amely egészek egy listáját előjelesen
rendezi! Egy lista előjelesen rendezett, ha a benne előforduló negatív
elemek megelőzik a nem negatív elemeket. A rendezés legyen konzervatív,
azaz két elem sorrendjét ne változtassa meg, ha azonos az előjelük! (13 pont)
% jelrend(L, R): Az L lista konzervatív előjeles rendezettje R.
% L adott, bemenő paraméter, R kimenő paraméter.
| ?- jelrend([1,2,-3,5,-4], R). R = [-3,-4,1,2,5] ? ; no
Első megoldás:
jelrend(L, R) :-
jelrend(L, N, NN),
append(N, NN, R).
% jelrend(L, N, NN): Az L lista negatív elemeinek listája N, nemnegatív
% elemeinek listája NN.
%
% Ha valaki nem érti mit csinál a vágó, az kiszedheti, de akkor a
% harmadik klózban kikommentezett részt vissza kell rakni. Ilyenkor
% az N = [E|N1] egyesitest a klóz fejébe lehet írni.
jelrend([], [], []).
jelrend([E|L], N, NN) :-
E < 0, !,
N = [E|N1],
jelrend(L, N1, NN).
jelrend([E|L], N, [E|NN]) :-
/* E >= 0, */
jelrend(L, N, NN).
Második megoldás:
% Ez a megoldás kicsit hatékonyabb, mert elkerüli az append meghívását.
% Mindezt azon az áron, hogy a segédeljárás gyűjtőargumentum-párokkal dolgozik.
jelrend1(L, R) :-
jelrend1(L, R, X, X, []).
% jelrend1(I, L, LT, R, RT): I lista negatív elemeinek listája L-LT,
% a nem negatív elemeinek listája R-RT.
jelrend1([], L, L, R, R).
jelrend1([H|T], L, LT, R, RT) :-
H < 0, !,
L = [H|L1],
jelrend1(T, L1, LT, R, RT).
jelrend1([H|T], L, LT, [H|R1], RT) :-
/* H >= 0, */
jelrend1(T, L, LT, R1, RT).
Programozási paradigmák, nagyzárthelyi, 2000. március 27. 17.15--18.45
Munkaidő: 90 perc, összpontszám: 60
Prolog, ,,B'' csoport (30 pont)
A Prolog eljárás megírását kérő feladatokban a jegyzetben szereplő összes
Prolog eljárás (akár beépített, akár a jegyzetben definiált) szabadon
használható. Ha segédeljárást definiál, feltétlenül adjon meg hozzá
fejkommentet; enélkül a megoldás nem értékelhető, vagy csak csökkentett
pontszámot kaphat. Törekedjék egyszerű, tömör és hatékony programozásra;
használjon jobbrekurziót, kerülje a felesleges hívásokat (pl. az append
eljárás felesleges használatát)!
1. Írja fel az alábbi kifejezések alapstruktúra-alakját (azaz szintaktikus
édesítőszerek nélküli formáját) vagy rajzolja fel a hozzájuk tartozó
fastruktúrákat! Állapítsa meg, hogy a két kifejezés egyesíthető-e, és ha
igen, milyen behelyettesítéssel! (3 pont)
[5+3+A,B+C] [X+y|.(X,Z)]
Megoldás:
.(+(+(5,3),A), .(+(B,C), [])) .(+(X,y), .(X,Z))
Egyesítés: A = y, B = 5, C = 3, X = 5+3, Z = []
2. Egy célsorozat keresési fája egy olyan irányított gráf, amelynek
csúcsaiban célsorozatok vannak és két csúcs között akkor megy él, ha a
kiinduló csúcs célsorozatából egyetlen (Prolog) redukciós lépéssel
eljuthatunk a cél csúcs célsorozatába. Az élek a redukció során
alkalmazott klóz sorszámával vannak címkézve. A fa gyökerében a teljes
kiindulási célsorozat van, az üres célsorozatot egy négyzettel jelöljük.
Rajzolja fel az alábbi célsorozat keresési fáját! A fa nem üres
célsorozatot tartalmazó leveleinél jelezze a visszalépést! (A select
és a write szavakat rövidítheti (s ill. w).) (7 pont)
| ?- select(1, [1,2,1], A), write(A).
A select/3 eljárás definíciója:
(1) select(E, [E|L], L).
(2) select(E, [X|T], [X|L]) :-
select(E, T, L).
Megoldás:
3. Írjon olyan Prolog eljárást, amely előállítja egy lista első N eleméből
álló listát! (7 pont)
% vesz(N, L, M): M az L lista első N elemének a listája.
% N és L adott, bemenő paraméter, M kimenő paraméter.
| ?- vesz(2, [1,2,3], L). L = [1,2] ? ; no
| ?- vesz(-1, [1,2,3], L). no
| ?- vesz(8, [1,2,3], L). no
Megolás:
vesz(0, _, L) :- !, L = [].
vesz(N, [H|T], [H|L]) :-
N > 0,
N1 is N-1,
vesz(N1, T, L).
4. Írjon olyan Prolog eljárást, amely egy listát átrendez úgy, hogy az
eredeti listában páratlan indexű elemeket előrehozza, de az azonos
paritású indexszel rendelkezők sorrendjét nem változtatja meg! (A listát
1-től kezdve indexeljük.)
Pontosabban: az N hosszú A lista páros permutáltja az N hosszú B
lista, ha B első (N+1)//2 eleme az A páratlan indexű elemeivel azonos
(a sorrend megtartásával), és B fennmaradó N//2 eleme pedig A páros
indexű elemeivel egyezik meg (szintén a sorrend megtartásával). Itt a
// művelet egész-osztást jelöl. (13 pont)
% parperm(L, P): P lista az L lista páros permutáltja.
% L adott, bemenő paraméter, P kimenő paraméter.
| ?- parperm([a,b,c,d,e], P). P = [a,c,e,b,d] ? ; no
| ?- parperm([a,b,c,d,e,f], P). P = [a,c,e,b,d,f] ? ; no
Első megoldás:
parperm(L, R) :-
parperm(L, Pt, Ps),
append(Pt, Ps, R).
% parperm(I, L, R): I lista páratlan indexű elemeinek listája L,
% páros indexű elemeinek listája R.
parperm([], [], []).
parperm([E|L], [E|Pt], Ps) :-
parperm(L, Ps, Pt).
Második megoldás:
% Ez a megoldás kicsit hatékonyabb, mert elkerüli az append meghívását.
% Mindezt azon az áron, hogy a segédeljárás gyűjtőargumentum-párokkal dolgozik.
parperm1(L, R) :-
parperm1(L, R, X, X, []).
% parperm1(I, L, LT, R, RT): I lista páratlan indexű elemeinek listája L-LT,
% páros indexű elemeinek listája R-RT.
parperm1([], L, L, R, R).
parperm1([H|T], [H|L], LT, R, RT) :-
parperm1(T, R, RT, L, LT).