Peatükk 3 Korduslaused

Arvutite võimest täita miljoneid käske sekundis oleks üsna vähe kasu, kui iga käsk tuleks eraldi välja kirjutada --- sellise lähenemise korral jätkuks kogu maailma programmeerijatest vaevalt mõne tänapäevase protsessori jõudluse ärakasutamiseks. Käesolevas peatükis vaatleme korduslauseid, mille abil on võimalik üht programmilõiku täita kuitahes palju kordi ja seega lühikese programmi abil väga suur hulk tööd ära teha.

3.1 Korduslause mõiste

Kordus- ehk iteratsiooni- ehk silmuselause (ingl loop statement) kõige levinum kuju on

senikui t
käsud
lõppsenikui

Rida senikui t nimetatakse selle korduse päiseks ja lõiku käsud korduse kehaks. Kui päises olev tingimus t kehtib, täidetakse korduse kehas olevad käsud ja pöördutakse seejärel tagasi päise juurde. Kui tingimus ikka veel kehtib, täidetakse uuesti käsud jne, kuni ükskord saabub hetk, kui t enam ei kehti. Siis jätkub algoritmi täitmine lõppsenikui järel olevast lausest.

Edasise jaoks on kasulik tähele panna, et vastavalt definitsioonile on eeltoodud korduslause samaväärne (lõpmatu) konstruktsiooniga

kui t
    käsud
    kui t
       käsud
       kui t
          käsud
          ...
       lõppkui
    lõppkui
lõppkui

3.1.1 Korduse invariant

Korduslauset sisaldava algoritmi vahetingimuste leidmiseks pöörame kõigepealt tähelepanu sellele, et korduse kehas olevate käskude täitmise järel võib juhtuda, et kohe hakatakse neidsamu käske uuesti täitma. Seega on korduse keha ühe täitmise järeltingimus ühtlasi ka sellesama korduse keha järgmise täitmise eeltingimus (täpsemalt küll selle osa).

Seda korduse keha eel- ja järeltingimuse ühisosa nimetataksegi korduse invariandiks (ingl loop invariant), vahel ka tsükli invariandiks.

Selleks, et vajalik eeltingimus oleks täidetud ka korduse keha esimesel läbimisel, peab invariant kehtima ka vahetult enne korduslauset. Algoritmi samme, mis selle tagavad, nimetatakse korduse algatamiseks (ingl loop initiation).

Seega on korduslausega seotud vahetingimused

korduse algatamine
--- vahetingimus: p
senikui t
    --- vahetingimus: p Ù t
    korduse keha
    --- vahetingimus: p
lõppsenikui
--- vahetingimus: p Ù Ø t

(kus p on muidugi selle korduse invariant).

Korduslause koostamist on kasulik alustada just selle invariandi leidmisest. Vaatleme näitena n-elemendilise arvumassiivi a_{1 ... n} elementide summeerimist nii, et korduse lõpuks oleks summa muutujas s.

Milline võiks olla selle korduse invariant? Ilmselt on meil summeerimise ajal osa elemente juba kokku liidetud ja osa veel liitmata. Kõige lihtsam on alustada summeerimist massiivi ühest otsast, siis saame juba liidetud ja veel liitmata elementide üle pidada arvet üheainsa abimuutuja i abil, mis osutab viimasena summasse liidetud elemendi positsiooni ehk järgmisena liidetavale elemendile eelnevat positsiooni.

Korduse invariant oleks seega s = a₁ + a₂ + ... + a_i ja selle säilitamiseks peame iga järjekordse elemendi summasse liitmisel edasi nihutama ka järjehoidjat, see tähendab suurendama i väärtust.

Millised tegevused sobivad sellise korduse algatamiseks? Loomulik on alustada seisust, kus ükski element pole veel summasse liidetud; ka i peab siis olema 0 --- järgmisena liidame summasse jada esimese elemendi a₁.

Kui kaua tuleks sellist kordust täita? Ilmselt seni, kuni on veel liitmata elemente, ehk siis seni, kuni kehtib i < n.

Seega otsitav kordus (koos algatamisega) võiks olla

i¬0
s¬0
senikui i < n
i¬i + 1
s¬s + a_i
lõppsenikui

3.1.2 Korduse osaline õigsus

Korduse osalise õigsuse (ingl partial correctness) tõestamiseks on vaja tõestada

