Torres de Hanoi

De Viquipèdia
Dreceres ràpides: navegació, cerca
Joc de fusta de les torres de Hanoi.

Les torres de Hanoi és un joc matemàtic, usat típicament com a exemple de recursivitat. Consisteix en tres varetes verticals i un nombre indeterminat de discs de mides diferents que determinen la complexitat de la solució. A l'inici estan col·locats de més gran a més petit en la primera vareta. El joc consisteix en passar tots els discs a la tercera vareta tenint en compte que només es pot canviar de vareta un disc cada vegada i que mai no podem tenir un disc col·locat sobre un que sigui més petit.

Llegenda de les torres de Hanoi[modifica | modifica el codi]

En un temple de Benarés hi havia una cúpula que assenyalava el centre del món. Allà hi havia una safata on hi havia tres agulles de diamant. En un matí plujós, un rei va manar posar-hi 64 discos d'or, que estiguessin ordenats per mida, de major a menor.

Després de col·locar-los, els sacerdots del temple van intentar moure els discos entre les agulles, seguint les normes que els havien dit: "El sacerdot no pot moure més d'un disc alhora, i no pot posar un disc de més diàmetre damunt d'un altre de diàmetre més petit".

Una altra llegenda explica que quan déu va crear el món, va posar tres barnilles de diamant amb 64 discos a la primera. També va crear un monestir amb monjos, que tenien la funció de resoldre aquesta Torre de Hanoi divina. El dia que aquests monjos aconseguissin acabar el joc, el món s'acabaria.

Aquesta llegenda va resultar ser un invent del creador del joc, un matemàtic del segle XVIII (pot ser que fos el matemàtic francès Edouard Lucas).

Resolució[modifica | modifica el codi]

Resolució del joc per a 4 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 funcions recursives.

Sigui m_k el nombre mínim de moviments necessaris per moure k discos d'una torre a l'altra. Així, podem veure que:

m_k = 2*m_{k-1} + 1

ja que la solució correspon a moure k-1 discos de la torre esquerra a la torre central, moure la peça més gran a la torre de la dreta, i tornar a moure els k-1 discos, ara a la torre de la dreta. Tenint aquesta recurrència, i tenint en compte el cas base m_1=1, trobem que:

m_k=2^k-1

És a dir, per k=4 discs fan falta m_4=2^4-1=15 moviments.

En la versió de la llegenda, amb 64 discs, caldrien 2^{64} - 1 = 18446744073709551615 moviments; suposant que els monjos fossin capaços d'efectuar un moviment per segon (i per tant, 31536000 moviments per any), trigarien més de mig bilió d'anys en fer tots els moviments.

Implementació en informàtica[modifica | modifica el codi]

Si tenim n discos, un procediment recursiu en C++ com el següent imprimeix a la pantalla la seqüència de moviments a seguir.

#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
}

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Torres de Hanoi