Hanoin torni

Hanoin torni on yksi 1800-luvun suosituimmista arvoimista . Annetaan kolme sauvaa, joista yksi on pujotettu kahdeksalla renkaalla, ja renkaat eroavat kooltaan ja pienempi on isomman päällä. Tehtävänä on siirtää kahdeksan renkaan pyramidi vähimmällä määrällä liikkeitä toiseen sauvaan. Voit kantaa vain yhtä sormusta kerrallaan, etkä voi laittaa suurempaa sormusta pienemmän päälle.

Palapelin historia

Tämän pelin keksi ranskalainen matemaatikko Edouard Lucas vuonna 1883 [1] , se myytiin hauskana leluna. Sitä kutsuttiin alun perin "Professor Claus of Li-Sou-Stian Collegesta" [1] , mutta pian selvisi, että salaperäinen professori lakkautetusta korkeakoulusta oli vain anagrammi pelin keksijän, professori Luken (Lucas) nimelle. Saint Louis Collegesta.

Ratkaisu

Ratkaisuun on useita lähestymistapoja.

Rekursiivinen ratkaisu

Ratkaisemme rekursiivisesti ongelman "tornin siirtämisestä n − 1 levyltä 2. nastalle". Sitten siirrämme suurimman levyn 3. nastalle ja ratkaisemme rekursiivisesti tehtävän "siirrä n − 1 levyn torni 3. nastalle".

Tästä syystä matemaattisella induktiolla päätämme , että pulman ratkaisemiseen vaadittavien liikkeiden vähimmäismäärä on 2 n − 1, missä n on kiekkojen lukumäärä [2] [3] .

Tietojenkäsittelytieteessä Hanoin tornin legendaan perustuvia ongelmia pidetään usein esimerkkinä rekursiivisten algoritmien käytöstä ja niiden muuntamisesta ei-rekursiivisiksi.

"Kolmio" ratkaisu

Järjestä neulat kolmion muotoon. Aloitetaan pienimmästä renkaasta ja siirretään se mihin tahansa merkkiin. Jatkossa tätä rengasta on siirrettävä samaan suuntaan kuin ensimmäisessä vaihdossa. Sitten siirrämme osan jäljellä olevista renkaista (tällaista liikettä on vain yksi), minkä jälkeen siirrämme jälleen pienimmän renkaan jne. (On mielenkiintoista huomata, että numeroimalla "renkaat" uudelleen järjestykseen saavutamme odottamattoman vaikutuksen : parilliset renkaat liikkuvat kärkikolmioista toiseen yhteen suuntaan ja parittomat vastakkaiseen suuntaan.)

Syklinen päätös

Merkitse "1-2":lla tällainen toiminta: siirrä levy joko 1. nastasta 2. tai 2. nastasta 1. sen mukaan, missä se on pienempi. Sitten ratkaistaksesi pulman, jossa on parillinen määrä levyjä, sinun on toistettava vaiheet monta kertaa: 1-2, 1-3, 2-3. Jos levyjen määrä on pariton - 1-3, 1-2, 2-3.

Harmaan koodin soveltaminen ratkaisemaan

Harmaa koodi , refleksi binäärikoodi binäärimuodossa , jossa kaksi vierekkäistä arvoa eroavat vain yhdessä bitissä. Harmaa koodi oli alun perin tarkoitettu suojaamaan sähkömekaanisten kytkimien väärältä toiminnalta. Nykyään Gray-koodeja käytetään laajalti yksinkertaistamaan virheiden havaitsemista ja korjaamista viestintäjärjestelmissä sekä palautesignaalien muodostamisessa ohjausjärjestelmissä. Koodi on nimetty Bell Labsin tutkijan Frank Grayn mukaan. Hän patentoi (numero 2632058) ja käytti tätä koodia impulssiviestintäjärjestelmässään.

Harmaa koodia voidaan soveltaa Towers of Hanoi -ongelmaan.
Olkoon N levyjen lukumäärä. Aloitetaan Gray-koodilla, jonka pituus on N ja joka koostuu vain noloista (eli G 0 ), ja siirrytään Gray-koodeja pitkin (G i :stä G i+1 :een ). Osoitetaan jokainen nykyisen Gray-koodin i:s bitti i:nnelle levylle (lisäksi vähiten merkitsevä bitti vastaa pienintä levyä ja merkittävin bitti vastaa suurinta). Koska täsmälleen yksi bitti muuttuu jokaisessa vaiheessa, voimme ymmärtää bitin i muutoksen i:nnen levyn siirtämiseksi. Huomaa, että kaikilla levyillä paitsi pienimmällä on tasan yksi mahdollinen liike jokaisessa vaiheessa (lukuun ottamatta aloitus- ja loppuasentoa). Pienimmälle kiekolle on aina kaksi siirtovaihtoehtoa, mutta oikean liikkeen valitsemiseksi on strategia: parittomille N:lle pienimmän kiekon liikesarja f→t→r→f→t→r→… (jossa f on aloitussauva, t on viimeinen sauva, r - jäljellä oleva sauva) ja parilliselle f→r→t→f→r→t→… .

