Intellektual tizimlar

1.1.7. Ispolzovaniye rekursii v prologe. Pravilo yavlyayetsya rekursivnыm, yesli soderjit v kachestve komponentы samo sebya. Rekursiya dopustima v bolshinstve yazыkov programmirovaniya (naprimer, v Paskale), no tam etot mexanizm ne yavlyayetsya takim vajnыm, poskolku imeyutsya drugiye, svoystvennыye prosedurnыm yazыkam, mexanizmы – siklы, prosedurы i funksii.
Rassmotrim preimuщyestva ispolzovaniya rekursii na primere.
Pust imeyutsya sleduyuщiye faktы o tom, kakaya valyuta kotiruyetsya vыshe:
doroje(dollar, rubl).
doroje(evro, rubl).
doroje(rubl, iena).
doroje(funt, euro).
Vыpolnim zapros:
? doroje(evro, rubl).
Yes
Budet poluchen utverditelnыy otvet, poskolku takoy fakt yavno opisan v programme. Yesli je sdelat zapros,
? doroje(evro, iena).
To otvet budet otrisatelnыy, poskolku takoy fakt otsutstvuyet.
Analogichnыm budet otvet na vopros:
? doroje(funt, rubl).
Izbejat protivorechiy zdes mojno vvedeniyem pravila, v kotorom dopustimo sravneniye mejdu soboy ne tolko dvux, no i trex obyektov:
doroje1(X, Y):- doroje(X, Y). /* dva obyekta */
doroje1(X, Y):- doroje(X, Z), doroje(Z, Y). /* tri obyekta */
Vtoroye pravilo opisыvayet, ochevidno, variant, kogda X>Z, a Z>Y, otkuda delayetsya vыvod, chto X>Y.
Odnako sepochka vzaimnыx sravneniy mojet bыt dlinnoy. Naprimer, pri chetыrex sravneniyax potrebuyetsya konstruksiya:
doroje2(X, Y):- doroje(X, M), doroje(M, K),
doroje(K, Z), doroje(Z, Y).
Opisыvat takiye dlinnыye pravila neudobno. Zdes vыgodneye primenit rekursiyu, obrativshis k pravilu iz samogo etogo pravila:
doroje1(X, Y):- doroje(X, Y).
doroje1(X, Y):- doroje(X, Z), doroje1(Z, Y).
Pervoye predlojeniye v etoy konstruksii opredelyayet moment prekraщyeniya rekursivnыx vыzovov.
Vtoroye pravilo opisыvayet vozmojnosti rekursivnыx vыzovov, kogda suщyestvuyut neproverennыye variantы resheniya.
Voobщye, lyubaya rekursivnaya prosedura doljna soderjat xotya bы odnu iz dvux komponent:
1. Nerekursivnuyu frazu, opredelyayuщuyu pravilo, primenyayemoye v moment prekraщyeniya rekursii.
2. Rekursivnoye pravilo, pervaya podsel kotorogo vыrabatыvayet novыye znacheniya argumentov, a vtoraya – rekursivnaya podsel – ispolzuyet eti znacheniya.
Baza pravil prosmatrivayetsya sverxu vniz. Snachala delayetsya popыtka vыpolneniya nerekursivnoy frazы. Yesli usloviye okonchaniya rekursii ne ukazano, to pravilo mojet rabotat beskonechno. Naprimer:
write_string :- write(“*****”),nl, write_string.
budet beskonechno pechatat zvezdochki na ekrane kompyutera.
Sleduyuщaya programma pechatayet na ekrane kompyutera sifrы ot 1 do 7.


