Deklaratív programozás

Definíciók

A számokból és változókból összeadás, kivonás és szorzás műveletekkel építhető kifejezéseket polinomoknak nevezzük. Egy polinom egyváltozós, ha csak egyféle változó szerepel a kifejezésben.

Egy egyváltozós polinom kanonikus alakja a polinom, melyet az eredetiből úgy kapunk, hogy az szorzatokat a disztributív szabály szerint kifejtjük, az azonos kitevőhöz tartozó tagokat összevonjuk, és az így kapott tagokat a kitevők csökkenő sorrendjébe rendezzük, és a 0-s tagokat eltüntetjük. Például a 2*x*(3*x+4)*(5*x-6)+7-x*x*x*30 polinom kanonikus alakját így kapjuk:

7+2*x*(3*x+4)*(5*x-6)-x*x*x*30 ==
7+2*x*(3*x*5*x-3*x*6+4*5*x-4*6)-x*x*x*30 ==
7 + 2*x*3*x*5*x - 2*x*3*x*6 + 2*x*4*5*x - 2*x*4*6 - x*x*x*30 ==
7 + 30*x*x*x - 36*x*x + 40*x*x - 48*x - x*x*x*30 ==
7 + 4*x*x - 48*x ==
4*x*x - 48*x + 7

Egy egyváltozós polinom foka a kanonikus alakja első tagjában szereplő változók száma. Például a fenti 2*x*(3*x+4)*(5*x-6)+7-x*x*x*30 polinom foka 2, mert a 4*x*x -ben 2 db x szerepel.

Egy egyváltozós polinom főegyütthatója a kanonikus alakja első tagjában szereplő konstans. Például a fenti 2*x*(3*x+4)*(5*x-6)+7-x*x*x*30 polinom főegyütthatója 4.

A feladat

Írjon olyan Prolog-programot, amely egy egyváltozós polinom főegyütthatóját számítja ki. A program tartalmazza a foegyutthato/2 eljárást a következő jelentéssel:

% foegyutthato(+P, ?A) pontosan akkor igaz, ha a P egyváltozós polinom
% főegyütthatója az A valós szám.
% Csak akkor működik helyesen, ha P tömör kifejezés, amely
% egyváltozós polinomot reprezentál.
% A polinomok Prolog-reprezentációja: egy polinom lehet egy szám (konstans),
% atom (a polinom változója), két polinom összege ('+'/2 funktorral),
% különbsége ('-'/2 funktorral) vagy szorzata ('*'/2 funktorral).

Egy példamegoldás, amely csak akkor működik, ha a polinom eleve kanonikus alakban van megadva:

foegyutthato(A*_XX, A0) :- A0 is A+0.0.
foegyutthato((A*_XX)+_MM, A0) :- A0 is A+0.0.

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

A beadott programot egész és valós számokkal fogjuk tesztelni. A program feltételezheti, hogy a Prolog is/2 beépített eljárása valós számok esetén is teljesen pontosan számol.

Megjegyzés: ha a P1 és P2 polinomoknak csak főegyütthatója és a fokszáma ismert, akkor ezekből még nem számolható ki P1*P2, P1+P2 és P1-P2 főegyütthatója és fokszáma, például a 30*x+5 és 30*x+4 polinomok különbsége esetén.

Példák

| ?- foegyutthato(3.14, A).
A = 3.14 ? ;
no

| ?- foegyutthato(0, A).
A = 0.0 ? ; /* mindenképpen valós számot kell visszaadni */
no

| ?- foegyutthato(x*5+3.14-100*x, A).
A = -95.0 ? ;
no

| ?- foegyutthato(x*x*0.9 + x*5 + 3.14 - 100*x + x*6.1*x, A).
A = 7.0 ? ;
no

| ?- foegyutthato((2*n+5)*(4*n)+7*n*n, A).
A = 15.0 ? ;
no

| ?- foegyutthato(x+5-x, A).
A = 5.0 ? ; /* az x kiesik, marad az 5 */
no

| ?- foegyutthato(x+y, A).
/* a működés nem definiált, mivel a bemeneti polinom nem egyváltozós */

| ?- foegyutthato(7+2*x*(3*x+4)*(5*x-6), A).
A = 30.0 ? ;
no

Otthoni tesztkörnyezet

:- consult(foegyutthato).
:- findall(A, foegyutthato(3.14, A), S), S==[3.14].
:- findall(A, foegyutthato(0, A), S), S==[0.0].
:- findall(A, foegyutthato(x+x+5, A), S), S==[2.0].
:- findall(A, foegyutthato(x*x+5, A), S), S==[1.0].
:- findall(A, foegyutthato(x-x+5, A), S), S==[5.0].
:- findall(A, foegyutthato(x+5-x, A), S), S==[5.0].
:- findall(A, foegyutthato(x*5+3.14-100*x, A), S), S==[-95.0].
:- findall(A, foegyutthato(x*x*0.9+x*5+3.14-100*x+x*6.1*x, A), S), S==[7.0].
:- findall(A, foegyutthato((2*n+5)*(4*n)+7*n*n, A), S), S==[15.0].
:- findall(A, foegyutthato(2*x*(3*x+4)*(5*x-6)+7-x*x*x*30.0, A), S), S==[4.0].
:- findall(A, foegyutthato(7+2*x*(3*x+4)*(5*x-6), A), S), S==[30.0].

Ha ezt a programot a környezet hiba nélkül betölti (pl. a sicstus -l teszt3.pl vagy az swipl -s teszt3.pl parancs hatására), akkor a foegyutthato.pl-ben nincs szintaktikai hiba, és a teszt3.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. Ez a harmadik Prolog kis házi feladat; a megoldást foegyutthato.pl néven kell beküldeni. A névben meg kell különböztetni a kis- és nagybetűket. A beadási határidő 2006. május 26., péntek 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.