Egyszerű példák DLV-hez

2. Háromszögek

Amibe most vágunk bele, az korai iskolai éveinkben helyettesíthetett volna bennünket. :) A DLV ezúttal a háromszögek tudományában lesz kénytelen eligazodni. Az egyszerűség kedvéért az euklideszi síkon.

2.1 Háromszög, vagy sem?

A háromszög oldalaira igaz az az szabály, hogy a leghosszabb oldal mindig rövidebb, mint a másik két oldal összege. Hogy megkerüljük a "leghosszabb" definiálását, fogalmazzuk át úgy, hogy "minden oldalra igaz, hogy az egyik rövidebb, mint a másik két oldal összege"!

Egyúttal megismerkedünk a DLV korlátozott aritmetikai képességeivel is.

Először is meg kell adnunk, mekkora az a legnagyobb szám, amivel a DLV számolhat:

#maxint = 1000.

Ezek után megadunk három oldalhosszt egyben és ennek értékeit változtatgatva tesztelhetjük programunkat:

oldalak( 11, 1, 1 ).

Ez például pont nem lehet háromszög.

Jöhet a kulcsszabály:

haromszog :- 
  oldalak( A, B, C ), 
  +(A, B, AB), AB > C,
  +(A, C, AC), AC > B,
  +(B, C, BC), BC > A.

Ez a következőt jelenti: vesszük az oldalakat, és ha ebből kettő összege az összes lehetséges sorrendben(!) nagyobb, mint a harmadiké, akkor kapunk vissza igaz értéket.

Próbáljuk ki:

haromszog?

DLV>dlv.mingw.exe -brave tri_1a.dlv
DLV [build BEN/Oct 11 2007   gcc 3.4.5 (mingw special)]

haromszog is bravely false.

A program teljes forráskódja.

Eddig igaza van. Írjuk át az értéket!

oldalak( 3, 4, 5 ).

haromszog?

DLV>dlv.mingw.exe -brave tri_1b.dlv
DLV [build BEN/Oct 11 2007   gcc 3.4.5 (mingw special)]

haromszog is bravely true, evidenced by {oldalak(3,4,5), haromszog}

A program teljes forráskódja.

Ez is igaz.

Hasonló módon dolgozhatunk szögekkel is. A háromszög szögeinek összege 180 fok:

haromszog :- 
  szogek( A, B, C ), 
  +( A, B, AB ), 
  +( AB, C, ABC ), 
  ABC = 180.

A program teljes forráskódja.

Az aritmetikai kifejezések leírása persze nem épp kényelmes.

Lépjünk tovább!

2.2 Milyen háromszög?

Teve van egypúpú, kétpúpú... Háromszögből is van pár, ennek osztályozását a DLV el tudja végezni, ha megtanítjuk rá.

egyenlo_oldalu_haromszog :-
  oldalak( A, B, C ), A = B, B = C.

egyenlo_szaru_haromszog :- oldalak( A, B, C ), A = B.
egyenlo_szaru_haromszog :- oldalak( A, B, C ), A = C.
egyenlo_szaru_haromszog :- oldalak( A, B, C ), B = C.

A program teljes forráskódja.

Eddig egyszerű, de ahhoz, hogy a derékszögű háromszögeket is fel tudjuk ismertetni, már kell a Pitagorasz-tétel is:

pitagorasz( A, B, C ) :- *( A, A, A2 ), *( B, B, B2 ), *( C, C, C2 ), +( A2, B2, A2B2 ), A2B2 = C2.

derekszogu_haromszog :- oldalak( A, B, C ), pitagorasz( A, B, C ).
derekszogu_haromszog :- oldalak( A, B, C ), pitagorasz( A, C, B ).
derekszogu_haromszog :- oldalak( A, B, C ), pitagorasz( B, C, A ).

Ennek futtatásával a DLV viszont már komolyan megterheli a gépet.

Miért is?

Lássuk a futás eredményét!

derekszogu_haromszog?

