Programmeerimise alused, 4: Veelkord korduslaused

Jätkub arvutiprogrammide koostamise põhimõtteid ja –võtteid tutvustav artiklisari, mis algas jaanuaris. Seekord vaatleme eelmises numbris ette võetud korduslausete teemat veidi põhjalikumalt.

Esimese kodutöö lahendus

Eelmise numbri kodustest ülesannetest esimese lahendamiseks oleks võinud ajakirjas toodud tekstist kaks koopiat teha, teises koopias tingimuse

IF Left(nimi, 1) = "A" THEN

asemel

IF Left(nimi, 1) <> "A" THEN

kirjutada ja siis muidugi ka väljastatavaid teateid muuta. Teine variant oleks olnud luua muutujaid S ja N kahes eksemplaris, üks paar A-täheliste ja teine muude jaoks:

Sheet = ThisComponent.CurrentController.ActiveSheet
SA = 0 : NA = 0 ' A-täheliste summa ja arv
SM = 0 : NM = 0 ' muude summa ja arv
FOR I = 0 TO 18 STEP 2
nimi = Sheet.getCellByPosition(0, I).Formula
hinne = Sheet.getCellByPosition(0, I + 1).Value
IF Left(nimi, 1) = "A" THEN
SA = SA + hinne : NA = NA + 1
ELSE
SM = SM + hinne : NM = NM + 1
ENDIF
NEXT I
IF NA > 0 THEN
MsgBox("A-täheliste keskmine on " & SA / NA)
ELSE
MsgBox("Pole ühtki A-tähelist")
ENDIF
IF NM > 0 THEN
MsgBox("Muutäheliste keskmine on " & SM / NM)
ELSE
MsgBox("Pole ühtki muutähelist")
ENDIF

Kindlasti oleks mõni võimalus veel.

Korduse invariant

Enne teise ülesande lahenduste juurde asumist uurime natuke üldisemat teooriat. Kordusega programmide kirjutamise peamine raskus on, et korduse kehaks olevaid käske võidakse täita kahest erinevast algseisust: esimesel läbimisel korduse eel olevate käskude loodud seisust (joonis 1, nool 1), igal järgmisel aga korduse keha eelmise läbimisega loodud seisust (nool 2).

Joonis 1: Kaks sisenemist korduse kehasse

Üldiselt läheb kordusega programmi kirjutamine palju libedamalt, kui me kohe alguses läbi mõtleme, millised on need tingimused, mille kehtimist me korduse kehas tööd alustades eeldame (ja mille kehtivuse me endale järgmiseks ringiks tagama peame). Neid tingimusi nimetatakse korduse invariandiks.

Näiteks eeltoodud keskmiste hinnete arvutamise programmis oleva korduse invariandi võib sõnastada nii: korduse iga läbimise alguses on NA, NM, SA, SM reale I eelnevatel olnud A-täheliste ja muutäheliste nimedega õpilaste arvud ja hinnete summad. Nii lihtsa korduse võime muidugi ka ilma invariandile mõtlemata valmis kirjutada, aga mida keerulisem kordus, seda kasulikum on selle invariant korralikult läbi mõelda.

Sarnaselt sisenemisega on ka korduse kehast väljumiseks kaks võimalust: esimesel juhul jätkame uuesti korduse keha täitmisega (joonis 1, nool 2), teisel juhul aga väljume kordusest (nool 3) ja jätkame programmi täitmist korduse järel olevatest käskudest. Muidugi tuleb ka selles pooles mõlemad variandid läbi mõelda.

Pistemeetod

Püüame nüüd seda mõtteviisi teise koduse ülesande lahendamisel kasutada. Ülesande püstituses oli vihje, et sorteerimiseks on vaja kaks kordust üksteise sisse panna. Järelikult on meil vaja ka kaht invarianti — üht kummagi korduse jaoks.

Joonis 2: Pistemeetodil sorteerimine

