Turnul din hanoi

Turnul din Hanoi este unul dintre puzzle-urile populare ale secolului al XIX-lea . Se dau trei tije, dintre care unul este înșirat cu opt inele, iar inelele diferă ca mărime, iar cel mai mic se află pe cel mai mare. Sarcina este de a transfera piramida de opt inele în cel mai mic număr de mișcări către o altă tijă. Puteți purta doar un inel la un moment dat și nu puteți pune un inel mai mare peste unul mai mic.

Istoria puzzle-ului

Acest joc a fost inventat de matematicianul francez Edouard Lucas în 1883 [1] , a fost vândut ca o jucărie distractivă. Inițial a fost numit „Profesor Claus of Li-Sou-Stian College” [1] , dar s-a descoperit curând că misteriosul profesor de la defunctul colegiu nu era altceva decât o anagramă pentru numele inventatorului jocului, profesorul Luke ( Lucas al Colegiului Saint Louis.

Soluție

Există mai multe abordări ale soluției.

Soluție recursiva

Rezolvăm recursiv problema „transferării unui turn de pe n − 1 discuri la al 2-lea pin”. Apoi mutam cel mai mare disc la al 3-lea pin și rezolvăm recursiv problema „transferă turnul de n - 1 discuri la al 3-lea pin”.

Prin urmare, prin inducție matematică concluzionăm că numărul minim de mișcări necesare pentru a rezolva puzzle-ul este 2 n − 1, unde n este numărul de discuri [2] [3] .

În informatică, problemele bazate pe legenda Turnului din Hanoi sunt adesea considerate ca un exemplu de utilizare a algoritmilor recursivi și de conversie a acestora în cei nerecursivi.

Soluție „triunghi”

Aranjați știfturile sub formă de triunghi. Să începem cu cel mai mic inel și să-l mutăm la orice semn. În viitor, acest inel trebuie mutat în aceeași direcție ca în timpul primei schimbări. Apoi transferăm unele dintre inelele rămase (există o singură astfel de mișcare), după care transferăm din nou cel mai mic inel etc. (Este interesant de remarcat că renumerotând „inelele” în ordine, vom obține un efect neașteptat : inelele pare se vor muta de la un triunghi de vârf la altul într-o direcție, iar cele impare în direcția opusă.)

Decizie ciclică

Notați cu „1-2” o astfel de acțiune: mutați discul fie de la primul pin la al doilea, fie de la al doilea la primul, în funcție de locul în care este mai mic. Apoi, pentru a rezolva un puzzle cu un număr par de discuri, trebuie să repetați pașii de mai multe ori: 1-2, 1-3, 2-3. Dacă numărul de discuri este impar - 1-3, 1-2, 2-3.

Aplicarea codului Gray pentru a rezolva

Cod gri , un cod binar reflex în notație binară , în care două valori adiacente diferă doar într-un singur bit. Codul gri a fost inițial destinat să protejeze împotriva funcționării false a comutatoarelor electromecanice. Astăzi, codurile Gray sunt utilizate pe scară largă pentru a simplifica detectarea și corectarea erorilor în sistemele de comunicație, precum și în formarea semnalelor de feedback în sistemele de control. Codul a fost numit după cercetătorul de la Bell Labs, Frank Gray. El a brevetat (numărul 2632058) și a folosit acest cod în sistemul său de comunicație de impuls.

Codurile gri pot fi aplicate problemei Turnurile din Hanoi.
Fie N numărul de discuri. Să începem cu un cod Gray de lungime N, format doar din zerouri (adică G 0 ), și ne vom deplasa de-a lungul codurilor Gray (de la G i la G i+1 ). Să atribuim fiecare i-lea bit al codului Gray curent discului i-a (mai mult, bitul cel mai puțin semnificativ corespunde celui mai mic disc, iar cel mai semnificativ bit corespunde celui mai mare). Deoarece exact un bit se schimbă la fiecare pas, putem înțelege schimbarea bitului i ca deplasarea discului i. Rețineți că pentru toate discurile, cu excepția celui mai mic, există exact o mișcare posibilă la fiecare pas (cu excepția pozițiilor inițiale și finale). Pentru cel mai mic disc, există întotdeauna două opțiuni pentru mutare, dar există o strategie pentru alegerea mișcării corecte: pentru N impar, succesiunea de mișcări ale celui mai mic disc f→t→r→f→t→r→... (unde f este tija de pornire, t este tija finală, r - tija rămasă), iar pentru f→r→t→f→r→t→… .

Implementări de algoritm

Un exemplu de algoritm de soluție în C++ :

// Turnurile din Hanoi #include <iostream> folosind namespace std ; void hanoi_towers ( int quantity , int from , int to , int buf_peg ) //cantitate-număr de inele, de la poziția de început a inelelor (1-3), până la poziția de sfârșit a inelelor (1-3) { //buf_peg - cuier intermediar (1-3) daca ( cantitate != 0 ) { hanoi_towers ( cantitate -1 , de la , buf_peg , la ); cout << de la << " -> " << până la << endl ; hanoi_towers ( cantitate -1 , buf_peg , la , de la ); } } int main () { setlocale ( LC_ALL , "rus" ); int start_peg , destination_peg , buffer_peg , plate_quantity ; cout << "Numărul primei coloane:" << endl ; cin >> start_peg ; cout << "Numărul coloanei de sfârșit:" << endl ; cin >> destination_peg ; cout << "Numărul coloanei intermediare:" << endl ; cin >> buffer_peg ; cout << "Număr de discuri:" << endl ; cin >> placa_cantitate ; hanoi_towers ( plate_quantity , start_peg , destination_peg , buffer_peg ); returnează 0 ; }

Un exemplu de algoritm de soluție în Pascal :

program hanoibns ( intrare , iesire ) ; var n : întreg ; turn de procedură ( k : întreg ; a , b , c : char ) ; începe dacă k > 1 atunci turn ( k - 1 , a , c , b ) ; writeln ( 'de la ' , a , ' la ' , b ) ; dacă k > 1 atunci turn ( k - 1 , c , b , a ) capăt ; beginread ( n ) ; _ turn ( n , 'A' , 'C' , 'B' ) capăt .

Un exemplu de algoritm de soluție în Haskell :

hanoiSteps :: Int -> [( Int , Int )] hanoiSteps n = pas ( max 0 n ) 1 3 2 [] unde pasul 0 _ _ _ rest = pas de odihnă n f t s rest = pas ( n - 1 ) f s t $ ( f , t ) : pas ( n - 1 ) s t f rest

Un exemplu de algoritm de soluție în Python :

def Hanoi ( n , A , C , B ): if ( n != 0 ): Hanoi ( n - 1 , A , B , C ) print ( 'Mutați placa de la' , A , 'la' , C ) Hanoi ( n - 1 , B , C , A )

Un exemplu de algoritm de soluție în Java :

public class Hanoi { public static void hanoiTowers ( int cantitate , int de la , int la , int buf_peg ) { if ( cantitate != 0 ) { hanoiTowers ( cantitate - 1 , de la , buf_peg , la ); Sistem . afară . println ( "" + de la + " -> " + la ); hanoiTowers ( cantitate - 1 , buf_peg , la , de la ); } } 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 ); } }

