Tornet i hanoi

Tornet i Hanoi är ett av 1800-talets populära pussel . Tre stavar ges, varav en är uppträdd med åtta ringar, och ringarna skiljer sig i storlek och den mindre ligger på den större. Uppgiften är att överföra pyramiden med åtta ringar i minsta antal drag till en annan stav. Du kan bara bära en ring åt gången, och du kan inte placera en större ring ovanpå en mindre.

Historia av pusslet

Detta spel uppfanns av den franske matematikern Edouard Lucas 1883 [ 1] , det såldes som en rolig leksak. Det kallades ursprungligen "Professor Claus of Li-Sou-Stian College" [1] , men det upptäcktes snart att den mystiska professorn från det nedlagda college inte var något annat än ett anagram för namnet på spelets uppfinnare, professor Luke ( Lucas från Saint Louis College.

Lösning

Det finns flera tillvägagångssätt till lösningen.

Rekursiv lösning

Vi löser rekursivt problemet med att "överföra ett torn från n − 1 skivor till det andra stiftet". Sedan flyttar vi den största skivan till 3:e stiftet och löser rekursivt problemet "överför tornet av n − 1 skivor till 3:e stiftet".

Genom matematisk induktion drar vi därför slutsatsen att det minsta antalet drag som krävs för att lösa pusslet är 2 n − 1, där n är antalet skivor [2] [3] .

Inom datavetenskap betraktas problem baserade på legenden om Hanois torn ofta som ett exempel på att använda rekursiva algoritmer och konvertera dem till icke-rekursiva.

"Triangel"-lösning

Ordna stiften i form av en triangel. Låt oss börja med den minsta ringen och flytta den till valfritt märke. I framtiden måste denna ring flyttas i samma riktning som vid första växlingen. Sedan överför vi några av de återstående ringarna (det finns bara ett sådant drag), varefter vi återigen överför den minsta ringen, etc. (Det är intressant att notera att genom att numrera om "ringarna" i ordning, kommer vi att uppnå en oväntad effekt : jämna ringar kommer att flytta från en vertextrianglar till en annan i en riktning och udda i motsatt riktning.)

Cykliskt beslut

Beteckna med "1-2" en sådan åtgärd: flytta skivan antingen från 1:a stiftet till 2:a eller från 2:a till 1:a, beroende på var den är mindre. Sedan, för att lösa ett pussel med ett jämnt antal skivor, måste du upprepa stegen många gånger: 1-2, 1-3, 2-3. Om antalet diskar är udda - 1-3, 1-2, 2-3.

Tillämpning av grå kod för att lösa

Gråkod , en binär reflexkod i binär notation , där två angränsande värden skiljer sig åt på bara en bit. Gråkoden var ursprungligen avsedd att skydda mot felaktig användning av elektromekaniska brytare. Idag används gråkoder i stor utsträckning för att förenkla upptäckt och korrigering av fel i kommunikationssystem, såväl som vid bildandet av återkopplingssignaler i styrsystem. Koden är uppkallad efter Bell Labs-forskaren Frank Gray. Han patenterade (nummer 2632058) och använde denna kod i sitt impulskommunikationssystem.

Grå koder kan tillämpas på Towers of Hanoi-problemet.
Låt N vara antalet diskar. Låt oss börja med en Gray-kod med längden N, som bara består av nollor (det vill säga G 0 ), och vi kommer att flytta längs med Gray-koderna (från G i går till G i+1 ). Låt oss tilldela varje i:te bit av den aktuella Gray-koden till den i:te skivan (dettare motsvarar den minst signifikanta biten den minsta skivan och den mest signifikanta biten motsvarar den största). Eftersom exakt en bit ändras vid varje steg, kan vi förstå förändringen av bit i som att den i:te skivan flyttas. Observera att för alla skivor utom den minsta finns det exakt ett möjligt drag vid varje steg (förutom start- och slutpositionen). För den minsta skivan finns det alltid två alternativ för draget, men det finns en strategi för att välja rätt drag: för udda N, sekvensen av rörelser för den minsta skivan f→t→r→f→t→r→... (där f är startspöet, t är det sista spöet, r - återstående spö), och för jämn f→r→t→f→r→t→… .

Algoritmimplementationer

Ett exempel på en lösningsalgoritm i C++ :

// Towers of Hanoi #include <iostream> använder namnutrymme std ; void hanoi_towers ( int kvantitet , int från , int till , int buf_peg ) //kvantitet-antal ringar, från startposition för ringar(1-3), till slutposition för ringar(1-3) { //buf_peg - mellanliggande pinne (1-3) if ( kvantitet != 0 ) { hanoi_towers ( kvantitet -1 , från , buf_peg , till ); cout << från << " -> " << till << endl ; hanoi_torn ( kvantitet -1 , buf_peg , till , från ); } } int main () { setlocale ( LC_ALL , "rus" ); int start_peg , destination_peg , buffer_peg , plate_quantity ; cout << "Första kolumnnummer:" << endl ; cin >> start_peg ; cout << "Slut kolumnnummer:" << endl ; cin >> destination_peg ; cout << "Mellankolumnnummer:" << endl ; cin >> buffert_peg ; cout << "Antal diskar:" << endl ; cin >> tallrik_kvantitet ; hanoi_torn ( plate_quantity , start_peg , destination_peg , buffer_peg ); returnera 0 ; }

Ett exempel på en lösningsalgoritm i Pascal :

program hanoibns ( ingång , utgång ) ; var n : heltal ; procedurtorn ( k : heltal ; a , b , c : char ) ; _ börja om k > 1 så torn ( k - 1 , a , c , b ) ; writeln ( 'från' , a , 'till' , b ) ; om k > 1 så torn ( k - 1 , c , b , a ) slut ; börja läsa ( n ) ; _ torn ( n , 'A' , 'C' , 'B' ) slut .

Ett exempel på en lösningsalgoritm i Haskell :

hanoiSteps :: Int -> [( Int , Int )] hanoiSteps n = steg ( max 0 n ) 1 3 2 [] där steg 0 _ _ _ vila = vila steg n f t s vila = steg ( n - 1 ) f s t $ ( f , t ) : steg ( n - 1 ) s t f vila

Ett exempel på en lösningsalgoritm i Python :

def Hanoi ( n , A , C , B ): if ( n != 0 ): Hanoi ( n - 1 , A , B , C ) print ( 'Flytta plattan från' , A , 'till' , C ) Hanoi ( n - 1 , B , C , A )

Ett exempel på en lösningsalgoritm i Java :

public class Hanoi { public static void hanoiTowers ( int quantity , int from , int to , int buf_peg ) { if ( quantity != 0 ) { hanoiTowers ( quantity - 1 , from , buf_peg , to ); System . ut . println ( "" + från + " -> " + till ); hanoiTowers ( kvantitet - 1 , buf_peg , till , från ); } } public static void main ( String [] args ) { int start_peg = 1 , destination_peg = 2 , buffer_peg = 3 , plate_quantity = 4 ; hanoiTowers ( plate_quantity , start_peg , destination_peg , buffer_peg ); } }

Ett exempel på en iterativ lösningsalgoritm i C

#include <stdio.h> #inkludera <math.h> void carryingOver ( int , int , int ); huvud () { int nummer , countDisk , räknare = 1 , count ; printf ( "Ange antal diskar: " ); /* Hanois torn */ scanf ( "%d" , & nummer ); while ( räknare <= pow ( 2 , nummer ) - 1 ) { /* Starta repetitionsslingan */ if ( räknare % 2 != 0 ) { /* Vid en udda sväng kommer vi bara att vidröra den minsta skivan */ printf ( "%3d %d" , räknare , 1 ); carryingOver ( nummer , räknare , 1 ); /* Med den här funktionen bestämmer vi rörelsen för denna disk */ } else { /* Bestäm disken som ska flyttas vid ett jämnt drag */ räkna = räknare ; countDisk = 0 ; while ( count % 2 == 0 ) { /* Disk att flytta */ countDisk ++ ; /* kommer att vara numret för att dividera dragnumret med 2 utan rest */ count = count / 2 ; } printf ( "%3d %d" , räknare , countDisk + 1 ); carryingOver ( nummer , räknare , countDisk + 1 ); } räknare ++ ; } returnera 0 ; } /* Funktion för att upptäcka rörelser av diskar */ void carryingOver ( int n , int i , int k ) { int t , axisX , axisY , axisZ ; if ( n % 2 == 0 ) { /* Bestäm axlarnas ordning beroende på pariteten */ axel X = 1 ; /* och icke-paritet antal diskar */ axel Y = 2 ; axel Z = 3 ; } annat { axel X = 1 ; axel Y = 3 ; axel Z = 2 ; } /* Flyttnumret kan representeras på ett unikt sätt */ /* som en produkt av ett udda tal gånger en potens av två */ /* k kommer att vara numret på disken vi flyttar */ t = (( i / pow ( 2 , k - 1 ) ) -1 ) / 2 ; if ( k % 2 != 0 ) { /* Bestäm skivrörelsen för udda drag */ switch ( t % 3 ) { /* Välj drag beroende på det givna villkoret */ fall 0 : printf ( "%d -> %d \n " , axelX , axelY ); bryta ; fall 1 : printf ( "%d -> %d \n " , axelY , axelZ ); bryta ; fall 2 : printf ( "%d -> %d \n " , axisZ , axisX ); bryta ; } } else { /* Bestäm skivornas rörelse för ett jämnt drag */ switch ( t % 3 ) { fall 0 : printf ( "%d -> %d \n " , axisX , axisZ ); bryta ; fall 1 : printf ( "%d -> %d \n " , axisZ , axisY ); bryta ; fall 2 : printf ( "%d -> %d \n " , axisY , axisX ); bryta ; } } }

Det finns program för att visualisera lösningen på detta pussel.

Alternativ

Med fyra eller fler spön

Även om varianten med tre spön har en enkel rekursiv lösning, har den optimala lösningen för Tower of Hanoi med fyra spön länge varit ett olöst problem.

Uppenbarligen, för valfritt antal stavar, finns det en algoritm för att hitta optimala lösningar, det räcker att representera pusslet som en oriktad graf, matcha hörnen till skivplaceringarna och kanterna till rörelser, och använda vilken sökalgoritm som helst (till exempel, bredd-först sökning ) för att hitta den optimala lösningen. Det finns dock ingen effektiv strategi för att hitta den optimala lösningen för ett stort antal skivor: antalet drag som krävs för att lösa ett pussel med 10 spön och 1000 skivor är fortfarande okänt.

Det finns en förment optimal Frame-Stewart-algoritm som utvecklades 1941 [4] . Den relaterade Frame-Stewart-förmodan säger att Frame-Stewart-algoritmen alltid hittar den optimala lösningen. Optimiteten hos Frame-Stewart-algoritmen har experimentellt verifierats upp till 30 skivor på 4 spön [5] . 2014 bevisades det äntligen att för fyra spön är Frame-Stewart-algoritmen optimal [6] .

Andra varianter av fyrstavslösningen Tower of Hanoi diskuteras i en recensionsartikel av Paul Stockmayer [7] .

Frame-Stewart-algoritm

Frame-Stewart-algoritmen, som ger en optimal lösning för fyra och en förmodat optimal lösning för fler spön, beskrivs enligt följande:

Låt vara antalet diskar. $n$
Låt vara antalet stavar. $r$
Låt oss definiera det som det minsta antalet drag som behövs för att överföra n skivor med r stavar. $T(n,r)$

Algoritmen kan beskrivas rekursivt:

För vissa , , överför de övre till pivoten i , som varken är den initiala eller sista pivoten, utgiftsrörelser för detta. $k$ $1\leq k<n$ $k$ $T(k,r)$
Utan att använda stav i , som nu innehåller de övre skivorna, överför de återstående skivorna till den sista staven, med endast de återstående stängerna och utgiftsdragen . $k$ $nk$ $r-1$ $T(nk,r-1)$
Flytta slutligen de övre skivorna till ändstången, utgiftsrörelser för detta. $k$ $T(k,r)$

Hela processen kräver rörelser. Värdet väljs så att värdet på detta uttryck är minimalt. I fallet med 4 stavar är det optimala , där är funktionen av närmaste heltal . [åtta] $2T(k,r)+T(nk,r-1)$ $k$ $k$ $n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1$ $\left\lfloor \cdot \right\rceil$

Legends

Legenden som uppfunnits av professor Luca säger att i det stora templet i staden Benares , under katedralen som markerar mitten av världen , finns en bronsskiva på vilken 3 diamantstavar är fixerade, en aln hög och lika tjock som ett bi . För länge sedan, i början av tiderna, var munkarna i detta kloster skyldiga inför guden Brahma. Rasande reste Brahma tre höga stavar och placerade 64 skivor gjorda av rent guld på en av dem. Och så att varje mindre skiva ligger på en större.

Så snart alla 64 skivorna har överförts från staven, som Brahma satte dem på när han skapade världen, till en annan stav, kommer tornet tillsammans med templet att förvandlas till damm och världen kommer att förgås under åskande ljud.

Antalet skift beroende på antalet ringar beräknas med formeln . $2^{n}-1$

Antalet skivrörelser som munkarna måste göra är 18 446 744 073 709 551 615 . Om munkarna, som arbetar dag och natt, gjorde en rörelse av skivan varje sekund, skulle deras arbete fortsätta i nästan 585 miljarder år .

I kulturen

I Eric Frank Russells novell "Your Move" (Now Inhale, i en annan översättning - "The Game of Survival") [9] , för att fördröja avrättningen av utomjordingar, väljer huvudpersonen spelet Hanois torn med 64 skivor som sista spel. De annonserade reglerna har ändrats för två spelare - spelare måste byta skivor en i taget, vinnaren är den som gör det sista draget. Hjälten kallar det här spelet "arki-malarki" och svär att "präster från Benares-templet" på jorden spelar det här spelet.

I filmen Rise of the Planet of the Apes används Hanois torn som ett intelligenstest för testpersoner. Apan slutför fyraringspusslet i tjugo drag.

The Tower of Hanoi är ett av de traditionella pusslen i det kanadensiska företaget BioWares videospel - i synnerhet " Jade Empire ", " Star Wars: Knights of the Old Republic ", " Mass Effect " och "Dragon Age: Inquisition" . De träffas också i uppdraget Legend of Kyrandia II.

Anteckningar

↑ 1 2 Martin Gardner, matematikpussel och nöje
↑ Petkovic, Miodrag. Berömda pussel av stora matematiker (neopr.) . - AMS Bookstore, 2009. - S. 197. - ISBN 0-8218-4814-3 .
↑ Graham, Ronald. Concrete Mathematics: A Foundation for Computer Science . - Addison-Wesley , 1998. - P. 21. - ISBN 0201558025 .
↑ Lösning på avancerat problem 3819, American Mathematical Monthly , 1941.
↑ Korf, Richard E. och Ariel Felner. Nyligen framsteg i heuristisk sökning: en fallstudie av Hanois fyra-Peg Towers- problem // IJCAI : journal. - 2007. - P. 2324-2329 . Arkiverad från originalet den 24 september 2015.
↑ Bousch, T. La quatrieme tour de Hanoi (neopr.) // Bull. Belg. Matematik. soc. Simon Stevin. - 2014. - T. 21 . - S. 895-912 .
↑ Paul Stockmeyer. Variationer på Hanoi-pusslet med fyra stolpar (neopr.) // Congressus Numerantium. - 1994. - T. 102 . - S. 3-12 .
↑ University of Toronto CSC148 Slog (5 april 2014). Hämtad: 22 juli 2015. (obestämd)
↑ Russell, Eric Frank. Ditt drag // Om . - 1994. - April. - S. 34-42 . (ryska)

Se även

Tower of London test

Länkar

sekvens A007664 i OEIS
Konstantin Knop. Hanois torn . Elements (22 oktober 2012). (obestämd)
Onlinespel Towers of Hanoi

Tematiska platser	Jättebomb
Ordböcker och uppslagsverk	Britannica (online) Britannica (online)
I bibliografiska kataloger	NKC : ph1060364