Välimise korduse invariandist alustades tundub üsna loomulik mõte oletada, et meil on tabeli alguses olevad read juba omavahel õigesse järjekorda sorteeritud (joonis 2, kolm ülemist elementi) ja me tahame sorteeritud osa pikendada sel moel, et pistame nende järel oleva (neljanda) elemendi nende vahele tema õigesse kohta.

Selleks võrdleme sisemises korduses seda neljandat elementi oma ülemise naabriga (joonisel vasakul). Kui neljas element peaks kolmandast eespool olema, vahetame nad ära ja võrdleme endist neljandat tema uue ülemise naabriga (joonisel keskel). Nii jätkame seni, kuni endine neljas element jõuab naabrini, kellest ta enam mööda minna ei tohi (joonisel paremal).

Kulutades veel veidi aega, et mõelda järele, kuidas toimida äärmuslikel juhtudel (näiteks kogu sorteerimise alguses, kui “juba sorteeritud” osa koosneb 0 reast, või järjekordsele elemendile koha otsimisel juhul, kui ta on juba tõusnud pingereas esimeseks ja seega pole enam naabrit, millega teda võrrelda), saame tulemuseks algoritmi, mida tuntakse pistemeetodi nime all.

Ülevaatlikkuse huvides sorteerib järgnev näide paaride “nimi + hinne” asemel arvujada elemendid kasvavalt:

Sheet = ThisComponent.CurrentController.ActiveSheet
FOR I = 0 TO 9
' invariant: read 0..I-1 on omavahel sorteeritud
J = I
WHILE J > 0
' invariant: read J..I on omavahel sorteeritud
n1 = Sheet.getCellByPosition(0, J - 1).Value
n2 = Sheet.getCellByPosition(0, J).Value
IF n1 > n2 THEN
Sheet.getCellByPosition(0, J - 1).Value = n2
Sheet.getCellByPosition(0, J).Value = n1
J = J – 1
ELSE
J = 0
ENDIF
WEND
NEXT I

Koduse ülesande täislahenduse leiate artikli lõpus toodud OpenOffice.org failist.

Valikumeetod

Teine võimalus on kasvatada sorteeritud osa sel moel, et valida igal sammul veel sorteerimata elementide hulgast välja see, mis peaks pingereas kõige eespool olema ja panna ta kõrgeimale veel vabale kohale. Selge on see, et kui me igal sammul valime allesjäänute hulgast välja minimaalse, siis saamegi tulemuseks kõik elemendid kasvavas järjekorras.

Minimaalse leidmiseks võime aga võrrelda elementide I..J-1 hulgast leitud parimat kandidaati elemendiga J ja selle võrdluse tulemuse põhjal selgitada välja elementide I..J hulgas minimaalse.

Lisades vajalikud algväärtustamised, saame algoritmi, mida tuntakse valikumeetodi nime all:

Sheet = ThisComponent.CurrentController.ActiveSheet
FOR I = 0 TO 9
' invariant: read 0..I-1 on 0..9 seas maksimaalsed
K = I
FOR J = I + 1 TO 9
' invariant: rida K on I..J-1 seas maksimaalne
n1 = Sheet.getCellByPosition(0, K).Value
n2 = Sheet.getCellByPosition(0, J).Value
IF n1 > n2 THEN
K = J
ENDIF
NEXT J
' vahetame read I ja K
n1 = Sheet.getCellByPosition(0, K).Value
n2 = Sheet.getCellByPosition(0, I).Value
Sheet.getCellByPosition(0, K).Value = n2
Sheet.getCellByPosition(0, I).Value = n1
NEXT I

Tähelepanuväärne on, et mõlemas toodud näites alustasime invariandi väljamõtlemist sellest, et kujutasime ette, milline peaks olukord olema korduse töötamise keskel. Alles seejärel lisasime vajalikud ettevalmistused või lisakontrollid, et ka korduse esimesel ja viimasel läbimisel midagi rumalat ei tehtaks. See ongi üldiselt kõige viljakam lähenemisviis.

