Hanois tårn

Tårnet i Hanoi er et af de populære gåder i det 19. århundrede . Der gives tre stænger, hvoraf den ene er spændt med otte ringe, og ringene er forskellige i størrelse, og den mindste ligger på den større. Opgaven er at overføre pyramiden af otte ringe i det mindste antal træk til en anden stang. Du kan kun bære én ring ad gangen, og du kan ikke placere en større ring oven på en mindre.

Historien om puslespillet

Dette spil blev opfundet af den franske matematiker Edouard Lucas i 1883 [1] , det blev solgt som et sjovt legetøj. Det blev oprindeligt kaldt "Professor Claus fra Li-Sou-Stian College" [1] , men det blev hurtigt opdaget, at den mystiske professor fra det hedengangne kollegium ikke var andet end et anagram for navnet på spillets opfinder, professor Luke ( Lucas fra Saint Louis College.

Løsning

Der er flere tilgange til løsningen.

Rekursiv løsning

Vi løser rekursivt problemet med at "overføre et tårn fra n − 1 diske til 2. ben". Derefter flytter vi den største disk til 3. ben og løser rekursivt problemet "overfør tårnet af n − 1 diske til 3. ben".

Derfor konkluderer vi ved matematisk induktion , at det mindste antal træk, der kræves for at løse puslespillet, er 2 n − 1, hvor n er antallet af diske [2] [3] .

Inden for datalogi betragtes problemer baseret på legenden om Tower of Hanoi ofte som et eksempel på at bruge rekursive algoritmer og konvertere dem til ikke-rekursive.

"Trekant" løsning

Arranger stifterne i form af en trekant. Lad os starte med den mindste ring og flytte den til et hvilket som helst mærke. Fremover skal denne ring flyttes i samme retning som ved første skift. Derefter overfører vi nogle af de resterende ringe (der er kun et sådant træk), hvorefter vi igen overfører den mindste ring osv. (Det er interessant at bemærke, at ved at omnummerere "ringene" i rækkefølge, vil vi opnå en uventet effekt : lige ringe vil bevæge sig fra en toppunkttrekanter til en anden i én retning og ulige ringe i den modsatte retning.)

Cyklisk beslutning

Betegn en sådan handling med "1-2": Skift disken enten fra 1. pind til 2. eller fra 2. til 1. afhængig af hvor den er mindre. Derefter, for at løse et puslespil med et lige antal diske, skal du gentage trinene mange gange: 1-2, 1-3, 2-3. Hvis antallet af diske er ulige - 1-3, 1-2, 2-3.

Anvendelse af grå kode til at løse

Grå kode , en refleks binær kode i binær notation , hvor to tilstødende værdier kun adskiller sig i én bit. Grå kode var oprindeligt beregnet til at beskytte mod falsk betjening af elektromekaniske kontakter. I dag bruges gråkoder i vid udstrækning til at forenkle detektering og korrektion af fejl i kommunikationssystemer såvel som i dannelsen af feedbacksignaler i styresystemer. Koden blev opkaldt efter Bell Labs-forskeren Frank Gray. Han patenterede (nummer 2632058) og brugte denne kode i sit impulskommunikationssystem.

Grå koder kan anvendes på Towers of Hanoi-problemet.
Lad N være antallet af diske. Lad os starte med en Gray-kode af længden N, der kun består af nuller (det vil sige G 0 ), og vi vil bevæge os langs Gray-koderne (fra G i går til G i+1 ). Lad os tildele hver i-te bit af den aktuelle Gray-kode til den i-te disk (desuden svarer den mindst signifikante bit til den mindste disk, og den mest signifikante bit svarer til den største). Da præcis én bit ændres ved hvert trin, kan vi forstå ændringen af bit i som at flytte den i-te disk. Bemærk, at for alle diske undtagen den mindste er der nøjagtig et muligt træk ved hvert trin (undtagen start- og slutpositionen). For den mindste skive er der altid to muligheder for træk, men der er en strategi for at vælge det rigtige træk: for ulige N, rækkefølgen af bevægelser af den mindste skive f→t→r→f→t→r→... (hvor f er startstangen, t er den endelige stang, r - resterende stang), og for endda f→r→t→f→r→t→... .

Algoritme implementeringer

Et eksempel på en løsningsalgoritme i C++ :

// Towers of Hanoi #include <iostream> bruger navneområde std ; void hanoi_towers ( int mængde , int fra , int til , int buf_peg ) //mængde-antal ringe, fra-startposition for ringe(1-3), til slutposition af ringe(1-3) { //buf_peg - mellempind (1-3) hvis ( kvantitet != 0 ) { hanoi_towers ( mængde -1 , fra , buf_peg , til ); cout << fra << " -> " << til << endl ; hanoi_towers ( mængde -1 , buf_peg , til , fra ); } } int main () { setlocale ( LC_ALL , "rus" ); int start_peg , destination_peg , buffer_peg , plate_quantity ; cout << "Første kolonnenummer:" << endl ; cin >> start_peg ; cout << "Slut kolonnenummer:" << endl ; cin >> destination_peg ; cout << "Mellem kolonnenummer:" << endl ; cin >> buffer_peg ; cout << "Antal diske:" << endl ; cin >> plate_quantity ; hanoi_towers ( plade_mængde , start_peg , destination_peg , buffer_peg ); returnere 0 ; }

Et eksempel på en løsningsalgoritme i Pascal :

program hanoibns ( input , output ) ; var n : heltal ; proceduretårn ( k : heltal ; a , b , c : char ) ; _ begynde hvis k > 1 så tårne ( k - 1 , a , c , b ) ; writeln ( 'fra' , a , 'til' , b ) ; hvis k > 1 så tårn ( k - 1 , c , b , a ) ende ; startread ( n ) ; _ tårn ( n , 'A' , 'C' , 'B' ) ende .

Et eksempel på en løsningsalgoritme i Haskell :

hanoiSteps :: Int -> [( Int , Int )] hanoiSteps n = step ( max 0 n ) 1 3 2 [] hvor step 0 _ _ _ hvile = hvile trin n f t s hvile = step ( n - 1 ) f s t $ ( f , t ) : trin ( n - 1 ) s t f hvile

Et eksempel på en løsningsalgoritme i Python :

def Hanoi ( n , A , C , B ): if ( n != 0 ): Hanoi ( n - 1 , A , B , C ) print ( 'Flyt pladen fra' , A , 'til' , C ) Hanoi ( n - 1 , B , C , A )

Et eksempel på en løsningsalgoritme 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 . ud . println ( "" + fra + " -> " + til ); hanoiTowers ( quantity - 1 , buf_peg , to , from ); } } 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 ); } }

