Deklaratív programozás

A kis házi feladat beadása nem kötelező.

A feladat

• A;
• A to B: csak akkor számlétra, ha A =< B (javítva; régebben itt ``<'' volt)
• A to B step S: csak akkor számlétra, ha S =\= 0 és (B - A) / S >= 0.

Minden számlétra egy véges számtani sorozatot definiál:

• A: az egyelemű (A) számtani sorozat
• A to B: a lehető leghosszabb (A, A + 1, A + 2, ...) számtani sorozat, melynek nincs B-nél nagyobb eleme;
• A to B step S: a lehető leghosszabb (A, A + S, A + 2S, ...) számtani sorozat, melynek nincs B-nél nagyobb eleme, ha S pozitív, illetve B-nél kisebb eleme, ha S negatív.

Azt mondjuk, hogy egy X szám a számlétra tagja, ha X a számlétra által meghatározott sorozat egyik eleme.

Számlétralistának nevezünk egy listát, ha annak minden eleme számlétra. A számlétralista taglistájának nevezzük azt a számokból álló listát, amelyet a számlétralista elemeinek tagjaiból képezünk a számlétralistában balról jobbra, egy számlistán belül pedig A-tól B felé haladva (az azonos számokat nem összevonva). Például az [1 to 5,5 to 12 step 3] számlétralista taglistája az [1,2,3,4,5,5,8,11] számlista.

Két számlétralista ekvivalens, ha a taglistájuk megegyezik (az azonos értékű lebegőpontos és egész számokat azonosnak tekintjük). Például az [1 to 3,4 to 7] és az [1,2.0 to 7] számlétralisták ekvivalensek, mert taglistájuk ugyanaz: [1,2,3,4,5,6,7]. Egy számlétralista minimális, ha nem létezik vele ekvivalens, nála rövidebb (azaz kevesebb számlétrából álló) számlétralista. Például az [1,2.0 to 7] számlétralista nem minimális, mert az [1.0 to 7] számlétralista rövidebb nála, és ugyanaz a taglistájuk. Az [1.0 to 7] számlétralista minimális (indoklás: csak az üres számlétralista rövidebb nála, de az nem ekvivalens vele).

Megírandó egy program Prolog nyelven, amely tartalmazza az kisletra/1 eljárást, melynek jelentése a következő:

% kisletra(+L) pontosan akkor igaz, ha L egy
% minimális számlétralista. Feltételezhető, hogy L tömör Prolog-kifejezés.

A to és step operátorokat a program elején definiálni kell. Célszerű 400-nál kisebb precedencia-számokat választani. Ehhez segítség: például a beépített + és * operátorokat így definiálták:

:- op(500, fx, '+').
:- op(500, yfx, '+').
:- op(400, yfx, '*').

:- (1 to 3) step 2 == 1 to 3 step 2.

Egy példamegoldás (khf-pl3.pl), amely csak 0 és 1 elemű számlétralistákra működik helyesen:

kisletra([]).
kisletra([A]) :- number(A), !.
kisletra([A to B]) :- number(A), number(B), !, A=<B.
kisletra([A to B step S]) :- number(A), number(B), number(S), !,
  S=\=0, (B-A)/S >= 0.

Ötletek a megvalósításhoz:

1. Számok összehasonlítására az =:=, =\=, <, >, <= és =< eljárásokat használjuk, ne pedig az is, =, \=, == vagy \== eljárásokat, mivel az utóbbiak például a 3 és 3.0 számokat különbözőnek tekintik.
2. Vegyük figyelembe, hogy ha kisletra/1 eljárás argumentumának egyik eleme nem számlétra, akkor a hívásnak meg kell hiúsulnia.
3. Az algoritmus lebegőpontos stabilitásával nem kell törődni. A tesztesetek olyanok lesznek, hogy a gép lebegőpontos kerekítést nem fog végezni (például 0.25 kerekítés nélkül, de 0.2 (== 4/5) csak kerekítéssel ábrázolható lebegőpontos 2-es számrendszerben). Például a (B-A)/S osztást el szabad végezni, és feltételezhető, hogy az osztás eredménye pontos.
4. Külön figyeljünk arra, hogy pl. a 3 és 3.0 számok azonos értékűek, tehát például a [3.0,4 to 5] számlétralista nem minimális, mert két eleme összevonható.
5. A megoldás során nem szabad taglistává kifejteni a kapott számlétralistát. Ezt a beadást kezelő keretrendszer úgy ellenőrzi, hogy ha a egy soktagú (pl. kisletra([0 to 9999999])) hívás túl hosszú ideig fut, akkor nem fogadja el a megoldást.
6. Segítség azok számára, akik tanácstalanok, hogy milyen algoritmust használjanak: érdemes először minden kéttagú számlétrát két egytagúvá felbontani, majd pedig balról jobbra haladva a szomszédos számlétrákat sorra összevonni, ha lehetséges (figyelembe véve, hogy két egytagú számlista mindig összevonható). Ha az így kapott számlétralista rövidebb, mint az eredeti, pontosan akkor nem minimális az eredeti.
7. 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.

