Deklaratív programozás

A feladat

Egy tömör listát kulcs-érték listának nevezünk, ha minden eleme K-V alakú kulcs-érték pár. (Tömörnek nevezzük az adatstruktúrát, ha nincs benne behelyettesítetlen változó.)

Írjon olyan Prolog programot, amely fölsorolja egy kulcs-érték lista összes olyan lehető leghosszabb (azaz egyik irányban sem kiterjeszthető), legalább kételemű [K1-V1, ..., Kn-Vn] folytonos részlistáit, amelyekre a következő feltételek teljesülnek:

• Ki<Kj, ha i<j (vagyis a kulcsok növekvő sorrendben vannak rendezve) és
• a Vi értékek számtani sorozatot alkotnak.

A program tartalmazza a seq/2 eljárást a következő jelentéssel:

% :- type intpair --> int-int.
% :- pred seq(list(intpair)::in, list(intpair))
% seq(+L,?S), ahol az S az L kulcs-érték listának egy olyan
% lehető leghosszabb, legalább kételemű részlistája, amelyben a
% kulcsok növekvő sorrendűek, az értékek pedig számtani sorozatot
% alkotnak.  Előfeltétel: L tömör, a kulcsok és az értékek egész számok.

Az alábbi példaprogram egy kulcs-érték lista kételemű, a feltételeknek megfelelő részlistáit sorolja föl (a ki-nem-terjeszthetőségtől eltekintve):

seq([K1-V1,K2-V2|_],[K1-V1,K2-V2]):-
        K1<K2.
seq([_|L],S):-
        seq(L, S).

A jobbrekurzív eljárások kevesebb memóriát igényelnek, mint az egyéb rekurzív eljárások, ezért a feladat megoldása során jobbrekurzív eljárások írása ajánlott, ám ez nem kötelező, a pontozásba nem számít bele.

Otthoni tesztkörnyezet

:- consult('seq').
:- \+ seq([],S).
:- \+ seq([1-3],S).
:- \+ seq([1-3,1-3],S).
:- findall(S,seq([1-3,2-5],S), L), L == [[1-3,2-5]].
:- findall(S,seq([1-3,2-5,4-7],S), L), L == [[1-3,2-5,4-7]].
:- findall(S,seq([1-3,2-5,4-9],S), L), L == [[1-3,2-5],[2-5,4-9]].
:- findall(S,seq([1-3,2-5,4-7,2-7],S), L), L == [[1-3,2-5,4-7]].
:- findall(S,seq([1-3,2-5,4-7,2-7,4-9],S), L), L == [[1-3,2-5,4-7],[2-7,4-9]].
:- findall(S,seq([1-3,2-5,4-7,2-7,4-9,7-9],S), L),
        L == [[1-3,2-5,4-7],[2-7,4-9],[4-9,7-9]].
:- findall(S,seq([1-3,2-5,4-7,2-7,4-9,7-9,8-9,5-7,6-8,7-9],S), L),
        L == [[1-3,2-5,4-7],[2-7,4-9],[4-9,7-9,8-9],[5-7,6-8,7-9]].
:- findall(S,seq([1-7,2-5,4-3,2-7,4-9,7-9,8-9,8-9,5-9,6-7,7-5],S), L),
        L == [[1-7,2-5,4-3],[2-7,4-9],[4-9,7-9,8-9],[5-9,6-7,7-5]].

Ha ezt a programot a környezet hiba nélkül betölti (pl. a sicstus -l seqtest.pl vagy az swipl -s seqtest.pl parancs hatására), akkor a seq.pl-ben nincs szintaktikai hiba, és a seqtest.pl-ben leírt tesztesetek is hibátlanul futottak le.

Tudnivalók a beadásról

A programot az Elektronikus Tanársegéd segítségével weben keresztül lehet beadni, a HF beadás menüpont alatt. A beadási határidő 2007. január 3. szerda 24:00, 2006. dec. 22-én vizsgázóknak dec. 21., csütörtök 24:00.

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatért plusz 1 pont jár.