Turnul din Hanoi

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Turnul din Hanoi cu opt discuri

Turnul din Hanoi (cunoscut și sub numele de Turnul lui Lucas după inventatorul său) este un puzzle matematic format din trei mize și un număr de discuri de dimensiuni reduse, care pot fi inserate în oricare dintre mize.

Jocul începe cu toate discurile stivuite pe o miză în ordine descrescătoare pentru a forma un con . Obiectivul jocului este de a aduce toate discurile la un pol diferit, putând muta doar un disc odată și fiind capabil să pună un disc numai pe alt disc mai mare, niciodată pe unul mai mic.

Origini

Jocul a fost inventat în 1883 [1] de matematicianul francez Édouard Lucas care a popularizat jocul sub pseudonimul lui N. Claus de Siam, mandarin al colegiului Li-Sou-Stian . [2] Legenda conform căreia într-un templu hindus unii călugări se angajează constant în mișcarea a 64 de discuri de aur pe trei coloane de diamante conform regulilor Turnului din Hanoi (numit uneori Turnul lui Brahmā ), a fost inventată de compania care a fost primul care a lansat puzzle-ul. Legenda spune că atunci când călugării vor termina treaba, lumea se va sfârși. Există, de asemenea, versiuni de jocuri video ale puzzle-ului. [3] [4] [5] [6]

Soluţie

Soluția Turn of Hanoi cu patru discuri

Proprietatea matematică de bază este că numărul minim de mișcări necesare pentru a finaliza jocul este , unde n este numărul de discuri. De exemplu, având 3 discuri, numărul minim de mișcări este 7. În consecință, conform legendei, călugării din Hanoi ar trebui să facă cel puțin 18.446.744.073.709.551.615 mișcări înainte ca lumea să se sfârșească, fiind . Cu alte cuvinte, chiar presupunând că călugării fac o mișcare pe secundă, lumea se va termina în 5,845,580,504 de secole . [7]

Soluția generală este dată de următorul algoritm .

Algoritm recursiv

Soluția de bază a jocului Turnul din Hanoi este formulată recursiv .[8] [9]

Lăsați postările să fie etichetate A, B și C, iar discurile să fie numerotate de la 1 (cel mai mic) la n (cel mai mare). Algoritmul este exprimat după cum urmează:

  1. Mutați primele n -1 discuri de la A la B. (Acest lucru lasă discul n singur în postarea A)
  2. Mutați discul n de la A la C
  3. Mutați n -1 discuri de la B la C

Pentru a muta n discuri, este necesar să efectuați o operație elementară (deplasarea unui singur disc) și una complexă, adică deplasarea a n -1 discuri. Totuși, această operațiune este rezolvată în același mod, necesitând mișcarea discurilor n -2 ca operație complexă. Iterarea acestui raționament reduce procesul complex la unul elementar, adică deplasarea lui n - ( n -1) = 1 disc.

Acesta este un algoritm recursiv ,[8] de complexitate exponențială.

Este interesant de observat că puzzle-ul este rezolvabil pentru orice „n”, cu o dovadă prin recurență : Să presupunem că avem un turn în A format din N discuri și să presupunem că N este numărul maxim de discuri permise pentru rezolvarea jocului. La sfârșitul mișcării turnului de la A la B, adăugăm un alt disc la A, cu dimensiunea egală cu N + 1 și presupunem că acest disc a fost staționat tot timpul sub celelalte. În acest moment, mutăm pur și simplu discul de la A la C și cu siguranță vom putea muta turnul de la B la C, urmând aceiași pași care au fost necesari pentru a-l muta de la A la B. După ce am demonstrat că un turn de N discuri se pot deplasa de la o coloană la alta, s-a demonstrat că chiar și un turn de discuri N + 1 poate fi mutat.

Problemă generalizată

Problema poate fi generalizată, presupunând, de exemplu, că numărul de posturi nu este stabilit la trei, dar poate fi extins generic.

Presupunând o astfel de generalizare, exemple de strategii optime pentru finalizarea jocului, sub ipoteze specifice, sunt cunoscute încă din 1941. Au fost găsite separat de diferiți autori.

Demonstrația că aceste strategii sunt cele optime în fiecare condiție este în schimb un rezultat al anului 2017. Principala dificultate a demonstrației a fost implicată de non-unicitate, în cazul cu mai mult de trei mize, a strategiei optime de urmat în timpul soluţie. În cazul general, de fapt, după fiecare mișcare, este posibil să se schimbe strategia rămânând în număr minim de cele necesare pentru a rezolva puzzle-ul, creând un arbore complex de căi de soluție care iau același număr minim de pași pentru a rezolva problema. . Această non-unicitate nu trebuie înțeleasă în sensul evident al permutărilor, ci în modul cel mai general posibil. [10]

Notă

  1. ^ (EN) Rezumat Lucas , pe www-history.mcs.st-and.ac.uk.
  2. ^ (EN) Turnul din Hanoi de pe cs.wm.edu.
  3. ^ (EN) Hanoi: Sega Dreamcast Game Console (animată) pe kernelthread.com.
  4. ^ (EN) Hanoi: Nintendo Gameboy Advance Handheld (Animat) , pe kernelthread.com.
  5. ^ Francesco Sblendorio, Towers of Hanoi pentru MS-DOS și Windows , pe sblendorio.eu , 1996.
  6. ^ (EN) Francesco Sblendorio, Towers of Hanoi - CP / M și C128 versiune generică specifică pe github.com, 2015.
  7. ^ Proiectul Polymath - Turnul din Hanoi , pe areasweb.polito.it .
  8. ^ A b (EN) Turnul din Hanoi , pe cut-the-knot.org.
  9. ^ www.matematici.it ( PDF ), pe mathematic.it .
  10. ^ (EN) Roberto Demontis, Care este cel mai mic număr de mișcări necesare pentru a rezolva problema K-peg Towers of Hanoi? ( PDF ), pe arxiv.org , 23.09.2013.

Bibliografie

Elemente conexe

Alte proiecte

linkuri externe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică
Adus de la „ https://it.wikipedia.org/w/index.php?title=Torre_di_Hanoi&oldid=113095309 ”