If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

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=5 koronggal.
Három, A-val B-vel és C-vel jelölt rúd. Az A rúdon van az 5-ős, 4-es, 3-as, 2-es és 1-es korong, az 5-ös legalul, az 1-es legfelül. A „B” és a „C” rúdon nincs korong.
Az a cél, hogy az n korongot átrakjuk az A rúdról a B rúdra:
Három, A-val B-vel és C-vel jelölt rúd. A „B” rúdon van az 5-ös, 4-es, 3-as, 2-es és 1-es korong, az 5-ös legalul, az 1-es legfelül. Az A és a C rúdon nincs korong.
Ugye könnyűnek tűnik? Azért nem olyan egyszerű, mert közben be kell tartanod két szabályt:
  1. Egyszerre csak egy korongot tehetsz át.
  2. 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=1. Az n=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 esetén? Három lépés kell hozzá. A kezdet kezdetén ezt látjuk:
Három, A-val B-vel és C-vel jelölt rúd. Az A rúdon van a 2-es korong alul és az 1-es korong felül. A „B” és a „C” rúdon nincs korong.
Először tegyük át az 1-es korongot az A rúdról a C-re:
Három, A-val, B-vel és C-vel jelölt rúd. Az A rúdon van a 2-es korong. A „B” rúdon nincs korong. A „C” rúdon van az 1-es korong.
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.
Három, A-val B-vel és C-vel jelölt rúd. Az „A” rúdon nincs korong. A „B” rúdon van a 2-es korong. A „C” rúdon van az 1-es korong.
Végül tegyük át az 1-es korongot az C rúdról a B-re:
Három, A-val, B-vel és C-vel jelölt rúd. Az A rúdon nincs korong. A „B” rúdon van a 2-es korong alul és az 1-es korong felül. A „C” rúdon nincs korong.
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.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.