Torres de Hanoi

De Viquipèdia

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.

[edita] Llegenda de les torres de Hanoi

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).

[edita] Resolució

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 $264 - 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.

[edita] Implementació en informàtica

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
}