Hanoi torony

A Hanoi-torony a 19. század egyik népszerű rejtvénye . Három rúd van megadva, amelyek közül az egyik nyolc gyűrűvel van felfűzve, és a gyűrűk mérete különbözik, és a kisebbik a nagyobbon fekszik. A feladat az, hogy a nyolc gyűrűből álló piramist a legkevesebb mozdulattal átvigyük egy másik rúdra. Egyszerre csak egy gyűrűt vihetsz magaddal, és nem helyezhetsz nagyobb gyűrűt egy kisebbre.

A rejtvény története

Ezt a játékot Edouard Lucas francia matematikus találta fel 1883- ban [1] , szórakoztató játékként adták el. Eredetileg "Professor Claus of Li-Sou-Stian College" [1] volt a neve, de hamarosan kiderült, hogy a megszűnt főiskola titokzatos professzora nem más, mint a játék feltalálója, Luke professzor (Lucas) nevének anagrammája. a Saint Louis College-ból.

Megoldás

A megoldásnak többféle megközelítése létezik.

Rekurzív megoldás

Rekurzív módon megoldjuk a "torony átvitele n − 1 lemezről a 2. tűre" problémáját. Ezután áthelyezzük a legnagyobb lemezt a 3. érintkezőre, és rekurzív módon megoldjuk az „ n − 1 lemezből álló tornyot a 3. érintkezőre” feladatot.

Emiatt matematikai indukcióval arra a következtetésre jutunk, hogy a rejtvény megoldásához szükséges lépések minimális száma 2 n − 1, ahol n a korongok száma [2] [3] .

A számítástechnikában a Hanoi-torony legendáján alapuló problémákat gyakran tekintik a rekurzív algoritmusok használatának és nem rekurzívvá alakításának példájának.

"Háromszög" megoldás

Rendezd el a csapokat háromszög alakban. Kezdjük a legkisebb gyűrűvel, és mozgassuk tetszőleges jelig. A jövőben ezt a gyűrűt ugyanabba az irányba kell mozgatni, mint az első váltáskor. Ezután áthelyezzük a megmaradt gyűrűk egy részét (csak egy ilyen mozdulat van), ezután ismét átvisszük a legkisebb gyűrűt stb. (Érdekes megjegyezni, hogy a „gyűrűk” sorba számozásával váratlan hatást érünk el : a páros gyűrűk az egyik csúcsháromszögből a másikba mozognak az egyik irányba, a páratlanok pedig az ellenkező irányba.)

Ciklikus döntés

Jelölje "1-2" egy ilyen műveletet: tolja el a lemezt az 1. tűről a 2. lábra, vagy a 2. lábról az 1. helyre, attól függően, hogy hol kisebb. Ezután egy páros számú korongból álló rejtvény megfejtéséhez többször meg kell ismételni a lépéseket: 1-2, 1-3, 2-3. Ha a lemezek száma páratlan - 1-3, 1-2, 2-3.

Gray kód alkalmazása a megoldáshoz

Szürke kód , egy reflex bináris kód bináris jelöléssel , amelyben két szomszédos érték csak egy bitben különbözik. A szürke kód eredetileg az elektromechanikus kapcsolók téves működése elleni védelmet szolgálta. Manapság a Gray kódokat széles körben használják a kommunikációs rendszerekben előforduló hibák észlelésének és kijavításának, valamint a vezérlőrendszerekben a visszacsatoló jelek kialakításának egyszerűsítésére. A kódot a Bell Labs kutatója, Frank Gray után nevezték el. Ezt a kódot szabadalmaztatta (2632058) és használta impulzuskommunikációs rendszerében.

A szürke kódok alkalmazhatók a Towers of Hanoi problémára.
Legyen N a lemezek száma. Kezdjük egy N hosszúságú Gray-kóddal, amely csak nullákból áll (vagyis G 0 ), és a Gray-kódok mentén haladunk (G i -től G i+1 -ig ). Az aktuális Gray-kód minden i-edik bitjét rendeljük hozzá az i-edik lemezhez (sőt, a legkisebb jelentőségű bit a legkisebb lemeznek, a legjelentősebb bit pedig a legnagyobbnak felel meg). Mivel minden lépésben pontosan egy bit változik, az i bit változását az i-edik lemez mozgatásaként értelmezhetjük. Ne feledje, hogy a legkisebb kivételével minden lemeznél pontosan egy lépés lehetséges minden lépésben (kivéve a kezdő és a végső pozíciót). A legkisebb korongnál mindig két lehetőség van a mozgásra, de van egy stratégia a megfelelő lépés kiválasztásához: páratlan N esetén a legkisebb korong mozgási sorrendje f→t→r→f→t→r→… (ahol f a kezdő rúd, t a végső rúd, r - maradék rúd), és páros f→r→t→f→r→t→… esetén .

