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, folytatás

Amikor a Hanoi tornyot megoldottad három korongra, fel kellett fedned a legalsó 3-as korongot, hogy át tudd tenni az A rúdról a B rúdra. Ahhoz, hogy felfedd a 3-as korongot, az 1-es és 2-es korongokat az A rúdról a tartalék rúdra kellett áttenni, ami a C rúd:
Várj csak, most két korongot mozgattunk egy lépésben, ezzel megszegve az egyes szabályt? De nem egy lépésben mozgattuk át! Elfogadtad, hogy az 1-es és 2-es korongokat tetszőleges rúdról tetszőleges rúdra át tudod tenni három lépésben. A fenti ábra a három lépés utáni helyzetet mutatja. (Mozgasd át az 1-es korongot az A rúdról a B-re; mozgasd át a 2-es korongot az A-ról a C-re; majd mozgasd át az 1-es korongot a B rúdról a C-re.)
Hogy precízebbek legyünk, az 1-es és 2-es korongok A rúdról C rúdra való átmozgatását a részfeladat rekurzív megoldásával oldottad meg: az 1 és n1 közötti korongok mozgatásával (ne feledd, n=3) A rúdról C rúdra. Miután megoldottad a részfeladatot, átteheted a 3-as korongot az A rúdról a B rúdra:
Befejezésképpen rekurzíó alapján megoldhatod az 1 és n1 közötti korongok C rúdról B rúdra való mozgatásának részfeladatát. Megegyeztünk abban, hogy ez három lépésben megoldható. (áttesszük az 1-es korongot a C rúdról az A rúdra; átrakjuk a 2-es korongot a C rúdról a B rúdra; majd átmozgatjuk az 1-es korongot az A rúdról a B-re.) És ezzel megvagy:
Most jön a szokásos kérdés – van bármi különbség a között, hogy melyik rúdról melyik rúdra tetted át a korongokat? Bármelyik rúdról bármelyikre pakolhattad volna át azokat. Például a B rúdról a C-re:
  • Rekurzióval oldd meg az 1-es és 2-es korongok B rúdról való átmozgatásának részfeladatát a tartalék A rúdra. (Mozgasd át az 1-es korongot a B rúdról a C-re; mozgasd át a 2-es korongot a B rúdról az A-ra; tedd át az 1-es korongot a C rúdról az A-ra.)
  • Most, hogy felfedtük a 3-as korongot a B rúdon, tedd azt át a C rúdra.
  • Rekurzióval oldd meg az 1-es és 2-es korongok A rúdról való átmozgatásának részfeladatát a C rúdra. (Mozgasd át az 1-es korongot az A rúdról a B-re; mozgasd át a 2-es korongot az A rúdról a C-re; tedd át az 1-es korongot a B rúdról az C-re.)
Függetlenül attól, hogy hogyan osztod fel, az 1-3 korongokat bármelyik rúdról bármelyik rúdra át tudod mozgatni 7 lépésben. Figyeld meg, hogy háromszor mozgatod a korongokat mindkét alkalommal, amikor rekurzívan megoldod az 1-es és 2-es korongok átmozgatását, amihez hozzájön a 3-as korong 1 lépésbeni átmozgatása.
És mi van n=4? esetében? Mivel rekurzívan meg tudod oldani az 1-3 korongok bármelyik rúdról bármelyik rúdra irányuló átmozgatásának részfeladatát, meg tudod oldani az n=4 esetet is:
  • Rekurzióval oldd meg az 1-3-es korongok A rúdról való átmozgatásának részfeladatát a C rúdra hét lépésben.
  • Mozgasd át a 4-es korongot az A rúdról a B-re.
  • Rekurzióval oldd meg az 1-3 korongok C rúdról való átmozgatásának részfeladatát a B rúdra hét lépésben.
Ehhez a megoldáshoz 15 mozgatás kell (7+1+7), és igen, az 1-4 korongokat bármelyik rúdról bármelyikre átmozgathatod.
Mostanra felismerhettél két mintát. Először is a Hanoi torony feladat rekurzívan megoldható. Ha n=1, egyszerűen mozgasd át az 1-es korongot. Egyébként, ha n2, oldd meg a feladatot három lépésben:
  • Rekurzióval oldd meg az 1-től n1-es korongok átmozgatásának részfeladatát a tartalék rúdra arról a rúdról, ahol éppen vannak.
  • Mozgasd az n-es korongot a kezdeti rúdról a cél rúdra.
  • Rekurzióval oldd meg az 1-től n1-es korongok átmozgatásának részfeladatát a tartalék rúdról a cél rúdra.
Másodsorban, n korong átmozgatásához 2n1 lépés kell. Láttuk, hogy ez igaz:
  • n=1 (211=1, csak egy lépés kell)
  • n=2 (221=3, három lépés kell)
  • n=3 (231=7, hét lépés kell)
  • n=4 (241=15, 15 lépés kell).
Ha meg tudod oldani a feladatot n1 koronggal 2n11 lépésben, akkor n koronghoz 2n1 lépés kell. Szükséged lesz:
  • 2n11 lépés kell az 1-től n1-es korongok rekurzív átmozgatásának első részfeladatához
  • 1 lépés kell az n-es korong mozgatásához
  • 2n11 újból lépés kell az 1-től n1-es korongok rekurzív átmozgatásának második részfeladatához
Ha összeadod a lépéseket, 2n1-t kapsz.
Térjünk vissza a szerzetesekhez. n=64 koronggal dolgoznak, úgyhogy 2641 korongot kell elmozgatniuk. Ezek a szerzetesek ügyesek és erősek. Tegyük fel, hogy másodpercenként egy korongot tesznek át másodpercenként, éjjel és nappal megállás nélkül.
Mennyi ideig tart 2641 másodperc? Durva becsléssel 365,25 nap van egy évben, ez alapján 584 542 046 090,6263 év jön ki. Ez több, mint 584 billió év. A Napnak még körülbelül 5-7 billió éve van hátra, mielőtt szupernóvává alakul. Hát igen, a világnak vége lesz, akármilyen odaadóan is dolgoznak a szerzetesek, mielőtt mind a 64 korongot áttennék a B rúdra.
Kíváncsi vagy, mire lehet ezt az algoritmust felhasználni a világvége megjóslásán kívül? A Wikipedián számos érdekes ötletet találsz.
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.