Fő tartalom
Számítástudomány
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 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 korong egy rúdon van méret szerinti sorrendben úgy, hogy az n-nel jelölt korong van legalul, és az 1-es korong van legfelül. Így néz ki a Hanoi torony n, equals, 5 koronggal.
Az a cél, hogy az 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:
- Egyszerre csak egy korongot tehetsz át.
- Soha nem tehetsz nagyobb korongot kisebbre. Például, ha a 3-as korong rajta van egy rúdon, akkor a 3-as korong alatt csak 3-nál nagyobb számmal jelölt korong lehet.
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, equals, 1. Az 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, 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.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.