Un exemplu de algoritm de soluție iterativă în C

#include <stdio.h> #include <math.h> void carryingOver ( int , int , int ); principal () { int număr , countDisk , counter = 1 , count ; printf ( "Introduceți numărul de discuri: " ); /* Turnul din Hanoi */ scanf ( "%d" , & număr ); while ( counter <= pow ( 2 , number ) - 1 ) { /* Începe bucla de repetare */ if ( counter % 2 != 0 ) { /* La o viraj impar, vom atinge doar cel mai mic disc */ printf ( "%3d %d " , contor , 1 ); reportingOver ( număr , numărător , 1 ); /* Folosind această funcție, determinăm mișcarea acestui disc */ } else { /* Determinați discul care urmează să fie mutat într-o mișcare uniformă */ count = contor ; countDisk = 0 ; while ( count % 2 == 0 ) { /* Disc de mutat */ countDisk ++ ; /* va fi numărul de împărțire a numărului de mutare la 2 fără rest */ numără = numără / 2 ; } printf ( "%3d %d " , counter , countDisk + 1 ); carryingOver ( număr , numărător , numărareDisc + 1 ); } contor ++ ; } returnează 0 ; } /* Funcție pentru detectarea mișcării discurilor */ void carryingOver ( int n , int i , int k ) { int t , axa X , axa Y , axa Z ; if ( n % 2 == 0 ) { /* Determinați ordinea axelor în funcție de paritate */ axaX = 1 ; /* și numărul de discuri fără paritate */ axa Y = 2 ; axa Z = 3 ; } else { axaX = 1 ; axa Y = 3 ; axa Z = 2 ; } /* Numărul de mutare poate fi reprezentat într-un mod unic */ /* ca produs al unui număr impar înmulțit cu o putere de două */ /* k va fi numărul discului pe care îl mutăm */ t = (( i / pow ( 2 , k - 1 )) - 1 ) / 2 ; if ( k % 2 != 0 ) { /* Determinați mișcarea discului pentru mișcare impară */ comutator ( t % 3 ) { /* Selectați mutarea în funcție de condiția dată */ cazul 0 : printf ( "%d -> %d \n " , axa X , axa Y ); rupe ; cazul 1 : printf ( "%d -> %d \n " , axa Y , axa Z ); rupe ; cazul 2 : printf ( "%d -> %d \n " , axaZ , axa X ); rupe ; } } else { /* Determinați mișcarea discurilor pentru o mișcare uniformă */ comutator ( t % 3 ) { cazul 0 : printf ( "%d -> %d \n " , axa X , axa Z ); rupe ; cazul 1 : printf ( "%d -> %d \n " , axaZ , axa Y ); rupe ; cazul 2 : printf ( "%d -> %d \n " , axa Y , axa X ); rupe ; } } }

