 | VI OSA sisukord |  |
6.4 HANOI TORNID JA MERSENNE'I ARVUD
Hanoi tornid
Selles silmaringi materjalis vaatleme mängulist, aga väga õpetlikku näidet, mis on seotud rekursiooniga. Tegemist on Hanoi tornide ülesandega. Nimelt on erineva läbimõõduga kettad nii laotud, et kõige suurem on kõige alumine ja väiksemad järjest üksteise peal kuni kõige väiksemani. Võimalik, et ketastes on augud ja neist on varras läbi, aga see pole hetkel meile tähtis.
Eesmärgiks on laduda kettad uuele platsile (vardale) ümber nii, et need oleksid jälle samal moel. Ühel sammul võib liigutada ainult ühte ketast ja mitte kunagi ei tohi suuremat ketast panna väiksema peale. Ümbertõstmisel saab kasutada kolmandat platsi (varrast).
Hanoi tornide ülesannet tutvustas prantsuse matemaatik Edouard Lucas 1883. aastal. Selle ülesandega on seotud erinevad legendid. Näiteks olla Indias ühes templis niimoodi paigutatud 64 kuldset ketast. Või olid sellised kettad hoopis Vietnamis Hanois?
Hanoi tornide ülesannet tuuakse väga sageli rekursiooni näiteks. Nimelt on rekursiivne lahendus intuitiivsem kui tsükliline. Püüamegi nüüd Hanoi tornide ülesande rekursiivse lahenduse läbi mõelda. Nagu ikka rekursiivse lahenduse puhul peab rekursiivne väljakutse olema lihtsama juhu jaoks. Praegusel juhul siis ilmselt väiksema ketaste arvu jaoks.
Võime mõelda nii, et kõige suurema ketta ümber tõstmine õigesse kohta saab toimuda ainult siis, kui kõik ülejäänud on vaheplatsile tõstetud.
Nende kõigi ülejäänute vaheplatsile tõstmine aga ongi ju sama ülesanne ühe võrra väiksema ketaste arvuga. Ainult sihtplatsi rollis on nüüd kolmas n-ö ajutine plats. Nüüd aga tuleb need vaheplatsilt kõik kenasti sihtplatsile suurima peale tõsta, mis on muidugi ka jälle sama funktsiooni väljakutse. Vaheplatsi rollis on aga esimene plats.
Järgnev programm näitabki, kuidas kettaid tõstetakse.
def hanoi(arv, lähe, siht, ajutine):
if arv > 0:
hanoi(arv - 1, lähe, ajutine, siht)
print("Ketas liigutati platsilt " + str(lähe) + " platsile " + str(siht))
hanoi(arv - 1, ajutine, siht, lähe)
hanoi(3, "A", "B", "C")
Kirjutame nüüd programmi ümber nii, et platside kettad oleksid eraldi järjendites.
def hanoi_järjend(arv, lähe, siht, ajutine):
if arv > 0:
hanoi_järjend(arv - 1, lähe, ajutine, siht)
liigutatav = lähe.pop()
siht.append(liigutatav)
print("Ketas " + str(liigutatav) + " liigutati platsilt " + str(lähe) + " platsile " + str(siht))
hanoi_järjend(arv - 1, ajutine, siht, lähe)
hanoi_järjend(5, [5, 4, 3, 2, 1], [], [])
Mersenne’i arvud
Kui loendada, mitu liigutamist need programmid ketaste paigutamisel teevad, siis saame
- 1 ketta puhul 1 liigutamise, lihtsalt tõstetaksegi paika;
- 2 ketta puhul 3 liigutamist, väiksem vaheplatsile, suurem paika, väiksem tema peale;
- 3 ketta puhul saame 3 liigutamisega 2 väiksemat ketast vaheplatsile ja siis suurim paika ja siis jälle 3 liigutamist, et 2 väiksemat tema peale saada.
Kui kettaid on n tükki, siis liigutamisi tehakse 2n - 1. See on ka teoreetiliselt kõige väiksem liigutamiste arv.
Enne oli meil juttu Fibonacci arvudest. Selgub, et ka arvudele, mis arvutatakse 2n - 1 abil, kus n on naturaalarv, on nimi pandud. Neid arve nimetatakse Mersenne'i arvudeks. Mersenne'i arvud on 1, 3, 7, 15, 31, 63, 127 ...
Mersenne'i arvude hulgas paistab olevat üsna mitmeid algarve. Algarv on ühest suurem naturaalarv, mis jagub ainult 1 ja iseendaga. Eeltoodud arvudest on algarvud 3, 7, 31, 127. Prantsuse teadlane Marin Mersenne 17. sajandi algul just selliseid algarve uuriski, mis on kujul 2n - 1. Tema auks nimetatigi 2n - 1 kujul arvud Mersenne'i arvudeks ja neist algarvud Mersenne'i algarvudeks.
Viimasel ajal leitud suurimad algarvud on kõik olnud Mersenne'i algarvud. Hetkel teadaolevatest suurim algarv on 277232917 − 1, mis leiti 2017. aasta detsembris. Tõestatud on, et algarve on lõpmatult palju. Põnevat infot Mersenne'i algarvude kohta on vikipeedias. Näiteks on seal Mersenne'i algarvude pikkused, leidmise ajad, leidjad.
| VI OSA sisukord | |