Példák

:- \+ kisletra(semmi). % rossz lista
:- kisletra([]).
:- kisletra([1]).
:- kisletra([1 to 5]).
:- kisletra([1 to 5 step 2.0]).
:- kisletra([1 to 1]).
:- kisletra([-1 to -1.0 step 42]).
:- \+ kisletra([-1 to -1.0 step 0]). % rossz lista
:- \+ kisletra([egy to 5 step 2.0]). % rossz lista
:- \+ kisletra([1 to 5 step 0]). % rossz lista
:- \+ kisletra([1 to 5 step 0.0]). % rossz lista
:- \+ kisletra([1 to 5 step -2]). % rossz lista
:- \+ kisletra([43,gyok(ketto),42]). % rossz lista
:- \+ kisletra([1 to 8 step 3, 1.5, 3.5 to 2 step -1.4, 4 to 6, 9 to 8]).
   % rossz lista (az utolsó eleme nem számlétra)
:- kisletra([1 to 8 step 3, 1.5, 3.5 to 2 step -1.4, 4 to 6]).
:- \+ kisletra([1,3]). % rövidebb nála: [1 to 3 step 2]
:- \+ kisletra([1,2.0]). % rövidebb nála: [1 to 2.0]
:- kisletra([-1,-1]). % azonos számok nem vonhatók össze
:- kisletra([3,3,3]). % azonos számok nem vonhatók össze
:- kisletra([3,3 to 3]). % azonos számok nem vonhatók össze
:- kisletra([1.0 to 3,5 to 6]).
:- \+ kisletra([1 to 2,3 to 5 step 2,6]). % rövidebb nála: [1 to 3,5 to 6]
:- \+ kisletra([1 to 2,3.0 to 5 step 2,6]). % rövidebb nála: [1 to 3,5 to 6]
:- \+ kisletra([2.0,3 to 8]). % összevonható
:- \+ kisletra([2 to 8.0,9]). % összevonható
:- \+ kisletra([2 to 8.0,9 to 9 step 42]). % összevonható
:- \+ kisletra([2 to 8.0,9 to 10 step 1.0]). % összevonható
:- \+ kisletra([2 to 8.0,9 to 10 step 7.0]). % összevonható (!): [2 to 9]
:- kisletra([3 to 8.0,9 to 23.0 step 7]).
:- \+ kisletra([3 to 8.0,2,9.0 to 23.0 step 7]). % összevonható
:- \+ kisletra([3 to 8.0,2.0,9 to 23.0 step 7]). % összevonható
:- \+ kisletra([3 to 8.0,9,9 to 23.0 step 7]). % összevonható
:- kisletra([-9999999 to 0, 0 to 9999999]).
   % nem vonható össze (dupla nulla), de a naiv implementáció timeout-os
:- \+ kisletra([-9999999 to -0.25 step 0.25, 0 to 9999999 step 0.25]).
   % összevonható, de a naiv (kifejtő) implementáció timeout-os
:- \+ kisletra([1,2 to 4 step 2,5 to 7 step 2, 8 to 8]).
   % rövidebb nála: [1 to 2,4 to 5,7 to 9]

Otthoni tesztkörnyezet

:- consult('khf-pl3').
% ide kell írni a fenti példákat (,,:-''-vel kezdődő sorok)

Tudnivalók a beadásról

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