korduse algatamise õigsus: on vaja näidata, et korduse algatamise käsud tagavad korduse invariandi p kehtivuse vahetult korduslause täitmise eel;
korduse invariandi säilimine: on vaja näidata, et eeltingimuse p Ù t kehtimisest korduse keha täitmise eel järeldub invariandi p kehtimine korduse keha täitmise järel;
korduse järeltingimuse kehtimine: on vaja näidata, et korduslause töö lõppedes kehtivast vahetingimusest p Ù Ø t järeldub algoritmi järgmise sammu tööks vajalik eeltingimus.

Massiivi summeerimise näite jaoks järeldub kõigi kolme nõutud tingimuse täidetus vahetult eelmise lõigu arutelust, millega me invariandi ja korduse tingimuse valisime.

3.1.3 Korduse täielik õigsus

Erinevalt teistest senivaadeldud juhtkonstruktsioonidest (järjend ja valik) pole korduse kasutamisel alati garanteeritud selle töö lõppemine.

Näiteks massiivi summeerimiseks leitud korduslause kehast mõlema omistamise eemaldamisel (korduse kehaks jääb tühi käsk) saame korduse, mis rahuldab küll kõiki osalise õigsuse nõudeid, kuid ei lõpeta tööd, kui n > 0.

Algoritmi osalise õigsuse mõiste tähendabki seda, et algoritm annab töö lõppedes alati õige vastuse, kuid võib mõnede sisendandmete korral lõpmatuseni tööle jääda.

Algoritmi täieliku õigsuse (ingl full correctness) tõestamiseks on vaja tõestada

algoritmi osaline õigsus: on vaja näidata, et kui see algoritm oma töö lõpetab, on ta saavutanud nõutud tulemuse (formaalselt väljendub see järeltingimuse kehtimises);
algoritmi peatumine: on vaja näidata, et algoritm lõpetab oma töö mistahes korrektsete (eeltingimust rahuldavate) sisendandmete korral.

Tasub märkida, et esimeses peatükis toodud üldkujuga algoritmi õigsuse tõestus vastab algoritmi osalisele õigsusele. Algoritmi täieliku õigsuse tõestamiseks on lisaks vaja näidata, et algoritmi iga samm lõpetab oma töö.

3.1.4 Korduse variant

Muidugi võib kordusega algoritmi täieliku õigsuse tõestamisel korduse keha täitmise arvu lõplikkust näidata ükskõik millise vettpidava arutluse abil. Aga et tegemist on sageli lahendatava ülesandega, siis on selle lahendamiseks välja mõeldud tüüptehnika.

Korduse variandiks (ingl loop variant) nimetatakse mittenegatiivset täisarvulist suurust t, millel on järgmised omadused

t väheneb korduse keha igal täitmisel vähemalt 1 võrra;
kui t väärtus on 0, siis korduse täitmine lõpetatakse.

Need kaks omadust koos tagavad, et t on korduse keha täitmiste arvu ülemine tõke: see tähendab, et t väärtus korduse keha täitmise eel on alati vähemalt sama suur kui selle korduse keha veel teha jäänud täitmiste arv; seetõttu nimetatakse teda ka tõkkefunktsiooniks (ingl bound function).

Sellise t olemasolu tagab alati, et korduse täitmine lõpeb teatava arvu sammude järel, sest pole võimalik koostada lõpmatut kahanevat positiivsete täisarvuliste liikmetega jada.

Näiteks massiivi summeerimise korduse variandiks sobib t = n - i:

kuna n väärtus korduse täitmisel ei muutu ja i väärtus suureneb korduse keha igal täitmisel 1 võrra, peab t väärtus samal ajal 1 võrra vähenema;
kui t = 0, siis i = n ja korduse täitmine lõpetataksegi.

Mitte alati ei ole võimalik korduse varianti leida. Mõnikord tähendab see, et kordus on tõesti vigane (ja selle algoritmi järgi kirjutatud programm võib ``rippuma'' jääda); mõnikord tähendab see, et kordus on lihtsalt variandi leidmiseks sobimatu kujuga ja selle täieliku õigsuse tõestamiseks tuleb kasutada muid vahendeid.

Mõnikord võib üsna lihtsa korduse täieliku õigsuse tõestamine üllatavalt raskeks pähkliks osutuda. Näiteks pole mitmete väljapaistvate matemaatikute katsed korduse

--- eeltingimus n > 0
senikui n > 1
    kui n / 2 Î N
       n¬n / 2
    muidu
       n¬3n + 1
    lõppkui
lõppsenikui

täielikku õigsust tõestada või ümber lükata siiani vilja kandnud. Kordus on n kõigi seni uuritud väärtuste korral oma töö lõpetanud, kuid pole kindel, et ta seda alati teeb.

