Deklaratív programozás

1. Prolog kis házi feladat

V1.0, 2006. november 26.

A feladat

Írjon olyan Prolog eljárást binoms/2 néven, amely meghatározza az n-ed rendű binomiális együtthatókat! (Az n-ed rendű binomiális együtthatók a Pascal-háromszög n-edik sorának elemei.)

A binoms/2 eljárás specifikációja a következő:

% binoms(+N,?L): Az L lista az N-edrendű binomiális együtthatókat tartalmazza,
%                azaz N+1 elemű és (0-tól számozva) I-edik elemének értéke "N alatt az I".

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.

A feladat megoldása során a gyorsítás érdekében szabad vágót és feltételes szerkezetet használni, ám ez sem kötelező, a pontozásba nem számít bele.

Példák

| ?- set_prolog_flag(toplevel_print_options,
     [quoted(true),numbervars(true),portrayed(true),max_depth(20)]).
yes /* a listák mutatása 20 hosszúságig */
| ?- binoms(0, L).
L = [1] ? ;
no
| ?- binoms(1, L).
L = [1,1] ? ;
no
| ?- binoms(4, L).
L = [1,4,6,4,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 (másolja ki és mentse el binomstest.pl néven):

:- consult('binoms').
:- \+ binoms(-1, L).
:- findall(L, binoms(0, L), S), S == [[1]].
:- findall(L, binoms(1, L), S), S == [[1,1]].
:- findall(L, binoms(4, L), S), S == [[1,4,6,4,1]].
:- findall(L, binoms(10, L), S), S == [[1,10,45,120,210,252,210,120,45,10,1]].
:- findall(L, binoms(16, L), S), S == [[1,16,120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1]].

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

Tudnivalók a beadásról

A kis házi feladat beadását, jóllehet nem kötelező, a tárgy minden hallgatójának nagyon ajánljuk.

A programot az Elektronikus Tanársegéd segítségével weben keresztül lehet beadni, a HF beadás menüpont alatt. A módosított beadási határidő 2006. december 12., kedd 24:00 (eredetileg dec. 8. volt).

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