Lõpuks võiks veel lisada, et toodud kaks lahendusvarianti pole sugugi ainsad võimalikud. Erinevaid sorteerimisalgoritme on väga palju, valiku- ja pistemeetod on nende hulgas ühed lihtsamad, aga samas suurte andmemahtude (mitmeid tuhandeid ridu ja üle selle) töötlemisel suhteliselt aeglased. Inglise keele oskajatele on üsna hea koht lisalugemiseks sorteerimisalgoritmide artikkel Wikipedias.

Auhind ja uus kodutöö

Eelmise numbri ülesannete õiged lahendused saatsid Andres Vahter, Andres Võsa, Toivo Hein, Toomas Vahter, Kristel Kivikangur, Anu Adler, Allan Voog, Kert Sasi, Aira Lõhmus, Roger Mikomägi, Harri Poom ja Taavi Ojaveer. Auhinna saab loosi tahtel Aira Lõhmus, kellel palume toimetusega ühendust võtta.

Uus kodune töö on aga selline:

• kirjutada kordus, mis teisendab õpilaste nimekirja, kus ühes veerus on üksteise all vaheldumisi õpilase nimi ja tema hinne (joonis 3, vasakul), kujule, kus esimeses veerus on õpilaste nimed ja teises nende hinded (joonis 3, paremal);
• kirjutada kordus, mis teeb eelmisega võrreldes vastupidise operatsiooni, see tähendab teisendab hinnete kaheveerulise esituse tagasi üheveeruliseks.

Joonis 3: Hinnete lehe kaks esitust

Et ülesanne oleks realistlikum ja huvitavam, pole seekord nimekirja pikkus ette teada — programm peab ise välja uurima, kui palju tabelis ridu täidetud on — ja lisaks nõuame veel, et teisendus tuleb teha “kohapeal” — esimese õpilase nimi ei tohi liikuda.

Sellised teisendused võivad olla kasulikud näiteks sellepärast, et kaheveerulise esituse korral on võimalik hinnete pingerea koostamiseks kasutada töölehe standardset sorteerimiskäsku ja seda pole enam vaja endal programmeerida.

Nagu ikka, on parimatele lahendajatele ka auhinnad!

AUHINNAD paneb välja MAX 123 — DELLi müügi- ja teeninduskeskus. Seekordseks kuuauhinnaks on DELLi USB mälupulk. AASTAAUHINNAKS on DELLi sülearvuti.

Rubriigi autor AHTO TRUU (1972) on WM-data AS tarkvaraarendaja. Viimased kümme aastat tegelenud lisaks põhitööle informaatikavõistluste korraldamisega nii üldhariduskoolide õpilastele kui ka Tartu Ülikooli tudengitele. Eesti Informaatikaolümpiaadi žürii esimees, mitme rahvusvahelise võistluse žürii liige.

Siit saate endale laadida programminäited OpenDocument Spreadsheet vormingus. Nende avamiseks kasutage OpenOffice.org versiooni 2.0 või uuemat.

Faili avamisel hoiatab OpenOffice.org, et see sisaldab makrosid, mis võivad teie arvutit kahjustada. Kui te tahate failis olevaid programme ainult vaadata, võite makrode käivitamise keelata (nupp ‘Disable Macros’). Kui aga tahate programme ka käivitada proovida, peate ise otsustama, kas usaldate makrode käivitamist lubada (nupp ‘Enable Macros’) või mitte.

Programmitekstide vaatamiseks valige pärast faili avamist peamenüüst ‘Tools’ → ‘Macros’ → ‘Organize Macros’ → ‘OpenOffice.org Basic’. Avanevas dialoogiaknas valige kastis ‘Macro from’ vastavatud fail, selle all ‘Standard’, selle all omakorda soovitava programmi nimi. Programmi teksti vaatamiseks vajutage seejärel nuppu ‘Edit’, käivitamiseks aga nuppu ‘Run’.