Algoritmus implementációk

Példa egy megoldási algoritmusra C++ nyelven :

// Hanoi tornyai #include <iostream> névtér használata std ; void hanoi_towers ( int mennyiség , int from , int to , int buf_peg ) //gyűrűk mennyisége-száma, a gyűrűk kezdetétől (1-3), a gyűrűk végpontjáig (1-3) { //buf_peg - köztes csap (1-3) if ( mennyiség != 0 ) { hanoi_towers ( mennyiség -1 , from , buf_peg , to ); cout << from << " -> " << to << endl ; hanoi_towers ( mennyiség -1 , buf_peg , to , from ); } } int main () { setlocale ( LC_ALL , "rus" ); int start_peg , target_peg , buffer_peg , plate_quantity ; cout << "Első oszlop száma:" << endl ; cin >> start_peg ; cout << "Vége oszlop száma:" << endl ; cin >> rendeltetési_pont ; cout << "Közbenső oszlopszám:" << endl ; cin >> puffer_peg ; cout << "Lemezek száma:" << endl ; cin >> lemez_mennyiség ; hanoi_towers ( plate_quantity , start_peg , destination_peg , buffer_peg ); return 0 ; }

Példa Pascal megoldási algoritmusára :

hanoibns program ( bemenet , kimenet ) ; var n : egész szám ; eljárástorony ( k : integer ; a , b , c : char ) ; _ kezdődik , ha k > 1 , akkor torony ( k - 1 , a , c , b ) ; writeln ( ' from ' , a , ' to ' , b ) ; ha k > 1 akkor torony ( k - 1 , c , b , a ) vége ; beolvasni kezd ( n ) ; _ torony ( n , 'A' , 'C' , 'B' ) vége .

Példa egy megoldási algoritmusra a Haskellben :

hanoiSteps :: Int -> [( Int , Int )] hanoiSteps n = lépés ( max 0 n ) 1 3 2 [ ] ahol 0 lépés _ _ _ pihenés = pihenőlépés n f t s pihenés = lépés ( n - 1 ) f s t $ ( f , t ) : lépés ( n - 1 ) s t f pihenés

Példa egy megoldási algoritmusra Pythonban :

def Hanoi ( n , A , C , B ): if ( n != 0 ): Hanoi ( n - 1 , A , B , C ) print ( 'Move the plate from' , A , 'to' , C ) Hanoi ( n - 1 , B , C , A )

Példa egy Java megoldási algoritmusra :

public class Hanoi { public static void hanoiTowers ( int mennyiség , int from , int to , int buf_peg ) { if ( mennyiség != 0 ) { hanoiTowers ( mennyiség - 1 , from , buf_peg , to ); Rendszer . ki . println ( "" + -tól + " -> " + -ig ); hanoiTowers ( mennyiség - 1 , buf_peg , to , from ); } } public static void main ( String [] args ) { int start_peg = 1 , destination_peg = 2 , puffer_peg = 3 , plate_quantity = 4 ; hanoiTowers ( plate_quantity , start_peg , destination_peg , buffer_peg ); } }

Példa egy iteratív megoldási algoritmusra C -ben

