Deklaratív programozás

2. Prolog kis házi feladat

2005. október 25.

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

A feladat

Egy E pozitív egész számot az L lista szép elemének mondjuk, ha az E szám E-szer szerepel a listában. Például az [1, 2, 2, 3, 3, 3, 2, 5-4, harom(kivansag), '9', 1.0] lista szép elemei az 1 és a 3. A 2 azért nem szép eleme, mert nem 2-ször szerepel, a harom(kivansag) és az 5-4 azért nem, mert nem egész szám, hanem struktúra-kifejezés, a '9' azért nem, mert nem egész szám, hanem atom, az 1.0 pedig azért nem, mert nem egész szám, hanem lebegőpontos szám.

A feladat felsorolni egy lista szép elemeit. Megírandó egy program Prolog nyelven, amely tartalmazza az annyiszor/2 eljárást, melynek jelentése a következő:

% annyiszor(+L,?E) pontosan akkor igaz, ha
% az L listának E olyan pozitív egész eleme, ami E-szer
% szerepel L-ben. Csak akkor kell helyesen működnie, ha L tömör. A lehetséges
% E értékek felsorolási sorrendje tetszőleges.

Egy példamegoldás (khf-pl2.pl), amely nem jó, mert azokat a pozitív egészeket is visszaadja, amelyek többször vagy kevesebbszer szerepelnek a listában, mint az értékük:

:- use_module(library(lists)).
annyiszor(L,E) :- sort(L,M), member(E,M), integer(E), E>0.

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

| ?- annyiszor([1,2,2,3,3,3,2,5-4,harom(kivansag),'9',1.0],E).
E = 1 ? ;
E = 3 ? ;
no

| ?- annyiszor([3,3,2,2,1,3],E).
E = 3 ? ; /* a sorrend tetszőleges */
E = 2 ? ;
E = 1 ? ;
no

| ?- annyiszor([2,3,gyok(ketto),harom,s(s(s(0))),2],E).
E = 2 ? ;
no

| ?- annyiszor([2,2,5,1,5,2,2,5,5,5],E).
E = 5 ? ; /* a sorrend tetszőleges */
E = 1 ? ;
no

Otthoni tesztkörnyezet

A fejlesztés közbeni tesztelésre a SICStus Prolog vagy az SWI-Prolog ajánlott. Hasznos lehet még az alábbi segédprogram (teszt2.pl):

:- consult('khf-pl2').
:- findall(E, annyiszor([1,ketto,2,harom(3),'3',3], E), L), L==[1].
:- findall(E, annyiszor([3,'1',3,2,3,2.0], E), L), L==[3].
:- findall(E, annyiszor([3,'1',3,2,3,1+1], E), L), L==[3].
:- findall(E, annyiszor([2,3,3,3,1,2,3,3,3], E), L),
   ( length(L,2) -> sort(L,M) ; L=M ), M==[1,2].
:- findall(E, annyiszor([999999999,999999999,2,1,1], E), L), L==[].
:- findall(E, annyiszor([5,9,2,10,9,7,8,3,5,8,4,4,9,10,8,6,6,10,5,3,6,7,6,6,
   1,6,2,4,5,7,7,8,10,3,7,4,5,10,7,7,8,10,9,9,9,10,8,8,8,9,10,10,9,10,9],E),
   L), ( length(L,10) -> sort(L,M) ; L=M ), M==[1,2,3,4,5,6,7,8,9,10].
:- findall(E, annyiszor([888888888,10,10,9,9,9,9,tiz,10,s(s(s(7))),9,9,9,10,
   8,9,10,10,8,7,10,8,7,6,8,7,6,10,8,8,8,7,6,6,6,8,6,4,5,9,4,5,3,4,3,5,7,7, 
   10,2,5,1,4,5,3,7,2,9], E), L), ( length(L,8) -> sort(L,M) ; L=M ),
   M==[1,2,3,4,5,6,7,8].

Ha ezt a programot a környezet hiba nélkül betölti (pl. a sicstus -l teszt2.pl vagy a

swipl -s
teszt2.pl

parancs hatására), akkor a khf-pl2.pl-ben nincs szintaktikai hiba, és a teszt2.pl-ben leírt három teszteset is hibátlanul fut 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. Ez az második Prolog kis házi feladat, ezért khf-pl2.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. november 15., kedd 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).