Există programe pentru a vizualiza soluția acestui puzzle.

Opțiuni

Cu patru sau mai multe tije

Deși varianta cu trei tije are o soluție recursivă simplă, soluția optimă pentru Turnul din Hanoi cu patru tije a fost de multă vreme o problemă nerezolvată.

Evident, pentru orice număr de tije, există un algoritm pentru găsirea soluțiilor optime, este suficient să reprezentați puzzle-ul ca un grafic nedirecționat, potrivirea vârfurilor cu plasările discului și marginile la mișcări și să utilizați orice algoritm de căutare (de exemplu, breadth-first search ) pentru a găsi soluția optimă. Cu toate acestea, nu există o strategie eficientă pentru găsirea soluției optime pentru un număr mare de discuri: numărul de mișcări necesare pentru a rezolva un puzzle cu 10 tije și 1000 de discuri rămâne necunoscut.

Există un algoritm Frame-Stewart presupus optim dezvoltat în 1941 [4] . Conjectura Frame-Stewart aferentă afirmă că algoritmul Frame-Stewart găsește întotdeauna soluția optimă. Optimitatea algoritmului Frame-Stewart a fost verificată experimental până la 30 de discuri pe 4 tije [5] . În 2014, s-a dovedit în sfârșit că pentru patru lansete algoritmul Frame-Stewart este optim [6] .

Alte variante ale soluției Tower of Hanoi cu patru bare sunt discutate într-un articol de recenzie al lui Paul Stockmayer [7] .

Algoritmul Frame-Stewart

Algoritmul Frame-Stewart, care oferă o soluție optimă pentru patru și o soluție presupus optimă pentru mai multe lansete, este descris după cum urmează:

Fie numărul de discuri. $n$
Fie numărul de tije. $r$
Să-l definim ca fiind cel mai mic număr de mișcări necesare pentru a transfera n discuri folosind r tije. $T(n,r)$

Algoritmul poate fi descris recursiv:

Pentru unii , , transferați-le pe cele superioare pe pivotul i , care nu este nici pivotul inițial, nici final, cheltuind mișcări pentru asta. $k$ $1\leq k<n$ $k$ $T(k,r)$
Fără a folosi tija i , care conține acum discurile superioare , transferați discurile rămase în tija finală, folosind doar tijele rămase și cheltuind mișcările. $k$ $nk$ $r-1$ $T(nk,r-1)$
În cele din urmă, mutați discurile superioare la tija de capăt, cheltuind mișcări pentru aceasta. $k$ $T(k,r)$

Întregul proces necesită mișcări. Valoarea este aleasă astfel încât valoarea acestei expresii să fie minimă. În cazul a 4 tije, optimul este , unde este funcția celui mai apropiat întreg . [opt] $2T(k,r)+T(nk,r-1)$ $k$ $k$ $n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1$ $\left\lfloor \cdot \right\rceil$