#include <stdio.h> #include <math.h> void carryingOver ( int , int , int ); fő () { int szám , countDisk , számláló = 1 , count ; printf ( "Adja meg a lemezek számát: " ); /* Hanoi tornya */ scanf ( "%d" , & szám ); while ( számláló <= pow ( 2 , szám ) - 1 ) { /* Az ismétlési ciklus indítása */ if ( számláló % 2 != 0 ) { /* Páratlan fordulatnál csak a legkisebb lemezt fogjuk megérinteni */ printf ( "%3d %d " , számláló , 1 ); carryingOver ( szám , számláló , 1 ); /* Ezzel a funkcióval meghatározzuk ennek a lemeznek a mozgását */ } else { /* Határozza meg, hogy melyik lemezt egyenletes mozgással kell mozgatni */ count = számláló ; countDisk = 0 ; while ( count % 2 == 0 ) { /* Mozgatandó lemez */ countDisk ++ ; /* a lépésszám 2-vel való osztásának száma maradék nélkül */ count = count / 2 ; } printf ( "%3d %d " , számláló , countDisk + 1 ); carryingOver ( szám , számláló , countDisk + 1 ); } számláló ++ ; } return 0 ; } /* A lemezek mozgását észlelő funkció */ void carryingOver ( int n , int i , int k ) { int t , tengelyX , tengelyY , tengelyZ ; if ( n % 2 == 0 ) { /* Határozza meg a tengelyek sorrendjét a paritástól függően */ X tengely = 1 ; /* és nem paritásos lemezszám */ Y tengely = 2 ; tengely Z = 3 ; } else { X tengely = 1 ; Y tengely = 3 ; tengely Z = 2 ; } /* A lépésszám egyedi módon ábrázolható */ /* néhány páratlan szám és kettő hatványának szorzataként */ /* k az áthelyezett lemez száma */ t = (( i / pow ( 2 , k - 1 )) - 1 ) / 2 ; if ( k % 2 != 0 ) { /* Lemez mozgásának meghatározása páratlan mozgás esetén */ kapcsoló ( t % 3 ) { /* Válassza ki a mozgást az adott állapottól függően */ eset 0 : printf ( "%d -> %d \n " , axisX , axisY ); szünet ; 1. eset : printf ( "%d -> %d \n " , axisY , axisZ ); szünet ; 2. eset : printf ( "%d -> %d \n " , axisZ , axisX ); szünet ; } } else { /* Határozza meg a korongok mozgását egyenletes mozgáshoz */ kapcsoló ( t % 3 ) { 0. eset : printf ( "%d -> %d \n " , axisX , axisZ ); szünet ; 1. eset : printf ( "%d -> %d \n " , axisZ , axisY ); szünet ; 2. eset : printf ( "%d -> %d \n " , axisY , tengelyX ); szünet ; } } }

Vannak programok a rejtvény megoldásának megjelenítésére.

Opciók

Négy vagy több rúddal

Bár a háromrudas változatnak egyszerű rekurzív megoldása van, a négy rúddal rendelkező Tower of Hanoi optimális megoldása régóta megoldatlan probléma.

Nyilvánvalóan tetszőleges számú rúdhoz létezik egy algoritmus az optimális megoldások megtalálására, elegendő a rejtvényt irányítatlan gráfként ábrázolni, a csúcsokat a lemezelhelyezésekhez, az éleket pedig a mozgásokhoz igazítani, és bármilyen keresési algoritmust használni (pl. szélesség-első keresés ) az optimális megoldás megtalálásához. Azonban nincs hatékony stratégia az optimális megoldás megtalálására nagyszámú korong esetén: a 10 rúdból és 1000 korongból álló rejtvény megfejtéséhez szükséges lépések száma ismeretlen.

Létezik egy állítólag optimális Frame-Stewart algoritmus, amelyet 1941-ben fejlesztettek ki [4] . A kapcsolódó Frame-Stewart sejtés azt állítja, hogy a Frame-Stewart algoritmus mindig megtalálja az optimális megoldást. A Frame-Stewart algoritmus optimálisságát kísérletileg igazolták 30 lemezig 4 rúdon [5] . 2014-ben végre bebizonyosodott, hogy négy rúd esetén a Frame-Stewart algoritmus az optimális [6] .

A négyrúdú Tower of Hanoi megoldás más változatait Paul Stockmayer áttekintő cikke tárgyalja [7] .

Frame-Stewart algoritmus

A Frame-Stewart algoritmus, amely négy és egy állítólag optimális megoldást ad több botra, a következőképpen írható le:

Legyen a lemezek száma. $n$
Legyen a rudak száma. $r$
Definiáljuk úgy, hogy a legkevesebb mozdulat szükséges n lemez átviteléhez r rúddal. $T(n,r)$

Az algoritmus rekurzív módon leírható:

Egyeseknél a felsőket tegyük át az i pivotba , ami nem a kezdeti és nem is a végső pivot, erre költenek. $k$ $1\leq k<n$ $k$ $T(k,r)$
Az i rúd használata nélkül , amely most a felső korongokat tartalmazza, vigye át a megmaradt korongokat a végső rúdra, csak a megmaradt rudakat és a költési mozdulatokat használja. $k$ $nk$ $r-1$ $T(nk,r-1)$
Végül mozgassa a felső tárcsákat a végrúdhoz, ehhez költsön mozdulatokat. $k$ $T(k,r)$

