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

Hanoi tornyai

Rekurzió a programozásban

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: 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: É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: 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.


2019-12-10 16:50:29 Admin Köszönöm, ha Ön lesz az első, aki megírja ide véleményét, észrevételét, kérdését ezzel a lappal kapcsolatban.




Ú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 tizenhárom + hét?
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