Viquipèdia

Torres de Hanoi: diferència entre les revisions

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
m Manteniment de plantilles de referències
Correcció de format
Línia 8:
# Els discs petits han d'estar sempre situats sobre els grans.
 
Amb 3 discos, el trencaclosques es pot resoldre en 7 moviments. El nombre mínim de moviments necessaris per resoldre'l amb '''n''' discs és de '''2 <supmath>2^n</sup> - 1'''</math>.
 
Aquest joc és usat típicament en matemàtiques i informàtica com a exemple de [[recursivitat]].
 
== Invenció i llegenda ==
AquestaAquest joc va ser inventat pel matemàtic francès [[Édouard Lucas]] el 1883. El mateix Lucas va escriure la següent llegenda per ambientar el joc:
 
''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=París|pàgines=19}}</ref>
 
== Resolució, nombre moviments necessaris ==
[[Fitxer:Tower of Hanoi.gif|miniatura|Resolució del joc per a 3 discs]]
[[Fitxer:Tower of Hanoi 4.gif|miniatura|Resolució del joc per a 4 discs.]]
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.
Línia 26:
La forma de fer-ho és moure els <math>k</math> discs superiors de la primera a la segona vareta (<math>m_k</math> moviments), el disc de base de la primera a la tercera vareta (1 moviment) i a continuació els <math>k</math> discs de la segona a la tercera vareta (<math>m_k</math> moviments un altre cop). Així que els moviments per moure una torre de <math>k+1</math> discs són:
 
: <math>m_{k+1} = 2*m_{k} + 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.
 
Línia 37:
Si tenim n discos, un procediment recursiu en [[C++]] com el següent imprimeix a la pantalla la seqüència de moviments a seguir.
 
<syntaxhighlight lang="c++">
#include <iostream>
 
using namespace std;
 
void hanoi(int n, char origen, char desti, char aux) {
if(n != 0) {
hanoi(n-1,origen,aux,desti);
cout << origen << " => " << desti << endl;
hanoi(n-1,aux, desti, origen);
}
}
 
int main() {
int n;
cout << "Introdueix el nombre de discs: ";
cin >> n;
cout << "Els moviments que s'han de fer:\n";
hanoi(n,'A','C','B'); // transfereix n discos de A a C utilitzant B
}</syntaxhighlight>
}
 
== Vegeu també ==
Obtingut de «https://ca.wikipedia.org/wiki/Torres_de_Hanoi»