Hanoi torony

Ha elolvastad a Rekurzió bevezető fejezetét, akkor készen állsz egy új feladat megoldására, ahol a többszörös rekurzió sokat segíthet a megoldásban. Ezt a feladatot Hanoi toronynak hívják. Adott három rúd és $n$n különböző méretű korong. Jelöljük az egyes rudakat „A”-val, „B”-vel és „C”-vel, és számozzuk be a korongokat 1-től 5-ig növekvő sorrendben. Kiinduláskor az $n$n korong egy rúdon van méret szerinti sorrendben úgy, hogy az $n$n-nel jelölt korong van legalul, és az 1-es korong van legfelül. Így néz ki a Hanoi torony $n = 5$n, equals, 5 koronggal.

Az a cél, hogy az $n$n korongot átrakjuk az A rúdról a B rúdra:

Ugye könnyűnek tűnik? Azért nem olyan egyszerű, mert közben be kell tartanod két szabályt:

Mondhatnád, hogy ez nem valami fontos probléma. Épp ellenkezőleg! Azt tartja a legenda, hogy valahol Ázsiában (Tibetben, Vietnámban vagy Indiában – döntsd el, melyik internetes oldal legendája tetszik a legjobban) szerzetesek ezt a problémát próbálják megoldani 64 koronggal, és – a legenda szerint – a szerzetesek úgy tartják, hogy amikor sikerül mind a 64 korongot átrakni az A rúdról a B rúdra a fenti szabályok betartásával, akkor a világnak vége szakad. Ha a szerzeteseknek igaza van, van-e okunk pánikba esni?

Először vizsgáljuk meg, hogyan tudjuk rekurzióval megoldani a feladatot! Kezdjünk egy igazán egyszerű esettel: ha egy korongunk van, azaz $n = 1$n, equals, 1. Az $n = 1$n, equals, 1 lesz az alapesetünk. Az 1-es korongot mindig átteheted az A rúdról a B rúdra, mert tudod, hogy minden alatta levő korong nagyobb nála. Semmi különös nincs az A illetve a B rúdban. Az 1-es korongot átteheted a B-ről a C-re, ha ezt szeretnéd, vagy akár C-ről A-ra, vagy bármelyik rúdról bármelyik másikra. A Hanoi tornya megoldása triviális egyetlen koronggal, és ebben az esetben egy mozgatás elég.

Mi a helyzet két korong esetén? Hogyan oldjuk meg a problémát $n = 2$n, equals, 2 esetén? Három lépés kell hozzá. A kezdet kezdetén ezt látjuk:

Először tegyük át az 1-es korongot az A rúdról a C-re:

Figyeld meg, hogy a C rudat lerakatnak használjuk a célból, hogy az 1-es korongot el tudjuk helyezni, amíg hozzáférünk a 2-es koronghoz. Most, hogy elértük a 2-es korongot – ez van legalul – át tudjuk azt tenni a B rúdra.

Végül tegyük át az 1-es korongot az C rúdról a B-re:

Ehhez a megoldáshoz három lépés kell, és megint csak nincs semmi különleges két korong átmozgatásában az A rúdról a B rúdra. Ugyanúgy tehetnéd a B-ről a C-re az A rudat használva lerakatnak: rakd át az 1-es korongot B-ről A-ra, majd a 2-es korongot B-ről C-re, végül az 1-es korongot az A rúdról a C-re. Egyetértünk abban, hogy az 1-es és 2-es korongokat tetszőleges rúdról három lépésben át tudod helyezni bármelyik másik rúdra? (Mondd, hogy igen!)

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.