3. TSÜKKEL

3.1 Korduv tegevus

Kui püüda arvuti võimalikke plusse välja tuua, siis üheks oluliseks neist on kahtlemata võime mingeid tegevusi kiiresti ja korduvalt sooritada. Nii saab teha arvutusi, midagi andmetest otsida, erinevaid variante läbi vaadata jpm. Arvutid on läinud järjest kiiremaks ja nii saavad paljud asjad tehtud praktiliselt silmapilkselt. Samas on ülesandeid, mille lahendamiseks kulub ikkagi rohkem aega kui tahaks, isegi kui mitu arvutit korraga ülesannet lahendama panna. Näiteks ilmaennustus on selline keeruline ülesanne.

Kui tahta mingeid asju korduvalt teha, siis võivad ju programmid väga pikaks minna? Näiteks kui tahame, et programm väljastaks ekraanile viis korda üksteise alla “Tere!”, siis kõlbaks selline programm.

Saja korra jaoks tuleks siis programm vastavalt pikem. Tegelikult on programmeerimiskeeltes olemas head võimalused selliste korduste lühemaks esituseks. Kõigepealt püütakse aru saada, mis on see korduv tegevus, mis päris samasugusena (või kindlate reeglite järgi muudetuna) tuleb ikka ja jälle teha. Eelmises näites oli selleks rida print("Tere!"). Teise asjana tuleb läbi mõelda, mitu korda me tahame seda tegevust teha. See võib olla meil ette teada, aga võib sõltuda ka mingitest välistest asjaoludest, näiteks kasutaja poolt antud vastusest. Näiteks pole mõtet parooli uuesti küsida, kui juba õige on sisestatud.

While-tsükkel

Korduvaid tegevusi realiseeritakse tsüklite abil. Vastavaid vahendeid võib konkreetses programmeerimiskeeles olla mitmeid. Näiteks Pythonis on olemas while-tsükkel ja for-tsükkel. Meie alustame eelkontrolliga tsüklist, mille põhimõte on teatud mõttes sarnane valikulausega. Sellist tsüklit kutsutaksegi while-tsükliks, sest reeglina on programmeerimiskeeltes just võtmesõna while selles tähenduses kasutusel. Erinevus if-lausest on selles, et pärast seda, kui tsükli sisus olevad laused on täidetud, minnakse uuesti tingimust kontrollima. Kui tingimus ikka veel kehtib, siis täidetakse sisu edasi jne. Kui mingil hetkel tingimust kontrollides see enam ei kehti, siis lõpetatakse tsükli täitmine. Tsükli sisus olevad laused peavad olema taandatud sarnaselt if-lause kehas olevatele lausetele.

Eelkontrolliga tsükli plokkskeem näeb välja selline:

Tsükli jätkamistingimus on (nagu ka if-lause tingimus) tõeväärtustüüpi. Kui tingimus on täidetud (tingimusavaldise väärtus on tõene), siis minnakse tsükli sisu täitma. Kui aga pole täidetud, siis minnakse tsüklist välja.

Tavaliselt on tingimus esitatud võrdlemisena, aga võib näiteks olla ka lihtsalt tõeväärtus True. Või hoopis tõeväärtus False. See viimane on küll üsna mõttetu: nii karm “piirivalvur”, et kunagi kedagi edasi ei lubata. Jätkamistingimuse True puhul on tegemist lõpmatu tsükliga, sest tingimusavaldis on alati tõene. Teoreetiliselt jääbki see tsükkel igavesti tööle. Praktiliselt siiski ilmselt pannakse arvuti millalgi kinni, toimub elektrikatkestus vms. Kui me nüüd Pythonis meelega või kogemata sellise programmi teeme, mis igavesti tööle jääb, siis ei ole meil katkestamiseks siiski vaja arvutit kinni panna. Nimelt saame Thonnys programmi töö katkestada Stop-märgiga nupu või klahvikombinatsiooni Ctrl + F2 abil. (Keskkonnas IDLE katkestatakse programmi töö Ctrl + C abil.) Tegelikult saab lõpmatut tsüklit kasutada ka päris sihipäraselt sellises olukorras, kus tuleb näiteks mingit sündmust aktiivselt oodata. Sellisel juhul on tsüklist väljasaamine teisiti organiseeritud.