Az egész folyamat mozdulatokat igényel. Az érték úgy van megválasztva, hogy ennek a kifejezésnek az értéke minimális legyen. 4 rúd esetén az optimális , ahol a legközelebbi egész szám függvénye . [nyolc] $2T(k,r)+T(nk,r-1)$ $k$ $k$ $n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1$ $\left\lfloor \cdot \right\rceil$

Legends

A Luca professzor által kitalált legenda szerint Benares városának Nagytemplomában , a világ közepét jelző katedrális alatt egy bronzkorong található, amelyen 3 gyémántrúd van rögzítve, egy könyök magas és méh vastagságú. . Réges-régen, az idők kezdetén ennek a kolostornak a szerzetesei vétkesek voltak Brahma isten előtt. Brahma feldühödve három magas rudat emelt, és az egyikre 64 tiszta aranyból készült korongot helyezett. És úgy, hogy minden kisebb lemez egy nagyobbra feküdjön.

Amint mind a 64 korong átkerül a rúdról, amelyre Brahma a világ teremtésekor feltette őket, egy másik rúdra, a torony a templommal együtt porrá válik, és a világ elpusztul a mennydörgés alatt.

A gyűrűk számától függő műszakok számát a képlet számítja ki . $2^{n}-1$

A szerzeteseknek 18 446 744 073 709 551 615 tárcsamozgások száma . Ha a szerzetesek éjjel-nappal dolgozva minden másodpercben megtennének egy mozgást a korongon, munkájuk csaknem 585 milliárd évig folytatódna .

A kultúrában

Eric Frank Russell "Your Move" című novellájában (Most Inhale, másik fordításban - "The Game of Survival") [9] , hogy késleltesse az idegenek általi kivégzést, a főhős a Hanoi Tower játékát választja. utolsó játékként 64 koronggal. A meghirdetett szabályok két játékos esetében módosultak – a játékosoknak egyenként kell korongokat váltaniuk, az nyer, aki az utolsó lépést teszi meg. A hős ezt a játékot "arki-malarki"-nak nevezi, és megesküszik, hogy "a Benares-templom papjai" a Földön játsszák ezt a játékot.

A Rise of the Planet of the Apes című filmben a hanoi tornyot intelligenciatesztként használják tesztalanyok számára. A majom húsz mozdulattal teljesíti a négykarikás rejtvényt.

A hanoi torony a kanadai BioWare cég videojátékainak egyik hagyományos feladványa – különösen a „ Jade Empire ”, a „ Star Wars: Knights of the Old Republic ”, a „ Mass Effect ” és a „Dragon Age: Inquisition”. . Találkoznak a Legend of Kyrandia II küldetésben is.

Jegyzetek

↑ 1 2 Martin Gardner, Matek rejtvények és szórakozás
↑ Petkovic, Miodrag. Nagy matematikusok híres rejtvényei (neopr.) . - AMS Könyvesbolt, 2009. - P. 197. - ISBN 0-8218-4814-3 .
↑ Graham, Ronald. Konkrét matematika: Számítástudományi Alapítvány . - Addison-Wesley , 1998. - P. 21. - ISBN 0201558025 .
↑ Megoldás a 3819-es speciális feladatra, American Mathematical Monthly , 1941.
↑ Korf, Richard E. és Ariel Felner. A heurisztikus keresés közelmúltbeli fejlődése: esettanulmány a hanoi négycsapos tornyok problémájáról // IJCAI : folyóirat. - 2007. - P. 2324-2329 . Az eredetiből archiválva : 2015. szeptember 24.
↑ Bousch, T. La quatrieme tour de Hanoi (neopr.) // Bull. Belg. Math. szoc. Simon Stevin. - 2014. - T. 21 . - S. 895-912 .
↑ Paul Stockmeyer. Variációk a hanoi négyoszlopos tornyra Puzzle (neopr.) // Congressus Numerantium. - 1994. - T. 102 . - S. 3-12 .
↑ University of Toronto CSC148 Slog (2014. április 5.). Letöltve: 2015. július 22. (határozatlan)
↑ Russell, Eric Frank. Az Ön lépése // Ha . - 1994. - április. - S. 34-42 . (Orosz)

Lásd még

Tower of London teszt

Linkek

A007664 szekvencia az OEIS -ben
Konstantin Knop. Hanoi tornya . Elemek (2012. október 22.). (határozatlan)
Online játék Hanoi tornyai

Tematikus oldalak	Óriásbomba
Szótárak és enciklopédiák	Britannica (online) Britannica (online)
Bibliográfiai katalógusokban	NKC : ph1060364