Matemaatilises mõttes sobiks selle ülesande (enim tuntud 3n+1 ülesande ja Ulami ülesande nime all) lahenduseks nii tõestus, et see kordus lõpetab oma töö n mistahes positiivse algväärtuse korral kui ka tõestus, et n mingi väärtuse korral jääb see kordus tõesti lõpmatuseni tööle, programmeerimise mõttes näeks me muidugi parema meelega, et lahendus oleks positiivne: et õnnestuks tõestada algoritmi täielik õigsus.

3.1.5 Terviklik näide

Naturaalarvu n faktoriaal (mida tähistatakse n!) defineeritakse järgmiselt:

n! =

ì
í
î

1,	kui n = 0,
1 · 2 · ... · n,	kui n > 0.

Antud arvu faktoriaali arvutamisel pole muidugi erilist vahet, kas korrutada tegureid n! avaldises kokku vasakult paremale või paremalt vasakule.

Otsustame näiteks paremalt vasakule korrutamise kasuks ja tähistame abimuutuja i abil järgmisena korrutisse lisatava teguri.

Selliste tähistuste korral on meil korduse iga läbimise alguses korrutisse lisamata tegurid 1 ... i. Pärast selle tähelepaneku tegemist on juba lihtne välja kirjutada kogu kordus koos kõigi oluliste vahetingimustega:

--- eeltingimus n ³ 0
f¬1
i¬n
--- vahetingimus: f = n! / i!
senikui i > 0
    --- vahetingimus: i > 0 Ù f = n! / i!
    f¬i * f
    --- vahetingimus: f = n! / i! · i = n! / (i-1)!
    i¬i - 1
    --- vahetingimus: f = n! / i!
lõppsenikui
--- vahetingimus: i = 0 Ù f = n! / i!

Algoritmi osalises õigsuses veendumiseks paneme tähele, et

korduse algatamine on korrektne: kui i = n, siis n! / i! = n! / n! = 1 = f;
korduse samm säilitab invarianti vastavalt selles välja toodud vahetingimustele;
korduse lõpetamine on korrektne: kui i = 0, siis n! / i! = n! / 1 = n! ja seega viimasest vahetingimusest järeldubki, et f = n!.

Algoritmi täielikus õigsuses veendumiseks paneme lisaks tähele, et tõkkefunktsiooniks sobib väga hästi i väärtus ise.

3.2 Kordusskeemide liigid

Programmikeeltes on olemas mitmeid veidi erineva ülesehitusega korduslauseid, mille sobivuse ühes või teises olukorras määrab üldiselt mugavus.

3.2.1 Loendajaga kordus

Loendajaga korduse üldkuju on

korda i¬a ... b
käsud
lõppkorda

ja see on samaväärne kordusega

i¬a
senikui i £ b
käsud
i¬i + 1
lõppsenikui

Loendajaga korduse õigsuse tõestamiseks on üks võimalus esitada see just eeltoodud kujul ja rakendada siis lõikudes 3.1.2 ja 3.1.3 vaadeldud tehnikaid.

Loendajaga kordust on mugav kasutada, kui korduse keha täitmiste arv on teada kohe korduslauseni jõudmisel. Näiteks on arvumassiivi summeerimise algoritmi loendajaga kordust kasutav versioon veidi ülevaatlikum:

s¬0
korda i¬1 ... n
    --- vahetingimus: s = a₁ + ... + a_i-1
    s¬s + a_i
    --- vahetingimus: s = a₁ + ... + a_i
lõppkorda

Mõnes keeles (näiteks Pascalis) ei ole lubatud korduse juhtmuutuja i väärtuse muutmine korduslause kehas --- sellise lubamatu operatsiooni tagajärjel võib programmi käitumine muutuda ettearvamatuks. Mõnes keeles (näiteks Basicus) on loendajaga korduse süntaksis olemas võimalus näidata loendaja suurendamise samm.

3.2.2 Eelkontrolliga kordus

Eelkontrolliga korduslause üldkuju on

senikui t
käsud
lõppsenikui

Lõigus 3.1 vaatlesime korduslauseid just eelkontrolliga korduslause näitel, seega pole selle skeemi tähendust enam vaja selgitada.

Eelkontrolliga lauset on hea kasutada, kui korduse keha täitmise kordade arv pole ette teada, vaid lõpetamise vajadus selgub alles siis, kui korduse keha on juba piisavalt täidetud.