Algoritmien toteutukset

Esimerkki ratkaisualgoritmista C++ :ssa :

// Hanoin tornit #sisältää < iostream > käyttäen nimiavaruutta std ; void hanoi_towers ( int määrä , int from , int to , int buf_peg ) // renkaiden määrä - välitappi (1-3) jos ( määrä != 0 ) { hanoi_towers ( määrä -1 , alkaen , buf_peg , to ); cout << alkaen << " -> " << to << endl ; hanoi_towers ( määrä -1 , buf_peg , to , from ); } } int main () { setlocale ( LC_ALL , "rus" ); int aloitusliitos , kohdeliitos , puskurin_liitos , levyn_määrä ; cout << "Ensimmäisen sarakkeen numero:" << endl ; cin >> start_peg ; cout << "Loppusarakkeen numero:" << endl ; cin >> kohde_liitin ; cout << "Välisarakkeen numero:" << endl ; cin >> buffer_peg ; cout << "Levyjen lukumäärä:" << endl ; cin >> levyn_määrä ; hanoi_towers ( levyn_määrä , aloitusliitos , määränpään_liitos , puskurin_liitos ); paluu 0 ; }

Esimerkki ratkaisualgoritmista Pascalissa :

ohjelma hanoibns ( input , output ) ; var n : kokonaisluku ; proseduuritorni ( k : kokonaisluku ; a , b , c : merkki ) ; _ alkaa jos k > 1 niin torni ( k - 1 , a , c , b ) ; writeln ( 'from' , a , 'to' , b ) ; jos k > 1 niin tornin ( k - 1 , c , b , a ) pää ; aloita lukeminen ( n ) ; _ torni ( n , 'A' , 'C' , 'B' ) pää .

Esimerkki ratkaisualgoritmista Haskellissa :

hanoiSteps :: Int -> [( Int , Int )] hanoiSteps n = askel ( max 0 n ) 1 3 2 [ ] missä vaihe 0 _ _ _ lepo = lepovaihe n f t s lepo = vaihe ( n - 1 ) f s t $ ( f , t ) : vaihe ( n - 1 ) s t f lepo

Esimerkki ratkaisualgoritmista Pythonissa :

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 )

Esimerkki ratkaisualgoritmista Javassa :

public class Hanoi { public static void hanoiTowers ( int määrä , int alkaen , int to , int buf_peg ) { if ( määrä != 0 ) { hanoiTowers ( määrä - 1 , alkaen , buf_peg , to ); Järjestelmä . ulos . println ( "" + alkaen + " -> " + paikkaan ); hanoiTowers ( määrä - 1 , buf_peg , to , from ); } } public static void main ( Merkkijono [ ] args ) { int aloitusliitos = 1 , kohdeliitos = 2 , puskurin_liitos = 3 , levyn_määrä = 4 ; hanoiTowers ( levyn_määrä , aloitusliitos , määränpään_liitos , puskurin_liitos ); } }

Esimerkki iteratiivisesta ratkaisualgoritmista C :ssä