Et eksempel på en iterativ løsningsalgoritme i C

#include <stdio.h> #include <math.h> void carryingOver ( int , int , int ); vigtigste () { int tal , tælDisk , tæller = 1 , tæller ; printf ( "Indtast antal diske: " ); /* Hanois tårn */ scanf ( "%d" , & nummer ); while ( tæller <= pow ( 2 , tal ) - 1 ) { /* Start gentagelsesløkken */ if ( tæller % 2 != 0 ) { /* På en ulige tur vil vi kun røre den mindste disk */ printf ( "%3d %d" , tæller , 1 ); carryingOver ( tal , tæller , 1 ); /* Ved hjælp af denne funktion bestemmer vi bevægelsen for denne disk */ } else { /* Bestem disken, der skal flyttes i et lige træk */ tælle = tæller ; countDisk = 0 ; while ( tæl % 2 == 0 ) { /* Disk til at flytte */ countDisk ++ ; /* vil være tallet for at dividere træktallet med 2 uden en rest */ tælle = tælle / 2 ; } printf ( "%3d %d" , tæller , countDisk + 1 ); carryingOver ( tal , tæller , tælDisk + 1 ); } tæller ++ ; } returnere 0 ; } /* Funktion til at detektere bevægelse af diske */ void carryingOver ( int n , int i , int k ) { int t , akseX , akseY , akseZ ; if ( n % 2 == 0 ) { /* Bestem rækkefølgen af akserne afhængigt af pariteten */ akseX = 1 ; /* og ikke-paritet antal diske */ akse Y = 2 ; akse Z = 3 ; } andet { akseX = 1 ; akse Y = 3 ; akse Z = 2 ; } /* Træknummeret kan repræsenteres på en unik måde */ /* som et produkt af et ulige tal gange en potens af to */ /* k vil være nummeret på den disk, vi flytter */ t = (( i / pow ( 2 , k - 1 ) ) -1 ) / 2 ; if ( k % 2 != 0 ) { /* Bestem diskbevægelse for ulige træk */ switch ( t % 3 ) { /* Vælg træk afhængigt af den givne betingelse */ case 0 : printf ( "%d -> %d \n " , akseX , akseY ); bryde ; tilfælde 1 : printf ( "%d -> %d \n " , akseY , akseZ ); bryde ; tilfælde 2 : printf ( "%d -> %d \n " , akseZ , akseX ); bryde ; } } else { /* Bestem bevægelsen af skiverne for et jævnt træk */ switch ( t % 3 ) { tilfælde 0 : printf ( "%d -> %d \n " , akseX , akseZ ); bryde ; tilfælde 1 : printf ( "%d -> %d \n " , akseZ , akseY ); bryde ; tilfælde 2 : printf ( "%d -> %d \n " , akseY , akseX ); bryde ; } } }

