Torres de Hanoi

De Viquipèdia
Salta a la navegació Salta a la cerca
Infotaula jocTorres de Hanoi
Tipus joc matemàtic
Epònim Hanoi
Modifica les dades a Wikidata
Joc de fusta de les torres de Hanoi.

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.

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 llegenda[modifica]

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 necessaris[modifica]

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àtica[modifica]

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 externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Torres de Hanoi Modifica l'enllaç a Wikidata

Referències[modifica]

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