Eszköztár

88 Kezdőlap - Webszerkesztés - JavaScript - Hanoi tornyai

Mintapélda

A Hanoi tornyai nevű közismert logikai játék a programozás tanulásában is kihagyhatatlan alapfeladatnak számít. Ennek az az oka, hogy segítségével szemléletesen lehet bemutatni azt a programozási fogást, amit rekurzió néven emlegetünk.

A rekurzió, és ilyenformán a rekurzív algoritmusok lényege, hogy a programtervezés során egy olyan eljárást, vagy függvényt hozunk létre, mely üzemszerűen hívja meg saját magát. Nyilván ha ez feltétel nélkül történne, akkor végtelen idejű programműködést (lefagyást) okozna. Ezért a rekurziót úgy kell tervezni, hogy a végrehajtás során, amikor tehát a programrész meghívja saját magát, előbb-utóbb mindig bekövetkezzen egy feltétel, amikor már nem kell újrahívni a programot, mert eljutottunk egy olyan egyszerű(bb) szintre, ahol a kívánt feladat már könnyedén - rekurzió nélkül is - megoldható.

A fenti gondolatmenetre mutat tehát gyakorlatias példát a Hanoi tornyai játék, melynek lényege, hogy egy rúdon elhelyezett - különböző átmérőjű - korongokat kell átpakolni egy másik rúdra, az alábbi szabályok betartása mellett:

• egyszerre csak egy korong mozgatható;
• mindig csak a legfelső korongot szabad levenni és áttenni egy másik rúdra;
• egy korong nem rakható nála kisebb átmérőjű korongra.

Pakoláskor segítségül rendelkezésünkre áll egy harmadik rúd is, hiszen korongot nem lehet félretenni, csak valamely rúdon elhelyezni.


3 korong esetén a feladat megoldása nem túl bonyolult, összesen 7 lépésből megoldható. Ezt szemlélteti a fenti animáció.

Több korong esetén azonban már nem ilyen egyértelmű, hogy hogyan kell nekiállni a feladatnak. Ezért érdemes programot készítenünk a megoldás bemutatására. Ám hogyan készítsünk programot, ha mi magunk sem tudjuk a korongok pakolásának szükséges sorrendjét? Épp ebben segíthet nekünk a rekurzív megvalósítás. Hiszen ha a programot rekurzívan meg tudjuk írni, akkor futtatáskor láthatóvá válik a keresett sorrend.

Vizsgáljuk meg, hogyan lehet a feladatot rekurzívan megközelíteni! Tekintsük a kiindulási állapotot 8 koronggal: Ha el tudnánk jutni oda, hogy a felső 7 korongot félre tudnánk rakni az utolsó oszlopra, akkor könnyen meg tudnánk oldani a feladatot, hiszen ebben az esetben csak a legalsó korongot kellene az új helyére mozgatni, majd ahogyan félretettük a 7 korongot, ugyanúgy azt rárakhatjuk a legalsó korongra.
De hogyan tudunk átrakni 7 korongot? Pont úgy, ahogyan a 8 korongot mozgattunk:

• a felső 6 korongot félrerakjuk,
• a maradék 1 korongot áthelyezzük,
• végül a félrerakott korongokat is a helyükre tesszük.

És hogyan tudunk 6 korongot félrerakni? Azt is pont ugyanúgy... de ezt a programrészt már nem kell megírnunk. Hiszen ha a programot elkészítjük általánosan N darab korongra, akkor a program ennél kevesebb korongra is működni fog - csak kisebb paraméterértékkel kell meghívni.

Mindez algoritmikusan a következőképpen néz ki:

	Eljárás Hanoi( N, A, B, C )
	    Ha N=1 akkor Mozgatás( A-ról B-re )
	    különben
	        Hanoi( N-1, A, C, B )
		Mozgatás( A-ról B-re )
	        Hanoi( N-1, C, B, A )
	Eljárás vége

ahol a Hanoi eljárás paraméterei rendre:

• N: mozgatandó korongok száma,
• A: oszlop, amelyikről mozgatni akarunk,
• B: oszlop, amelyikre mozgatni akarunk,
• C: oszlop, amelyiket segítségként használhatunk.

Az algoritmusból készített program működése az alábbiakban próbálható ki:



A megvalósításhoz tartozó forráskód a lenti kis képre kattintva érhető el.

Eddig 1 hozzászólás van a témához:

---

Új hozzászólás:
E-mail cím:	Erre a címre küldjük ki a hozzászólás jóvá- hagyásához szükséges linket. Az e-mail címet sehol nem tesszük közzé.
Név:	Ez a név fog megjelenni az Ön hozzászólásai mellett.
Mennyi tizenkilenc + négy? Számjegyekkel írja be!	Ez a robotok beírása elleni védelem miatt szükséges ellenőrzés.

© infojegyzet.hu, 2018. március