Der er programmer til at visualisere løsningen på dette puslespil.

Indstillinger

Med fire eller flere stænger

Selvom varianten med tre stænger har en simpel rekursiv løsning, har den optimale løsning for Tower of Hanoi med fire stænger længe været et uløst problem.

For et hvilket som helst antal stænger er der naturligvis en algoritme til at finde optimale løsninger, det er nok at repræsentere puslespillet som en ikke-rettet graf, der matcher hjørnerne til diskplaceringer og kanter til bevægelser og bruge enhver søgealgoritme (f.eks. bredde-første søgning ) for at finde den optimale løsning. Der er dog ingen effektiv strategi for at finde den optimale løsning for et stort antal diske: antallet af træk, der skal til for at løse et puslespil med 10 stænger og 1000 diske, er stadig ukendt.

Der er en angiveligt optimal Frame-Stewart-algoritme udviklet i 1941 [4] . Den relaterede Frame-Stewart-formodning siger, at Frame-Stewart-algoritmen altid finder den optimale løsning. Optimiteten af Frame-Stewart-algoritmen er blevet eksperimentelt verificeret op til 30 diske på 4 stænger [5] . I 2014 blev det endelig bevist, at for fire stænger er Frame-Stewart-algoritmen optimal [6] .

Andre varianter af fire-bar Tower of Hanoi-løsningen er diskuteret i en oversigtsartikel af Paul Stockmayer [7] .

Frame-Stewart algoritme

Frame-Stewart-algoritmen, som giver en optimal løsning til fire og en formodet optimal løsning til flere stænger, beskrives som følger:

Lad være antallet af diske. $n$
Lad være antallet af stænger. $r$
Lad os definere det som det mindste antal træk, der er nødvendigt for at overføre n diske ved hjælp af r stænger. $T(n,r)$

Algoritmen kan beskrives rekursivt:

For nogle , , skal du overføre de øverste til pivot i , som hverken er det indledende eller sidste pivot, forbrugsbevægelser for dette. $k$ $1\leq k<n$ $k$ $T(k,r)$
Uden at bruge stang i , som nu indeholder de øverste skiver, overfør de resterende skiver til den endelige stang, kun ved at bruge de resterende stænger og forbrugsbevægelser . $k$ $nk$ $r-1$ $T(nk,r-1)$
Til sidst skal du flytte de øverste skiver til endestangen, forbrugsbevægelser for dette. $k$ $T(k,r)$

