Viquipèdia

Torres de Hanoi: diferència entre les revisions

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
→‎Resolució: reformulació amb llenguatge més planer
Línia 17:
''Al gran temple de [[Benarés]], per sota de la cúpula que marca el centre del món, hi ha tres agulles. En una d'aquestes agulles, un déu va posar als inicis dels segles, seixanta-quatre discos d'or pur, el més gran sota de tots i els altres, cada vegada més petits, sobre seu. Nit i dia, els monjos treballen movent els discos d'or sense desviar-se de les regles immutables imposades pels déus.  Quan hagin aconseguit traslladar tota la torre a la tercera agulla, arribarà la fi del món.''<ref>{{Ref-llibre|cognom=Lucas|nom=Édouard|títol=La Tour d'Hanoi|url=http://edouardlucas.free.fr/oeuvres/Jeux_3_La%20tour%20de%20hanoi.pdf|edició=|llengua=|data=1889|editorial=Chambon & Baye|lloc=Paris|pàgines=19|isbn=}}</ref>
 
==Resolució, nombre moviments necessaris==
[[Fitxer:Tower of Hanoi 4.gif|thumb|Resolució del joc per a 4 discs.]]
[[Fitxer:Tower of Hanoi.gif|miniatura|Resolució del joc per a 3 discs]]
La solució de les torres de Hanoi és senzilla de calcular i el nombre de creix [[exponencialment]] a mesura que augmenta el nombre de discos. La típica manera de solucionar-lo és mitjançant [[Funció recursiva|funcions recursives]].
La solució de les torres de Hanoi és senzilla en el cas de 3 o 4 discs, com mostren les imatges calen 7 i 15 moviments respectivament.
 
El càlcul dels moviments mínims necessaris a mesura que augmenta el nombre de discos, es fa típicament de forma [[Definició inductiva|inductiva]] (també anomenada [[Recursivitat|recursiva]]). Això vol dir que partim del coneixement dels moviments mínims que cal fer per moure <math>k</math> discos (posem que són <math>m_k</math>moviments) per pensar els moviments per moure una torre amb <math>k+1</math> discs.
Sigui <math>m_k</math> el nombre mínim de moviments necessaris per moure <math>k</math> discos d'una torre a l'altra. Així, podem veure que:
 
<math>m_k = 2*m_{k-1} + 1</math>▼
jaLa queforma lade soluciófer-ho correspon aés moure els <math>k-1</math>discs discossuperiors de la torre esquerraprimera a la torresegona centralvareta (<math>m_k</math>moviments), moureel ladisc peçade mésbase grande la primera a la torretercera devareta la(1 dreta,moviment) i tornar a mourecontinuació els <math>k-1</math> discos,discs arade la segona a la torretercera devareta la dreta(<math>m_k</math>moviments un altre cop). Tenint aquestaAixí recurrència,que iels tenintmoviments enper comptemoure eluna castorre basede <math>m_1=k+1</math>, trobemdiscs quesón:
 
▲ <math>m_km_{k+1} = 2*m_{k-1} + 1</math>
 
Ara, tenint en compte el cas base <math>m_1=1</math>, trobem que:
<math>m_k=2^k-1</math>
El nombre de moviments creix doncs [[exponencialment]] de forma sorprenent per un joc tan senzill.
És a dir, per <math>k=4</math> discs fan falta <math>m_4=2^4-1=15</math> moviments.
 
En la versió de la llegenda, amb 64 discs, caldrien <math>2^{64} - 1 = 18446744073709551615</math> moviments; suposant que els monjos fossin capaços d'efectuar un moviment per segon (i per tant, <math>31536000</math> moviments per any), trigarien més de mig bilió d'anys en fer tots els moviments.
Obtingut de «https://ca.wikipedia.org/wiki/Torres_de_Hanoi»