Praktikas väga levinud näide on failist tekstiridade lugemine --- tekstifaili avamisel pole üldiselt teada, mitu rida failis on, seega pole praktiliselt muud võimalust kui iga rea lugemisel kontrollida, kas fail sai läbi või ei saanud.¹

3.2.3 Järelkontrolliga kordus

Nagu nimestki arvata võib, erineb järelkontrolliga korduslause eelkontrolliga lausest selle poolest, et tingimuse täidetust kontrollitakse mitte enne, vaid pärast korduse keha täitmist.

Järelkontrolliga korduslause esineb levinud programmikeeltes kahel erineval kujul. Neist kahest kujust esimene,

korda
käsud
senikui t

on samaväärne eelkontrolli kasutava konstruktsiooniga

käsud
senikui t
käsud
lõppsenikui

ning teine,

korda
käsud
kuni t

on samaväärne konstruktsiooniga

käsud
senikui Ø t
käsud
lõppsenikui

Nagu näha, täidetakse järelkontrolliga korduslauses korduse kehaks olevaid käske alati vähemalt üks kord ja selle korduslause kahe variandi ainuke erinevus on see, et ühel juhul näidatakse korduslause tingimusena korduse täitmise jätkamis- teisel juhul aga lõpetamistingimus.

Kahe vastandliku variandi kasutamine on tingitud inglise keele eripärast², kummagi olemasolu või puudumine on põhiliselt konkreetse programmikeele autori(te) maitse küsimus.

Üldiselt kasutatakse seda liiki kordust praktikas harvemini kui loendajaga või eelkontrolliga kordust.

3.2.4 Muud kordusskeemid

Tingimuseta kordus, mille üldkuju on

korda
käsud
lõppkorda

töötab alati lõpmatuseni ja pole sellisel kujul ilmselt eriti praktiline.

Seda liiki kordust kasutatakse (keeltes, kus see üldse olemas on) alati koos katkestusega kujul

korda
    eel-käsud
    kui t
       katkesta
    lõppkui
    järel-käsud
lõppkorda

Keeltes, kus katkestus olemas on, saab seda tavaliselt kasutada ka teiste korduste täitmise ``ennetähtaegseks'' lõpetamiseks. Keeltes, kus katkestus puudub, saab selle asendada abimuutujaga ja eel- või järelkontrolliga. Näiteks eeltoodud kordus on samaväärne skeemiga

l¬väär
senikui Ø l
    eel-käsud
    l¬t
    kui Ø l
       järel-käsud
    lõppkui
lõppkorda

3.3 Korduste pesastamine

Kuigi teoreetiliselt on iga algoritm võimalik esitada ülimalt ühe korduslause abil, on praktikas sageli mugavam kasutada mitut kordust.

Vaatleme näiteks järjestamisülesannet: antud on n-elemendiline arvumassiiv a_{1 ... n}; järjestada selle elemendid mittekahanevalt (see tähendab nii, et a₁ £ a₂ £ ... £ a_n).

Tegemist on klassikalise ülesandega, mille lahendamiseks on väga palju erinevaid algoritme, siinkohal vaatleme neist üht lihtsamat, mida tuntakse pistemeetodi (ingl insertion sort) nime all.

Meetodi idee on hoida massiivi algusosa elemente omavahel järjestatult ja kasvatada seda järjestatud osa, pistes veel järjestamata elemente nende õigetele kohtadele juba järjestatud elementide vahele.

Algoritmi põhiosaks on seega kordus, mille igal sammul kehtib invariant a₁ £ a₂ £ ... £ a_i-1 mingi i jaoks. Kuna tühi jada on alati järjestatud, kehtib invariant i = 1 jaoks triviaalselt ja korduse algatamiseks polegi vaja midagi teha. Kui invariant kehtib i = n + 1 jaoks, on kogu massiiv sobivalt järjestatud ja korduse võib lõpetada.

Otsitava algoritmi üldkuju on seega

korda i¬1 ... n
--- invariant: a₁ £ a₂ £ ... £ a_i-1
korduse keha
lõppkorda

ja jääb vaid üle kirjutada korduse keha nii, et selle igal täitmisel suureneb i väärtus, mille jaoks invariant kehtib.

Selleks kasutame korduse kehana omakorda kordust. Vaatleme esimest veel järjestamata elementi a_i ja võrdleme teda oma vasakpoolse naabriga: kui see on suurem kui a_i, vahetame nad omavahel ja jätkame vaadeldava elemendi (nüüd juba a_i-1) võrdlemist oma uue vasakpoolse naabriga jne.

