Les torres de Hanoi és un trencaclosques o joc matemàtic. Consisteix en tres varetes verticals i un nombre indeterminat de discs de mides diferents escalonades que determinen la complexitat de la solució i que poden inserir-se a les varetes lliscant-hi lliurement.

Infotaula jocTorres de Hanoi
Tipusjoc matemàtic
EpònimHanoi
Modifica les dades a Wikidata
Joc de fusta de les torres de Hanoi.

A l'inici, els discs estan col·locats de més gran a més petit en la primera vareta formant una estructura cònica. El joc consisteix a passar tots els discs a la tercera vareta tenint en compte les regles següents:

  1. Cada moviment consisteix a agafar un dels discos superiors d'una de les torres i situar-lo a una de les altres torres.
  2. 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 n - 1

Aquest joc és usat típicament en matemàtiques i informàtica com a exemple de recursivitat.

Invenció i llegendaModifica

Aquesta 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.[1]

Resolució, nombre moviments necessarisModifica

 
Resolució del joc per a 3 discs
 
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.

El càlcul dels moviments mínims necessaris a mesura que augmenta el nombre de discos, es fa típicament de forma inductiva (també anomenada recursiva). Això vol dir que partim del coneixement dels moviments mínims que cal fer per moure   discos (posem que són  moviments) per pensar els moviments per moure una torre amb   discs.

La forma de fer-ho és moure els   discs superiors de la primera a la segona vareta (  moviments), el disc de base de la primera a la tercera vareta (1 moviment) i a continuació els   discs de la segona a la tercera vareta (  moviments un altre cop). Així que els moviments per moure una torre de   discs són:

 

Ara, tenint en compte el cas base  , trobem que:

 

El nombre de moviments creix doncs exponencialment de forma sorprenent per un joc tan senzill.

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

Implementació en informàticaModifica

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

Enllaços externsModifica

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

ReferènciesModifica

  1. Lucas, Édouard. La Tour d'Hanoi. París: Chambon & Baye, 1889, p. 19.