Legende

Legenda inventată de profesorul Luca spune că în Marele Templu al orașului Benares , sub catedrala care marchează mijlocul lumii , se află un disc de bronz pe care sunt fixate 3 tije de diamant, înalte de un cot și groase ca o albină. . Cu mult timp în urmă, chiar la începutul timpurilor, călugării acestei mănăstiri erau vinovați în fața zeului Brahma. Înfuriat, Brahma a ridicat trei vergele înalte și a pus pe una dintre ele 64 de discuri din aur pur. Și astfel încât fiecare disc mai mic să se afle pe unul mai mare.

De îndată ce toate cele 64 de discuri sunt transferate de la tija, pe care Brahma le-a pus când a creat lumea, pe o altă tijă, turnul împreună cu templul se vor transforma în praf și lumea va pieri sub zgomote tunătoare.

Numărul de schimburi în funcție de numărul de inele este calculat prin formula . $2^{n}-1$

Numărul de mișcări ale discurilor pe care călugării trebuie să le facă este de 18.446.744.073.709.551.615 . Dacă călugării, lucrând zi și noapte, ar face o mișcare a discului în fiecare secundă, munca lor ar continua timp de aproape 585 de miliarde de ani .

În cultură

În nuvela lui Eric Frank Russell „Your Move” (Now Inhale, într-o altă traducere – „The Game of Survival”) [9] , pentru a întârzia execuția de către extratereștri, protagonistul alege jocul Turnului din Hanoi. cu 64 de discuri ca ultimul joc. Regulile anunțate au fost modificate pentru doi jucători - jucătorii trebuie să schimbe discurile pe rând, câștigătorul este cel care face ultima mișcare. Eroul numește acest joc „arki-malarki” și jură că „preoții templului Benares” de pe Pământ joacă acest joc.

În filmul Rise of the Planet of the Apes , Turnul din Hanoi este folosit ca test de inteligență pentru subiecții de testare. Maimuța completează puzzle-ul cu patru inele în douăzeci de mișcări.

Turnul din Hanoi este unul dintre puzzle-urile tradiționale din jocurile video ale companiei canadiane BioWare - în special, „ Jade Empire ”, „ Star Wars: Knights of the Old Republic ”, „ Mass Effect ” și „Dragon Age: Inquisition” . Ei se întâlnesc și în căutarea Legenda lui Kyrandia II.

Note

↑ 1 2 Martin Gardner, Math Puzzles and Fun
↑ Petkovic, Miodrag. Puzzle-uri celebre ale marilor matematicieni (neopr.) . - Librăria AMS, 2009. - P. 197. - ISBN 0-8218-4814-3 .
↑ Graham, Ronald. Matematică concretă: o fundație pentru informatică . - Addison-Wesley , 1998. - P. 21. - ISBN 0201558025 .
↑ Rezolvarea problemei avansate 3819, American Mathematical Monthly , 1941.
↑ Korf, Richard E. și Ariel Felner. Progrese recente în căutarea euristică: un studiu de caz al problemei turnurilor cu patru chei din Hanoi // IJCAI : jurnal. - 2007. - P. 2324-2329 . Arhivat din original pe 24 septembrie 2015.
↑ Bousch, T. La quatrieme tour de Hanoi (neopr.) // Bull. Belg. Matematică. soc. Simon Stevin. - 2014. - T. 21 . - S. 895-912 .
↑ Paul Stockmeyer. Variații ale puzzle-ului Turnului cu patru stâlpi din Hanoi (neopr.) // Congressus Numerantium. - 1994. - T. 102 . - S. 3-12 .
↑ Universitatea din Toronto CSC148 Slog (5 aprilie 2014). Preluat: 22 iulie 2015. (nedefinit)
↑ Russell, Eric Frank. Mișcarea ta // Dacă . - 1994. - Aprilie. - S. 34-42 . (Rusă)

Vezi și

Testul Turnului Londrei

Link -uri

secvența A007664 în OEIS
Konstantin Knop. Turnul din Hanoi . Elemente (22 octombrie 2012). (nedefinit)
Joc online Towers of Hanoi

Site-uri tematice	Bombă uriașă
Dicționare și enciclopedii	Britannica (online) Britannica (online)
În cataloagele bibliografice	NKC : ph1060364