Seega on sisemise korduse invariant a_j £ a_j+1 £ ... £ a_i. See tingimus kehtib j = i jaoks triviaalselt järelikult pole ka selle korduse algatamiseks peale j algväärtustamise midagi muud teha. Kui invariant kehtib j = 1 jaoks, olemegi saavutanud välimise korduse invariandi senisest ühe võrra suurema i jaoks ja võime lõpetada.

Järgneva algoritmi täielikus õigsuses veendumiseks paneme veel tähele, et mõlemad kordused lõpetavad kindlasti oma töö. Välimise korduse variandiks sobib t₁ = (n + 1) - i ja sisemise omaks t₂ = j - 1.

Algoritm 1 Järjestab antud massiivi elemendid mittekahanevalt
Sisend: a_{1 ... n} --- sorteeritav massiiv
Väljund: a_{1 ... n} --- väärtused vahetatud nii, et " i < n : a_i £ a_i+1
Abimuutujad: i, j

korda i¬1 ... n
--- invariant: a₁ £ a₂ £ ... £ a_i-1
j¬i
senikui j > 1
--- invariant: a_j £ a_j+1 £ ... £ a_i
kui a_j-1 > a_j
a_j-1«a_j
j¬j-1
muidu
j¬1
lõppkui
lõppsenikui
lõppkorda

(siin ja edaspidi kasutame kahe muutuja väärtuste vahetamiseks lühiduse huvides süntaksit a«b).

Ülesanded

Ülesanne 1 Kirjutada kordus, mis leiab summa

1 + 1/2 + 1/3 + ... + 1/n.

Kirjutada välja selle korduse eel- ja järeltingimus, invariant ning variant. Tõestada selle osaline ja täielik õigsus.

Ülesanne 2 Kirjutada kordus, mis leiab antud arvumassiivi maksimaalse väärtuse. Tõestada selle õigsus.

Ülesanne 3 Kirjutada kordus, mis leiab antud arvumassiivi maksimaalse väärtusega elemendi indeksi. Tõestada selle õigsus. Millise indeksi väljastab see kordus, kui massiivis on mitu maksimaalse väärtusega elementi?

Ülesanne 4 Kirjutada kordus, mis leiab antud arvumassiivist suuruselt teise väärtuse. Tõestada selle õigsus. Kontrollida, et programm töötab õigesti ka siis, kui massiivis on mitu maksimaalse väärtusega elementi.

Ülesanne 5 Kirjutada kordus, mis summeerib antud arvumassiivi need elemendid, millele eelnev element on positiivne. Tõestada selle õigsus.

Ülesanne 6 Kirjutada kordus, mis summeerib antud arvumassiivi positiivsed elemendid, millele eelnev ja järgnev element on negatiivsed. Tõestada selle õigsus.

Ülesanne 7 Kirjutada kordus, mis leiab summa

1 + 1/2! + 1/3! + ... + 1/n!.

Tõestada selle õigsus. (Mitte kasutada kahte pesastatud kordust.)

Ülesanne 8 Vaatleme lõigus 3.2.4 toodud skeemi, mis kasutab katkestusega korduse simuleerimiseks eelkontrolliga kordust ja abimuutujat. Koostada analoogiline skeem, mis kasutab katkestusega korduse simuleerimiseks järelkontrolliga kordust ja abimuutujat. Põhjendada, et teie skeem on samaväärne lõigus 3.2.4 toodud skeemiga.

Ülesanne 9 Koostada arvumassiivi elementide järjestamiseks algoritm, mis suurendab massiivi alguses olevat järjestatud osa sel teel, et leiab veel järjestamata elementide hulgast minimaalse ja paigutab selle järjestatud osa lõppu. Tõestada selle algoritmi õigsus.

1: Väärib eraldi märkimist, et ka faili lõppemise kontroll on erinevates süsteemides põhimõtteliselt erinevalt lahendatud. Näiteks Pascali ja Basicu funktsioonid annavad ette teada, kui järgmine katse failist midagi lugeda ebaõnnestuks faili lõppemise tõttu; C ja C++ funktsioonid seevastu annavad alles tagantjärele teada, kui viimane juba tehtud katse failist lugeda sel põhjusel ebaõnnestus.
2: Erinevalt eesti keelest, kus tsüklilise tegevuse märkimiseks kasutatakse põhiliselt ühte lausekonstruktsiooni ``korda..., kuni...'', on inglise keeles neid kaks: ``repeat...while...'' ja ``repeat...until...'', kusjuures esimeses neist on ``while'' järel jätkamistingimus, teises aga ``until'' järel lõpetamistingimus.