BME Villamosmérnöki és Informatikai Kar
Műszaki informatika szak
Nappali tagozat
2004/2005. tanév, tavaszi félév

Deklaratív programozás

3. Prolog kis házi feladat

2005. április 20.

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

A feladat

A 2. kisHF-ben megismert ,,számlétra'' fogalmat ez a feladat is használja. Számlétrának nevezzük az alábbi tömör Prolog kifejezéseket (ahol A, B és S számok, to és step operátorok):

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

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, '*').
A to és a step közül a step precedencia-száma legyen nagyobb, vagyis az alábbi hívás sikeres legyen:
:- (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

Az alábbi példák olyan formában adottak, hogy azok a .pl fájl végére írhatók, és ha a SICStus a programot - goal failed üzenet (az SWI-Prolog pedig Goal (directive) failed üzenet) nélkül betölti, akkor a program a megadott példákra helyesen működik.
:- \+ 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

A fejlesztés közbeni tesztelésre a SICStus Prolog vagy az SWI-Prolog ajánlott. Érdemes a fenti példákat a megoldás (.pl fájl) végére írni, hogy a megoldás minden újratöltésekor tesztesetként lefussanak. Ha a teszteseteket külön fájlba szeretnénk írni, akkor hasznos lehet az alábbi segédprogram (teszt3.pl):
:- consult('khf-pl3').
% ide kell írni a fenti példákat (,,:-''-vel kezdődő sorok)
Ha ezt a programot a környezet hiba és figyelmeztetés nélkül betölti (pl. a sicstus -l teszt3.pl vagy a swipl -s teszt3.pl parancs hatására), akkor a khf-pl3.pl-ben nincs szintaktikai hiba, és a teszt3.pl-ben leírt három teszteset is hibátlanul fut le. Ha - goal failed vagy Goal (directive) failed üzenetet kapunk, akkor az adott tesztesetre a program hibásan működik.

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. Ez az második Prolog kis házi feladat, ezért khf-pl3.pl néven kell beküldeni a megoldást. A névben meg kell különböztetni a kis- és nagybetűket. A beadási határidő 2005. május 4., szerda 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 (a 100 pontból).