Lähme tagasi algse ülesande juurde. Me tahaks, et tsükli abil viis korda “Tere!” ekraanile tuleks. Seega peab olema midagi, mis tsükli sisus muutub nii, et just pärast viiendat korda “piirivalvur” enam tsükli sisu juurde ei lubaks. Kuidas me inimlikult sellises olukorras loendaksime? Üks võimalus oleks näiteks sõrmedel lugeda ja nii meeles hoida, kui palju kordi juba tsükli sisu on täidetud. Põhimõtteliselt teeme sarnaselt ka programmeerides. Võtame kasutusele ühe muutuja, mille nimeks saagu i. Olgu i väärtus esialgu 0: i = 0. Igal tsükli sammul liidame väärtusele 1. Varem olid näited, kus muutujale saime erinevaid väärtusi anda mingite teiste muutujate või näiteks arvude ja tehete abil. Nüüd aga on vaja selle sama muutuja väärtust muuta. Saame seda teha sellise avaldisega

i = i + 1

Võimalik, et selline võimalus vajab natuke harjumist. Kui vaatame koolimatemaatikat, siis võib see paista üsna kummaline, aga võrdusmärgi tähendus on siin teistsugune kui matemaatikas. Vasak pool näitab, et muutuja i saab uue väärtuse. Paremal pool on avaldis, millega see uus väärtus arvutatakse. Selles arvutamises kasutatakse ka muutuja i senist väärtust. Enne programmi kokkupanekut mõtleme veel jätkamistingimusele. Selleks sobib i < 5, sest kui i on esialgu 0 ja igal sammul liidetakse 1, siis just 5 sammuga jõuame niikaugele, et tingimus i < 5 ei ole enam täidetud. Panemegi nüüd programmi kokku. Olulisel kohal on taas koolon ja taandamine.

On kokkulepe, et just i ongi tavaliselt sellise loendaja (tsüklimuutuja) nimeks. Püüame nüüd programmi tööd analüüsida sammude kaupa.

• Jätkamistingimus (i < 5) on täidetud, kui esimest korda tsükli juurde jõuame, sest 0 < 5.
• Pärast esmakordset sisu täitmist on i väärtus 1 ja jätkamistingimus ikkagi täidetud, sest 1 < 5.
• Pärast teist korda on i väärtus 2 ja ikka saame jätkata, kuna 2 < 5.
• Ja siis i on 3 ja ikka 3 < 5.
• Ja siis i on 4 ja ikka 4 < 5.
• Ja siis i on 5 ja kontrollime, kas i < 5? Kas 5 < 5? Ei ole, sest 5 ja 5 on võrdsed, seega võrratus 5 < 5 ei kehti ja jätkamistingimus on väär.

Lisame tsükli kehasse ühe rea, mis i väärtuse ekraanile tooks, siis saame seda paremini jälgida.

Pange programm tööle.

Kui me programmi alles teeme, siis on mingites kohtades muutujate väärtuste väljastamine täiesti omal kohal, et olla kursis, mis seis vastaval hetkel on. Thonnys on muutuja väärtuste jälgimine sisse ehitatud ja seda saab nähtavale tuua View-menüüst valikuga Variables. Kuna programm töötab kiiresti, siis tavaliselt käivitades jäävad näha ainult programmi töö lõpus kehtivad väärtused. Selleks, et sammsammult programmi tööst ülevaadet saada, tuleb käivitada hoopis silumisrežiimis – putukaga nupuga või Run-menüüst Debug current script. Seejärel saab erineva ulatusega samme teha vastavate nuppude või Run-menüü valikute abil.