#include <stdio.h> #include <math.h> void carryingOver ( int , int , int ); tärkein () { int numero , countDisk , laskuri = 1 , count ; printf ( "Anna levyjen määrä:" ); /* Hanojen torni */ scanf ( "%d" , & numero ); while ( laskuri <= pow ( 2 , numero ) - 1 ) { /* Aloita toistosilmukka */ if ( laskuri % 2 != 0 ) { /* Parittomalla käännöksellä kosketamme vain pienintä levyä */ printf ( "%3d %d " , laskuri , 1 ); carryingOver ( numero , laskuri , 1 ); /* Tällä funktiolla määritämme tämän levyn liikkeen */ } else { /* Määritä tasaisella siirrolla siirrettävä levy */ count = laskuri ; countDisk = 0 ; while ( count % 2 == 0 ) { /* Siirrettävä levy */ countDisk ++ ; /* on luku, joka jakaa siirtonumeron kahdella ilman jäännöstä */ count = count / 2 ; } printf ( "%3d %d " , laskuri , countDisk + 1 ); carryingOver ( numero , laskuri , countDisk + 1 ); } laskuri ++ ; } paluu 0 ; } /* Toiminto levyjen liikkeen havaitsemiseen */ void carryingOver ( int n , int i , int k ) { int t , akseliX , akseliY , akseliZ ; if ( n % 2 == 0 ) { /* Määritä akselien järjestys pariteetin mukaan */ akseliX = 1 ; /* ja levyjen pariteettiton määrä */ akseli Y = 2 ; akseli Z = 3 ; } else { akseliX = 1 ; akseli Y = 3 ; akseli Z = 2 ; } /* Siirtonumero voidaan esittää ainutlaatuisella tavalla */ /* jonkun parittoman luvun tulona kahden potenssilla */ /* k on siirrettävän levyn numero */ t = (( i / pow ( 2 , k - 1 )) - 1 ) / 2 ; if ( k % 2 != 0 ) { /* Määritä parittoman liikkeen levyn liike */ kytkin ( t % 3 ) { /* Valitse siirto tietyn ehdon mukaan */ case 0 : printf ( "%d -> %d \n " , akseliX , akseliY ); tauko ; tapaus 1 : printf ( "%d -> %d \n " , akseliY , akseliZ ); tauko ; tapaus 2 : printf ( "%d -> %d \n " , akseliZ , akseliX ); tauko ; } } else { /* Määritä kiekkojen liike tasaista liikettä varten */ kytkin ( t % 3 ) { tapaus 0 : printf ( "%d -> %d \n " , akseliX , akseliZ ); tauko ; tapaus 1 : printf ( "%d -> %d \n " , akseliZ , akseliY ); tauko ; tapaus 2 : printf ( "%d -> %d \n " , akseliY , akseliX ); tauko ; } } }

On olemassa ohjelmia tämän pulman ratkaisun visualisoimiseksi.

Vaihtoehdot

Neljällä tai useammalla vavalla

Vaikka kolmitankoisessa versiossa on yksinkertainen rekursiivinen ratkaisu, optimaalinen ratkaisu Tower of Hanoin neljän tangon kanssa on ollut pitkään ratkaisematon ongelma.

Ilmeisesti mille tahansa sauvamäärälle on olemassa algoritmi optimaalisten ratkaisujen löytämiseen, riittää, että palapeli esitetään suuntaamattomana graafina, joka sovittaa kärjet levyjen sijoitteluihin ja reunat liikkeisiin, ja käyttää mitä tahansa hakualgoritmia (esim. leveyshaku ) löytääksesi optimaalisen ratkaisun. Ei kuitenkaan ole olemassa tehokasta strategiaa optimaalisen ratkaisun löytämiseksi suurelle määrälle kiekkoja: 10 sauvan ja 1000 kiekon pulman ratkaisemiseen tarvittavien liikkeiden määrä on edelleen tuntematon.

On olemassa oletettavasti optimaalinen Frame-Stewart-algoritmi, joka kehitettiin vuonna 1941 [4] . Tähän liittyvä Frame-Stewart-oletus väittää, että Frame-Stewart-algoritmi löytää aina optimaalisen ratkaisun. Frame-Stewart-algoritmin optimaalisuus on varmistettu kokeellisesti 30 levylle 4 sauvalla [5] . Vuonna 2014 vihdoin todistettiin, että Frame-Stewart-algoritmi on optimaalinen neljälle sauvalle [6] .

Muita muunnelmia nelipalkista Tower of Hanoi -ratkaisusta käsitellään Paul Stockmayerin katsausartikkelissa [7] .

Frame-Stewart-algoritmi

Frame-Stewart-algoritmi, joka antaa optimaalisen ratkaisun neljälle ja oletettavasti optimaalisen ratkaisun useammalle sauvalle, on kuvattu seuraavasti:

Antaa olla levyjen lukumäärä. $n$
Antaa olla sauvojen lukumäärä. $r$
Määritellään se vähiten liikkeiden lukumääräksi, joka tarvitaan n levyn siirtämiseen r tangolla. $T(n,r)$

Algoritmi voidaan kuvata rekursiivisesti:

Joillekin , , siirrä ylemmät pivotiin i , joka ei ole alku- eikä viimeinen pivot, kulutusliikkeitä tähän. $k$ $1\leq k<n$ $k$ $T(k,r)$
Ilman sauvaa i , joka sisältää nyt ylemmät kiekot, siirrä jäljellä olevat kiekot lopulliseen sauvaan käyttämällä vain jäljellä olevia sauvoja ja kulutusliikkeitä . $k$ $nk$ $r-1$ $T(nk,r-1)$
Siirrä lopuksi ylemmät levyt päätytankoon ja käytä tätä varten liikkeitä. $k$ $T(k,r)$

Koko prosessi vaatii liikkeitä. Arvo valitaan siten, että tämän lausekkeen arvo on minimaalinen. 4 sauvan tapauksessa optimaalinen on , jossa on lähimmän kokonaisluvun funktio . [kahdeksan] $2T(k,r)+T(nk,r-1)$ $k$ $k$ $n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1$ $\left\lfloor \cdot \right\rceil$