D:\phd\02-felev\DLV>dlv.mingw.exe -brave tri_3c.dlv
DLV [build BEN/Oct 11 2007   gcc 3.4.5 (mingw special)]

derekszogu_haromszog is bravely true, evidenced by {oldalak(5,3,4), pitagorasz(0
,0,0), pitagorasz(0,1,1), pitagorasz(0,2,2), pitagorasz(0,3,3), pitagorasz(0,4,4
), pitagorasz(0,5,5), pitagorasz(0,6,6), pitagorasz(0,7,7), pitagorasz(0,8,8), p
itagorasz(0,9,9), pitagorasz(0,10,10), pitagorasz(0,11,11), pitagorasz(0,12,12),
 pitagorasz(0,13,13), pitagorasz(0,14,14), pitagorasz(0,15,15), pitagorasz(0,16,
16), pitagorasz(0,17,17), pitagorasz(0,18,18), pitagorasz(0,19,19), pitagorasz(0
,20,20), pitagorasz(0,21,21), pitagorasz(0,22,22), pitagorasz(0,23,23), pitagora
sz(0,24,24), pitagorasz(0,25,25), pitagorasz(0,26,26), pitagorasz(0,27,27), pita
gorasz(0,28,28), pitagorasz(0,29,29), pitagorasz(0,30,30), pitagorasz(0,31,31),
pitagorasz(1,0,1), pitagorasz(2,0,2), pitagorasz(3,0,3), pitagorasz(3,4,5), pita
gorasz(4,0,4), pitagorasz(4,3,5), pitagorasz(5,0,5), pitagorasz(5,12,13), pitago
rasz(6,0,6), pitagorasz(6,8,10), pitagorasz(7,0,7), pitagorasz(7,24,25), pitagor
asz(8,0,8), pitagorasz(8,6,10), pitagorasz(8,15,17), pitagorasz(9,0,9), pitagora
sz(9,12,15), pitagorasz(10,0,10), pitagorasz(10,24,26), pitagorasz(11,0,11), pit
agorasz(12,0,12), pitagorasz(12,5,13), pitagorasz(12,9,15), pitagorasz(12,16,20)
, pitagorasz(13,0,13), pitagorasz(14,0,14), pitagorasz(15,0,15), pitagorasz(15,8
,17), pitagorasz(15,20,25), pitagorasz(16,0,16), pitagorasz(16,12,20), pitagoras
z(17,0,17), pitagorasz(18,0,18), pitagorasz(18,24,30), pitagorasz(19,0,19), pita
gorasz(20,0,20), pitagorasz(20,15,25), pitagorasz(20,21,29), pitagorasz(21,0,21)
, pitagorasz(21,20,29), pitagorasz(22,0,22), pitagorasz(23,0,23), pitagorasz(24,
0,24), pitagorasz(24,7,25), pitagorasz(24,10,26), pitagorasz(24,18,30), pitagora
sz(25,0,25), pitagorasz(26,0,26), pitagorasz(27,0,27), pitagorasz(28,0,28), pita
gorasz(29,0,29), pitagorasz(30,0,30), pitagorasz(31,0,31), derekszogu_haromszog}

A program teljes forráskódja.

Látható, hogy a DLV "össze-vissza" próbálkozik sok-sok számmal, és aztán talál megoldást. A tétel ilyen módon való beépítése nem célszerű.

derekszogu_haromszog :- oldalak( A, B, C ), *( A, A, A2 ), *( B, B, B2 ), *( C, C, C2 ), +( A2, B2, A2B2 ), A2B2 = C2.
derekszogu_haromszog :- oldalak( A, C, B ), *( A, A, A2 ), *( B, B, B2 ), *( C, C, C2 ), +( A2, B2, A2B2 ), A2B2 = C2.
derekszogu_haromszog :- oldalak( C, A, B ), *( A, A, A2 ), *( B, B, B2 ), *( C, C, C2 ), +( A2, B2, A2B2 ), A2B2 = C2.

Így a válasz gyors lesz, a kód viszont "csúnya".