Kuna muutuja väärtuse muutmist eelmise väärtuse alusel tuleb päris sagedasti ette, siis on selleks ka lühemad variandid olemas. Näiteks a = a + 3 asemel võime kirjutada a += 3. Samasugused variandid on ka lahutamise (-=), korrutamise (*=), jagamise (/=), täisarvulise jagamise (//=), jäägi leidmise (%=) ja astendamise (**=) jaoks.

3.2 TSÜKKEL. IGAL SAMMUL JUHTUB MIDAGI

3.2.1 Kilpkonn tsüklis

Eelmisel nädalal tutvusime kilpkonnagraafikaga ja tegime näiteprogrammina ruudu.

Näiteprogramm. Ruut

On näha, et kilpkonn peab täitma korduvalt samu käske: minema 100 pikslit edasi ja pöörama seejärel 90° vasakule. Tegemist on tsüklilise tegevusega, seega saame kasutada tsüklit.

Kirjutame programmi ümber nii, et ruut joonistatakse while-tsüklit rakendades.

Näiteprogramm. Ruut II

Pange see programm tööle ja püüdke seda modifitseerida nii, et joonistataks hoopis võrdkülgne kolmnurk. Mis sellisel juhul on ruudust erinev? Külgi on kolm ja pöörama peab … proovige ise!

3.2.2 Igal sammul juhtub midagi

Nagu juba eelmiste näidete puhul oli näha, juhtub igal sammul midagi. Võib juhtuda samu asju, võib natuke erinevaid asju juhtuda. Näiteks “Tere!” väljastamisel juhtus see nii igal sammul. Samuti liikus kilpkonn igal tsüklisammul 100 pikslit edasi ja pööras 90 kraadi vasakule. Kui tsüklis oli aga käsk print(i), siis igal sammul toimus väljastamine, aga tsüklimuutuja i väärtus oli eri sammudel erinev. Tsüklimuutuja väärtuse muutumine tagati reaga i = i + 1.

Modifitseerime ruudu joonistamise programmi nii, et igal sammul tehtav sõltuks ka tsüklimuutuja i tolle hetke väärtusest. Asendame rea forward(100) reaga forward(100 * i). Pange programm tööle ja proovige toimunut seletada:

Muutke programmis tsükli sammude arvu. Selleks tuleb tingimuses i < 4 arv 4 asendada suurema või väiksema arvuga. Samuti võib 100 piksli asemel kasutada mõnda väiksemat arvu, et tulemus paremini nähtav oleks.

Tsükli kehas ei pruugi alati midagi silmnähtavat juhtuda. Näiteks võidakse hoopis mingeid asju “meelde jätta” ja pärast tsüklit kasutada. Nii on järgmises programmis võetud kasutusele muutuja summa, millesse hakatakse “koguma” summat.

3.2.3 Pikem samm! Või hoopis lühem?

Eelmistes näidetes on tsüklimuutuja muutunud iga sammuga ühe võrra. See on küll kõige sagedasem variant, kuid kaugeltki mitte ainus. Põhimõtteliselt saame tsüklimuutujat muuta ükskõik millise lubatud tehtega. Proovige näiteks nii.

Samm võib ka hoopis lühem olla: i = i + 0.5. Või näiteks võib igal sammul i väärtus kolm korda kasvada: i = i * 3. Korrutamise puhul peab aga hoiduma esialgsest väärtusest 0, sest korrutamine seda ei muuda.

Teeme programmi, mis väljastab ekraanile 1, 3, 9, 27 … . Näeme, et iga eelmine tulemus korrutatakse järgmise saamiseks kolmega. Kasutajalt küsitakse näiteks, millisest arvust peab tulemus väiksemaks jääma:

Nagu näeme, on siin oluliseks muutujaks tulemus ise. Selleks, et lugeda, mitmendal sammul me oleme (mitmendat tulemust oleme väljastamas) ja näiteks hoopis tulemuste arvu piirata, peab kasutusel olema teine muutuja.

Kui nüüd tahta, et arvutataks ainult näiteks 6 järjestikust tulemust, peaks vastava tingimuse asendama: while tulemus < piir asemel while jrk < 6.

3.3 Tsükkel. Mitu korda?

3.3.1 Suur arv?

Alustame elulisema näitega, kus tsüklimuutuja suureneb igal sammul ühe võrra, aga algväärtus pole 0, vaid hoopis 2017. Oletame, et aastal 2017 on kedagi 1 315 635 (https://www.stat.ee/505933). Iibe kordaja näitab selle arvu muutumist aasta jooksul 1000 inimese kohta (positiivse iibe kordaja korral on arv kasvanud, negatiivse korral langenud).

Proovige ka teiste väärtustega!

Kui aga näiteks tahaks teada, mis aastal oleks eestlasi 2 000 000, kui iibe kordaja oleks 6 promilli (tegelikult pole nii kõrget loomulikku iivet vähemalt viimase saja aasta jooksul Eestis olnud):

Täpsema prognoosi saamiseks on muidugi vaja arvestada väga erinevaid asjaolusid (huvi korral vt ka https://www.stat.ee/76578).

3.3.2 Mitu korda?

Eelmistes näidetes oli meil tsükli korduste arv tegelikult juba algul teada või siis kindlatel alustel arvutatav nagu viimases näites. Nüüd aga püüame teha programmi, kus tsükli läbimiste arv sõltub kasutaja sisestatud vastustest. Võtame aluseks valikulause materjali juures olnud programmi, milles küsitakse PIN-koodi. Seal küsiti PIN-koodi üks kord ja lõplik otsus tehti juba ühe pakkumise järel:

Tavaliselt siiski antakse ka eksimisvõimalusi ja vale koodi puhul küsitakse uuesti. Püüamegi nüüd selle programmi vastavalt ümber kirjutada. Ilmselt on siin kasu tsüklist. Antud juhul peame tsükliliselt käituma (uuesti küsima) vaid siis, kui sisestatud PIN-kood ei ole õige. Jätkamistingimuseks sobiks seega sisestatud_pin != "1234". Programm ise oleks näiteks järgmine:

Püüdke samm-sammult läbi mõelda, kuidas selline programm töötab. Vajadusel joonistage selle plokkskeem. Proovige see programm tööle panna ja testige erinevate PIN-koodidega. Proovige ka oma pangakaardi tegeliku koodiga! 🙂 Või ärge ikka proovige!

Programmi vaadates näeme, et järgmine lõik on kahes kohas:

Võime proovida tsükli eest selle lõigu ära jätta:

Sellisel juhul aga tuleb veateade, sest muutujal sisestatud_pin ei ole väärtust, kui seda while-tingimuses esimest korda kontrollida tahetakse:

Anname muutujale sisestatud_pin esialgseks väärtuseks tühja sõne. Sellega garanteerime, et muutujal sisestatud_pin on alati väärtus ja while jätkamistingimus on esialgu kindlasti tõene, sest tühi sõne ei ole võrdne sõnega "1234".

Nüüd ei pääse ilma parooli sisestamata edasi. Paraku on süsteem ebaturvaline, sest katsetada saab suvaline arv kordi. Püüame ka katsete arvu piirata:

Nüüd koosneb jätkamistingimus kahest osast – endiselt kontrollitakse, ega sisestatud PIN-kood õige ei ole, aga lisaks kontrollitakse ka seda, mitu korda veel vastata saaks. Enne tsüklit on kordade arvuks määratud 3 ja pärast igat tsükli keha täitmist väheneb see arv 1 võrra. Esimesel korral saab muutuja katseid väärtuseks 2, teisel korral 1 ja kolmandal korral 0.

Jätkamistingimuses kasutatakse võtmesõna and, mis tähendab, et tingimuse kehtimiseks peab nii selles sõnast paremal pool kui vasakul pool olev tingimus tõene olema, teisisõnu peavad mõlemad osaavaldised olema tõesed. Tõesti, selleks et PIN-koodi peaks uuesti küsima, ei tohi olla veel õiget sisestatud ja järele jäänud katseid peab olema rohkem kui 0. Nagu eelmise nädala materjalides juttu oli, võib ka siin tingimus olla ükskõik kui keeruline. Tehetega and, or ja not saab väga erinevaid avaldisi tekitada.

Mure on nüüd selles, et küsimiste arv on küll piiratud, aga isegi kui valet koodi kolm korda sisestatakse, saadakse ikka pangaautomaati sisse. Muudame programmi nii, et arvestataks, kas lõpuks sisestati õige kood või mitte. Kui ei sisestatud, siis on kuri karjas ja lahkumiseks antakse 10 sekundit! 🙂 Programmi saab üheks sekundiks “uinutada” käsuga sleep(1), kuid selle kasutamiseks tuleb see importida moodulist time nii: from time import sleep.

Huvi korral mõtisklege ja katsetage, mida teeks programm teisiti, kui

if sisestatud_pin == "1234":

asemel oleks

if katseid > 0:

Eelmises programmis oli viimane tsükkel valikulause else-osa sees. Näeme, et taane on vastavalt läinud veel kaugemale. Selline mitmetasemeline struktuur on programmides täiesti tavaline. Vabalt võib olla ka näiteks while-tsükkel, mille sees on tingimuslause, mille sees on veel üks tsükkel, aga sellise programmi käitumise ette ennustamine võib muutuda keeruliseks, seega tuleks võimaluse korral keerulisemast struktuurist hoiduda.

Klassikalises arvamismängus on aga kasu tingimuslausest tsükli sees:

Proovige mängida, aga ärge sellest sõltuvusse sattuge! Proovige mängu modifitseerida. Näiteks las programm loeb vastamiste arvu ka ja reageerib vastavalt sellele. (Kui arvatakse arv esimese korraga ära, siis näiteks võiks mängijal soovitada oma selgeltnägija võimeid ehk laiemaltki kasutada.) Huvitav oleks ka teistpidi mäng, kus arvuti oleks arvaja rollis ja arvaks võimalikult mõistliku strateegiaga.

Ülesanne

Mõelda oma elule ja ümbritsevale ning kirjeldada ühte tsüklilist protsessi. Seejuures märkida, kas tsükli läbimiste arv on enne teada või selgub täitmise ajal. Protsess ei pea olema (lihtsasti) programmeeritav. Lahendus esitada Moodle’is vastava testiküsimuse vastusena.

3.4 Juhuslikust arvust veel

3.4.1 Viskame täringuid

Eelmisel nädalal tutvusime juhuslike arvudega, mida saab kasutada näiteks erinevate mänguliste programmide loomisel. Proovime juhuslikkust nüüd tsükliga siduda. Esialgu teeme programmi, mis viskab viis korda täringut. Olgu see tavaline kuuetahuline täring.

Kui me midagi muud visketulemusega teha ei taha, siis võimegi selle väljundisse sisse kirjutada. Sageli aga tahame viske tulemusega midagi teha. Näiteks tulemused kokku liita ja kuue saamisel eriliselt rõõmustada.

Soovijad võivad täringu nii ümber teha, et täringul oleks mingi muu arv tahke. Näiteks mängus Dungeons & Dragons on ka 4-, 8-, 10-, 12- ja 20-tahulised täringud. Võib ka soovitud tahkude arvu kasutajalt küsida.

3.4.2 Kui tõenäosused pole võrdsed

Eelmises näites oli meil täring, mille iga tahk võis tulla võrdse tõenäosusega. Kuuetahulise täringu puhul oli iga tahu tulemise tõenäosus 1/6. Selle tagas funktsioon randint(1, 6). Mündiviske puhul saame ausa mündi funktsiooni randint(1, 2) abil.

Nüüd aga kujutame ette, et keegi on mündiga manipuleerinud ning teinud nii, et kulli ja kirja tõenäosused pole enam võrdsed. Olgu näiteks kirja tulemise tõenäosus 73% (ehk 0,73). Sellise mündi viskamist saab programmiga simuleerida mitmel viisil. Näiteks võiksime kasutada funktsiooni randint(1, 100), mis annab võrdse tõenäosusega ühe täisarvu lõigus 1 kuni 100. Saadud arv on 73 või väiksem tõenäosusega 73%. Nii saame järgmise programmi:

Kui seda programmi korduvalt tööle panna, siis näeme, et kümnest viskest kipub tõesti kirjasid kullidest rohkem olema. Võite ka kirjade loenduri lisada, mis seda aitab jälgida. Siiski juhtub vahel, et kirjasid on samapalju või vähem kui kulle. Ka see on oodatav.

Samalaadselt saame simuleerida ka teiste tõenäosuslike protsesside tulemusi.

3.4.3 Seiklus metsas

Järgmine programm on eelnevatest pikem ja simuleerib võimalikku jalutuskäiku metsas. Hoiatus! Tegemist on metsaga, kus leidub nii ohte kui ahvatlusi. Soovitame aga siiski katsetada. Ennekõike aga püüdke programmist aru saada.

Soovitatav on püüda seda programmi täiendada. Näiteks teha nii, et

• teatud müntide arvu juures kuulutatakse mängija võitjaks. Hetkel on selgelt letaalse seiklusega tegemist;
• ohte või ahvatlusi oleks rohkem;
• elu kaotamise tõenäosus oleks väiksem;
• ka kasutaja saaks saatuse määramisel kuidagi kaasa lüüa.

3.5 Labürint

3.5.1 Mis on labürint

Labürindiks nimetatakse keerdkäikudega ehitist ehk keerdkäigustikku (vt ÕS 2013) ning sõna labürint tuleneb kreekakeelsest sõnast labyrinthos.

Sageli jagatakse labürindid kahte erinevasse liiki, mis erinevad teineteisest läbitavuse poolest.

• Leidub labürinte (ingl labyrinth), mille puhul pole eesmärgiks inimese eksitamine, vaid rändaja juhtimine ühe võimaliku tee kaudu. Selliseid keerdkäigustikke tuntakse juba tuhandeid aastaid. Eestiski leidub selline labürint Aegna saarel, mille ehitamise aega täpselt ei teata (vt kivilabürint).
• Samas on rajatud labürinte (ingl maze), mille eesmärgiks on sinna sattunud külalist segadusse ajada erinevate võimalike teedega. Neid võib nimetada ka labürintmõistatusteks ning üle maailma on neid rajatud hekklabürintidena näiteks aedadesse. Ka Kreeka mütoloogias esinev Minotauruse labürint on mõeldud selleks, et sinna sattunud inimene eksiks ja ei leiaks väljapääsu.

Meie keskendumegi niisugustele labürintidele, mis püüavad inimesi eksitada.

3.5.2 Maailma suurimad

Labürinte on tekitatud erinevat moodi. Näiteks on neid ehitatud jääst, kasvatatud hekina ja rajatud maisipõllule. Tutvustame mõnda rekordilist labürinti.

Maailma suurim jääst valmistatud labürint tehti Buffalos, USAs Buffalo Powder Keg festivali raames 26. veebruaril 2010. aastal. Labürindi pindala oli 1194,33 m², laius 25,85 m ja pikkus 46,21 m. Müüride kõrguseks oli 1,83 m ning selle ehitamiseks kulus 2171 jääplokki, kusjuures üks plokk kaalus 136 kg.

Allikas: http://www.guinnessworldrecords.com/world-records/4000/largest-maze-ice-maze

Maailma suurim hekklabürint asub Hiinas, Yanchengis. Labürindi pindala on 35 596,74 m² ja raja kogupikkus on 9 457,36 m. Labürint koosneb suurest hirvelabürindist ja mitmetest väiksematest labürintidest (südamekujuline labürint, 2 ringikujulist labürinti ja lastepargi labürint).

Allikas: http://www.guinnessworldrecords.com/world-records/1/largest-maze-permanent-hedge-maze

Suurim maisipõllule rajatud labürint on 24,28 ha suurune. See loodi ettevõtte Cool Patch Pumpkins poolt ja asub California osariigis Dixonis.

Allikas: http://www.guinnessworldrecords.com/world-records/1000/largest-maze-temporary-corn-crop-maze

3.5.3 Labürindist pääsemine

Labürint kui ehitis pole otseselt seotud programmeerimisega, kuigi labürinti saab arvuti abil planeerida. Selliseid generaatoreid on veebiski.

Suuremat huvi pakuvad aga keerdkäigustikust väljapääsemise ülesanded, sest nende lahendused on algoritmilised. Järgmisena tutvustatakse mõnda lahenduseeskirja, mis aitavad eksinud ränduril leida keerulisest labürindist pääsetee.

Hiire algoritm

Üks lihtsamaid algoritme, mida saab väljapääsu leidmiseks kasutada, on juhuslik hiire algoritm (ingl Random mouse algorithm). Nagu selle nimigi ütleb, siis tegemist on viisiga, kuidas hiir otsiks labürindist väljapääsu. Selle põhimõtteks on liikuda labürindis otse seinani ning seejärel pöörata suvalisse suunda ja liikuda taas otse seinani. Seesugust tegevust korratakse kuni väljapääsu leidmiseni. Teisisõnu on idee selles, et uidatakse keerdkäigustikus ringi kuni avastatakse väljapääs. Tegelikult on siin tegemist tsüklilise käitumismustriga. Igal tsükli sammul minnakse otse seinani ja siis pööratakse suvalisse suunda. Selle algoritmi nõrkuseks on see, et sageli kulub palju aega enne väljapääsu leidmist, eriti kui on tegemist väga suure labürindiga.

Seinajärgija algoritm

Teine lihtne võimalus, kuidas labürinti läbida, on kasutada seinajärgija algoritmi. Esmalt tuleb valida parem või vasak käsi ja hoida see käsi pidevas kontaktis labürindi seinaga väljapääsu leidmiseni.

Allikas: https://en.wikipedia.org/wiki/Maze_solving_algorithm#/media/File:Maze01-02.png

Selline algoritm aga ei tööta, kui algus- ja lõpp-punkt pole omavahel seinapidi ühendatud.

Tupikute täitmise algoritm

Leidub labürindi lahendusalgoritme, mis ei aita tundmatus keerdkäigustikus teed kaotanud inimesel pääseda, sest tal pole ülevaadet kogu labürindist. Küll aga võimaldavad need leida tee, kui kogu labürindi kaart on ees. Näiteks võib selleks luua vastava programmi. Tupikute täitmise algoritmi puhul vaadatakse kogu labürinti korraga ning eesmärgiks on

1. leida kõik tupikud,
2. arvata kogu tee tupikust esimese ristmikuni kaardilt välja.

Trémaux’ algoritm

Algoritm on saanud oma nime selle looja Charles Pierre Trémaux’ järgi, kes oli 19. sajandi prantsuse matemaatik. Tema algoritmi põhimõte on selles, et labürindi lahendamiseks peab eksinud rändur läbitud tee märkimiseks joonistama enda järele joone. Juhul, kui satutakse tupikusse, siis pööratakse ümber ja minnakse tuldud teed tagasi. Kui leitakse ristmik, kus varem käidud pole, siis valitakse suvaline suund (kust ei tuldud) ning jätkatakse teed. Kui kõnnitakse mööda teed, mida on juba külastatud (näiteks on üks kord joonega märgitud) ja satutakse ristmikule, siis valitakse uus tee, kui see on saadaval (pole joonega märgitud), ning minnakse mööda seda teed. Vastasel juhul minnakse mööda vana teed, mis oli ühel korral märgitud. Kõik teed on kas märkimata, märgitud üks kord (käidud on seda teed vaid üks kord) või märgitud kaks korda, mis tähendab seda, et seda mööda on käidud ja siis tagasi tuldud. Lõpptulemusena saadakse ühe joonega märgitud tee, mis ühendab algust ja lõppu. 

Edasijõudnutele

Need, kelle jaoks on tsükkel ja moodulite importimine selged ja soovivad oma programmerimisoskusi proovile panna, võiksid uurida lisamaterjali “Pykkar”, kus saab luua ise labürindi ning kirjutada programmi, mis selle lahendab.