Programma 10
DOMAINS
number=integer
PREDICATES
write_number(number)
GOAL
write(“Eto chisla:”), nl, write_number(1).
CLAUSES
write_number(10).
write_number(N) :- N<10,write(N),nl,N1:=N+1, write_number(N).
V razdele clauses danы dva opisaniya predikata write_number. Yesli v prosesse resheniya pervoye opisaniye neuspeshno, to ispolzuyetsya vtoroye opisaniye.
Programma 11 pechatayet summu vsex sifr vvedennogo s klaviaturы chisla.
Programma 11
PREDICATES
summa(integer,integer)
CLAUSES
summa(X,Y):-X<10,Y=X,!.
summa(X,Y):-X1=X div 10,summa(X1,Y1),Z=X mod 10, Y=Y1+Z.
Ispolzovaniye predikata ! v opisanii nerekursivnogo pravila pozvolyayet izbejat zdes perepolneniya steka.
Suщyestvuyut problemы, v kotorыx ispolzovaniye rekursii osobenno vыgodno.
Rassmotrim zadachu «Xanoyskaya bashnya» kotoruyu, kak govoryat, pridumal v 1883 g. fransuzskiy matematik Lyuka.
Imeyutsya tri sterjnya, na odnom iz kotorыx pomeщyenы N koles raznogo diametra, pri etom, chem menshe diametr kolsa, tem vыshe ono lejit (ris. 1).

Ris 1.
Naprimer, dlya chetыrex koles poluchayetsya kartinka:
Trebuyetsya peremestit diski s pervogo na tretiy sterjen za nekotoruyu posledovatelnost xodov, kajdыy iz kotorыx zaklyuchayetsya v perekladыvaniya verxnego diska s odnogo iz sterjney na drugoy sterjen. Pri etom bolshiy disk nikogda nelzya stavit na menshiy disk.
Yesli vvesti oboznacheniya:
elementarnaya operasiya-peremeщyeniye diska so sterjnya s nomerom a na sterjen b,
(m,a,b) programma peremeщyeniya m diskov s a na b.
(1,a,b) → peremeщyeniye odnogo diska – elementarnaya operasiya.
Ochevidno mojno zapisat:
(m,a,b) → (m-1,a,c) (m-1,c,b)
T. ye. dlya peremeщyeniya m-diskov s a na b nujno:
1) Peremestit m-1 – disk s a na c (s – vspomogatelnыy sterjen).
2) Peremestit nijniy disk s nomerom m s a na b.
3) Peremestit m-1 – disk s c na b (s – vspomogatelnыy sterjen).
Zdes voznikayet rekursiya – selevoye deystviye opredelyayetsya cherez
promejutochnыye deystviya togo je vida.
Naprimer, pust m = 3, t. ye. imeyetsya tri kolsa. Togda:
(3,1,3)→(2,1,2)<1,3>(2,2,3)
Mojno perepisat v vide
(3,1,3)→ (2,1,2) <1,3> (2,2,3)
→ (1,1,3)<1,2>(1,3,2) <1,3> (1,2,1)<2,3>(1,1,3)
Okonchatelno:
<1,3><1,2><3,2><1,3><2,1><2,3><1,3>
Takim je obrazom mojet bыt poluchena programma dlya lyubogo chisla koles.
Suщyestvuyet «vostochnaya legenda» (kotoruyu, kak govoryat, pridumal tot je matematik Lyuka), soglasno kotoroy v odnoy iz peщyer Gimalayev tri buddiyskix monaxa reshayut etu zadachu dlya 64 koles. Kogda oni perelojat vse kolsa, nastupit kones sveta.
Resheniye zadachi trebuyet 2ⁿ-1 deystviy. Yesli schitat, chto odno deystviye vыpolnyayetsya za 1 s, to uje dlya 40 koles doljno potrebovatsya boleye 2000000 let, chto zvuchit dostatochno optimisticheski.
Programma 12 reshayet zadachu «Xanoyskaya bashnya» na PROLOGe.
Programma 12
DOMAINS
loc =right;middle;left
PREDICATES
hanoi(integer)
move(integer,loc,loc,loc)
inform(loc,loc)
GOAL
hanoi(5).
CLAUSES
hanoi(N):- move(N,left,middle,right).
move(1,A,_,C):- inform(A,C),!.
move(N,A,B,C):- N1=N-1, move(N1,A,C,B), inform(A,C),
move(N1,B,A,C).
inform(Loc1, Loc2):- nl,write(“Disk s”, Loc1, “ na “, Loc2).