A probléma az, hogy első esetben a DLV túlzottan "szabadjára" lett engedve, s ha ezt korlátozni tudjuk, azaz csak a szóba jöhető értékek vizsgálatát engedjük meg, gyors választ kapunk.

kivalasztott_oldal( X ) :- oldalak( X, _, _ ).
kivalasztott_oldal( X ) :- oldalak( _, X, _ ).
kivalasztott_oldal( X ) :- oldalak( _, _, X ).

pitagorasz( A, B, C ) :- 
  kivalasztott_oldal( A ), 
  kivalasztott_oldal( B ), 
  kivalasztott_oldal( C ), 
  *( A, A, A2 ), *( B, B, B2 ), *( C, C, C2 ), +( A2, B2, A2B2 ), A2B2 = C2.

derekszogu_haromszog :- pitagorasz( A, B, C ).

A futtatás mutatja, hogy a kivalasztott_oldal szabály veszi le a terhet a programról, illetve rólunk, hogy minden permutációt lekódoljunk.

derekszogu_haromszog?

D:\phd\02-felev\DLV>dlv.mingw.exe -brave tri_3e.dlv
DLV [build BEN/Oct 11 2007   gcc 3.4.5 (mingw special)]

derekszogu_haromszog is bravely true, evidenced by {oldalak(4,3,5), kivalasztott
_oldal(3), kivalasztott_oldal(4), kivalasztott_oldal(5), pitagorasz(3,4,5), pita
gorasz(4,3,5), derekszogu_haromszog}

A program teljes forráskódja.

2.3 Kerület, terület?

A kerület kiszámolása triviális:

kerulet( K ) :- oldalak( A, B, C ), +( A, B, AB ), +( AB, C, K ).

A területhez viszont szögfüggvény kellene, de még osztás, sőt kivonás sincs!

Azért nézzük meg, mit lehet tenni!

Segítségünkre siet Héron, az ő képletével:

T = sqrt( s * ( s - a ) * ( s - b ) * ( s - c ) )

ahol s = K / 2
tehát jól jön a kerület.

terulet( X ) :-
  oldalak( A, B, C ),
  kerulet( K ),
  *( 2, S, K ),
  +( A, SA, S ),
  +( B, SB, S ),
  +( C, SC, S ),
  *( SA, SB, SAB ),
  *( SC, SAB, SABC ),
  *( S, SABC, X2 ),
  *( X, X, X2 ).

A program teljes forráskódja.

Itt érdemes sorról sorra magyarázatot adni:

1. sor: A megadott oldalértékekkel fogunk számolni.
2. sor: Szükségünk van a kerület értékére.
3. sor: Kiszámoljuk s értékét, ami a kerület fele. Igen, "ráillesztjük" a szorzásra, csak épp most az egyik szorzandó az ismeretlen. DLV-ben ez megy. Ezért nem kell osztás.
4-6. sor: Rendre kiszámoljuk az s-a, s-b, s-c értékeket az előbbi "trükkel".
7-9. sor: Összeszorozzuk a tagokat (s, s-a, s-b, s-c ).
10. sor: Gyököt vonunk. Így. :)

A programunk sajnos csak egész számokkal tud futni.

A gyökvonást ilyen környezetben közelítő módszerrel tudjuk (úgy-ahogy) pótolni, ami a gyökhöz legközelebb eső egész számot adja vissza:

sq( X, X2 ) :- *( X, X, X2 ).
sq( X, X2 ) :- *( X, X, X2T ), +( D, X2T, X2 ), D <= X.
sq( X, X2 ) :- *( X, X, X2T ), +( D, X2, X2T ), D <= X.

Az első sor akkor ad eredményt, ha a szám gyöke is egész, a másik kettő olyan közelítő eredményt ad, mely négyzetének eltérése a négyzetszámtól kisebb, vagy egyenlő, mint a gyök értéke.

Tehát |X²-X₂| <= X.

Háromszögekről talán ennyi elég is. :)