Legendat

Professori Lucan keksimä legenda kertoo, että Benaresin kaupungin suuressa temppelissä , katedraalin alla, joka merkitsee maailmaa , on pronssikiekko, johon on kiinnitetty 3 timanttitankoa, yhden kyynärän korkea ja mehiläisen paksuinen. . Kauan sitten, aivan aikojen alussa, tämän luostarin munkit olivat syyllisiä Brahman jumalan edessä. Raivostuneena Brahma pystytti kolme korkeaa sauvaa ja asetti 64 puhtaasta kullasta tehtyä kiekkoa yhteen niistä. Ja niin, että jokainen pienempi levy on suuremman päällä.

Heti kun kaikki 64 kiekkoa on siirretty sauvasta, jolle Brahma ne asetti maailmaa luodessaan, toiseen sauvaan, torni yhdessä temppelin kanssa muuttuu tomuksi ja maailma tuhoutuu ukkosen jylinän alla.

Vuorojen lukumäärä soittojen lukumäärästä riippuen lasketaan kaavalla . $2^{n}-1$

Munkkien on tehtävä kiekon liikkeitä 18 446 744 073 709 551 615 . Jos munkit, jotka työskentelevät yötä päivää, tekisivät yhden kiekon liikkeen sekunnissa, heidän työnsä jatkuisi lähes 585 miljardia vuotta .

Kulttuurissa

Eric Frank Russellin novellissa "Your Move" (Now Inhale, toisessa käännöksessä "The Game of Survival") [9] päähenkilö valitsee Hanoin tornipelin viivyttääkseen muukalaisten suorittamaa teloitusta. 64 levyä viimeisenä pelinä. Ilmoitettuja sääntöjä on muutettu kahdelle pelaajalle - pelaajien on vaihdettava kiekkoja yksi kerrallaan, voittaja on se, joka tekee viimeisen liikkeen. Sankari kutsuu tätä peliä "arki-malarkiksi" ja vannoo, että "Benaresin temppelin papit" maan päällä pelaavat tätä peliä.

Rise of the Planet of the Apes -elokuvassa Hanoin tornia käytetään koehenkilöiden älykkyystestinä. Apina suorittaa neljän renkaan palapelin kahdessakymmenessä liikkeessä.

Hanoin torni on yksi kanadalaisen BioWaren videopelien perinteisistä pulmapeleistä - erityisesti " Jade Empire ", " Star Wars: Knights of the Old Republic ", " Mass Effect " ja "Dragon Age: Inquisition". . He tapaavat myös Legend of Kyrandia II -tehtävässä.

Muistiinpanot

↑ 1 2 Martin Gardner, Math Puzzles and Fun
↑ Petkovic, Miodrag. Suurten matemaatikoiden kuuluisat palapelit (uuspr.) . - AMS Bookstore, 2009. - S. 197. - ISBN 0-8218-4814-3 .
↑ Graham, Ronald. Konkreettinen matematiikka: Tietojenkäsittelytieteen säätiö . - Addison-Wesley , 1998. - S. 21. - ISBN 0201558025 .
↑ Ratkaisu edistyneeseen tehtävään 3819, American Mathematical Monthly , 1941.
↑ Korf, Richard E. ja Ariel Felner. Viimeaikainen edistyminen heuristisessa haussa: tapaustutkimus Hanoin neljän nastan tornien ongelmasta // IJCAI : päiväkirja. - 2007. - S. 2324-2329 . Arkistoitu alkuperäisestä 24. syyskuuta 2015.
↑ Bousch, T. La quatrieme tour de Hanoi (uuspr.) // Bull. Belg. Matematiikka. soc. Simon Stevin. - 2014. - T. 21 . - S. 895-912 .
↑ Paul Stockmeyer. Muunnelmia Hanoin nelipylvään tornista (uuspr.) // Congressus Numerantium. - 1994. - T. 102 . - S. 3-12 .
↑ Toronton yliopiston CSC148 Slog (5. huhtikuuta 2014). Haettu: 22.7.2015. (määrätön)
↑ Russell, Eric Frank. Sinun siirtosi // Jos . - 1994 - huhtikuu. - S. 34-42 . (Venäjän kieli)

Katso myös

Lontoon Towerin testi

Linkit

sekvenssi A007664 OEIS : ssä
Konstantin Knop. Hanoin torni . Elements (22. lokakuuta 2012). (määrätön)
Online-peli Towers of Hanoi

Temaattiset sivustot	Jättiläinen pommi
Sanakirjat ja tietosanakirjat	Britannica (verkossa) Britannica (verkossa)
Bibliografisissa luetteloissa	NKC : ph1060364