Hele processen kræver bevægelser. Værdien er valgt, så værdien af dette udtryk er minimal. I tilfælde af 4 stænger er det optimale , hvor er funktionen af det nærmeste heltal . [otte] $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 opfundet af professor Luca siger, at i det store tempel i byen Benares , under katedralen, der markerer midten af verden , er der en bronzeskive, hvorpå 3 diamantstænger er fastgjort, en alen høj og så tyk som en bi . For længe siden, i begyndelsen af tid, var munkene i dette kloster skyldige over for guden Brahma. Rasende rejste Brahma tre høje stænger og placerede 64 skiver lavet af rent guld på en af dem. Og så hver mindre disk ligger på en større.

Så snart alle 64 skiver er overført fra stangen, som Brahma satte dem på, da han skabte verden, til en anden stang, vil tårnet sammen med templet blive til støv, og verden vil gå til grunde under tordnende bølger.

Antallet af skift afhængigt af antallet af ringe beregnes af formlen . $2^{n}-1$

Antallet af skivebevægelser, munkene skal foretage, er 18.446.744.073.709.551.615 . Hvis munkene, der arbejdede dag og nat, lavede én bevægelse af disken hvert sekund, ville deres arbejde fortsætte i næsten 585 milliarder år .

I kultur

I Eric Frank Russells novelle "Your Move" (Now Inhale, i en anden oversættelse - "The Game of Survival") [9] , for at forsinke henrettelsen af aliens, vælger hovedpersonen spillet i Tower of Hanoi med 64 diske som sidste spil. De annoncerede regler er blevet ændret for to spillere - spillere skal skifte diske én ad gangen, vinderen er den, der foretager det sidste træk. Helten kalder dette spil "arki-malarki" og sværger, at "præster fra Benares-templet" på jorden spiller dette spil.

I filmen Rise of the Planet of the Apes bruges Hanois tårn som en intelligenstest for testpersoner. Aben fuldfører puslespillet med fire ringer i tyve træk.

The Tower of Hanoi er et af de traditionelle gåder i det canadiske firma BioWares videospil - især " Jade Empire ", " Star Wars: Knights of the Old Republic ", " Mass Effect " og "Dragon Age: Inquisition" . De mødes også i Legend of Kyrandia II-missionen.

Noter

↑ 1 2 Martin Gardner, Matematikpuslespil og sjov
↑ Petkovic, Miodrag. Berømte gåder af store matematikere (neopr.) . - AMS Boghandel, 2009. - S. 197. - ISBN 0-8218-4814-3 .
↑ Graham, Ronald. Konkret matematik: Et fundament for datalogi . - Addison-Wesley , 1998. - S. 21. - ISBN 0201558025 .
↑ Løsning på avanceret problem 3819, American Mathematical Monthly , 1941.
↑ Korf, Richard E. og Ariel Felner. Seneste fremskridt i heuristisk søgning: et casestudie af Hanoi- problemet med fire pinde tårne // IJCAI : journal. - 2007. - S. 2324-2329 . Arkiveret fra originalen 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å Fire-Post Tower of Hanoi Puslespil (neopr.) // Congressus Numerantium. - 1994. - T. 102 . - S. 3-12 .
↑ University of Toronto CSC148 Slog (5. april 2014). Hentet: 22. juli 2015. (ubestemt)
↑ Russell, Eric Frank. Dit træk // Hvis . - 1994. - April. - S. 34-42 . (Russisk)

Se også

Tower of London test

Links

sekvens A007664 i OEIS
Konstantin Knop. Hanois tårn . Elementer (22. oktober 2012). (ubestemt)
Online spil Towers of Hanoi

Tematiske steder	Kæmpe bombe
Ordbøger og encyklopædier	Britannica (online) Britannica (online)
I bibliografiske kataloger	NKC : ph1060364