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 $n-1$‍ 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 $n-1$‍ 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:

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:

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 $n\ge 2$‍, oldd meg a feladatot három lépésben:

Másodsorban, $n$‍ korong átmozgatásához $2^n-1$‍ lépés kell. Láttuk, hogy ez igaz:

Ha meg tudod oldani a feladatot $n-1$‍ koronggal $2^{n-1}-1$‍ lépésben, akkor $n$‍ koronghoz $2^n-1$‍ lépés kell. Szükséged lesz:

Ha összeadod a lépéseket, $2^n-1$‍-t kapsz.

Térjünk vissza a szerzetesekhez. $n=64$‍ koronggal dolgoznak, úgyhogy $2^{64}-1$‍ 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 $2^{64}-1$‍ 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.