|
ELEKTRONINĖS KNYGOS |
|
|
Gintautas GRIGAS
PROGRAMAVIMAS PASKALIU
|
8. REKURSIJA
|
Pasaulis nuolat atsinaujina. Vaikai atkartoja tėvus.
Rekursija tai atkartojimas. Funkcija arba
procedūra gali kreiptis į save pačią ir tuo pačiu atkartoti
savo pačios veiksmus vėl nuo pradžios, tik su kitais parametrais.
Toks atkartojimas vadinamas rekursija.
Rekursija yra ir paprasta, ir sudėtinga.
Paprasta dėl to, kad ja dažnai vartojama matematikoje, kai jos
pagalba labai paprastai ir akivaizdžiai apibrėžiamos priklausomybės
tarp dydžių. Sudėtinga dėl to, kad dažnai sunkiau suvokti, kaip
tuos dydžius rasti, kad jie tenkintų tas priklausomybes.
|
8.1. Rekursinės funkcijos
|
Programuojant visada stengiamasi didesnį uždavinį
skaidyti į mažesnius arba sudėtingesnį paversti keliais
paprastesniais.
Veiksmų sudėtingumas kartais priklauso nuo
duomenų. Pavyzdžiui, faktorialą galima apibrėžti šitaip:
n !=
1,
jei n = 1,
(n 1)! ·n,
jei n > 1.
Jei pradinis duomuo lygus vienetui, tai jau
pats apibrėžimas pateikia rezultatą. Taigi vienetas yra pats
paprasčiausias pradinis duomuo, skaičiuojant faktorialą.
Jeigu pradinis duomuo didesnis už vienetą,
tai jo faktorialas išreiškiamas kita, paprastesne operacija
daugyba ir ... faktorialu, bet jau vienetu mažesnio skaičiaus.
Taigi iš karto rezultato negauname. Tačiau, toliau taikydami antrąją
faktorialo apibrėžimo dalį, faktorialą išreiškiame vis ilgesnės
skaičių eilės sandauga:
n !=
= (n 1)! · =
= 3! ·... ·(n 1) ·n =
= 2! ·3 ·... ·(n 1) ·n =
= 1! ·2 ·3 ·... ·(n 1) ·n =
= 1 ·2 ·3 ·... ·(n 1) ·n.
36 paveiksle grafiškai pavaizduota, kaip
einama link vieneto. Kai pasiekiame vienetą, eilėje lieka vien
skaičiai ir juos galime sudauginti. Dauginame iš kairės į dešinę.
Taigi dabar eile einame priešinga kryptimi į dešinę nuo
vieneto.
36 pav. Skaičiaus n faktorialo išreiškimas sandauga 1·2·3·...·(n-1)·n
Jau esame sudarę faktorialo skaičiavimo
algoritmą (žr. 6.2.3 užd.), kuriame skaičiaus n faktorialą
išreiškėme skaičių nuo 1 iki n sandauga. Jau žinojome,
kad faktorialas yra natūraliųjų skaičių sandauga, o
kompiuteriui pavedėme tik juos sudauginti, t. y. atlikti antrąją
uždavinio dalį eiti nuo 1 iki n. Turint funkcijas,
galima kompiuteriui pavesti ir pirmąją uždavinio dalį išsiaiškinti,
ar faktorialas yra skaičių sandauga. Tam pakanka faktorialo apibrėžimą
užrašyti programavimo kalbos žymenimis:
function f (n: integer): integer;
begin
if n = 1 then f := 1
else f := f(n -1)*n
end;
Funkcija ypatinga tuo, kad jos programoje yra
kreipinys į ją pačią, kaip ir faktorialo apibrėžime vėl
faktorialas. Funkcijos ir procedūros, kuriose yra kreipinių į jas
pačias, vadinamos rekursinėmis.
Pateikiame pavyzdžių.
1 pavyzdys. Kėlimą laipsniu galima
apibrėžti šitaip:
an = a, jei n
= 1,
an-1 ·a, jei n > 1.
Užrašome rekursinę kėlimo laipsniu funkciją:
function laipsnis (a, n: integer);
begin
if n = 1 then laipsnis := a
else laipsnis := laispnis(a, n-1)*a
end;
2 pavyzdys. Fibonačio skaičių seka
yra tokia:
1, 1, 2, 3, 5, 8, 13, 21, ...
Jos pirmieji du nariai lygūs vienetui, o bet
kuris tolesnis narys lygus dviejų prieš jį einančių narių
sumai. Taigi n-tasis narys F(n) apibrėžiamas
šitaip:
1,
jei n = 1,
F(n) =
1,
jei n = 2,
F(n
1) + F(n 2), jei n
> 2.
Šį apibrėžimą išreiškiame funkcija:
function fib (n: integer): integer;
begin
if (n = 1) or (n = 2) then fib := 1
else fib := fib(n-2)+fib(n-1)
end;
Fibonačio sekos n-tajam nariui apskaičiuoti
reikia dviejų prieš jį einančių narių dviejų skaičių.
Todėl reikalingi du atramos taškai du skaičiai, kurie
nurodyti apibrėžime (1 ir 2) ir į kuriuos atsiremia rodyklės 37
paveiksle.
37 pav. Fibonačio skaičių radimo schema
Kaip matome, rekursinę funkciją sudaryti
labai paprasta reikia tik matematinį jos apibrėžimą užrašyti
programavimo kalbos žymenimis.
Kreipinys į funkciją iš jos vidaus išreiškia
tos funkcijos veiksmų kartojimą. Tuo rekursinė funkcija panaši
į ciklą. Ji, kaip ir ciklas, turi būti baigtinė.
3 pavyzdys. Duota nebaigtinė rekursinė
funkcija
function ff (x: integer): integer ;
begin
if x = 0 then ff := 1
else if x < 0 then ff := ff(x-1)
else ff := (x+1)
end;
Kai x < 0, iš funkcijos vidaus
kreipiamasi į funkciją ff su vis mažesniu parametru; kai x
> 0, kreipiamasi su vis didesniu parametru. Savaime suprantama,
kad x niekada nebus lygus nuliui, todėl visą laiką
kreipiniai į funkciją kartosis. Vadinasi, ši funkcija yra baigtinė
tik tada, kai x = 0.
Parašius rekursinę funkciją, visada reikėtų
įsitikinti, ar ji baigtinė.
Uždaviniai
8.1.1. Skaičiaus 2 n-tąjį
laipsnį galima apibrėžti šitaip:
2n =
1,
jei n = 0,
2n-1 ·2,
jei n > 0.
Parašykite rekursinę funkciją pagal šį
apibrėžimą.
8.1.2. Duota rekursinė funkcija:
function x (a, b: integer): integer;
begin
if b >= a then x := 0
else x := x(a-b, b) + 1
end;
Kokios šių kreipinių reikšmės:
a) x(9, 4),
b) x(9, 5),
c) x(29, 2)?
Kokią aritmetinę natūraliųjų skaičių
operaciją apibrėžia ši funkcija?
8.1.3. Šiame skyrelyje pateikta
funkcija f apibrėžta kaip natūraliųjų skaičių
faktorialas. Kas
atsitiktų, jeigu
kreipinio f(x) parametras x būtų
neigiamas skaičius? Ką reikėtų
pakeisti funkcijos
apraše, kad f(x) būtų lygus 1, kai x £ 0?
8.1.4. Natūraliųjų skaičių seka
apibrėžiama šitaip:
a1 = 1,
a2n = an ,
a2n+1 = an + an+1 .
Parašykite rekursinę funkciją n-tajam
sekos nariui an rasti.
8.1.5. Didėjančios aritmetinės
progresijos pirmasis narys yra neigiamas, paskutinis narys
yra n, o
skirtumas d. Reikia rasti šios progresijos teigiamų narių
kvadratų sumą.
Parašykite dvi
funkcijas šiam uždaviniui spręsti: rekursinę ir ne rekursinę.
8.1.6. Vadinamasis dvigubas faktorialas
apibrėžiamas šitaip:
f!! = 1×3×5×...×n, kai n
nelyginis skaičius
2×4×6×...×n, kai n
lyginis skaičius
Parašykite rekursinę funkciją skaičiaus n
dvigubam faktorialui rasti.
|
8.2. Rekursinių funkcijų veiksmai
|
Rekursines funkcijas atlieka kompiuteris, o
programuotojas privalo jas taisyklingai užrašyti. Todėl jis gali
ir nežinoti, kokiais paprastesniais veiksmais kompiuteris jas išreiškia.
Tačiau, analizuojant painesnes situacijas, ieškant klaidų
programose, programuotojui kartais pravartu žinoti, kaip
kompiuteris atlieka rekursines funkcijas. Apie tai pakalbėkime plačiau.
8.1. skyrelyje sudarytą faktorialo funkciją
įjungsime į programą:
program rekursija;
function f (n: integer): integer;
begin
if n = 1 then f := 1
else f := n*f(n-1)
end;
begin
write(f(1));
writeln;
write(f(2));
writeln;
write(f(3))
end.
Išnagrinėsime, kaip atliekami trys programos
kreipiniai į faktorialo funkciją.
Primename, kad funkcijos kintamiesiems
neskiriama vietos atmintyje ir neatliekami funkcijos veiksmai tol,
kol į ją nesikreipiama.
Programa rekursija pirmą kartą kreipiamasi į
funkciją f atliekant sakinį write(f(1)). Tai galima įsivaizduoti
taip: vietoj kreipinio f(1) į sakinį rašoma funkcija f (38
pav.), jos kintamiesiems priskiriama vieta atmintyje. Nagrinėjama
funkcija f turi tik vieną kintamąjį parametrą n.
Jam paskirta atmintis 38 paveiksle pavaizduota mažyčiu stačiakampiu.
Po kreipimosi į funkciją į tą atminties vietą įrašoma tikroji
parametro reikšmė, šiuo atveju skaičius 1. Toliau atliekami
funkcijos veiksmai, šiuo atveju sąlyginio sakinio šaka po žodžio
then. Funkcijos vardui f priskiriama vieneto reikšmė.
Pasiekus funkcijos veiksmų pabaigą rodantį žodį end,
funkcijos reikšmė perduodama kreipiniui, o pačiai funkcijai ir
jos kintamiesiems skirta vieta atmintyje panaikinama. Šiuo atveju
funkcija f nesikreipia į save, todėl ji atliekama taip,
kaip ne rekursinė.
38 pav. Funkcijos f(1) reikšmės skaičiavimas.
Plonesnėmis linijomis (su rodyklėmis galuose) parodytas duomenų
persiuntimas, storesnėmis veiksmų eiga
Antrasis kreipinys į funkciją f yra sakinyje write(f(2)).
Dabar ,
ir atliekama sąlyginio sakinio šaka po žodžio else (39
pav.). Čia vėl kreipinys į funkciją f. O jeigu yra
kreipinys, tai į jo vietą įrašomas tos funkcijos aprašas,
paskiriama vieta tos funkcijos kintamiesiems. Taip sukuriamas
naujas, antrasis, funkcijos f egzempliorius, visiškai
nepriklausantis nuo pirmojo (39 pav.). Antrojo funkcijos f
egzemplioriaus faktinis parametras lygus vienetui, todėl atliekama
pirmoji sąlyginio sakinio šaka. Taip apskaičiuojama antrojo
egzemplioriaus funkcijos reikšmė. Ji perduodama į pirmąjį
egzempliorių ir ten įrašoma vietoj kreipinio. Atmintyje
panaikinamas antrasis funkcijos egzempliorius. Dabar, kai vietoj
kreipinio į funkciją f pirmajame egzemplioriuje yra įrašyta
reikšmė (vienetas), apskaičiuojama reiškinio reikšmė (2 * 1=
2), ji priskiriama pirmojo egzemplioriaus funkcijos vardui ir
perduodama į pagrindinę programos dalį. Kompiuterio atmintyje
panaikinamas ir pirmasis funkcijos egzempliorius.
39 pav. Funkcijos f(2) reikšmės skaičiavimas.
Sukuriami du funkcijos egzemplioriai
Atlikus paskutinį programos sakinį
write(f(3))
iš naujo sukuriami trys funkcijos f egzemplioriai
(40 pav.), po to funkcijos rastos reikšmės grąžinamos į jų
kreipinius ir visi funkcijos egzemplioriai pašalinami iš
kompiuterio atmintinės atvirkščia tvarka, negu ten jie buvo įrašyti
(pirma trečias, po to antras ir paskui pirmas).
Bendru atveju, kai funkcijos f parametras
yra n, bus sukuriama n funkcijos egzempliorių (41
pav)..
40 pav. Funkcijos f(3) reikšmės skaičiavimas. Sukuriami
trys funkcijos egzemplioriai
41 pav. Kai skaičiuojama f(n), sukuriama n
funkcijos egzempliorių
Kiekvienas funkcijos egzempliorius turi savus
kintamuosius su sava kompiuterio atmintinės sritimi jų reikšmėms
saugoti. Dėl to rašant rekursines funkcijas naudinga iš funkcijos
iškelti visus nebūtinus kintamuosius.
Pavyzdys. Natūraliųjų skaičių seka
apibrėžiama šitaip:
a1 = x,
a2 = y ,
an = an-1 + an-2 .
Parašysime rekursinę funkciją n-tajam
sekos nariui an rasti. Paprasčiausias sprendimas
būtų toks:
function narys
(n,
{ ieškomo nario nr. }
x,
{ pirmasis narys }
y: integer { antrasis narys } ): integer;
begin
if n = 1
then narys := x
else if n = 2
then narys := y
else narys :=
narys(n-1, x, y) + narys(n-2, x, y)
end;
Seka panaši į Fibonačio seką. Skiriasi tik
pirmieji du nariai. Jie yra nėra konstantos. Todėl kreipinyje į
funkciją juos reikia pateikti kaip funkcijos parametrus. Tačiau
toliau, einant gilyn į rekursiją, jų reikšmės nesikeičia. Todėl
juos galima iškelti iš funkcijos ir naudoti kaip globaliuosius
kintamuosius. Todėl reikia dviejų funkcijų. Į vieną (ne
rekursinę) funkciją su visais trimis parametrais kreipiasi
programa, o ši funkcija kreipiasi į kitą jos viduje esančią
rekursinę funkciją, turinčią tik vieną parametrą.
function narys
(n,
{ ieškomo nario nr. }
x,
{ pirmasis narys }
y: integer { antrasis narys } ): integer;
function nar (n: integer): integer;
begin
if n = 1
then nar
:= x
else if
n = 2
then nar := y
else nar := nar(n-1, x, y) + nar(n-2, x, y)
end;
begin
narys := nar(n)
end;
|
8.3. Rekursinės funkcijos pritaikymo pavyzdys: didžiausio
bendro daliklio uždavinys
|
Norėdami tiksliai suformuluoti, kokie
reikalavimai keliami funkcijai, pirmiausia užrašysime jos antraštę:
function dbd (x, y: integer): integer;
Laikykime, kad abu parametrai yra neneigiami.
Pirmiausia aptarkime ypatingus atvejus: vienas iš parametrų lygus
nuliui, abu parametrai lygūs nuliui. Jeigu vienas parametras lygus
nuliui, tai didžiausiu bendru dalikliu laikysime kitą parametrą,
nelygų nuliui. Jeigu abu parametrai lygūs nuliui, tai bendras jų
daliklis kiekvienas nelygus nuliui skaičius. Susitarkime, kad
tokiu atveju funkcijos reikšmė lygi nuliui.
Dabar jau galime aiškiai suformuluoti uždavinį:
reikia sudaryti dviejų neneigiamų skaičių funkciją didžiausiam
bendram dalikliui rasti. Jeigu abu skaičiai lygūs nuliui, tai
funkcijos reikšmė turi būti lygi nuliui. Jeigu vienas parametrų
lygus nuliui, tai funkcijos reikšmė turi būti lygi kitam nelygiam
nuliui parametrui.
Taigi nulis yra atramos taškas, nuo
kurio galime pradėti rašyti funkcijos veiksmus:
if (x = 0) and (y = 0) then
bdd := 0
else if x = 0 then bdd := y
else if y = 0 then
bdd := x
else ...
Funkcijos pradžią jau turime. Tačiau liko
pati sunkiausia dalis, kuri turi būti po žodžio else.
Pritaikykime didžiausio bendro daliklio savybę:
dviejų skaičių didžiausias bendras daliklis lygus mažesniojo
skaičiaus ir liekanos, gautos didesnįjį skaičių padalijus iš
mažesniojo, didžiausiam bendram dalikliui:
dbd(30, 18) = dbd(18, 30 mod 18) =
dbd(18, 12).
Toliau remdamiesi šia taisykle, gauname:
dbd(18, 12) = dbd(12, 6) = dbd(6, 0).
Taigi skaičiai, kurių didžiausią bendrą
daliklį reikia rasti, nuolat mažėja. Galų gale vienas iš jų
tampa lygus nuliui. O tada jau žinome, kaip rasti bendrą daliklį.
Šiuos veiksmus užrašę programavimo kalba ir
juos prijungę prie ankstesnių, gauname šitokią rekursinę
funkciją:
function dbd (x, y: integer): integer;
{ x >= 0, y >= 0 }
begin
if (x = 0) and (y = 0) then dbd :=
0
else if x = 0 then dbd := y
else if y =
0 then dbd := x
else
if x >= y then dbd := dbd(x mod y, y)
else dbd := dbd(y mod x, x)
end;
Dabar pamėginkime patikrinti ir patobulinti
funkciją dbd.
Pirmos trys sąlyginio sakinio šakos apima
visus atvejus, kai bent vienas pradinis duomuo lygus nuliui. Tai
faktiškai tos pačios skyrelio pradžioje nagrinėtos sąlygos, tik
užrašytos Paskalio kalbos žymenimis, taigi yra teisingos.
Bandykime patobulinti parašytą programos dalį.
Atidžiai išnagrinėję tris pirmąsias sąlyginio sakinio eilutes,
galime jas pakeisti viena eilute:
if (x = 0) or (y = 0) then
dbd := x + y
Norint įsitikinti, kad šia viena eilute išreikšti
tie patys veiksmai, kaip ir trimis ankstesnėmis, reikia įrodyti,
kad abiem atvejais gaunama ta pati rezultato dbd reikšmė, esant
bet kokiems pradiniams duomenims. Įrodoma:
1. Kai (x = 0) and (y = 0) = true, tai
pirmu atveju atliekamas sakinys dbd := 0. Antro atvejo sąlyga (x
= 0) or (y = 0) tenkinama ir atliekamas sakinys dbd := 0.
Taigi abiem atvejais gaunamas tas pats rezultatas.
2. Kai x = 0 ir y ¹ 0, pirmu
atveju atliekamas sakinys dbd := y. Antru atveju sąlyga
tenkinama, ir atliekamas sakinys dbd := x + y. Kadangi x = 0, tai
šis sakinys ekvivalentus sakiniui dbd := y. Taip matome, abiem
atvejais gaunamas tas pats rezultatas.
3. Kai y = 0 ir (x ¹ 0),
kintamuosius x ir y sukeitę vietomis, gauname jau
įrodytą antrą atvejį.
Taigi funkcijos aprašą galima sutrumpinti:
function dbd (x, y: integer): integer;
{ x >= 0, y >= 0 }
begin
if (x = 0) and (y = 0) then dbd :=
x + y
else if x >= y then
dbd := dbd(x mod y, y)
else dbd := dbd(y mod x, x)
end
Dabar patikrinsime dvi paskutines sąlyginio
sakinio šakas. Abiejų šakų didesnysis skaičius (x arba y)
dalijamas iš mažesniojo. Į šias šakas patenkama tol, kol nė
viena kintamųjų x ir y reikšmė nelygi nuliui.
Naujame kreipinyje į funkciją dbd didesnioji kintamojo reikšmė
pakeičiama tų kintamųjų dalybos liekana. Teigiamųjų skaičių
dalybos liekana yra visada mažesnė už dalinį ir daliklį. Taigi
kintamųjų x ir y reikšmės nuolat mažės ir
pagaliau kuriame nors kreipinyje viena jų pasidarys lygi nuliui.
Tada bus patenkama į pirmąją šaką, o ten kreipinių nėra.
Vadinasi, ši rekursinė funkcija baigtinė.
Dabar įsitikinkime, kad rezultatas teisingas.
Kai bent vienas funkcijos parametras lygus
nuliui, tai atliekama pirmoji sąlyginio sakinio šaka. Rezultatas
bus x + y, kuris, kaip jau anksčiau įrodėme, yra
bendras didžiausias skaičių x ir y daliklis.
Kai nė viena kintamųjų x ir y reikšmė
nelygi nuliui, atliekama antra arba trečia sąlyginio sakinio šaka.
Kreipiantis į funkciją dbd, skaičių x ir y
bendras didžiausias daliklis pakeičiamas naujų skaičių bendru
didžiausiu dalikliu, kuris abiejose šakose sutampa su ankstesnių
skaičių bendru didžiausiu dalikliu. Kai bent vienas skaičių
virsta nuliu, patenkama į pirmąją šaką, ir gaunamas teisingas
rezultatas.
Kadangi dalybos su liekana rezultatas
liekana visada mažesnė už daliklį, tai operacijos x mod
y rezultatas visada mažesnis už y. Todėl galime dar
suprastinti funkciją:
function dbd (x, y: integer): integer;
begin
if (x = 0) and (y = 0) then dbd :=
x + y
else dbd := dbd(y mod
x, x)
end
Laikykime, kad x <= y. Tada,
kreipiantis į funkciją dbd iš jos vidaus, pirmuoju
parametru reikia rašyti y mod x, o antruoju
x, nes y mod x < x. Kai į
funkciją dbd kreipiamasi pirmą kartą iš programos
pagrindinės dalies, gali būti netenkinama sąlyga x <= y.
Tada pirmą kartą funkcija atliekama beveik tuščiai pagal ją
tik sukeičiamos parametrų x ir y reikšmės
vietomis. Toliau sąlyga x <= y visada bus
tenkinama. Kai x > 0, o y = 0, pirmiausia taip pat
bus sukeičiamos vietomis parametrų reikšmės. Todėl funkciją
galima dar suprastinti:
function dbd (x, y: integer): integer;
begin
if x = 0 then dbd := y
else dbd := dbd(y mod x, x)
end
Įrodėme, kad paprasčiausio funkcijos
varianto rezultatas teisingas. Kitus funkcijos variantus gavome iš
ankstesnių, pakeitę kai kurias programos dalis trumpesnėmis,
ekonomiškesnėmis, bet ekvivalenčiomis programos dalimis. Todėl,
jei teisingas pradinis funkcijos variantas, turėtų būti teisingi
ir kiti jos variantai.
Kad įsitikintume, jog nepadarėme klaidų,
keisdami ir perrašinėdami funkciją, reikėtų ją patikrinti su
keliomis būdingiausiomis parametrų reikšmėmis:
dbd(0, 25);
dbd(25, 0);
dbd(30, 75);
dbd(13, 13);
dbd(75, 30);
dbd(0, 0);
Pamėginkite atlikti funkciją su nurodytais
kreipiniais ir įsitikinsite, kad rezultatai šitokie:
25 25 15
13 15 0
Norint išbandyti funkciją kompiuteriu, reikia
sudaryti ją gaubiančią programą. Kad iš karto patikrintume
funkciją, esant įvairiems pradiniams duomenims, programoje reikia
parašyti daug kreipinių arba vieną kreipinį cikle.
Pateikiame programą, turinčią šešias
pradinių duomenų poras:
program bandymas;
var a, b, j: integer;
function dbd (x, y: integer): integer;
begin
if x =
0 then dbd := y
else dbd := dbd(y mod x, x)
end;
begin
for j := 1 to 6 do
begin
read(a, b);
writeln(a: 7, b:
7 , dbd(abs(a), abs(b)): 7)
end
end.
Programos pradiniai duomenys gali būti ir
neigiami. Tada randamas jų absoliutinių didumų (modulių) didžiausias
bendras daliklis.
Uždaviniai
8.3.1. Parašykite rekursinę funkciją
dviejų natūraliųjų skaičių didžiausiam bendram dalikliui
(dbd) rasti,
remdamiesi tokiomis dbd savybėmis:
dbd (a, b) = a, jei a
= b;
dbd(a, b) = dbd(a, b a),
jei a < b;
dbd(a, b) = dbd(a b, b),
jei a >b.
8.3.2. Pradiniai duomenys skaičių,
nelygių nuliui, seka. Sekos pabaigoje nulis.
Vartodami funkciją
dbd, sudarykite programą visos sekos skaičių didžiausiam
bendram dalikliui
rasti. Jeigu seką sudaro tik vienas nulis, tai jo didžiausias
bendras
daliklis lygus
nuliui, jeigu nelygus nuliui skaičius ir nulis, tai didžiausias
bendras
daliklis lygus
pirmajam skaičiui.
8.3.3. Sudarykite funkciją dviejų skaičių
mažiausiam bendram kartotiniam rasti. Pavartokite
ją visų skaičių
nuo 1 iki 10 mažiausiam bendram kartotiniam rasti.
8.3.4. Sudarykite loginę funkciją,
patikrinančią, ar du duoti skaičiai yra tarpusavyje pirminiai.
|
8.4. Rekursinės procedūros
|
Rekursinės gali būti ne tik funkcijos, bet ir
procedūros.
1 pavyzdys. Pradiniai duomenys skaičių
seka. Jos ilgis nežinomas. Paskutinis sekos skaičius nulis, o
visi kiti skaičiai nelygūs nuliui. Reikia sudaryti programą
pradiniams duomenims rašyti atvirkščia tvarka. Pavyzdžiui, jeigu
pradiniai duomenys yra skaičiai
3 25 115
400 13 0
tai kompiuteris turi rašyti
0 13 400
115 25 3
Sudarome programą su rekursine procedūra atb:
program atbulai;
procedure atb;
var x: integer;
begin
read(x);
if x <> 0 then
atb;
writeln(x)
end;
begin
atb
end.
Procedūra atb yra be parametrų.
Pagrindinę programos dalį sudaro vienintelis sakinys kreipinys
į procedūrą atb. Procedūra atb turi tik vieną
kintamąjį x. Kiek kartų bus kreipiamasi iš procedūros atb
į ją pačią, priklausys nuo pradinių duomenų sekos ilgio. Išnagrinėkime
atskirus atvejus.
Kai seką sudaro tik vienas nulis (nepamirškime
ir tokio atvejo!), pirmuoju sakiniu perskaitoma x reikšmė,
antrasis sakinys kreipinys į procedūrą atb
neatliekamas (nes x = 0), trečiuoju sakiniu spausdinamas nulis. Štai
ir atlikta procedūra, kartu ir visa programa.
Kai seką sudaro du skaičiai (ir
x2 = 0), pirmasis jų priskiriamas kintamajam x.
Sąlyga tenkinama,
todėl pakartotinai kreipiamasi į procedūrą atb. Antrajame
procedūros egzemplioriuje bus perskaitytas antrasis skaičius
nulis. Sąlyga
netenkinama, ir iš antrojo procedūros egzemplioriaus nebebus
kreipiamasi į procedūrą atb. Trečiuoju sakiniu bus išspausdinta
kintamojo x reikšmė (nulis), ir skaičiavimas grįš į
pirmąjį procedūros egzempliorių. Čia bus atliekamas trečiasis
sakinys write(x) ir rašoma pirmojo pradinio duomens reikšmė
(prisiminkime, kad ji buvo priskirta pirmojo procedūros
egzemplioriaus kintamajam x dar prieš kreipiantis į antrąjį
egzempliorių).
Nesunku įsitikinti, kad n skaičių
sekai sukuriama procedūros atb n egzempliorių.
Spausdinimo sakinys yra po kreipinio į procedūrą, todėl skaičiai
spausdinami atvirkščia tvarka negu buvo kreiptasi į procedūra
(atvirkščia tvarka negu skaičius perskaitė kompiuteris).
Uždaviniai
8.4.1. Duota programa:
program ra;
procedure s (n: integer);
begin
write(n);
if n > 10 then
s(n-1)
else
writeln;
write(n: 4)
end;
begin s(15) end.
Ką parašys kompiuteris, atlikęs programą?
8.4.2. Paaiškinkite, kaip atliekamos šitokios
procedūros:
a)
procedure xxx (n: integer);
begin
if n = 5 then write('*')
else xxx(n-1)
end
b)
procedure yyy (b: boolean);
begin
if b then yyy(true)
end
|
8.5. Rekursija ir ciklas
|
Rekursinių funkcijų ir procedūrų veiksmai
gali būti kartojami be ciklo. Jeigu kreipinys į funkciją arba
procedūrą yra jos pačios viduje, tai reiškia, kad ten bus
pakartotinai atliekami jos pačios veiksmai, tik galbūt jau su
kitais duomenimis. Taigi rekursija išreiškia veiksmų kartojimą.
3.7 skyrelyje sakėme, kad bet kokiai veiksmų
atlikimo tvarkai aprašyti pakanka trijų valdymo struktūrų:
sakinių sekos, sąlyginio sakinio ir ciklo. Ciklą pakeitę
rekursija, gauname kitą trejetą sakinių seką, sąlyginį
sakinį ir rekursiją. Šiomis konstrukcijomis (valdymo struktūromis)
taip pat galima išreikšti kiekvieną veiksmų atlikimo tvarką.
Kadangi rekursija yra abstraktesnė už ciklą
konstrukcija, ją labiau mėgsta teoretikai. Ciklus vertina
praktikai, nes juose konkrečiau nurodoma veiksmų atlikimo tvarka.
Programos su ciklais būna ekonomiškesnės negu tuos pačius
veiksmus aprašančios rekursinės programos.
Teoriškai kiekvieną rekursiją galima
pakeisti ciklu, ir atvirkščiai.
1 pavyzdys. Bendro didžiausio daliklio
funkcijoje (žr. 8.3 skyr.) rekursiją pakeiskime ciklu.
Nagrinėjame antrąjį, šiek tiek patobulintą,
bet dar negalutinį rekursinės funkcijos variantą Kadangi iš
anksto neaiškus veiksmų kartojimo skaičius, tai vartosime while
ciklą. Rekursinės funkcijos pradžioje užrašytą sąlygą
(x = 0) or (y = 0)
galima laikyti ciklo pabaigos sąlyga.
Vadinasi, ciklas turi vykti tol, kol ši sąlyga netenkinama. Todėl
ciklo antraštė turėtų būti šitokia:
while not (x = 0) or (y
= 0) do
Pritaikę loginių reiškinių pertvarkymo
taisykles (žr. 3.2 skyr.), sąlygą (tuo pačiu ciklo antraštę)
suprastiname:
while (x <> 0) and (y
<> 0) do
Dabar galime užrašyti ir visą funkciją:
function dbd (x, y: integer): integer;
begin
while (x <> 0) and (y <> 0) do
if x >= y then x := x
mod y
else y :=
y mod x;
dbd := x + y
end;
Rekursinę funkciją pavyko suprastinti išbraukus
ir sąlyginį sakinį, nes jame galima buvo lengvai sukeisti
vietomis parametrus. Šią funkciją taip pat prastinti neverta,
nes, norint kintamųjų reikšmes sukeisti vietomis, reikėtų naujo
kintamojo ir daugiau prieskyros sakinių.
Rekursiją pakeisti ciklu nesunku ir kituose šiame
skyriuje pateiktuose pavyzdžiuose, išskyrus paskutinį (procedūra
atb, žr. 8 .4 skyr.). Mat jame rekursija vartojama ne tik veiksmams
kartoti, bet ir pradinių duomenų sekai įsiminti ir išsaugoti
kiekviename procedūros atb egzemplioriuje įsimenama vis naujo
pradinio duomens reikšmė. O kol kas nenagrinėjome kitokių būdų
didesniam duomenų kiekiui įsiminti.
Ką tikslingiau naudoti rekursiją ar ciklą,
priklauso nuo konkretaus uždavinio ir jo algoritmo. Universalių
pasirinkimo receptų nėra. Kiekvienu konkrečiu atveju reikia
naudoti vaizdžiausias ir ekonomiškiausias išraiškos priemones.
|
8.6. Sprendimų paieška grįžties metodu
|
Tik nedaugelio uždavinių sprendimus galima išreikšti
formulėmis arba lygtimis. Dažnai sprendinio tenka ieškoti bandymų
keliu.
Pateiksime gana universalų uždavinių
sprendimo metodą, kuris dažnai vadinamas grįžimo arba bandymų
ir klaidų metodu. Sistemingai bandomi visi galimi sprendimų keliai
ir visada atrandamas sprendinys, jeigu tik jis egzistuoja arba, peržiūrėjus
visus galimus kelius, nustatoma, kad sprendinio nėra (gali būti ir
tokių atvejų).
Metodo esmę pailiustruosime laipiojimu
po medį (42 pav.).
42 pav. Medis, po kurį laipioja kirminas, norėdamas
surasti obuolį
Tarkime, kad po medį laipioja kirminas. Nuo žemės
(taško A) jis nori pasiekti obuolį, kabantį ant šakos galo I.
Kol kirminas lipa kamienu iki taško B, jam viskas aišku, nes kito
kelio nėra. Taške B medis šakojasi. Kurią šaką pasirinkti? Mat
kirminas, būdamas viename šakos gale, dar nemato, kas yra kitame
jos gale (obuolys, tuščias šakos galas ar naujas išsišakojimas).
Todėl jis nežino, kurį kelią (kurią šaką) pasirinkti. Belieka
išbandyti visus kelius (ištyrinėti visas šakas). Tam, kad būtų
sistemingai išbandyti visi keliai, sutarkime, kad kirminas visada
pasirenka kairiausią dar neišbandytą šaką. Taigi jis eina į tašką
C, po to į tašką D, po to į tašką E. Toliau nebėra kur
eiti (ir obuolio nėra). Tenka grįžti atgal į tašką D. Dabar iš
taško C kirminas eina jau į tašką G (kelias CD jau išbandytas).
Iš G į H ir vėl tuščias šakos galas. Tenka grįžti į tašką
H. Toliau kirminas eina į tašką I ir sėkmingai pasiekia obuolį.
Uždavinys išspręstas.
Jo sprendinys kelias ABCGI. Šis kelias
buvo nutiestas palaipsniui, išbandant šitokias kelio atkarpas:
A
AB
ABC
ABCD
ABCDE
ABCD
ABCDF
ABCD
ABC
ABCG
ABCGH
ABCG
ABCGH
Atkreipiame dėmesį, kad tada, kai sužinoma,
kad nueita klaidingu keliu (pasiekiamas tuščias šakos galas), uždavinį
spręsti pradedama ne iš naujo, o daromas tiktai vienas žingsnis
atgal ir iš čia vėl bandome eiti. Jeigu žengus žingsnį atgal
pasirodo, kad ir čia nebėra naujų nenagrinėtų kelių, tai žengiamas
dar vienas žingsnis atgal ir t.t., kol pasiekiamas taškas, iš
kurio eina bent vienas dar neišbandytas kelias. Jeigu sugrįžtama
į pradinį taškas ir iš jo nebėra naujų kelių, tai reiškia,
kad išbandyti visi galimi keliai ir nė vienas nepasiekė tikslo.
Tokiu atveju uždavinys sprendinio neturi.
Laipiojimas po medį yra akivaizdi sprendimo
paieškos grįžties metodu iliustracija. Metodą galima taikyti
daugeliui uždavinių spręsti. Tai kelio paieška labirinte, teksto
perskaitymas šachmatų žirgo ėjimu, šachmatų figūrų išdėstymas
lentoje taip, kad būtų tenkinamos tam tikros sąlygos ir daugelis
kitų uždavinių, kurie dėl sprendimo paieškos sudėtingumo dažnai
pateikiami kaip galvosūkiai.
Pavyzdys. Sudarysime šachmatų lentos
apėjimo žirgu algoritmą. Šachmatų žirgo ėjimu turi būti
pereinami visi lentos langeliai taip, kad kiekviename langelyje žirgas
pabuvotų tik vieną kartą. Pradinė žirgo padėtis apatinis
kairysis langelis. Pirmiausia pateiksime algoritmo eskizą. Procedūros
eiti veiksmus detalizuosime vėliau.
const n =
8;
{ lentos dydis }
type koord =
1..n;
{ koordinatės }
lenta = array
[koord, koord] of integer;
procedure žirgas (var len: lenta);
var i, j: koord;
viskas:
boolean;
procedure eiti (i:
integer;
{ ėjimo numeris }
x, y:
koord;
{ pradinė žirgo padėtis}
var len:
lenta;
viskas:
boolean);
{ užpildyta visa lenta }
Ėjimai surašomi į lentą (t.y. į masyvą len).
Jie pradedami nuo langelio (x, y) laikoma, kad ten jau yra žirgas.
Ėjimai numeruojami pradedant skaičiumi i. Kintamojo viskas
reikšmė true, jeigu sprendinys egzistuoja (t.y. po vieną
kartą žirgas apsilankė visuose langeliuose) ir false priešingu
atveju.
begin
{ žirgas }
viskas := false;
for i := 1 to n do
for j := 1 to n do
len[i,
j] := 0;
len[1, 1] :=
1; {
pradinė žirgo padėtis }
eiti (2, 1, 1, len, viskas);
end;
Algoritme užrašyti veiksmai pakankamai aiškūs.
Visa uždavinio sprendimo esmė slypi procedūroje eiti, kuri turi užpildyti
ėjimų eilės numeriais visus likusius lentos langelius.
Detalizuokime šią procedūrą.
Sudaryti procedūrą, kuri iš karto išspręstų
visą uždavinį (t.y. užpildytų visus lentos langelius žingsnių
numeriais), sunku. Todėl uždavinį suprastinsime panaudodami
rekursiją. Sudarysime procedūrą, kuri darytų tik vieną žirgo
ėjimą ir užpildytų tik vieną lentos langelį. Tam, kad būtų
daromas naujas ėjimas, procedūra turi vėl kreiptis pati į save.
Kreipiniai tęsiasi tol, kol užpildoma visa lenta arba prieinama
aklavietė, t.y. lenta dar neužpildyta, o eiti nėra kur. Tada grįžtama
atgal ir bandoma eiti nauju keliu.
Kai žirgas nėra lentos krašte, galimi ėjimo
variantai, parodyti paveiksle. Taigi, jeigu pradinė žirgo padėtis
masyvo len langelis len[x, y], tai bet kuri (viena
iš aštuonių) nauja padėtis parodyta 43 paveiksle.
43 pav. Šachmatų žirgo ėjimai
len[x + cx[k], y + cy[k]]
Čia k - varianto eilės numeris, o
masyvų cx ir cy reikšmės nustatomos iš pateikto brėžinio:
cx[1] := 2; cy[1] := 1;
cx[2] := 1; cy[2] := 2;
cx[3] := -1; cy[3] := 2;
cx[4] := -2; cy[4] := 1;
cx[5] := -2; cy[5] := -1;
cx[6] := -1; cy[6] := -2;
cx[7] := 1; cy[7] := -2;
cx[8] := 2; cy[8] := -1;
Kai žirgas yra arčiau lentos krašto, tai
variantų skaičius mažesnis reikia atmesti tuos variantus, kai
bent vienas (arba abu) masyvo len indeksai nepatenka į
atkarpą 1..n (t.y. nurodo langelį už lentos ribų).
Pateikiame procedūrą eiti.
procedure eiti (i:
integer;
{ ėjimo numeris }
x, y:
koord;
{ pradinė žirgo padėtis }
var len: lenta;
iskas: boolean); { užpildyta visa lenta }
const nn =
64;
{ lentos dydis n“ n }
cx: array [1..8] of integer =
(2, 1. -1, -2, -2, -1, 1, 2);
cy: array [1..8] of integer =
(1, 2, 2, 1, -1, -2, -2, -1);
var k:
0..8;
{ varianto numeris }
u, v:
integer;
{ nauja žirgo padėtis }
begin
{ eiti }
k := 0;
repeat
k := k + 1;
u := x + cx[k];
v := y + cy[k];
if (u >= 1) and (u
<= n) and (v >= 1) and (v <= n)
then
{ naujos koordinatės dar patenka į lentą }
if len[u, v] = 0
then
{ langelis dar tuščias }
begin
len[u, v] := i;
if i < nn then
begin
eiti (i+1, u, v, len, viskas);
if not viskas then len[u, v] := 0
end
else viskas := true
end
until
viskas
{ užpildyta visa lenta }
or (k =
n);
{ peržiūrėti visi variantai }
end;
{ eiti }
Belieka procedūrą įdėti į programą.
Pastaba. Masyvo ir įrašo tipų
konstantas turi tik Turbo Paskalis. Jeigu jų nenaudotume, vietoj
konstantų cx ir cy reikėtų aprašyti tokio pat tipo
kintamuosius ir programos (procedūros) pradžioje jiems priskirti
pradines reikšmes.
Panašiai rekursinės programos sudaromos ir
kitiems uždaviniams, kuriuos sprendžiant variantai peržiūrimi
tol, kol gaunamas bent vienas sprendinys, arba nustatoma, jog
sprendinys neegzistuoja. Jeigu norima rasti visus galimus
sprendinius, tai po pirmojo rasto sprendinio skaičiavimai
nebaigiami ieškoma kitų sprendinių tol, kol randami visi.
Abiejuose pavyzdžiuose pateikėme rekursinius
algoritmus. Šios rūšies uždaviniams rekursija gerai tinka,
kadangi paieškos požiūriu visi kelio taškai yra lygiaverčiai.
Todėl nuėjus į naują tašką tolesnį kelią galima ieškoti vėl
pagal tą patį algoritmą. Tačiau galima parašyti ir
nerekursinius algoritmus juk kiekvieną rekursinį algoritmą
galima išreikšti ne rekursiniu (iteraciniu) algoritmu. Tiktai
nenaudojant rekursijos tektų parašyti šiek tiek daugiau veiksmų
ir tuos, kuriuos neišreikštiniu pavidalu atlieka rekursija per
procedūrų (arba funkcijų) parametrų perdavimo mechanizmą.
Praktikos darbas
8.6.1. Kelio paieška labirinte.
Labirintas vaizduojamas n x m (n, m nelyginiai
skaičiai) langelių dydžio lenta (44 pav.) Vieni langeliai juodi,
kiti balti. Vaikščioti galima tik baltais langeliais
horizontaliai arba vertikaliai. Eiti įstrižai negalima. Kelias
prasideda nuo centrinio langelio. Todėl jis turi būti baltas.
Reikia rasti bent vieną kelią iš centrinio langelio į lentos kraštą.
Parašykite algoritmą keliui rasti ir
apipavidalinkite jį rekursine procedūra. Po to procedūrą įjunkite
į programą ir išbandykite kompiuteriu.
a
b
44 pav. 9 x 21 langelių dydžio labirintas.
Pavaizduoti du variantai: a) tuščias tik centrinis langelis (iš
jo išėjimo nėra) ir b) yra daugiau tuščių langelių (iš
centrinio langelio yra du išėjimai abu į viršų)
|
E Ankstesnis
puslapis |
3
Turinys |
Kitas
puslapis F |
|
|
|
|